Ptz Camp 2021s D2: The American Contest¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 30/92 | 7 | 8 | 13 |
A¶
upsolved by JLK
题意¶
给定一个长度为\(n\)的不相同正整数序列\(a\)，满足如下性质：
对于每个\(a_i\)，所有\(x\)在二进制下的子集也在\(a\)中。
要求找到\(a\)的一个排列\(b\)，使得\(\forall i,a_i\&b_i=0\)。
\(1 \le n \lt 2^{18},0 \le a_i \lt 2^{60}\)
题解¶
比较巧妙的一个构造。用如下的方法即可构造出答案：
初始令所有\(b_i=a_i\)。递归求解，Solve(pre)将构造出不考虑pre这个前缀的情况下，所有以pre为前缀的数的\(b_i\)。（即在pre之后的若干二进制位保证所有\(a_i\&b_i=0\)）
每次要加一个二进制位，按照当前这一二进制位的0/1分类。
如果都是0，就直接Solve(pre+0)
如果不都是0，那么首先调用Solve(pre+0),Solve(pre+1)。然后枚举所有这一位为1的数。将pre+1+x和pre+0+x对应的\(b_i\)交换。
下面证明正确性。
由\(a\)的性质，每次枚举这一位为1的数\(a_x\)，一定存在对应这一位为0的数\(a_y\)，因为后者是前者子集。目前已经构造出的\(a_y\&b_y\)是在这一位为0，而\(a_x\&b_x\)是1。通过交换\(b_x,b_y\)，使得两个与起来都是0。对于没有访问到的这一位为0的数，也不需要动了，本身这一位就是0。因此这样构造是正确的。
\(O(60n)\)
B¶
**upsolved by **
题意¶
题解¶
C¶
solved by TYB
题意¶
\(n\times m\)的方格图，其中\(k\)个点是障碍，求边长最大的正方形，使得用这个正方形上下左右动能覆盖每一个非障碍点。
\(k,n,m,n\times m\le5\times10^6,8s\)
题解¶
二分答案\(x\)，考虑原图中每个没有障碍的边长为\(x\)的正方形，用其左上角的点代表，若一个正方形能移动到另外一个处，则把这两个正方形代表的点连边，用并查集维护连通性，最后首先看所有点有没有都连通，然后看这些正方形是否能覆盖所有非障碍点即可。
\(\mathcal{O}(nm\log\min(n,m))\)
D¶
solved by JLK
题意¶
签到，略
题解¶
E¶
solved by YZW
题意¶
题解¶
F¶
solved by TYB
题意¶
签到，略
题解¶
略
G¶
**upsolved by **
题意¶
题解¶
H¶
**upsolved by **
题意¶
题解¶
I¶
upsolved by JLK
题意¶
\(n\)个点\(m\)条边的图，有\(g\)个人，每个人有一个点集，表示这个人可以被派遣到哪些点。选出一些边，满足以下条件：
把每个人派遣到一个点上，一个连通块里只能有一个人，不能有人没有被派遣，也不能有连通块没有人。
求出满足条件的最小边权和。
\(1 \le n \le 300,0 \le m \le \frac {n(n-1)}2,1 \le g \le n\)
题解¶
题目没有说是连通图！！不连通也有可能合法！
首先可以观察到，最终选出的边一定是最小生成树（其实是森林，下面简称MST）里的边。对于一个合法的派遣人的方案，一定能在MST里选出对应的一些边，而在MST外选边是不优的。那么只需要考虑MST里的边。
而对于一个连边的方案，相当于是把人和连通块放在两边，跑二分图匹配。最后的合法方案一定是完美匹配。
Sol.1¶
一种贪心的做法是，从小到大枚举MST里的边，每次是把两个连通块并起来，如果并起来之后匹配数比人数少，那么这条边就不可行。把合法的边挑出来就是答案。（还需要判断最终选出的边集是否合法，比如是否有孤立没有被匹配的连通块，下面所有解法都是一样）
其实这样暴力跑Dinic是可以通过的。\(O(n^{3.5})\)
不过还有更快的方法。每次并了两个连通块，相当于只改了至多一个匹配。以被改动的人出发找一个增广路，如果能再匹配上就说明可行。这样一次至多\(O(n^2)\)，总复杂度为\(O(n^3)\)，而且跑不满，实测很快。
Sol.2¶
有一种费用流的解法。\((x,y)\)表示流量为\(x\)，费用为\(y\)。
首先把每个点拆点。源点连到每个人\((1,0)\)，然后每个人连到对应点的反点\((1,0)\)。每个点的反点连到自己的正点\((1,0)\)。
对于MST里的所有连通块，可以固定一个根，然后每个点的正点连到父亲的反点\((1,0)\)，正点再连到汇点\((1,-edge(i,fa_i))\)。（对于根，边权看做0）
这样做的目的是，每个人\(a\)的流看做一条链，是从派遣到的点延伸到他占有的连通块的深度最低的点。这个连通块和其上面的点断开的花费就是最顶上的边权。
而对于另一个人\(b\)，如果\(b\)在\(a\)的子树内，为了最大流，必须在\(a\)的链下面某处切断，也就是分出来另一个连通块。以此类推。这样求出的最大流代表一种合法的划分连通块方案，最小费用就是断边的最大花费，和MST总边权和相减就是选出来的最小花费。
直接这样会有bug，还需要强制每个连通块的根一定被流到（由上面流的意义可得）。那么可以再开一个点\(T'\)，不是根的点先连到\(T'\)，然后\(T'\to T\)连\((g-(n-cnt),0)\)（\(cnt\)为连通块个数）。所有根就直接\((1,0)\)连到\(T\)。
如果最大流等于人数，并且满足上面的所有限制，就是合法的。
\(O(n^3)\)，我一开始的模板TLE了，用ZKW跑的还挺快，不过还是比解法1慢四倍左右。
J¶
solved by YZW
题意¶
题解¶
K¶
**upsolved by **
题意¶
题解¶
L¶
solved by YZW
题意¶
题解¶
M¶
solved by YZW
题意¶
题解¶
记录¶
开局签MFDJ(0:29)。
然后看C，感觉像是之前的一道题，略有不同。讨论之后TYB开写，然后过了(1:22)。
YZW写L，WA一次后AC(2:05)。
剩下几个题AEIK都不太会写。TYB尝试K打表，没有找到规律。
JLK写E，写了一半发现有个地方不会。YZW突然会E了，然后过了(3:09)。
最后几十分钟JLK尝试了网络流写I，TLE。
总结¶
Dirt¶
L(-1)