2016-2017 ACM-ICPC Northeastern European Regional Contest (NEERC 16)¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 79/471 | 5 | 12 | 13 |
A¶
solved by Bazoka13
题意¶
题解¶
B¶
upsolved by
题意¶
题解¶
C¶
upsolved by 2sozx
题意¶
三种操作方式：
- 将图中所有颜色为 \(c_1\) 的变为颜色 \(c_2\)
- 将点 \(a, b\) 所在的图合并为一个图，但不连边
- 将图中所有颜色为 \(c_1\) 的点与颜色为 \(c_2\) 的点连边
现给定 \(n\) 个点，初始颜色均为 \(1\) ，分别属于 \(n\) 个不同的图，问是否能通过上述操作并且使用不超过 \(4\) 种颜色构成给出的仙人掌。\(n\le 50000\)
题解¶
先考虑把仙人掌缩点，对于一棵树，显然可以通过现合并子树完成，对于以后再也不需要合并的点可以设成颜色 \(2\) ，而需要合并的点显然一颗子树只有深度最低的点有用，颜色设为 \(1\) 即可，合并也很简单。
现在考虑环缩成点的情况，可以在子树合并完后将环合并起来即可。方式如下图。
D¶
upsolved by 2sozx
题意¶
\(n\) 天，每天可以吃或睡，各有不同的贡献，每个连续的 \(k\) 天吃饭不得少于 \(me\) 天，睡觉不得少于 \(ms\) 天，问最大收益是多少，\(n\le 1000, s_i, e_i \le 10^9\)。
题解¶
首先我们可以先认为每天都在睡觉，现在只需要考虑哪天变成吃，考虑建图。
-
令 \(s = 0, t = n + 1\) ，每个点 \(i\) 向 \(min(i + k, t)\) 连容量为 \(1\) ，费用为 \(e_i - s_i\) 的边
-
\(s\) 向 \(1\) 连一条容量为 \(k - ms\) ，费用为 \(0\) 的边，表示最多改变 \(k - ms\) 的睡觉
-
\(i < k\) 时向 \(i + 1\) 连一条容量为 \(k - ms\) ，费用为 \(0\) 的边
-
\(i \ge k\) 时向 \(i + 1\) 连一条容量为 \(k - ms - me\) ，费用为 \(0\) 的边，表示一定得留下 \(me\) 的时间睡觉
最后跑费用流即可。
E¶
solved by JJLeo Bazoka13
题意¶
题解¶
G¶
upsolved by 2sozx
题意¶
给定一个有向图，两个人移动， \(A\) 的倾向为无限循环 \(>\) 赢 \(>\) 输， \(B\) 的倾向为赢 \(>\) 输 \(>\) 无限循环，问从每个点由 \(A/B\) 分别开始最后 \(A/B\) 的状态是什么。\(n\le 10^5, m \le 2 \times 10^5\)
题解¶
先考虑无限循环，因为除了无限循环，两人的想法是相同的，无限循环只需要建反图然后拓扑即可。
在已知每个点由 \(A/B\) 开始是否为无限循环时，首先通过无限循环计算出非无限循环的每个点的度数，再用反图拓扑即可。
最后如果还有点判断不出来，则 \(A\) 一定赢， \(B\) 一定输。
I¶
upsolved by
题意¶
题解¶
J¶
solved by JJLeo Bazoka13
题意¶
题解¶
K¶
upsolved by 2sozx
题意¶
给三个 \(01\) 矩阵，可以平移前两个矩阵，然后两个矩阵异或，问第三个矩阵是否能够包含异或后矩阵中的所有 \(1\)。\(n,m\le 1000\)
题解¶
枚举三个矩阵那两个矩阵的最左上的 \(1\) 对齐即可，判断相同可以 \(hash\) 判断。
L¶
upsolved by
题意¶
题解¶
M¶
upsolved by 2sozx
题意¶
一个完全二叉树，每个点有个容量，每次会有一个点出现一个鼹鼠，问每次这个点和之前所有点的鼹鼠向有容量的点移动的最小距离和是多少。\(n \le 10^5\)
题解¶
显然是个费用流的模型，每次流量多 \(1\) ，考虑这是一个二叉树，树高只有 \(log\) ，因此可以模拟费用流，记录 \(f_x\) 表示从点 \(x\) 到子树的最短路径及到哪个点，因此暴力跳父亲取最优即可。
记录¶
0min：开局分题，没有啥太签到的，AH大模拟，CSK 冲 A
30min：冲F，被卡 long double ，WA1后AC，ZYF 冲 H
67min：H WA1后AC，继续冲A
72min：CSK AC，冲J
133min：ZYF AC，MJX ZYF想 E， CSK 想 K
?min：想不出来，换着想，CSK想出E
197min：ZYF AC，挂机
till end：MJX想了个大概的C，但是情况处理没想明白
after end：C最后思路就差一点，K题读错了
总结¶
Dirt¶
A(+1):多输出了一个空格
F(+1):卡精度，要long double，下次1e-9精度一定开long double
H(+1):