A 九小时九个人九扇门 dpH 牛牛看云 思维F 中位数切分 思维I B站与各唱各的 数学D 牛牛做数论 数学B 炸鸡块君与FIFA22 倍增/分块/线段树K 冒险公社 dpG ACM is all you need总结
比赛链接
A 九小时九个人九扇门 dp
题目链接 题解： 转移方程 题目链接 题解： 题目链接 题目链接 题解： 题目链接 题意： 题解： 题目链接 题解： 待补 题目链接 题目链接 Qwq
题意：
一个数字的数字根是指：将该数字各数位上的数字相加得到一个新的数，直到得到的数字小于
10
10
10 为止.。设置小于
10
10
10 的数字，其数字根就为其本身。
k
k
k 个人能够打开门上数字为d的一扇数字门，当且仅当这
k
k
k 个人的腕表数字之和的数字根恰好为
d
d
d。
(
1
<
=
n
<
=
1
e
5
,
1
<
a
i
<
=
1
e
9
)
(1<=n<=1e5,1(1<=n<=1e5,1
状态
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 表示考虑了前
i
i
i 个数，选择了一些数字使得数字根为
j
j
j 的方案数
不加当前位使得数字根为
j
j
j 的方案数为上一位继承来
d
p
[
i
]
[
j
]
+
=
d
p
[
i
−
1
]
[
j
]
;
dp[i][j] += dp[i - 1][j];
dp[i][j]+=dp[i−1][j];
加上当前位使得数字根为
f
(
a
[
i
]
∗
10
+
j
)
f(a[i]*10+j)
f(a[i]∗10+j) 的方案数为上一位继承来
d
p
[
i
]
[
f
(
a
[
i
]
∗
10
+
j
)
]
+
=
d
p
[
i
−
1
]
[
j
]
;
dp[i][f(a[i]*10+j)] += dp[i - 1][j];
dp[i][f(a[i]∗10+j)]+=dp[i−1][j];
当前位的方案数+1
d
p
[
i
]
[
f
(
a
[
i
]
)
]
+
+
;
dp[i][f(a[i])]++;
dp[i][f(a[i])]++;#include
题意：
求
n
n
n
n
n
n
Σ
Σ
Σ
Σ
Σ
Σ
∣
a
i
+
a
j
−
1000
∣
∣ai+a j −1000∣
∣ai+aj−1000∣
i
i
i=1
j
j
j=
i
i
i
(
0
<
a
i
<
=
1000
,
n
<
=
1000000
)
(0(0
因为这个
n
n
n 很打，
a
i
ai
ai很小
就从
a
i
ai
ai 入手
记录
a
i
ai
ai 的个数枚举
a
i
ai
ai
直接计算答案
假如
a
i
=
=
a
j
ai==aj
ai==aj ans=自己和自己+自己和别人
/
2
/2
/2 (因为
j
j
j 是从
i
i
i 开始的 所以
/
2
/2
/2
a
i
!
=
a
j
ai!=aj
ai!=aj ans=
c
n
t
[
a
i
]
∗
c
n
t
[
a
j
]
/
2
cnt[ai]*cnt[aj]/2
cnt[ai]∗cnt[aj]/2vector
题意：
给定一个长为
n
n
n 的数组
a
a
a 和一个整数
m
m
m，求最多可以划分成多少段，使得每一段的中位数都大于等于
m
m
m。
(
1
<
a
i
,
m
<
=
1
e
9
,
1
<
=
n
<
=
1
e
5
)
(1(1
原数组大于等于m的记为1，记录
c
n
t
1
cnt1
cnt1 个
小于的记为-1，记录
c
n
t
2
cnt2
cnt2 个
当一段的
s
u
m
>
=
1
sum>=1
sum>=1 的时候这一段中位数就
>
=
m
>=m
>=m
然后就去拿
1
1
1 的去中和
−
1
-1
−1, 最大的段数就是先把负数中和了使得
s
u
m
=
=
0
sum==0
sum==0 再加上一个
1
1
1，假如
c
n
t
1
−
c
n
t
2
<
=
0
cnt1-cnt2<=0
cnt1−cnt2<=0则不存在，不然段数为
c
n
t
1
−
c
n
t
2
cnt1-cnt2
cnt1−cnt2个 。#include
题意：
分子为欧拉函数
打表呜呜呜
最小值是
下一个数是210
就发现是素数的乘积
2
,
2
∗
3
,
2
∗
3
∗
5
2,2*3,2*3*5
2,2∗3,2∗3∗5
因为素数乘积的数不是素数，那么他的因子也少
那么
H
(
x
)
H(x)
H(x)就大
因为素数
x
x
x 的欧拉函数等于
x
−
1
x-1
x−1，那么最大值就是范围内最大的素数的
H
(
x
)
=
(
x
−
1
)
/
x
H(x)=(x-1)/x
H(x)=(x−1)/x
p
s
:
ps:
ps:牛客题解上说
1
e
9
1e9
1e9 以内最大的两个素数间隔是
282
282
282 就直接暴力找#include
有
n
n
n 位人在翻唱一首共
m
m
m 句的歌曲，人不交流。一句歌词被所有人唱或者没被人唱这句歌词无效，让成功唱出的句子数尽可能多，求期望唱成功的句子数量对1e9 +7取模的结果。
(
1
<
=
t
<
=
1
e
4
,
1
<
=
n
,
m
<
=
1
e
9
,
)
(1<=t<=1e4,1<=n, m<=1e9,)
(1<=t<=1e4,1<=n,m<=1e9,)
m
m
m 句歌词相互独立
设唱的概率为
p
i
pi
pi 不唱的概率为
(
1
−
p
i
)
(1-pi)
(1−pi)
那么答案就是失败的概率就是
(
p
1
∗
p
2
∗
p
3
∗
.
.
.
∗
p
n
)
(p1*p2*p3*...*pn)
(p1∗p2∗p3∗...∗pn)+
(
1
−
p
1
)
∗
(
1
−
p
2
)
∗
.
.
.
∗
(
1
−
p
n
)
(1-p1)*(1-p2)*...*(1-pn)
(1−p1)∗(1−p2)∗...∗(1−pn)
那么成功的概率就是
1
−
(
p
1
∗
p
2
∗
p
3
∗
.
.
.
∗
p
n
)
1-(p1*p2*p3*...*pn)
1−(p1∗p2∗p3∗...∗pn)+
(
1
−
p
1
)
∗
(
1
−
p
2
)
∗
.
.
.
∗
(
1
−
p
n
)
(1-p1)*(1-p2)*...*(1-pn)
(1−p1)∗(1−p2)∗...∗(1−pn)
最大化成功就是最小化石板就要使得pi都为
1
/
2
1/2
1/2 其实是猜的不过可以验算几个
那么答案就等于
m
∗
(
1
−
(
1
/
2
)
n
∗
2
)
m*(1-(1/2)^n*2)
m∗(1−(1/2)n∗2)#include
【补】
题意：
打游戏胜利将使得分加一、失败使分减一、平局使分不变。若你当前的排位分是
3
3
3 的整倍数（包括0倍），则若下一局游戏失败，你的排位分将不变（而不是减一）
给定一个游戏结果字符串和若干次询问，你需要回答这些询问。
(
1
<
=
l
,
r
<
=
n
，
q
<
=
2
e
5
,
0
<
=
s
<
=
1
e
9
)
(1<=l, r<=n，q<=2e5,0<=s<=1e9)
(1<=l,r<=n，q<=2e5,0<=s<=1e9)
n
,
q
n,q
n,q 很大就想到要预处理
每次询问每段的答案发现只和首位的初始值%3的值有有关
那么预处理从每一位开始以初始值为
0
,
1
,
2
0, 1, 2
0,1,2开始向后进行操作，但是不能
n
∗
n
n*n
n∗n
所以就想到暴力分块
假如在同一个分块里就直接暴力模拟
不在的话
就在一整块和另一块以%3的值结果来转移#include
总结
