2013-2014 ACM-ICPC, NEERC, Moscow Subregional Contest¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 2/12 | 8 | 9 | 12 |
A¶
solved by JLK
题意¶
有\(n\)个点，第\(i\)个点可以连出去\(K_i\)条边，问最多可以构成多少三元环。（边无视方向，可以有重边，但一条边只能算在一个三元环内）
\(1 \le n \le 10^4,0 \le K_1 \le 10^4\)
题解¶
一个比较直观的感觉是，如果\(K_i\)是比较平均的，那么总能构造出一种方案，使得答案为\(\lfloor \frac {sum}3 \rfloor\)。
如果不平均，有一个\(K_i\)特别大，那么就不一定了。就算一直从\(i\)连两条边出去，然后在外面选两个点连边，也可能消耗不掉所有\(K_i\)。
所以需要分类讨论，找到最大的\(K_i\)，看能不能被完全消耗。如果不能，就是其他点\(K_i\)之和。可以的话就是\(\lfloor \frac {sum}3 \rfloor\)。
B¶
solved by YZW
题意¶
签到。
题解¶
略。
C¶
**upsolved by **
题意¶
题解¶
D¶
solved by TYB & YZW
题意¶
题解¶
TYB 写了个黑盒给 YZW 调用。
YZW 继承黑盒，又整上去了只 SAM。
E¶
**upsolved by **
题意¶
题解¶
F¶
solved by TYB
题意¶
阅读理解。
题解¶
G¶
solved by JLK
题意¶
买卖东西，低价买高价卖，一开始没有东西。有\(q\)个事件，一种是增加/减少某个买入价格的商品数量，一种是增加/减少某个卖出价格的商品数量。强制在线，求每次事件之后的最大收益。
\(1 \le q \le 10^5\)
题解¶
最优策略肯定是买最便宜的，然后卖最贵的。如果知道要买卖\(K\)个东西，那么就是买最便宜的\(K\)个，卖出最贵的\(K\)个。买入的最大价格不会高于卖出的最低价格。
那么可以二分\(K\)，只要知道买入的最大价格和卖出的最低价格，就可以比较了。用动态开点线段树或者平衡树即可。
\(O(q\log w)\)或\(O(q\log q)\)
H¶
solved by YZW
题意¶
签到。
题解¶
略。
I¶
solved by JLK
题意¶
\(n\)个集合，给定两两的交，求每个集合。
\(1 \le n \le 200\)，交不超过\(10\)个数，\(1 \le a_i \le 10^4\)。
题解¶
用bitset维护一下，每个集合把所有交或起来就是一个可能的解。求出所有集合然后check一下即可。
\(O(n^2 \frac {10^4}{64})\)
J¶
**upsolved by **
题意¶
题解¶
K¶
solved by JLK
题意¶
\(n\)个数，求其中最大的\(K\)个。其中\(a_i=(A\times a_{i-2}+B\times a_{i-1}+C) \mod 2^{31}\)。
\(1 \le n \le 10^8, 1\le K\le 2\times 10^5\)
题解¶
做法较多。
我们的做法是，先把\(n\)个数分成\(K\)段，每段有一个最大值。每次可以把所有段对半切开，得到\(2K\)段，然后取最大值最大的\(K\)段，直到所有段的长度为1。因为肯定只有最大值最大的\(K\)段是有用的。
取最大值最大的\(K\)段可以直接排序。由于每次元素减半，所以每次求最大值的复杂度是\(O(n+\frac n2+\frac n4 +\dots)=O(n)\)
\(O(n+k\log k \log n)\)
还可以利用nth_element，先取前\(K\)个数，然后每次加入\(K\)个数，用nth_element求出前\(K\)大，保留这些，删去小的，这样还是\(K\)个数，一直做直到结束。
本质上思想是差不多的。\(O(n)\)
还可以利用桶排序，先考虑高位，找到前\(K\)大的最小的高位。高位比它大的肯定是答案。对于这个高位，再对低位排序，找到大的一些加入答案。
\(O(n+2^{15})\)
L¶
upsolved by JLK
题意¶
\(m\)个有向边，每个点入度至多为\(1\)，\(q\)次询问，给两个点集，问第一个点集里是否存在一个点，能到达第二个点集里的任意一点。如果能，输出最少要取前多少条边才能到达。
\(1 \le m.q \le 5\times 10^5\)
题解¶
考虑树上怎么做。把每个边是第几条边看成权值。询问可以给第一个点集里的点打标记，从第二个点集里的点往上跳，直到碰到一个打了标记的点。然后求这个路径的边的最大值。（相当于最大值最小，那么肯定是找到第一个点。）
扩展到基环外向树上。可以把环看成一个点然后大量分类讨论，比较麻烦。
事实上可以把环上最大权值的边断掉，剩下构成一棵树，如果能找到的话就直接找。找不到的话，就有可能用到这个断掉的边。如果环上有标记点，那么就能找到，并且在环上的这部分的边权最大值就是断掉的边的权值。环上没有标记点就是找不到。
树剖线段树维护一下即可，细节比较多。每次往上跳需要在线段树上二分。
还要注意会有很多连通块，有很多没有连边的点，题目只限制了边数，点的编号在\([1,5\times 10^5]\)任意取。所以每个连通块都要维护一下这个环的信息。
\(O(q \log^2 m)\)
另一个题解¶
有向的基环树可以直接倍增求走 \(k\) 步之后到哪里以及这 \(k\) 步边权的最大值。
找环之后把环缩成一个点，记录环上的顺序。由于点之间可能不连通，可以添加一个超级根结点把独立的缩环之后的基环树连起来。
对于询问，建立虚树之后遍历一遍虚数就可以找到最近的染色祖先，如果染色祖先对应环，需要在环上展开找到环上最近的染色点，倍增求答案即可。
\(O(q \log m)\)
记录¶
JLK过A(0:10)，YZW过H(0:13)，B WA一次后AC(0:29)。
JLK过I(0:37)，TYB过F(0:50)。
TYB写D，WA了一次。
YZW和JLK看K，JLK提出了乱搞，YZW想到一个比较靠谱的做法，JLK开始写，AC(2:24)。
讨论后发现D假了，可以改对但是很麻烦。然后发现G可做，JLK开始写，MLE一次WA一次后AC(3:14)。
开始改D，WA了几次。期间JLK会了L。
JLK先写L，途中改了多次D还是没过。L写完了也一直WA。最后D改对了(4:48)，L没过。
总结¶
JLK：再也不最后1h写数据结构了。。
Dirt¶
B(-1)
D(-6)
G(-2)