Difference between revisions of "ACM-ICPC 2017 Asia Tsukuba Regional"
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
| Line 28: | Line 28: | ||
Unsolved. | Unsolved. | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== Problem E == | == Problem E == | ||
Revision as of 11:11, 26 September 2018
One,Two,Three,AK
中后期上机时间严重不足，卡题过多，稳定性不够。
Problem A
Solved by Xiejiadong. 00:09:42(+)
煞笔dp，温暖的签到。
Problem B
Solved by oxx1108. 00:35:42(+)
题意：把 $m$ 个点两两匹配成 $m/2$ 条直线，然后求最多的平行线对数。
题解：暴力dfs匹配。
Problem C
Solved by oxx1108. 00:58:09(+)
题意：非常类似于 CPU 中的流水线。每条指令在每个阶段的用时只跟指令有关，不跟阶段有关。求某个时间点各个指令都在第几个阶段（或在等待第几个阶段）。
题解：算出每个东西进入流水线的时间(注意要减掉之前出现的最长的一个零件时间，因为在等待做下一个的时间也算下一个了)，和流水线之后每个周期的时间，然后就可以算出答案了。
Problem D
Unsolved.
Problem E
Solved by Xiejiadong. 03:00:39(+1)
题意：每次修改是把一整段变成同一个颜色，求最少多少次可以变成目标状态。
题解：如果把某一整段修改的话，显然剩下的就是把中间不一样的一段一段改。
那么，显然，整段的喷涂是不连续的一段一段组成的，我们可以用dp解决。
用$f[i]$表示，喷涂到第$i$位的最小代价，那么$f[i]=min{f[j]+cost(j+1,i)}+1$，当$a[i]=b[i]$时，$f[i]=f[i-1]$
$cost(j+1,i)$可以用前缀和解决，然后用单调队列维护dp，时间复杂度$O(n)$。
Problem F
Unsolved.
Problem G
Solved by oxx1108. 04:56:50(+1)
题意：两个蚂蚁在四面体上爬，求爬了一定长度后是否在同一个面上。
题解：展成面即可，化成60度坐标系，然后找到对应的正三角形位置算出属于哪个三角形（可以参数方程转换成直角坐标简单一些？）。 时间不够了，没想清楚就上了，写得非常丑，分了八个if……
Problem H
Unsolved.
Problem I
dreamcloud 和 oxx1108 读漏了关键信息，导致了卡题。
Solved by Xiejiadong. 03:22:13(+3)
题意：两种方案买票，求最少需要的作为数量。
第一种方案是：不给定顺序，每个人不会买别人做过位置的票，求最坏情况下需要的座位数量。
第二种方案是：认为的安排座位。
题解：第二种方案，显然是求某一个时刻最多的人数。
第一个方案，可以转化成求那个人所要买的那个区间会有多少人，那么这个人需要的座位数量就是那个区间的人数$+1$。
上面两部分都可以用前缀和搞一搞。
Problem J
Unsolved.
Problem K
Upsolved by oxx1108.
最后时间不够了，把一个等号敲成了不等号，没多少时间debug（还有个G等着做）。算法很快就想出来了，但是等到能上机的时候已经没剩多久了。不过由于在机下想了很久，所以细节想得很清楚，上机敲得非常快。
题意：给一个稀疏联通无向图，找其中有几个简单环。
题解：因为稀疏图，把度数1和2的点缩掉，之后图就很小，然后暴力dfs找所有简单环。
注意几个细节：
1、先把度数为1的点都缩掉，类似拓扑排序，这样之后就不会再出现度数为1的点了。
2、然后缩度数为2的点，为了避免自环和重边，当该点连的两条边之间有边时（三元环）就不缩了，这样虽然会导致结点数多一些，但是最后图的规模不会超过50个点（16个三元环）。
3、dfs时候我采取的是对每条边暴力找含这条边的环，具体方法就是把这条边删了然后从i开始dfs找到j。然后把这条边从图里删掉接着搜下一条边。这样好处是一定不会算重少算，就算时间复杂度不能够得到严格证明，当然最后跑出来只有7ms。因该有别的找环方法。
ECNU Foreigners
ultmaster: 签到成功！kblack 再次扛起重任，拿下全场贡献最佳奖。
Problem A
Solved by zerol. 00:12 (+)
温暖的签到。
Problem B
Solved by ultmaster. 01:26 (+)
题意：把 $m$ 个点两两匹配成 $m/2$ 条直线，然后求最多的平行线对数。
题解：可能划分的数量大概只有 2E6。巧妙地把这些方案枚举出来了以后，逐一计算就可以了。
因为没有输出答案，错误地把 debug 信息当成了答案。自闭半小时。
Problem C
Solved by ultmaster. 00:38 (+1)
题意：非常类似于 CPU 中的流水线。每条指令在每个阶段的用时只跟指令有关，不跟阶段有关。求某个时间点各个指令都在第几个阶段（或在等待第几个阶段）。
题解：暴力算出每个东西进入流水线的时间。然后进入流水线之后每个周期的时间，是跟之前进入流水线的所有指令所需要的时钟周期的最大值有关的。至于如何判断是否已经结束是否在等待，大概只要模一下算一算就好了。同时要考虑到进入第一个阶段之前的情况（要先判断）。
Problem D
Problem E
Upsolved by ultmaster.
题意：把一个 01 串刷成另一个 01 串，每次只能把连续不超过 $k$ 的一段修改成一段 0 或一段 1。求最少次数。
题解：基本照抄题解。$\displaystyle f(x) = \lceil \frac{\min_{x-k \le i \le x-1} (2f(i)-b(i+1)) + b(x) + 2}{2} \rceil$。
其中 $b(i)$ 是 $0...i$ 的目标串有多少个变化点。前面一段用单调上升队列维护一下就好了。复杂度是 $\mathcal{O} (n)$。
Problem F
ultmaster: 题目读错背大锅。而且可能顺带抹杀了做出其他题的可能性。读成了叠加的，然后就一直思考给的那些条件有什么性质（其实如果不叠加的话一切都说得通了）。三个人都读了题，然而队友都先入为主了，等于我责任重大。
Upsolved by ultmaster.
题意：给一个有向图，每次反转一条边（不叠加！），询问 $S$ 到 $T$ 最短路径是变短的还是变长了还是不变。
题解：只要从源和终点分别预处理一遍最短路，就可以很快地处理变短了的情况：ds[v] + w + dt[u] < presumed。下面需要判断变长了还是不变。变长了的话可以证明删掉的这条边一定是在最短路的骨干道路上的。也就是说要走当前的最短路非走这条边不可。可以先把骨干网络求出来（用 ds[u] + w + dt[v] ?= presumed 判断边是否在骨干网络上），然后骨干网络一定是一个 DAG，问题转化成求 DAG 的桥。
我的做法是这样子的（参考毛子的某道题，当时好像是 kblack 提出的）：拓补排序之后遍历点，维护一个计数器。对于每个点，计数器减去入度加上出度。如果计数器当前值为 1，那么可以断言出度为 1，而且这条出边是一个桥。证明的话努力感受一下就好了。
由于有重边，存边的时候加一个 id 字段会方便一点。
Problem G
Solved by kblack. 02:28 (+)
题意：两个点四面体上走直线，问最后是否在同一个面。
题解：铺平以后相当于算在那个正三角形，大力讨论就好了。
Problem H
Problem I
Solved by kblack. 01:28 (+1)
题意：火车上区间占座，按自由选择和系统分配，分别最少需要准备多少个位置。
题解：系统分配贪心即可，自由选择的话最大最少需要，与任意区间有交的数量 $+1$ 座位，可以保证这样也是足够。
Problem J
Solved by kblack. 03:33 (+)
题意：告诉你一个字符串若干组相等的子串，规定一些字符，问一些字符能否推出。
题解：注意到输入的区间十分特殊，将相等关系看作右向左的有向边后，每个点出度最多 1，也就是有每组相等的点有唯一的根，那么剩下的事情就简单了，将所有规定和询问的位置都规约到最左的位置，看看是否有规定即可。