The 2020 ICPC Asia Macau Regional Contest¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 3/51 | 8 | 10 | 12 |
A¶
solved by TYB
题意¶
给出序列\(\{a_n\}\)，对所有\(n\)的排列\(p\)，求\(\frac{1}{n!}\sum_p\sum_{i=1}^n\Pi_{j=i}^{n}a_{p_j}\)，结果对\(998244353\)取模。
\(n\le10^5\)
题解¶
考虑对每个长度为\(i\)的后缀积算出其贡献，那么最后答案的式子就是\(Ans=\frac{1}{n!}\sum_{i=1}^ni!(n-i)!f_i\)，其中\(f_i\)表示从\(a\)中选出\(i\)个不重复的数的乘积的和，那么只需要求出\(f\)。考虑生成函数，\(f_i\)就是\(\Pi_{i=1}^n(1+a_ix)\)这个多项式的\(i\)次项系数，直接分治NTT即可。
\(\mathcal{O}(n\log^2n)\)
B¶
**upsolved by **
题意¶
题解¶
C¶
solved by YZW
题意¶
给出 \(n\) 个数，将其分为两个集合，使得两个集合内任意两个数的异或和最小值最大。
题解¶
似乎是擦边假做法。按异或边权从小到大枚举加边（Trie 经典套路），判断当前是否仍为二分图，出现奇环时的权值减一即为答案。并且可以通过带权并查集的奇偶性分配集合。复杂度不会证，但是感性理解理解感觉挺小的，但是还是不会证，所以为什么能 AC 呢？
D¶
solved by JLK
题意¶
原批模拟题，略
题解¶
E¶
solved by JLK
题意¶
有\(n\)个点\((i,h_i)\)以及\((0,0),(n+1,0)\)。相邻的点用折线相连，形成山的形状。在\(n\)个点上各拍了一个照片，照片是以拍照点为中心，横\(2W\)纵\(2H\)的矩形。对于每个\(k=1,2,\dots,n\)，要选出\(k\)张照片，使得照到山的面积的并集最大。求每个最大面积。
\(1 \le n \le 200,1 \le W \le 5,1 \le H,h_i \le 10^4\)
题解¶
看到\(W\)很小，很容易想到状压。
\(dp_{i,j,S}\)表示前\(i\)个点，选了\(j\)张照片，前9个点的选照片情况为\(S\)，的最大面积。
对于确定的\(i,S\)，枚举前后\(W\)列，检查前面几个照片的情况，求出选上\(i\)的照片新增的面积即可。
\(j\)实际上和\(i,S\)独立，对于\(i,S\)算出面积后再枚举\(j\)转移即可。
\(O(n^22^9)\)
F¶
solved by YZW
题意¶
构造 \(n\) 个点的无向图，要求每个点度为 \(d\)，并且恰好有 \(c\) 个联通块。
题解¶
拍脑袋的构造，しかし多くの corner case がある。
G¶
solved by TYB
题意¶
给出长度为\(n\)的序列\(a\)，\(m\)次操作，每次给出\(k\)，分为以下两种：
\(\bullet\) 将\(k\)加到序列末尾。
\(\bullet\) 两人进行以下游戏：将一个棋子放在序列第\(k\)个位置，每次将其移到某个\(k'\)，满足\(k<k'\)且\(popcount(a_k\bigoplus a_{k'})\le1\)，无法移动的玩家输，输出先手还是后手获胜。
\(n,m\le2\times10^5,0\le a_i\le 255\)，且对于所有操作\(1\)，\(0\le k\le 255\)
题解¶
重要结论：对于某个\(k\)，若存在\(k'>k\)且\(a_{k'}=a_k\)，则在\(k\)这个位置开始游戏先手必胜。证明考虑\(a_k\)最后一次出现的位置\(p\)，若从\(p\)开始先手必胜，也就是存在某个\(p'>p\)，从\(p\)可以跳到\(p'\)，且从\(p'\)开始游戏先手必败，那么对于\(a_k\)之前出现的位置，也可以跳到\(p'\)；若从\(p\)开始先手必败，那么对于\(a_k\)之前出现的位置可以跳到\(p\)。有了这个结论后，有效的位置只有每种数最后一次出现的位置，只需要在每次询问的时候对这些位置求一下即可。
时间复杂度\(\mathcal{O}(255\log {255}\times m)\)。
H¶
**upsolved by **
题意¶
题解¶
I¶
upsolved by TYB
题意¶
初始序列为空，然后进行\(m\)次操作，每次为以下两种之一：
\(\bullet\) ADD a b：在序列末尾添加一个数\(a\)，其价值为\(b\)。
\(\bullet\) DEL：删除序列末尾的数。
每次操作后，设当前序列所有数的异或和为\(s\)，从中选出若干个数，使他们的异或和也为\(s\)，且价值总和最小，求这个最小价值。
\(0\le a<2^{14},m\le40000\)，空间限制\(8\)MB。
题解¶
操作删除均在末尾进行，所以可以建出操作树，这样就有了一个时空复杂度均为\(\mathcal{O}(am)\)的做法：\(f[S]\)表示当前数异或出\(S\)这个数的最小价值，在每个节点记录下当前的\(f\)数组，递归完一个儿子后暴力改回来。但去掉某个数之后无法令\(f\)回撤，空间无法达到题目要求。考虑进行轻重链剖分，每个节点到根节点的路径上轻边的条数不超过\(\log m\)，于是可以只记录下每条轻链的开头的父亲处的状态，在dfs时先访问轻儿子即可，空间复杂度降为\(\mathcal{O}(a\log m)\)。
J¶
solved by JLK
题意¶
有\(n\)个点排成一列，每个点有颜色\(c_i\)和权值\(v_i\)的物品。\(m\)个操作：
1：单点修改颜色和权值。
2：询问。
从一个点\(s\)出发，往右走收集物品，但是同色的物品只能拿一个，而且跳过的物品不能超过\(k\)个。问最大权值。
\(1 \le n,m \le 2 \times 10^5,1 \le c_i \le n,1 \le v_i \le 10^9,0 \le k \le 10\)
题解¶
显然肯定是尽可能走到最右边。权值最大，就是对于相同颜色的物品，只取一个最大权值的。
注意到\(k\)很小，考虑暴力跳。
定义\(nxt_i\)为\(i\)点右边第一个颜色相同的点，用线段树维护区间最小\(nxt\)。
那么跳的时候相当于是找到一个最右边的\(x\)，使得\([s,x]\)区间的\(nxt_i\)最小值为\(x+1\)（也可能直接跳到末尾了）。
可以在线段树上二分。找到一个\(x\)之后把当前冲突的那个点的\(nxt\)改成INF，就可以找下一个，最后恢复即可。
\(O(nklogn)\)
K¶
upsolved by JLK
题意¶
有\(n\)个长\(w\)宽\(h\)的广告，第\(i\)个广告的左下角为\((x_i,y_i)\)，要求在\([l_i,r_i]\)时间内一直挂上。在任何一个时刻，挂上的广告不能有任何重叠。现在要选一些广告挂上。
另外有\(m\)个要求，\(a_i,b_i\)两个广告不能都不挂。求方案或判无解。
\(1 \le n \le 5\times 10^5,1 \le w,h,x_i,y_i,l_i,r_i \le 2000,1 \le m \le 10^6\)
题解¶
很显然的2-sat问题，但是需要优化，因为边数是\(O(n^2+m)\)级别的。
首先要求出不能同时挂上的广告，可以通过bitset维护每个点x坐标相交，y坐标相交，时间相交的广告状态，把三种情况与一下就是冲突的广告。
现在知道边的情况了，要优化2-sat。这里需要使用Kosaraju算法求强连通分量。由于过程中只需要遍历没有遍历过的点，所以可以用bitset加速，每次把边的bitset和没遍历过的点的bitset与一下，找到第一个即可。可以使用bitset的_Find_first函数。
\(O(\frac {n^2}w+m)\)
注意，每次必须用一个tmp的bitset存下需要进行运算的bitset，然后一步一步来执行运算，不能直接用现成的bitset运算，否则会MLE。（大概是因为每次运算系统重新开了一个bitset来存）
L¶
solved by YZW
题意¶
签到，略。
题解¶
见上。
记录¶
YZW过L(0:11)。
JLK写D，WA一发后AC(0:48)。TYB和YZW讨论A。
TYB写A，JLK和YZW讨论E，发现YZW一开始读错题了，其实可做。
TYB过A(1:10)，JLK写E。
写完没过样例，YZW说F好写，先写F。
随后F WA两次，JLK改对了E(1:56)，接着YZW改对了F(1:57)。
JLK写J，WA了一次，对拍了一下又TLE，换TYB写G。
JLK改对了J(3:31)，然后TYB过了G(3:36)。
YZW开始搞C，JLK和TYB讨论BHK，没有什么进展。
YZW过了C(4:31)，然后下班。
总结¶
JLK：这场先开了几个没人写的题，比较成功。还是应该多看题，少看榜。
Dirt¶
D(-1)
F(-2)
J(-2)