2019 Summer Petrozavodsk Camp, Day 8: XIX Open Cup Onsite¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 26/? | 6 | 9 | 12 |
A¶
upsolved by
题意¶
题解¶
B¶
solved by TYB
题意¶
不是签到，但比较standard，略。
题解¶
略。
C¶
upsolved by
题意¶
题解¶
D¶
upsolved by YZW
题意¶
Gomory-Hu Tree 板板题。
题解¶
敲板板，ACC！
E¶
solved by JLK
题意¶
问\(n \in [l,r]\)中使得\(f^m(n)=1\)的最大\(m\)，以及\(m\)最大时\(n\)的最小值和最大值。
\(2 \le k \le 10^{18},1 \le l \le r \le 10^{18}\)
题解¶
对于一个确定的\(n\)，\(m\)就是\(k\)进制下\(n\)的每个数位之和+位数-2。
首先考虑如何确定最大\(m\)。如果从\(r\)开始枚举，如果要变，肯定是某一位-1，然后比这一位低的位全部变成\(k-1\)。
每次变的时候可以计算出代价，如果能增大就变。
\(n\)的最大值和最小值都可以通过这样的方法产生。因为不这样变肯定不是最大的\(m\)。
\(O(T\log_k^2 r)\)
F¶
upsolved by TYB
题意¶
给一个仅包含小写字母的串\(S\)，找出满足下列条件的最长子序列\(T\)：
\(1、|T|\)为偶数。
\(2、\forall i\in[1,\frac{|T|}{2}],T_i=T_{i+\frac{|T|}{2}}\)
\(n\le3000\)
题解¶
枚举分界点，然后\(\mathcal{O}(\frac{n^2}{w})\)算最长公共子序列（见HDU板子）。
G¶
solved by YZW
题意¶
球交！
题解¶
分类讨论：
-
相离，不交。
-
包含，全交。
-
相切，……反正，要么不交，要么全交，要么和下面一样也行。
-
剩下的情况，诶呀我草，怎么只交了一半，我们来讨论一下。
设球 \(A\) 球心位于 \(O_A = (x_A, y_A, z_A)\)，半径 \(r_A\)，球 \(B\) 同理。
容易写出球面方程：
小学生都会的减法：
嘿嘿，这就是球面交圆所在的平面。球交的部分可以被这个平面分成俩……球盖？还是啥的东西。
接下来我们只需要算球盖体积就好，设半径 \(R\)，球盖高度 \(r\)，这是一个小朋友都会的积分：
没了。
H¶
solved by TYB
题意¶
签到。
题解¶
略。
I¶
upsolved by
题意¶
题解¶
J¶
upsolved by TYB
题意¶
给长度为\(n\)的串\(S\)，\(q\)次询问区间\([l,r]\)有多少满足下列条件的子串\(T\)：
\(|T|\)为偶数，且\(\forall i\in[1,\frac{|T|}{2}],T_i=T_{i+\frac{|T|}{2}}\)。
\(n,q\le10^6\)
题解¶
先把runs求出来，对于一组\((l,r,p)\)，我们可以把它分成若干个\((l,r,k)\)，表示区间\([l,r]\)中任意长度为\(k\)的区间都有\(1\)的贡献，根据runs的理论，这个数量级也是\(\mathcal{O}(n)\)的，接下来就成了数据结构问题。
考虑拆贡献，把一个\((l,r,k)\)拆成\((l,+\infty,k)\)和\((r-k+2,+\infty,k)\)，下面讨论一个\((u,+\infty,k)\)对询问\((l,r)\)的贡献。
符合条件的左端点\(x\)有下列条件：
贡献为：\(\max(r-k+2-\max(u,l),0)\)，这个难以计算，尝试化一下：
然后就可以树状数组算了。
K¶
solved by YZW
题意¶
签到。
题解¶
想了想，觉得状压时在 \(O(2^{|S|})\) 的时间内枚举集合 \(S\) 的子集是人尽皆知的事情，似乎没啥必要写，略。
L¶
solved by YZW
题意¶
有无限行点排成金字塔形状，其中第 \(i\) 行有 \(i\) 个点。
给出 \(l, r\)，问第 \(l\) 行至第 \(r\) 行点能形成多少个不同的等边三角形。
\(T\) 组数据，\(1\leq T\leq 3\times 10^5\)，\(1\leq l\leq r\leq 10^5\)。
题解¶
容易得到答案为和式：
显见答案应为关于 \(l, r\) 的二元多项式，但在 \(2l < r\) 与 \(2l > r\) 时有所不同。
咋看都觉得次数不会很高，算出来前 \(8\times 8\) 项，高斯消元算出来系数就知道二元多项式是啥了。实际上次数好像是 \(4\)。
Fuck Python! Too slow to get AC!
\(O(T)\)
记录¶
TYB开场犯病觉得会F，交了两次，JLK帮忙看，发现假了，也不会修。
YZW过K(0:46)。
YZW在搞L，TYB和JLK讨论H。
YZW交L，用Python先TLE了一次，换C++又WA了。
TYB先写H，过了(1:55)。
YZW过L(2:25)。
JLK大概会了E，开始写。YZW也会了G。
E写完wa了，YZW写G，TYB和JLK发现E还有一些情况，又讨论了一下，又交了一次，又wa了。
YZW过G(3:26)，JLK过B(3:27)。
TYB写了一年B，终于过了(4:32)。
然后开摆。
总结¶
TYB：开场可能有点糊涂，还是应该让队友确认一下做法；B这种有些细节的题，应该仔细想清楚；准备Python的FastIO。
YZW：想清楚再写应该会快不少。
Dirt¶
E(-2)
L(-2)