Petrozavodsk Camp, Summer 2021 NAC-2021 Finals Contest¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 55/92 | 6 | 10 | 13 |
A¶
upsolved by JJLeo
题意¶
长度为 \(n\) 的序列 \(a_1,a_2,\ldots,a_n\)，保证对任意 \(x\) 满足 \(a_i \& x = a_i\)，存在 \(a_j=x\)。
构造一个排列 \(p_1,p_2,\ldots,p_n\) 使得 \(a_i \& a_{p_i}=0\)。(\(1 \le n \le 2^{18}\)，\(0 \le a_i < 2^{60}\))
题解¶
考虑将 \(a_1,a_2,\ldots,a_n\) 插到 01-Trie 上，每个叶子代表一个元素。那么题目中的条件就变为对于任意节点，如果忽略当前位和深度更小所代表的位，那么右儿子的每个叶节点也存在于左儿子中，也就是二进制表示的 \(x0y\) 是 \(x1y\) 的子集，其中 \(x,y\) 分别是二进制串的前缀和后缀。
考虑递归地完成构造，对每个节点，对该节点的所有叶节点构造一个自己到自己的双射，使得有映射关系的两个数在忽略当前位和深度更小所代表的位时 \(\&\) 为 \(0\)：
- 对于叶子节点，直接将其映射到自己，因为所有位都被忽略了，从而合法。
- 对于非叶节点，左儿子中的映射不会发生冲突，因此它们新增这一位均是 \(0\)；但右儿子会，考虑将右儿子中每个叶子映射的元素和左儿子中对应叶子映射的元素互换。对于这些元素，更低的位根据递归构造是合法的，当前新增的位均为一个 \(1\) 一个 \(0\) 因此合法。
B¶
upsolved by
题意¶
毒瘤几何。
题解¶
崔佬冲！
E¶
upsolved by JJLeo
题意¶
给定一个长度为 \(n\) 的带问号的小写字母字符串，每个问号都可以随意填，求合法回文划分的方案数。两个方案不同当且仅当有一个问号填的不同或划分不同。(\(1 \le n \le 3 \times 10^4\))
卡空间，\(64 \text{MB}\)。
题解¶
考虑两边一起进行匹配，因此只需要看一侧，可以 \(O\left(n^2\right)\) 预处理一个区间能否匹配和有多少个匹配的问号，然后就可以 \(O\left(n^2\right)\) dp，然而空间复杂度也是 \(O\left(n^2\right)\) 的，寄。
设原字符串为 \(s_1s_2\cdots s_n\)，如果将原字符串变为 \(s_1s_ns_2s_{n-2}\cdots\) 的形式，将其划分为数个偶回文串和一个后缀，可以发现和上述 dp 等价。
枚举每个偶回文串的中心，向左右进行扩展，设扩展到了 \([l,r]\)，可以发现 \(f_{l-1}\) 一定都被更新完了了，所以可以直接将其加到 \(f_{r}\) 上，这样就把空间剩下来了。一段能贡献当且仅当其能进行匹配，如果有 \(i\) 个问号和问号匹配，则贡献是 \(26^i\)。
G¶
upsolved by
题意¶
题解¶
H¶
upsolved by
题意¶
题解¶
I¶
upsolved by JJLeo
题意¶
\(n\) 个点 \(m\) 条边的带权无向图，边权均为正。有 \(g\) 个守卫，每个守卫有一个点集。你需要选择一个边集，使得存在一个守卫和连通块的完美匹配，每个守卫对应的连通块必须存在一个点在他对应的点集中，最小化边集的权值之和，或判断无解。(\(1 \le n \le 300\)，\(0 \le m \le \dfrac{n(n-1)}{2}\)，\(1 \le g \le n\))
题解¶
首先一定是恰好连 \(n-g+1\) 条边，否则连多了成环肯定不优。
其次连的边一定是在最小生成树上的，否则同样的连通块可以用最小生成树上的边代替。
然后，可以证明所有符合下述所有条件的边集 \(S\) 构成拟阵：
- 存在一个边集 \(T \supseteq S\) 满足 \(T\) 是一个合法的边集。
证明少一页 PPT，视频又没声音，我也很绝望。
因此只需要将最小生成树上的边从小到大排序后依次添加，将每个守卫和可以匹配的连通块连边，看是否每个守卫都能匹配上，如果可以则选择这条边，否则不要这条边。
每次匹配可以跑 dinic 来解决，但是每次修改量很小，这样做很浪费。
可以先在不连边时跑一次增广路算法得到匹配数，如果此时都不行说明一定无解。
接下来依次加边，可以发现只有合并的两个连通块的匹配情况会发生变化，如果两者都匹配了一个守卫那么需要删掉一个，我们对被删掉匹配的那个守卫再跑一次增广路即可，总时间复杂度为 \(O\left(n^3\right)\)。
实现细节上，增广路算法中每次将右侧的点变为其并查集中的父亲即可实现连通块的合并。
K¶
upsolved by JJLeo
题意¶
题解¶
记录¶
0h：MJX和CSK在但不完全在，MJX看了个A可能是个签到（？，看M过了一堆，MJX瞅了瞅M给喂了ZYF，ZYF喂给了MJX一个假的F，MJX觉得是个裸的manacher，ZYF冲了M过了，还有D是签到，ZYF过了。MJX写完了让ZYF看，ZYF说MJX写的不对，MJX说写的老对了，ZYF说应该是balabala，MJX说那样例都过不了，然后看了样例和题，发现题读错了，扫一遍就行了，MJX就直接写了。MJX过了样例直接冲了，WA了，ZYF直接重构，过了。ZYF开始读错题了，然后写了一发过了样例，交上去WA了。
1h：MJX想着直接DP过J，然后太困了，写了一堆P话，不过过了就行。CSK和ZYF想了个C的做法，ZYF直接冲，debug一万年，一维数组模拟二维数组忘记处理边界情况一直越界，之后交了两发wa，一个是只从左上角dfs，另一个是双重循环break了一个，寄！改了过了。MJX给了 ZYF L做法，看起来L是个sb题，喂了ZYF。
2h：ZYF写了写过样例了，想了想WA了，没判最短路，改了就过了，之后不写了，太nt了，MJX和CSK已经快到另一个世界了。