XXI Open Cup. Grand Prix of Korea¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 82/? | 5 | 7 | 12 |
A¶
solved by JLK
题意¶
有\(n\)个广告，要投放到\(m\)个人去，每个广告要求投放\(a_i\)次，每个人最多收到\(b_i\)个广告，并且不能收到相同广告。\(q\)次操作，每次对于某个\(a_i\)或\(b_j\)加减1，问是否可行。
\(1 \le n,m,q \le 2.5\times 10^5,0 \le a_i,b_j \le 2.5\times 10^5\)
题解¶
可行的充要条件是对\(a_i\)从大到小排序后，\(\forall i\)满足\(\sum\limits_{j=1}^ia_i\le \sum\limits_{j=1}^mmin\{b_j,i\}\)。
用线段树维护\(\sum\limits_{j=1}^mmin\{b_j,i\}-\sum\limits_{j=1}^ia_i\)的最小值即可。下标为式中的\(i\)。
预处理初始值。修改\(b\)的时候就是区间加减1。修改\(a\)的时候也是区间加减，但是还需要找到当前\(a_i\)的排名，可以直接在排序后的\(a_i\)数组上二分找到对应的位置。如果+1就是找相同的第一个，-1就是找相同的最后一个。
全局最小值非负就代表是合法的。
\(O(q\log n)\)
B¶
upsolved by JLK
题意¶
一个\(n\times m\)的矩阵，\((i,j)\)的权值为\(A_i+B_j\)，只能往右或往下走权值非负的格子。起点是\((s,1)\)，终点是\((t,m)\)，求有多少起点和终点点对是合法的。
\(1 \le n,m \le 2\times 10^5\)
题解¶
实际上只有四种情况会导致不合法：
1、某一行被阻断
2、某一列被阻断
3、存在一个点\((x,y)\)，这个点往上和往左可以封住起点
4、往下和往右会封住终点
这个矩阵比较特殊，对于每个被封住的情况，都可以找到一条笔直的分界线。
因为对于任意两行，不能走的列的集合一定是包含关系，不会出现类似这种情况：
OXXOO
XOOXX
所以可以把所有不合法的情况归纳成四种。
对于第一种，假设\(i\)行阻断，那么\(s\le i \le t\)都是不合法的。
对于第二种，肯定是用一个最小的\(B_j\)来判断。它会把所有行分成若干区间\([L_k,R_k]\)，每个区间内部是被列阻断的。那么\(L_k \le s \le t \le R_k\)都是不合法的。
对于第三种，枚举这个点所在的行，那么首先要找到从左往右最多到哪里，然后再用这个区间里最小的\(B_j\)来向上走。向上走的这些行的起点全部不合法。
第四种同理。
这些都可以用一些数据结构来维护。最后枚举起点计算合法的终点的个数。
\(O(n\log n)\)
C¶
**upsolved by **
题意¶
题解¶
D¶
solved by JLK
题意¶
\(n\)个点的无向图，给定\(m\)条边，每条边有边权。要加上一些边使得变成完全图，并且满足对于每个三元环，不存在有一条边边权小于另外两条。求最小的边权和。
\(1 \le n \le 3\times 10^5,0 \le m \le 3\times 10^5\)
题解¶
对于这个限制条件，如果有两条连着的边已经确定，那么另外一条边一定是这两条边的min。
考虑从大到小加边，对于最大边权的所有来说，它们构成的连通块一定是最大边权的连通块，因为要通过上面限制条件不断扩展。
然后加入次大的边。他们单独构成的连通块也是次大边权的完全图。如果次大连通块和最大连通块连起来了，那么就可以扩展出这两个连通块并集的完全图。新增的边都是次大的边。
以此类推，从大到小加边，每次对于同一个边权的边，要把所有含有这个边权的边的连通块补成完全图。用并查集维护一下即可。
加入小的边的时候如果发现两端已经被大的边连成连通块了就是无解。
\(O(m\log m)\)
E¶
upsolved by TYB
题意¶
给一个无向图，求有多少对\([L,R]\)，使得仅保留编号在这个范围内的点和所有它们之间的边，是一条链。
\(n,m\le2.5\times10^5\)
题解¶
先转化一下一条链的条件：1、没有度数\(\ge3\)的点；2、没有环；3、点数\(=\)边数\(+1\)。枚举右端点，前两个条件用双指针解决，其中第二个需要用LCT动态维护图连通性。可以发现，满足前两个条件后，这个图是若干条链的集合。用线段树维护点数\(-\)边数的值，只有一条链仅当这个值为\(1\)，再维护最小出现次数即可。细节较多。
F¶
upsolved by TYB
题意¶
有\(n\)个带权的区间\([l_i,r_i]\)，权值为\(w_i\)，要求选出权值和最大的若干个区间，使得任意一点最多只被\(2\)个区间覆盖。
\(1\le l_i\le r_i\le 5\times10^5,n\le2.5\times10^5,0\le w_i\le 10^{12}\)
题解¶
这居然是广为人知的套路题吗……
考虑如果是最多只被\(1\)个区间覆盖，那么可以dp。实际上，还有一种最短路做法，按如下方法建图：
第一种边：对于每个区间，从\(l_i\)到\(r_i+1\)建一条权值为\(-w_i\)的有向边；
第二种边：对于\(i\in[1,5\times10^5)\)，从\(i\)到\(i+1\)建一条权值为\(0\)的有向边。
那么从\(1\)到\(5\times10^5\)的最短路的相反数即为答案，正确性显然。
回到这道题，只被最多\(2\)个区间覆盖的等价条件是，按照上面的方法建图，可以选出两条第一种边不相交的最短路，即可以将选出的所有区间分成两个集合，每个集合的区间两两间都不交。这个结论还可以推广到被至多\(k\)个区间覆盖。这是经典费用流问题，只需要把第一种边的流量设为\(1\)，第二种边的流量设为\(2\)即可。
需要dijkstra费用流，且需要处理负权边。
2022/7/29 Update：CF164C
G¶
**upsolved by **
题意¶
题解¶
H¶
solved by TYB
题意¶
有\(0\sim n-1\)共\(n\)种数，给出每种数的个数\(c_i\)，执行以下操作若干次，直到剩下一个数：选择\(k(k\ge1)\)个数删除，加入一个他们的\(mex\)值。求最后的数最大是多少。
\(n\le10^5,c_i\le10^9\)
题解¶
先特判一个数的情况。二分答案，设为\(x\)，则\(\ge x\)的数全部可以变为\(0\)。然后从\(x-1\)开始倒着搞，如果不够就从前面补，如果多了就变成\(0\)。注意二分上界略大于\(n\)，以及中间可能爆long long。
I¶
upsolved by JLK
题意¶
\(n\)个点以1为根的树，每个点初始是0，\(q\)次操作，每次链+1或者子树+1，求每次操作后的加权重心，有多个取深度最小的。
\(2 \le n \le 10^5,1 \le q \le 10^5\)
题解¶
先考虑只有一个重心的情况。
重心的性质是每个子树权值和都不超过总权值的一半。
分析这个性质，如果一个点是重心，那么它往根方向的子树的权值和一定不超过总权值的一半。也就是它自己为根的子树的权值和不少于总权值的一半。
那么也就是找到一个深度最大的点，满足它自己为根的子树的权值和不少于一半。
如果把每个点按dfs序排列，并且一个点看做有权值大小个，那么这个序列的中位数的点一定会被重心为根的子树包含。
找到这个中位数点之后，用倍增或者树剖往上跳找到一个合适的位置即可。
如果有多个重心，要找到深度最小的那一个重心，那么不是最小的重心为根的子树权值和一定恰好为总和的一半。那么答案就是最深的子树权值和大于总权值一半的点。
修改用树剖+线段树或BIT维护即可。
\(O(q\log^2n)\)
J¶
solved by TYB
题意¶
无穷大的平面直角坐标系，\((0,0)\)是障碍点，给出一个固定的长度为\(n\)的由UDLR组成的序列，表示每一步的移动方向，如果走了某一步后到达障碍点，那么不走这一步。\(q\)次询问，给出起点\((x,y)\)，求最后会到达的坐标。
\(n,q\le3\times10^5\)
题解¶
首先可以对于每个前缀，求出哪个点在此第一次到达障碍点。询问时若不是\(n\)个特殊点之一，则直接加偏移即可。否则，到达障碍点的前一步一定是在\((0,1),(0,-1),(1,0),(-1,0)\)这四个点之一，只需要预处理出从这四个点出发，走过每个后缀后到达哪个位置即可。具体方法类似，找下一个到达障碍物的位置即可。
K¶
solved by YZW
题意¶
题解¶
L¶
**upsolved by **
题意¶
题解¶
记录¶
YZW写K，WA一次后AC(0:27)。
TYB写H，WA两次后AC(0:51)。
然后就卡住了，主要跟榜看DJ，没有思路。
把题目过一遍，TYB和JLK讨论后JLK写A，WA一次后AC(2:12)。
YZW开始写J，写完了之后又感觉有问题。换TYB写，写了一会YZW又改了一下原来代码交上去，WA。
然后JLK把YZW拉走去看DF。
TYB过J(3:16)。
TYB突然提出了D的思路，JLK开始写，WA一次后AC(4:12)。
最后把E口胡出来了，G也大概有了思路，但没时间了。
总结¶
JLK：确定新思路之后就不要回去改原来代码了，容易浪费时间。
Dirt¶
A(-1)
D(-1)
H(-2)
J(-1)
K(-1)