2020-2021 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred)¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 92/840 | 4 | 6 | 11 |
A¶
upsolved by
题意¶
题解¶
B¶
upsolved by TYB
题意¶
给出\(n\)个\(d\)位的\(01\)串密码，你开始时有一个\(d\)位全是\(0\)的串，每次操作可以选择将这个串某个位变为\(1\)，或者将全部位都变为\(0\)，求最少操作多少次，过程中得到的串包含了所有\(n\)个密码，并输出方案。
\(d\le10,n<2^d\)
题解¶
首先答案有上界：\(\sum_i(popcount(S_i)+1)-1\)，表示每个输入密码时都先清空一次（除了第一次不用清空），再逐位输入。考虑两个密码\(S_a,S_b\)，若\(S_a\&S_b=S_a\)，则在输入\(S_b\)的过程中可以顺便输入\(S_a\)，也可以看作输入\(S_a\)不需要代价。由此我们可以得到一个做法：将初始答案设为上界，若\(S_a\&S_b=S_a\)，则\(S_a\)向\(S_b\)连一条权值为\(popcount(S_a)+1\)的边，然后跑最大权匹配，初始答案减去最大权匹配即为答案。但这样点数\(2^d\approx1000\)，边数\(3^d\approx60000\)，费用流跑不动（但好像有优秀的模板可以跑过去）。注意到这张图的边权只和点有关，所以其实可以转化为最大匹配问题。具体来说，匈牙利算法寻找增广路的时候，会把这条路径上的边匹配情况全部取反，但是注意到，原来已经匹配了的点依然会匹配，也就是原来的边权并不会损失，所以只需要贪心地让\(popcount\)较大的点匹配即可。
复杂度\(\mathcal{O}(6^d)\)。
C¶
solved/upsolved by
题意¶
题解¶
D¶
solved by TYB
题意¶
给\(n\)个正整数，要求选出若干个数，使得他们乘积个位数为\(d\)，且乘积最大，判断无解或输出方案。
\(n\le10^5,1\le a_i\le10^9,d\le9\)
题解¶
取对数DP即可。
E¶
solved by YZW
题意¶
对于一个长度为 \(n\) 的括号序列，以如下方式将括号序列对应到多边形：
- 设起点在 \((0,0)\)，将括号序列中的
(对应到向量 \((1,1)\)，将)对应到向量 \((-1,-1)\)，向量依次连接得到终点在 \((n,0)\) 的一条折线段，折线段与 \(x\) 轴围成的区域即为对应多边形。
给出长度 \(n\) 与多边形的重心 \((x,y)\)，求括号序列。
\(1\leq n\leq 36\)，\(x,y\) 与重心的距离误差不超过 \(10^{-9}\)。
题解¶
起初得到了错误的式子，以为多边形的面积 \(S\) 能直接计算，然而并不行。
考虑 \(S\) 确定时如何求出对应的括号序列。记重心为 \((\bar x,\bar y)\)，首先有：
将多边形划分为紧邻 \(x\) 轴的 \(n/2\) 个三角形与 \(s={S-n\over 2}\) 个边长为 \(\sqrt 2\) 的斜正方形 \(A_1,A_2,\dots,A_s\)，设这些斜正方形中心的横坐标为 \(x_1,x_2,\dots,x_s\)，则有：
考虑令：
容易估计得到 \(n\leq 36\) 时有 \(s\leq 153\)，\(s_x\leq 2754\)。
将坐标轴逆时针旋转 \(45\) 度，斜正方形转为正方形。可以发现可选的正方形排成 \(n/2-1\) 行，第 \(i\) 行有 \(n/2-i\) 个正方形。
考虑轮廓线 DP，令 \(f(i,j,s,s_x)\) 表示轮廓线划分到第 \(i\) 行第 \(j\) 列正方形的左上角，第 \(i\) 行轮廓线划分在第 \(j\) 列左侧时，前 \(i\) 列轮廓线确定了 \(s\) 个正方形，这 \(s\) 个正方形 \(A_{k_1},\dots,A_{k_s}\) 的横坐标之和 \(\sum_{i=1}^s x_{k_i}\) 为 \(s_x\) 的情况能否取得。边界条件为 \(f(1,n/2,0,0)=1\)，设第 \(i\) 行第 \(j\) 列的正方形横坐标为 \(x_{ij}\)，容易得到状态转移方程：
转移时需要记录是否能从上方或右方转移。求和可以提前预处理，因此转移时间复杂度为 \(O(1)\)。总状态数为 \({1\over 8}n^2 s_{\max} s_{x,\max}<7\times 10^7\)，跑得过！
由于 \(S\) 不确定，但是 \(S\leq 324\)，可以暴力枚举 \(S\)，考察 \(\bar xS,\bar yS\) 是否为整数，对应的 \(s,s_x\) 是否合法。对于合法的 \(s,s_x\)，考察 \(f(n/2,1,s,s_x)\) 对应的状态是否能取得，若能取得则逆推状态，得到所有可能的满足 \(S\) 与 \(\bar x\) 限制的括号序列，暴力验证 \(\bar y\) 是否满足条件。
最坏情况感性理解应该在 \(\bar x=n/2\) 时取得，此时满足 \(\bar x\) 限制的括号序列共有 \(2^{n/2}\) 个，该部分的复杂度为 \(O(n2^{n/2})\)，跑得过！
总时间复杂度为 \(O({1\over 8}n^2 s_{\max} s_{x,\max}+n2^{n/2})\)，跑得过！
F¶
solved/upsolved by
题意¶
题解¶
G¶
solved by JLK
题意¶
\(n\)个点的树，\(1\)为根，求从根出发经过恰好\(k\)个不同点的最小步数以及方案。
\(1 \le k \le n \le 100,1 \le T \le 100\)
题解¶
一开始以为是树形DP，但不方便输出方案。
其实，给定了\(k\)之后，最小步数就是\(2\times (d-1)-Mxdep\)。因为选中的点一定是包含根的连通块，再选一个点过去不返回。
那么就是要考虑\(Mxdep\)。把深度最大的点找出来、如果其深度大于\(k\)，就直接走这条链到第\(k\)层即可。否则，可以设置最后走到这个点，在到这个点之前还需要走到一些点，可以按dfs序找到前几个不在这条链上的，依次遍历，按dfs序选一定是联通的。
具体来说，把在链上的点标为1，不在链上但是选了的点标为2，dfs的时候先走2再走1即可。
\(O(Tn)\)
H¶
solved/upsolved by
题意¶
题解¶
I¶
upsolved by JLK
题意¶
交互题。你和\(n\)个人一起猜\(m\)个问题，每个问题有0/1两个选项。对于每个问题给出\(n\)个人的答案，然后你要给出自己的答案，交互器返回这道题的正确答案，然后继续下一题。要求最后你答错的题数不能超过\(1.3\times b+100\)，\(b\)为\(n\)个人里最少的答错题数。
\(1 \le n \le 1000,1 \le m \le 10^5\)
题解¶
有一个奇妙的方法。一开始设置一个常数\(\alpha(\alpha \lt 1)\)，每个人有相同的可信度\(A_i\)。每次根据每个人的可信度，用随机数判断当前选0还是选1。例如，把所有选0的人的可信度加起来，除以所有人的可信度，然后和一个\([0,1]\)内的随机数比较。如果随机数较小，就选0。公布答案后，对于答错的人，给\(A_i\)乘上\(\alpha\)。
本题取\(\alpha=0.8\)即可通过。
J¶
solved/upsolved by
题意¶
题解¶
K¶
solved by YZW
题意¶
给出一个 \(2n\) 的排列 \(p\)，可以进行以下操作：
-
交换 \(p_1,p_2\)，\(p_3,p_4\)，……，\(p_{2n-1},p_{2n}\)。
-
交换 \(p_1,p_{n+1}\)，\(p_2,p_{n+2}\)，……，\(p_n,p_{2n}\)。
求最少操作次数使得 \(p\) 有序，或判断不可能有序。
\(1\leq n\leq 1000\)。
题解¶
设第一个操作为 \(A\)，第二个操作为 \(B\)，易见 \(p\xrightarrow{A}p'\xrightarrow{A}p\) 且 \(p\xrightarrow{B}p'\xrightarrow{B}p\)，所以只可能交替进行 \(A,B\) 操作。注意到 \(p\) 在至多 \(O(n)\) 次 \(A,B\) 或者 \(B,A\) 操作之后会得到 \(p\)，因此暴力操作判断即可。
时间复杂度 \(O(n^2)\)。
记录¶
YZW过K(0:13)。
TYB和JLK讨论D，想到了取对数，担心精度问题，但没有更好的想法，试了一下过了(0:32)。
JLK写G，但是发现不会输出方案。TYB给了一个假做法，发现假了又给了个真做法，写完也过了(1:26)。
然后YZW想到了E的DP，讨论后开始写。
写完第一发RE了(2:50)，发现式子推错了。
又讨论了一下，还是可做，又WA了2发后过了(4:22)。
期间TYB和JLK主要在看B、I，但都不会。
TYB最后写了几发J的乱搞，寄了。
总结¶
TYB：B想了太久了，应该早点扔了。没想出来也不应该。
Dirt¶
E(-3)