Petrozavodsk Winter-2018. Carnegie Mellon U Contest¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 61/157 | 6 | 9 | 11 |
A¶
solved by TYB
题意¶
数轴上有一些点有炸弹，每个炸弹有爆炸半径和引爆的花费，引爆一个炸弹，在其爆炸半径内的炸弹也会引爆，产生连锁反应，\(q\)次修改，每次修改某个炸弹的引爆花费，输出每次修改后引爆所有炸弹的最小花费。
\(n,q\le2\times10^5\)
题解¶
考虑暴力怎么做，可以每个炸弹向它能引爆的炸弹连边，求出强连通分量缩点后，求所有入度为\(0\)的强连通分量最小引爆花费之和。考虑优化，首先按坐标排序后，每个炸弹能引爆的炸弹是一段连续的区间，可以线段树优化建图；至于修改，用一个multiset维护所有入度为\(0\)强连通分量的最小值即可。
B¶
solved by JLK
题意¶
题解¶
C¶
solved by TYB
题意¶
给出两个\(01\)串\(A,B\)，随机生成字符串，初始为空，每次等概率随机把\(0/1\)接到当前串末尾，当前串能与\(A/B\)匹配后结束，求先匹配到\(A\)、先匹配到\(B\)、同时匹配到\(A,B\)的概率。
\(|A|,|B|\le20\)
题解¶
建AC自动机，每次相当于随机选一条边在AC自动机上走，直接DP+高斯消元解方程即可。
D¶
upsolved by JLK
题意¶
有一个无穷大的图，由无数个八边形组成，每个八边形的八条边由abc中的两个字母交替组成，而且每个点恰好连到三条字母不同的边上。给定一个字母序列，问从任意一个点出发，路径构成这个序列的路径，是否能够构成一个回路。
\(1 \le len \le 10^5\)
题解¶
看图可以发现，如果能构成回路，那么肯定在某个八边形内经过了连续的至少五条边。
从这里切入，那么每次对于ababa这样的五个连续交替序列，可以看做是bab（走劣弧）。同理，ababab可以看做ba，以此类推。八个连续交替可以直接消去。两个相同字母也可以直接消去（走一个来回）。
用栈来模拟，一直这样消去即可，最后如果能全部消去，就是回路。
在实现的时候遇到了问题，消去的时候需要把用来替换的串依次插入才能通过。比如ababa需要删去ababa，然后依次插入bab。原因未知。
E¶
upsolved by TYB
题意¶
\(n\)个点的树，求有多少条路径满足路径上所有点的编号连续。
\(n\le50000\)
题解¶
可以转化为统计满足\(\max(u,v)-\min(u,v)=dis(u,v)\)的路径\((u,v)\)数量，\(\max(u,v),\min(u,v)\)分别为\(u\)到\(v\)路径上点编号的最大最小值。考虑点分治，可以枚举最大值所在的链，分最小值在这条链和另外一条链两种情况讨论，用树状数组维护即可。
\(\mathcal{O}(n\log^2n)\)
F¶
solved by YZW
题意¶
题解¶
G¶
upsolved by
题意¶
题解¶
H¶
solved by YZW
题意¶
题解¶
I¶
upsolved by JLK
题意¶
\(n\)个物品，要求恰好选出体积为\(V\)的物品，并且选的物品最少。对于四个量：
1.物品体积平均数
2.物品体积中位数
3.选的最多的同一体积物品的次数
4.选的物品中最大体积和最小体积的差值
分别求出最小的四个量是多少。
\(1 \le n,V \le 5000,1 \le v_i \le V\)
题解¶
首先可以做一个01背包，得到选出\(V\)体积所需最少的物品数量。如果不行则-1。
第一个问题白给。
第二个问题，按体积大小预处理出前缀背包和后缀背包，枚举中位数，\(O(V)\)合并两侧的背包（只需要得到合并后的\(V\)这一个点的值）。从小到大第一个可以满足物品最少并且体积小的物品较多的就是中位数。
第三个问题，可以枚举次数，每次把同一体积次数还够用的做背包，第一次满足物品数量最少的即为答案。
第四个问题，从小到大枚举右端点，满足条件的最大左端点也是单调递增的。但是背包并不能直接撤销。利用单调性，有一个很巧妙的方法：维护两个栈。枚举右端点时，每次往第一个栈顶扔一个物品，然后做前缀背包。撤销时，如果第二个栈是空的，就把第一个栈的所有数倒序放到第二个栈里，再做前缀背包。这样删除第二个栈顶就相当于撤销最左边的一个物品了。而这样也需要每次\(O(V)\)来判断合并后的\(V\)体积是否能达到最少物品。
\(O(nV)\)
J¶
solved by JLK
题意¶
定义长度为\(k\)的Zigzag序列\(x\)为：对于任意\(1 \le i \le k-2\)，\((x_i,x_{i+1},x_{i+2})\)构成峰或者谷。
求两个序列的最长公共Zigzag序列。
\(1 \le n,m \le 2000\)
题解¶
考虑\(O(n^4)\)的一个dp。\(dp_{i,j,0/1}\)表示第一个以\(i\)结尾，第二个序列以\(j\)结尾，上升或下降的最长长度。
实际上，先枚举\(i\)，再枚举\(j\)，就可以只记录\(j\)了，因为\(a_i\)和\(b_j\)一定相同，由于枚举顺序，之前得到的\(dp\)值的\(i\)一定小于当前的\(i\)。那么现在就是记录\(dp_{j,0/1}\)表示目前已经转移到的状态中，第二个序列以\(j\)结尾，上升或下降的最长长度。这样是\(O(n^3)\)。
而对于指定的\(i\)，\(a_i\)是一定的，那么也就知道每个数需要转移到上升还是下降。\(j\)扫描的时候，将\(b_j\)和\(a_i\)比较，记录一下两个状态的前缀最大值，就可以直接转移了。
要特判长度为2的情况！！！
\(O(nm)\)
K¶
upsolved by
题意¶
题解¶
记录¶
H一开始就有人过了，但是全员降智，没想到方法。
JLK一开始觉得B可以用Splay做，打算扔了，但是看到榜上过的人很多，想了想可以简单实现，0:31过了。
F一开始也觉得实现较复杂，看到过的人很多，YZW开写，RE后AC(1:06)。
JLK嘴了一个C的做法给TYB写，AC(3:02)。
YZW写J，又发现复杂度不对，换JLK写，由于题意模糊和没有特判，WA4次后AC(3:28)。
一起看ADH。发现A是经典问题，TYB开始写。同时YZW想到H的一个写法（虽然还是麻烦了很多）。
H RE一次WA一次后AC(4:20)。
A WA一次后AC(4:26)。
然后一起看D，JLK尝试了一下，WA on 170，改了好几个地方都没变化，直到结束。
总结¶
JLK:对经典问题/模型的把握不太充分。这场总体发挥不太好，有点降智。
Dirt¶
A(-1)
F(-1)
H(-2)
J(-4)