CCPC威海站¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 22/240 | 8 | 10 | 13 |
A¶
solved by JLK
题意¶
签到，略
题解¶
B¶
upsolved by
题意¶
题解¶
C¶
upsolved by
题意¶
题解¶
D¶
solved by YZW
题意¶
给出一个字符串 \(S\)，有 \(q\) 组询问，每组询问给出下标 \(i\)，问将 \(S[i]\) 置为 # 后有多少个不同的周期。
\(1\leq |S|,q \leq 10^6\)
题解¶
若 \(S[1:r]\) 为原串的一个 border，则当 \(r<i\leq |S|-r\) 时 border 对应一个周期。
KMP 求出所有 border，将区间加法差分为 \(+1,-1\) 再前缀和即可 \(O(1)\) 回答询问。
时间复杂度 \(O(|S|+q)\)。
E¶
solved by YZW
题意¶
有 \(n\) 首曲子，系统从中随机选取两首不同的曲子给你打，打第 \(i\) 首曲子得分 \(a_i\)。你有至多 \(k\) 次机会选择重抽，问最优方案下的期望得分。
额外给出 \(q\) 个 case，问抽到第 \(x,y\) 首曲子还有 \(c\) 次重抽机会时，直接开打和重抽哪个更优，二者期望得分相差 \(10^{-4}\) 时视为同样优。
\(2\leq n\leq 10^5\)，\(1\leq q\leq 10^5\)，\(1\leq k\leq 100\)，\(0\leq a_i\leq 10^6\)，\(1\leq x<y\leq n\)，\(0\leq c\leq k\)。
题解¶
设 \(f(c)\) 表示还有 \(c\) 次重抽机会时期望得分，容易写出：
对排序后的 \(\{a_i\}\) 双指针即可求出 \(a_i+a_j\leq f(c-1)\) 的 \((i,j)\) 对数量与贡献和，从而可以计算 \(f(1),\dots,f(k)\)。
对于 \(q\) 个 case，将 \(a_x+a_y\) 与 \(f(c-1)\) 比较即可。需要注意 \(c=0\) 时只能直接开打。
F¶
solved by YZW
题意¶
题解¶
G¶
solved by TYB
题意¶
对所有\(k\in[1,m]\)，求\(\prod_{i=1}^nC_k^{a_i}\)。
\(n,m\le5\times10^4,\sum a_i\le10^5\)
题解¶
\(C_k^{a_i}=\frac{k!}{{a_i}!(k-a_i)!}\)，只需要快速计算\(\prod_{i=1}^n\frac{1}{(k-a_i)!}\)即可。注意到不同的\(a_i\)的值只有根号种，直接暴力即可，这样的复杂度是\(\mathcal{O}(m\sqrt{\sum a_i}\log n)\)，\(\log\)为快速幂的复杂度。
还有一种空间换时间的方法：注意到\(\frac{1}{(k-a_i)!}\)不同的取值只有\(\mathcal{O}(m)\)种，且我们要求的是它的\(x\)次方（\(x\le n\)）。考虑分块，设\(B=\sqrt n\)，对于每个\(\frac{1}{x!}\)，我们预处理出\((\frac{1}{x!})^B,(\frac{1}{x!})^{2B},\dots,(\frac{1}{x!})^{B^2}\)以及\((\frac{1}{x!})^0,(\frac{1}{x!})^1,\dots,(\frac{1}{x!})^{B-1}\)这\(2B\)个值，即可\(\mathcal{O}(1)\)计算快速幂。
但这种方法的时空复杂度均为\(\mathcal{O}(n\sqrt n)\)，所以实际应用中不会快多少甚至更慢。
H¶
solved by TYB
题意¶
一棵\(n\)个节点的树，可以选择一些点，选择节点\(i\)要付出\(w_i\)的代价，但对于某个节点，若与它距离\(\le p\)的点全部被选择（包括它自己），则会获得\(v_p\)的收益（对所有节点\(v\)相同，收益不叠加，若有多个满足条件的\(p\)取最大的一个），求最大收益。
\(n\le200\)
题解¶
思维僵化……看完题就觉得是网络流，实际上确实是最大权闭合子图的裸题，具体建图方法不再赘述。还有优秀的\(\mathcal{O}(n^2)\)DP做法。
Upd by JLK：
DP思路就是，\(dp_{i,j}\)表示让\(i\)点周围\(\le j\)距离的点都选择，所得的最大收益。具体来讲，就是假设\(i\)最终能得到\(v_j\)的收益，那么\(i\)子树内深度\(\le j\)的点都选了，并且到父亲的时候，父亲周围距离\(\le j-1\)的点都要被选。这样才是合法的。
按照上面的定义，\(dp_{i,j}\)可以从\(dp_{p,j-1},dp_{p,j},dp_{p,j+1}\)中选择一个最大的加上，其中\(p\)是\(i\)的儿子。因为既要满足子树内的点都选择，也要保证儿子的收益能够合法得到。
需要考虑\(i\)不选的情况，那么可以把\(dp\)中\(j\)整体+1，\(dp_{i,0}\)表示\(i\)不选的情况，转移是一样的。每个点\(dp_{i,j}\)转移后加上自己这个点的贡献\(v_{j-1}-w_i\)就可以了。
I¶
upsolved by TYB
题意¶
\(n\)个点的图，\(x\)和\(y\)之间有一条双向边当且仅当\(x|y\)且\(y/x\)为质数，且边权为\(y/x\)。定义\(dis(i,j)\)为\(i,j\)两点间的最短路，求\(\sum_{i=1}^n\sum_{j=1}^ndis(i,j)\)
\(n\le10^{11}\)
题解¶
定义\(f(x)\)为将\(x\)分解质因数有所有因子的和，如\(60=2^2\times3\times5,f(60)=2+2+3+5=12\)，则答案显然为
考虑每个质数的贡献（应该不难推吧，过程略），可以得到答案的式子为
对于\(\le \sqrt n\)的质数，可以直接暴力；对于\(>\sqrt n\)的质数，\(k=1\)，数论分块后我们只需要知道区间质数和，min25筛即可。
J¶
solved by YZW
题意¶
签到，略。
题解¶
K¶
upsolved by JKAC
题意¶
给出奇素数 \(p\)，有 \(p-1\) 个点，每个点 \(i\) 需要选择二者之一连边：
- \(i\leftrightarrow {i\over a}\bmod p\)，花费 \(1\)。
- \(i\leftrightarrow {a\over i}\bmod p\)，花费 \(\lceil \log_2 p\rceil\)。
其中 \(a\) 为未知待定参数。对于一个大小为 \(s\) 的连通块，额外花费为 \(s^2\)。
你需要给出一个连边方案。
每组数据将使用 \(20\) 个随机参数测试连边方案，只要其中一个参数计算得到的花费 \(\leq 12p\) 就算通过。
\(3\leq p\leq 10^4\)。
题解¶
注意到：
只要这四个点连成一个环，这四个点的平均花费就不超过 \({2\times 1+2\times 14+4^2 \over 4}={46\over 4}=11.5\leq 12\)。
考虑如何连边。注意到 \(({a\over p})=({a^{-1}\over p}),({a^2\over p})=1\)，因此有 \(({i\over p})=({a^2i^{-1}\over p}),({ia^{-1}\over p})=({ai^{-1}\over p})\)。可以考虑按 \(({i\over p})\) 分配两种边，当 \(({a\over p})=-1\) 时这四个点即可成为一个环。由于 \(a\) 随机，\(({a\over p})=-1\) 的概率为 \(1/2\)，因此错误率为 \(2^{-20}\)。
所以依 \(({i\over p})\) 定义快速幂计算后输出即可。
L¶
upsolved by
题意¶
题解¶
M¶
solved by JLK
题意¶
长度为\(n\)的01串，有\(m\)个1，并且最长连续1的长度恰好为\(k\)的方案数。
\(0 \le n,m,k \le 10^5\)
题解¶
先把一些特殊情况判掉。
考虑算出最长连续1长度\(\ge k\)和\(\ge k+1\)的，然后相减得到答案。
对于\(\ge k\)，可以用经典容斥，枚举\(\ge k\)的段数。只需要让我们选出的连续1段不相邻即可，就是在中间插0。用隔板法可以得到\(\ge k\)的答案为：
\(\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}C_{n-m+1}^i\times C_{(n-m)+(m-ik)}^{m-ik}\)
就可以直接算了。\(O(\frac {n} {k})\)
记录¶
开局JLK过A(0:07)，YZW过J(0:21)和D(0:36)。
先跟榜看M，没想到，扔了。
然后看G，推了个式子但是不会求。后来TYB想到根号就过了(1:15)。
YZW和TYB讨论后上手写E，JLK看M。
E WA一次，打印了代码后JLK写M。
M WA一次，E改了两个错误，还是WA。
M改了一个long long又RE了，修了一下边界条件（越界）就过了(2:07)。
继续改E，然后过了(2:22)。
然后看H，TYB马上想到了网络流，写完交上去T了。
JLK觉得Dinic板子不行，加了一些优化，但是本地不会造数据，测不出时间，就没交。
然后JLK想了个\(O(n^3)\)的树形DP，调了一年没调出来。
YZW和TYB讨论出了F，上来写过了F(4:28)。
H还是没调出来，最后十分钟把改过的网络流交上去就过了(4:49)。
总结¶
JLK：建议把所有板子整个最快的备用（。计数题一定要注意检查ll和组合数的数组越界。
Dirt¶
E(-2)
H(-1)
M(-2)