XXII Open Cup. Grand Prix of Korea¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 74/? | 5 | 9 | 13 |
A¶
solved by YZW
题意¶
题解¶
B¶
upsolved by JLK
题意¶
有\(n\)个物品，要分给\(n\)个人。每个物品有0/1属性，每个人有0/1的需求。有一个放物品的栈。物品按顺序摆放，某个人来的时候可以选择前面若干（可以是0）个物品，依次放到栈里，然后把栈顶给物品这个人。求出第一个人可能拿到的物品的下标之和。
\(1 \le n \le 5\times 10^6\)
题解¶
物品串为\(S\)，需求串为\(T\)。
结论1：对于某个\(S\)和\(T\)，有解当且仅当两个串的0/1个数分别相同。
因为一定存在一种方案，可以始终保持栈里所有元素相同，并且它们和还不在栈里的第一个物品是不同的（或者所有都在栈里了）。
结论2：如果\(S_i=T_1,S_j=T_1,i \lt j\)，且\(j\)可能被第一个人拿到，那么\(i\)也可能被第一个人拿到。
比较显然，对于\(j\)对应的方案，如果第一个人取\(i\)，第二次补齐到\(j\)再做相同操作即可。
由结论2，那么实际上就是找到最右边的一个合法的\(j\)，\(j\)左边的和\(T_1\)相同的就是答案，\(j\)右边的则不是。
有了结论还是不太好想，需要对物品考虑。要让第一个人拿到的物品尽量靠右边，也就是让左边的物品尽量被后面的人拿。
对于第一个物品，假设它被第\(x\)个人拿走，那么一定是\(S_{1..x}\)对应着\(T_{1..x}\)，由于\(S_1\)和\(T_x\)匹配，一定需要满足\(S_{2..x}\)和\(T_{1..x-1}\)，\(S_{x+1..n}\)和\(T_{x+1..n}\)的0/1个数相同，才能保证是合法的操作。
接下来相当于是在\(S_{2..x}\)和\(T_{1..x-1}\)的子问题里套用类似算法。
那么总的来说就是从小到大枚举物品，对于第\(i\)个物品，假设它被第\(x\)个人拿走，一定需要满足\(S_{i+1..x+i}\)和\(T_{1..x-1}\)的0/1个数相同。
如果碰到一个\(x=1\)的\(i\)，那么这个\(i\)就是最右的。否则就一直找。
\(O(n)\)
C¶
solved by TYB
题意¶
给\(d\)棵\(n\)个点有边权的树，定义两棵树相同当且仅当对于任意两个节点，它们两棵树中简单路径上的最小边权相等。对于每棵树，输出与它相同的树的最小编号。
\(d\times n\le5\times10^5\)
题解¶
考虑把一棵树所有的信息用hash存下来，设\(dis(i,j)\)为\(i,j\)两点简单路径上的最小边权，我们把所有三元组\((i,j,dis(i,j))\)存下来，具体方法是给每个节点随机一个新编号，每种边权也随机一个新编号，一棵树的hash值即为\(\sum v[i]\times v[j]\times v'[dis(i,j)]\)。可以用重构树并查集之类的东西实现。
D¶
**upsolved by **
题意¶
题解¶
E¶
upsolved by TYB
题意¶
\(n\)种物品，每种个数都是无限的。第\(i\)种有价值\(c_i\)和重量\(w_i\)，且\(c_{i+1}>c_i,c_i|c_{i+1}\)，要求选出恰好\(k\)个物品，且他们的价值之和恰好为\(p\)，求出满足上述两条件下，选出物品重量之和的最大最小值。
\(n\le60,k\le1000,p\le10^{18}\)
题解¶
\(p\)非常大，而\(k\)很小，\(c\)有特殊的性质，所以考虑先满足\(p\)的限制。我们从第\(n\)种物品到第\(1\)种物品，在满足\(p\)的限制下，能取就取。这样，任意一种方案都可以通过把这种方案中若干个\(c\)较大的物品拆成若干个\(c\)较小的物品得出。
考虑DP，设\(f[i][j][k]\)表示后\(i\)种物品，共选出了\(j\)个，其中第\(i\)种选了\(k\)个。状态是\(\mathcal{O}(nk^2)\)的，转移枚举第\(i\)种有多少个拆成了第\(i-1\)种，复杂度\(\mathcal{O}(k)\)。但发现转移的时候是取了一个后缀最大值，所以可以\(\mathcal{O}(1)\)转移。
所以为啥比赛时没推出来呢……
F¶
**upsolved by **
题意¶
题解¶
G¶
upsolved by TYB
题意¶
给一个序列\(\{a_n\}\)，\(q\)次操作，分为两种：
1、给出\(l,r,x\)，执行以下流程：
初始\(h_0=x\)，\(i\)从\(1\)到\(n\)顺序遍历，\(h_i=\min(x,h_{i-1}+a_i)\)。特别地，若\(l\le i\le r\)时\(h_i\)的值\(\le\lceil\frac{x}{10}\rceil\)，则\(h_i\)的值马上变为\(\lceil\frac{x}{10}\rceil\)且维持不变直到\(i>r\)。任意时刻若\(h\)的值为\(0\)马上结束流程，问最后\(h\)的值。
2、把某个\(a_i\)的值改为\(x\)。
\(n,q\le3\times10^5\)
题解¶
可以发现所有过程其实本质是一样的，只是下界有所变化。首先考虑如何判断到过下界，设初始值为\(h\)，上界为\(x\)，考虑两种情况：一是到达下界时没有到达过上界，那么条件为\(h+最小前缀和\le下界\)；一是到达过上界，那么条件为：\(x+最小子段和\le下界\)。正确性显然。
类似地，设\(h\)经过这个区间变为\(h'\)，同样考虑两种情况：没有到达过上界，那么\(h'=h+区间和\)；到达过上界，\(h'=x+v\)，\(v\)的含义是：初值\(h=0\)，上界\(x=0\)，下界为\(-INF\)，最后\(h'\)的值。因为两种情况一定会在某个位置同时到达上界，且没有到达过下界，之后的行为是一样的。
所有信息都可以用线段树维护。
H¶
solved by TYB
题意¶
给出\(n\)个数\(a_i\)，\(l\)种操作，每种操作形如\(a_x|=a_y\)，依次循环执行这\(l\)种操作\(t\)次，问最后每个数变成多少。
\(n,l\le2^{18},0\le a_i<256,t\le10^{18}\)
题解¶
设\(f[i][j]\)表示第\(i\)个数的第\(j\)位变成\(1\)的最短时间，最短路即可。
I¶
**upsolved by **
题意¶
题解¶
J¶
solved by YZW
题意¶
题解¶
K¶
solved by JLK
题意¶
\(n\)个人两两比赛，每个人有三个rank（都是\(n\)的排列），只要有至少两个rank比另一个人低就赢。\(q\)个询问，问\(a\)能不能直接或间接赢\(b\)。
\(2 \le n \le 2\times 10 ^5,1 \le q \le 2\times 10^5\)
题解¶
很显然的做法就是分三种情况讨论，用主席树维护二维偏序，然后用主席树优化建边，跑Tarjan，然后缩点，看\(a\)能不能到\(b\)。
\(O(n\log n)\)，时空常数都巨大。
实际上因为这是一个竞赛图，可以通过出度得到scc。
首先竞赛图缩点后是一条链。在缩点后的图中，对于两个scc中的点，度数大的一个一定能到达度数小的那一个。所以如果按度数排序，同一个scc里的点是位于排序后的一个连续区间。
按出度从大到小枚举，如果去掉一个最后的scc，假设剩下\(x\)个点，那么一定会满足剩下的点总出度=\(C_{x}^2\)。这样就可以找到所有scc了。找到scc之后判断是否能到达就是先看是否在同一个scc里，不在就判断出度即可。
重要部分是计算每个点的出度，需要实现二维偏序和三维偏序。
\(O(n \log^2n)\)
还有一种方法，就是优化Kosaraju。
对于某一种情况，dfs的时候需要找到两维都高于当前点的没有访问过的点。由于每个点的两维坐标都是排列，所以可以直接用线段树维护。线段树下标为第一维，值为第二维。一个点被访问过，就直接在线段树上清空即可。
反图上dfs同理，这样就可以直接找出scc了。
\(O(n \log n)\)
L¶
**upsolved by **
题意¶
题解¶
M¶
upsolved by TYB
题意¶
给出数组\(\{A_n\}\)，定义\(B_{i,j}=[i\le j]\min(A_i,A_{i+1},\dots,A_j)\max(A_i,A_{i+1},\dots,A_j)\)，\(q\)次询问，每次给出\(l,r,s,e\)，求\(\sum_{i=l}^r\sum_{j=s}^eB_{i,j}\)。
\(n,q\le1.5\times10^5\)
题解¶
首先转化为求\(\sum_{i=1}^a\sum_{j=1}^bB_{i,j}\)。
然后先考虑对于某个固定的\(j\)，\(\sum_{i=1}^aB_{i,j}\)怎么求。这是个经典问题，可以枚举右端点\(j\)，用两个单调栈维护，只需要线段树支持区间乘法即可。
再考虑原问题，实际上只需要再维护历史版本和即可，可以借助\(2\times2\)的矩阵维护。
有个小问题，如果令\(B_{i,j}=0(i>j)\)，那么我们还要支持区间修改操作。为了简单起见，我们令这些位置的值为\(1\)，最后减去即可。
记录¶
YZW过J(0:23)。
TYB写H，WA一次后AC(0:38)。
把题目过了一遍，感觉都不太会。跟榜看ACE。
JLK想了个K的做法，但不太敢写，先放着。
TYB决定乱搞一下C，然后就过了(2:41)。
还剩2h时JLK开始写K，期间YZW想出了A，换YZW写A。
YZW过A(3:54)。
JLK写完了K，然后TLE/MLE/RE循环，在YZW的优化下过了(4:43)。
总结¶
Dirt¶
H(-1)
K(-9)