Namomo Camp 2021 Contest¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 9/46 | 6 | 6（7） | 11 |
A¶
solved by 2sozx
题意¶
定义两个字符相等仅有 \((b, q), (d, p), (w, m), (n, u), (o, o), (s, s),(z, z), (x, x)\) 问序列的最长回文子串是多长。 \(|S| < 10^5\)
题解¶
改变 \(Manacher\) 的匹配条件即可。
B¶
upsolved by JJLeo
题意¶
给出一个积性函数 \(f(n)\)，\(f(1)=1\)，只考虑 \([1,n]\) 的值。
\(q\) 次询问，每次修改一个质数幂次对应的函数值，或者求该积性函数的一个前缀和 \(\sum \limits _{i=1} ^ m f(i)\)，结果对 \(2^{32}\) 取模。保证第二种操作次数不超过 \(1000\)。(\(1 \le n\le 10^6\)，\(1 \le q \le 10^4\))
题解¶
第一种操作直接改对应的值即可，如果是改的质数点处的要用树状数组修改，可以见下面第二种操作。
第二种操作使用 min_25 筛，跑一边整除分块对于 \(m\) 的整除分块，处理出 \(O(\sqrt{m})\) 个点的质数函数值的前缀和，这可以使用上述的树状数组维护。同时 \(O(\sqrt{m})\) 内质数的函数前缀和可以直接暴力处理，之后直接跑 min_25 筛第二步即可。
弱智的我第二步全用的一开始的关于 \(n\) 的整除分块，板子题没调出来，吐了。
C¶
upsolved by
题意¶
题解¶
D¶
solved by JJLeo
题意¶
CF1399F。
题解¶
原题。
E¶
upsolved by
题意¶
题解¶
F¶
solved by Bazoka13
好像忘完了啊草
题意¶
给一个数字串，每个划分的 \(value\) 就是所有当前划分产生的所有数字的积，计算总 \(value\) % 998244353，长度不超过 \(200000\)
题解¶
线性递推，，记录前 \(i\) 个总价值为 \(sum_i\).
考虑当前加入了第 \(i\) 个数字 \(x\)，对于前 \(i-1\) 个字符的某个划分的 \(value\) \(P\) ，假设最后一个数字为 \(u\) ，那么此时有两种选择
- \(u\) 和 \(x\) 组合，则 \(value\) 为\(\frac{P}{u}\cdot(u*10+x)\)，去括号得到 \(p*10+\frac{p}{u}\cdot x\)，而对于所有的 \(\frac{p}{u}\)之和，其实就是 \(sum_{i-2}\)
- \(x\) 不组合，\(P*x\) 即可
G¶
solved by 2sozx
题意¶
多组询问，每组询问给定一个 \(01\) 串其中包含一些 \(?\) ，\(?\) 可以使 \(01\) 任意一个，问是否有一种构造方式使得产生的串相邻位置不同的个数恰好为 \(k\)。如果有，求出一个字典序最小的方案。 \(k < |S| \le 10^5\)
题解¶
我们可以显然的 \(dp\) 出来从位置 \(i\) 开始到结尾最多与最少能够产生多少个相邻不同的位置，记为 \(dp[i][0/1]\)，下面有几个易证的结论。
- 如果 \(s[1],s[n] \not = ?\) ，那么 \(k\) 的奇偶性一定与 \(dp[1][0],dp[1][1]\) 相同。
- 如果 \(s[1], s[n]\) 其中一个是 \(?\) ，那么 \(k\) 的奇偶性任意。
- \(dp[1][1] \le k \le dp[1][0]\)
因此我们根据这个操作贪心即可，遇到 \(?\) 先填 \(0\) ，填不了再填 \(1\) 即可。
H¶
solved by JJLeo
题意¶
设 \(s(n)\) 表示 \(n\) 各数位之和，问有多少对数 \((a,b)\) 满足：
- \(L \le a,b \le R\)。
- \(s(a)+s(b) \equiv s(a+b) \pmod d\)
(\(1 \le L \le R \le 10^{1000}\)，\(2 \le d \le 9\))
题解¶
使用容斥定理，只需求 \(a,b \in [0,R]\) 的方案数，再减去 \(a \in [1,L-1],b\in[1,R]\) 和 \(a \in [1,L-1],b\in[1,R]\) 的方案数，再加上 \(a,b \in [1,L-1]\) 的方案数。
设 \(f_{i,j,k,l,m}\) 为从高到低第 \(i\) 位，\(s(a)+s(b)-s(a+b) \bmod d = j\)，\(a+b\) 前面有 \(k\) 个连续的 \(9\)，\(a\) 是否贴上界，\(b\) 是否贴上界，直接进行数位 dp 即可。注意当 \(a+b\) 进位时 \(a+b\) 前面的所有 \(9\) 都会被消去。
一开始贡献写反了一个符号，边吃饭边调瞪眼了一个小时，然后标程错了，寄。
I¶
upsolved by
题意¶
题解¶
J¶
solved by JJLeo
题意¶
随机生成的 \(n\) 个数 \(a_i\)，每次可以让一个数增加 1 或减少 1，但不能减为 0，问最少操作多少次可以让所有相邻的数都互质。(\(1 \le n \le 10^4\)，\(1 \le a_i \le 10^5\))
题解¶
因为数据随机，每个数改变次数不会很多，直接 dp 即可。
dls 说每个数最多改 1（
K¶
upsolved by
题意¶
题解¶
记录¶
namomo疯狂namo，阴间时间开始
0min：开始了自闭的一场，MJX 发现 A 好像就是个模板，写去了，ZYF 发现 D 是个原题，直接冲了
12min：ZYF AC
15min：MJX WA，ZYF 发现 MJX 的愚蠢错误，AC，MJX 看 G 是个简单贪心，ZYF 看 H 是个裸数位DP直接开冲
78min：MJX WA2 后自信认为数据错了，直接看别的题
131min：ZYF WA，这题数据真错了，看 J 去了
162min：ZYF AC J，期间 CSK回来了冲F
182min：CSK AC F，成功击败 xudyh
??min：突然发现有人过G了，应该数据没问题，开始大力调G
216min：MJX AC，字符串末尾不是 '\0' ，老脑瘫了，错失一血
till end：ZYF 冲 B 未果，MJX C 忘清零了和一个愚蠢操作，不过不知道其余的对不对
总结¶
- MJX在用 printf("%s") 时字符串末尾一定要是0