2016-2017 ACM-ICPC, NEERC, Southern Subregional Contest¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 31/? | 9 | 10 | 12 |
A¶
solved by 2sozx
题意¶
给 \(n\) 个数 \((2 \le n \le 100)\)，每次可以选择 \(2 \sim 5\) 个数将值减一，值不会小于零，最后要求所有数相等。求一种操作方案使得最后的数最大。
题解¶
每次操作看最大值的个数，如果等于 \(n\) 直接结束。否则判断奇偶性，如果是偶数选择其中两个减一，否则判断最大值是否大于一。如果大于一则选择三个减一，否则找到次大值与最大值一起减一即可。
B¶
solved by 2sozx
题意¶
给 \(n\) 个数，请在比较次数不超过 \(\lceil \frac{3 * n}{2} \rceil - 2\) 下找到序列的最大值和最小值。
题解¶
考虑两两比较出最大值和最小值，按照线段树的方式从子节点向上合并，总共比较次数正好是上限。
C¶
solved by 2sozx
题意¶
题解¶
D¶
solved by JJLeo
题意¶
贪心题。
题解¶
贪就完了。
E¶
upsolved by
题意¶
题解¶
F¶
upsolved by JJLeo
题意¶
巨毒瘤的买东西送券类题目。
题解¶
不理解为什么复杂度明显不对的算法能过，可能是我算错了（x
等什么时候有时间算对了再把题解补上吧。
G¶
upsolved by
题意¶
题解¶
H¶
upsolved by
题意¶
题解¶
I¶
solved by JJLeo
题意¶
费用流裸题。
题解¶
冲就完了。
J¶
solved by JJLeo
题意¶
背包裸题。
题解¶
冲就完了。
K¶
upsolved by JJLeo
*本题题意和题解来自叉姐 wiki。
题意¶
给你一个无向图和其中两个点\(s\), \(t\). 要求你将这个无向图定向成一个从\(s\)到\(t\)的格(定义: \(s\)是唯一的入度为0的点, \(t\)是唯一的出度为0的点, 且整个图无环).
题解¶
首先我们有一个无视时限的做法. 先把\(s\)到\(t\)连起来, 这条链从\(s\)到\(t\)定向. 然后每次找从链上出去再回来的一条路径, 按照出去和回来的点在链上的先后给他们定向. 但是为了不超时, 需要实现这个做法. 方法是从\(s\)开始做个dfs树. 这棵树上有一些返祖边, 还有点\(t\). 我们考虑下面一个递推过程: 首先置\(t\)于队列中, 并标记\(t\)为"沿树向上". 每次取队列中任意元素\(v\), 如果\(v\)到\(v\)的父亲之间的边没有定向, 就照\(v\)上面的标记来定向, 同时把\(v\)赋值为\(v\)的父亲, 标记不变. 在这个过程中, 如果对一条边\((father[v], v)\)定向, 并且存在一条以\(father[v]\)为祖先, 以\(v\)的某个后代\(u\)为后代的返祖边\((father[v],u)\), 就将这条边按照\((father[v], v)\)的相同方向定向, 同时将\(u\)标记为\(v\)相反标记(沿树向上<->沿树向下), 将\(u\)插入队列中. 这个过程能正确的定向所有边(当有解的时候. 无解的判断法是, 有条边在递推过程结束后还没有被染色. 这说明有无法走到\(t\)的死路.). 因为在这个过程中, 如果\((father[v], v)\)被定向为\(father[v]->v\), 那么从\(v\)的任意子孙无法走到\(father[v]\), 对称地, 如果\((father[v], v)\)被定向为\(v->father[v]\), 那么\(v\)无法走到\(v\)的任意子孙(除了\(v\)自己). 这个可以循环不变式证明.
L¶
upsolved by
题意¶
题解¶
记录¶
0min：分题，CSK冲G
13min：CSK WA，MJX冲A
20min：CSK 找到bug AC,MJX AC，CSK 冲H
34min：CSK WA2，ZYF冲J
36min：ZYF AC，CSK继续冲H
46min：CSK AC，MJX 冲B
51min：MJX挂一次后AC,ZYF 冲I
64min：ZYF AC，MJX 冲C
96min：MJX WA3，ZYF 冲D
119min：ZYF WA，CSK 冲E
138min：CSK AC，ZYF AC，MJX 继续冲C
152min：MJX AC,一起冲K
till end：冲不动了
总结¶
- MJX：求求BFS好好学学吧，太蠢了太蠢了，好几次了，还要注意审题
- ZYF：背包写慢了，贪心写裂开了，要加强练习。