Petrozavodsk Winter-2019. Oleksandr Kulkov Contest 1¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 33/99 | 5 | 8 | 11 |
A¶
upsolved by TYB
题意¶
给出\(k,a[0\dots3^k-1],b[0\dots3^k-1]\)，求\(c_x=\sum_{mex3(i,j)=x}a_i\times b_j\)，其中\(mex3(i,j)\)为将\(i,j\)转成三进制后，逐位做\(mex\)得到的数。
\(k\le12\)
题解¶
考虑如何求\(c[0\times3^x+i],c[1\times3^x+i],c[2\times3^x+i]\)。
\(c[0\times3^x+i]=\)
\(\sum_{mex3(j,k)=i}(a[1\times 3^x+j]+a[2\times 3^x+j])(b[1\times 3^x+k]+b[2\times 3^x+k])\)
\(c[1\times3^x+i]=\)
\(\sum_{mex3(j,k)=i}(a[0\times 3^x+j]+a[2\times 3^x+j])(b[0\times 3^x+k]+b[2\times 3^x+k])-a[2\times 3^x+j]\times b[2\times 3^x+j]\)
\(c[2\times3^x+i]=\)
\(\sum_{mex3(j,k)=i}(a[0\times 3^x+j]+a[1\times 3^x+j]+a[2\times 3^x+j])(b[0\times 3^x+j]+b[1\times 3^x+k]+b[2\times 3^x+k])\)
\(-c[0\times3^x+i]-c[1\times3^x+i]\)
这样，一个\(3^k\)的卷积结果可以通过\(4\)个\(3^{k-1}\)的卷积结果得到，也就是每一层要分下去四层，复杂度\(\mathcal{O}(4^k)\)。
B¶
**upsolved by **
题意¶
题解¶
C¶
**upsolved by **
题意¶
题解¶
D¶
solved by YZW
题意¶
给出 \(\{a_k\}\) 与 \(\{b_k\}\)，\(F\) 为满足 \(F_n=\sum_{i=1}^k a_iF_{n-i}\) 的线性递推，求 \(\{c_k\}\) 使得 \(F\) 满足 \(F_n=\sum_{i=1}^k c_iF_{n-b_i}\)。
\(k\leq 128\)，答案对 \(10^9+7\) 取模。
题解¶
\(F_n\) 可表为 \(F_0,\dots,F_{k-1}\) 的线性组合，倍增求系数，高斯消元即可。\(O(k^3\log k)\)
E¶
solved by TYB
题意¶
有\(n\)堆石子，每次可以选择一堆石子数量不为一的将其分成两堆，每堆至少一个石子，然后将其中一堆染成黑色，另外一堆染成白色，当所有堆都只有一个石子时结束。先手想让黑色尽量多，后手想让白色尽量多，问最后黑色石子的数量。
题解¶
可以发现每次操作能让己方颜色的石子数\(+1\)，所以答案为\(\lceil\frac{sum}{2}\rceil\)。
F¶
solved by JLK
题意¶
给定一个\(n\)个点\(m\)条边的图，有边权，其中给定一棵生成树。要找到满足如下条件的点：从这个点出发到所有别的点，对于这两个点之间任意在原图上经过的路径\(P\)和在生成树上的简单路径\(Q\)，满足\(P\)的最小边权不能大于\(Q\)的最小边权。求出所有这样的点。
题解¶
自环直接忽略。
对于所有边模拟建最大生成树的过程。把在给定生成树上的边\(A\)和不在生成树上的边\(B\)分开考虑。
按边权从大到小枚举边，同样边权先枚举\(A\)边，并且同边权同种类型的边同时考虑。
对于\(A\)边，如果边的两端已经在之前形成了连通块，那么这整个连通块都不合法。因为这个连通块里所有点出发的路径都存在一个不经过这个\(A\)边，只经过较大的边的路径。
对于\(B\)边，如果边的两端在之前没有形成连通块，那么两端代表的连通块都不合法。因为所有点都存在一个以\(B\)边为最小边权的路径，会比只经过\(A\)边的大。
第一种情况一定是判断完再连边，否则会被相同边权的\(A\)边干扰。
并查集同时维护一下每个点是否不合法即可。
\(O(n\log n)\)
G¶
**upsolved by **
题意¶
题解¶
H¶
solved by TYB
题意¶
A和B玩游戏，一开始选择权在A。每轮会随机出现一个\([1,m]\)范围内的整数\(x\)，拥有选择权的人可以选择：1.获得\(x\)的分数，把选择权交给对方；2.让对方获得\(x\)的分数，自己保留选择权。求无限轮后A比B期望多的分数。
数组组数\(T\le5\times10^5,m\le10^9\)
题解¶
显然，双方的最优策略是相同的，且存在一个分界点\(k\)，若\(x\in[1,k]\)，则保留选择权，\(x\in[k+1,m]\)，则获得该分数。设答案为\(f\)，则可以列出式子：
解出\(f\)为：
没什么好的办法，直接求导，然后在根附近几个点找一找即可。注意即使是long double也无法达到精度要求，需要存下分子分母后用int128比较。
I¶
upsolved by TYB
题意¶
给出一个只有小写字母的串\(S\)，问有多少个不关心顺序的二元组\((a,b)\)，\(a\)和\(b\)都是\(S\)的子串，且\(a\)不是\(b\)的子串，\(b\)也不是\(a\)的子串。
\(n\le10^5\)
题解¶
考虑用总数减去不合法的，即\(a\)为\(b\)子串的\((a,b)\)对数。建出SAM，上面的每个节点表示若干个字符串，他们的右端点一样，设为\(r\)，左端点是一段连续的区间，设为\([a,b]\)，那么该节点的贡献就是\(\sum_{i=a}^b\)区间\([i,r]\)本质不同子串个数，这是经典问题，可以参考区间本质不同子串数 - Poor_Math-Wiki (poormath.github.io)，对比原问题，只需要在线段树上多维护一个\(\sum a_i\times i\)的值即可。
J¶
upsolved by TYB
题意¶
给出\(m\)个长度均为\(n\)的字符串，每个字符串中至多有一个通配符，其它字符ASCII值在\([33,126]\)范围内。求有多少个\(n\)的排列\(p\)，满足\(\forall i\in[1,m)\forall j\in[1,n],s[i][j]=s[i+1][p_j]\)均成立，其中\(s[i][j]\)表示第\(i\)个字符串的第\(j\)位。
\(n,m\le3000\)
题解¶
首先可以发现，除去无解的情况，所有通配符要么已经可以确定，要么全部都是同一个字符。
首先考虑所有字符均已确定的情况。若\(p_i\)的值可以为\(j\)，则\(\forall x\in[1,m),s[x][i]=s[x+1][j]\)均成立可以看作是两个长度为\(m-1\)的字符串\(s_1[i],s_2[j]\)能匹配，其中\(s_1[i][x]=s[x][i],s_2[j][x]=s[x+1][j]\)。这样利用字符串hash就可以快速得出匹配情况。对于\(s_2[i]\)，假设有\(a[i]\)个\(s_1\)能与其匹配，则答案为\(\Pi_{i=1}^na[i]!\)（注意相同的只用算一次），在这里，\(0!=0\)。用map统计一下字符串的出现次数就好了，复杂度\(\mathcal{O}(nm)\)。
然后考虑通配符不能确定的情况，由于字符集不大，且修改一个字符后改变hash值的时间是\(\mathcal{O}(m)\)，所以可以直接枚举通配符填的是什么，再计算答案，复杂度\(\mathcal{O}(nm+(n+m)\log |\Sigma|)\)。但这样会算重。考虑什么时候会算重，当且仅当这个通配符无论填什么都可以通过相同的方式匹配，也就是跟自己匹配。那么可以直接让它变成一个与所有已有字符都不同的字符，这样它就只会匹配自己，就可以算出这部分重复的方案了，减去即可。
K¶
solved by TYB
题意¶
给出\(n\)个数，进行\(n-1\)轮操作，每一轮等概率随机地从剩下的数中选出两个相邻的数\(a,b\)，然后\(b\)消失，\(a\)变为\(a-b\)，求最后剩下的数的期望。
题解¶
最后得到的数可以看作是\(a_1-a_2\pm a_3\pm \cdots\pm a_n\)，可以证明共\(2^{n-2}\)种情况，即除第一个符号必须为减号外，其他符号任意，且每种情况出现的概率均等，所以答案为\(a_1-a_2\)。
记录¶
开局JLK和TYB看E，一开始结论想简单了WA了一发，然后改对了(0:15)。
然后看K，TYB说做过类似的题，然后用结论过了(0:21)。
三人看H，推了个式子，T一次WA一次后AC(1:31)。
YZW写D，JLK和TYB想F。
JLK想到了一个做法，等YZW过了D(3:07)之后开写，不放心写了个对拍，对着改了改就过了(3:43)。
然后罚坐到结束。
总结¶
JLK:以后涉及分数比较的还是尽量用乘法来比较。
Dirt¶
E(-1)
H(-2)