Difference between revisions of "ACM-ICPC 2017 Asia Tsukuba Regional"

From EOJ Wiki
Jump to navigation Jump to search
 
(6 intermediate revisions by 2 users not shown)
Line 28: Line 28:
  
 
Unsolved.
 
Unsolved.
 
考虑二分答案,假设当前需要验证的答案为$x$,表示答案$≥x$是否成立
 
 
那么,根据最下面一行和$≥x$的关系,我们可以得到底层的$0/1$数列,$1$表示$≥x$
 
 
我们现在得到了底层的$0/1$数列,而题目所给的条件,上一层的一格为$1$,当且仅当下一层与之对应的三个中至少有两个$1$
 
 
现在,符合情况的话,那么就是顶层为$1$
 
 
我们可以画画图来分析一下底层的情况,如何向上传导
 
 
我们可以发现,当出现连续的两个$1$的时候,他们所对应的的上面,全部为$1$
 
 
[[File:Agc1.png|400px]]
 
 
那么,这样的情况如何向外拓展呢?
 
 
我们发现,当连续的两个$1$旁边出现隔着一个位置的$1$的是否,这个全是$1$的竖行,可以向着隔着一个位置的$1$的方向拓展一列
 
 
[[File:Agc2.png|400px|thumb|right|M-2]]
 
 
那么我们只需要正着反着,各扫一遍
 
 
这样一来,我们就可以在$O(2n)$的时间内验证答案了
 
 
还有一种比较特殊的情况是,底层不需要出现连续的两个$1$
 
 
[[File:Agc3.png|400px|thumb|right|M-3]]
 
 
特判一下
 
 
总的时间复杂度是$O(3n*logn)$
 
  
 
== Problem E ==
 
== Problem E ==
Line 77: Line 45:
 
== Problem F ==
 
== Problem F ==
  
Unsolved.
+
Upsolved by dream_cloud & oxx1108
 +
 
 +
题意:给一个有向图,每次反转一条边(不叠加!),询问 S 到 T 最短路径是变短的还是变长了还是不变。
 +
 
 +
题解:分别从S和T出发做两次最短路。对于变长还是变短分情况讨。将一条u到v的边反向,变短的情况只有$ds[v]+w+dt[u]< ans$。变长的情况时,从S到T的最短路中如果去掉某条边之后S到T的最短路长度改变,也就是找出从S到T所有最短路,图另外取出来之后,也就是求这个子图的桥。剩下的就是不变的情况。
  
 
== Problem G ==
 
== Problem G ==
Line 90: Line 62:
 
== Problem H ==
 
== Problem H ==
  
Unsolved.
+
Upsolved by oxx1108.
 +
 
 +
题意:有两种作业,每种作业有一个完成区间,必须在这个区间完成,每天可以选择一种作业完成deadline最早的作业(如果没有就skip),问最多最少分别能做多少作业。
 +
 
 +
题解:网络流建图,最大很直接的就是二分图跑一下就行,最小的将所有第一类作业与起点连,第二类作业与终点连,然后都和中间的时间连,由于要限制每天只能完成一个作业,时间还要拆点。正确性在于是求最小割,最终的每条流无论选那一类作业都可以完成。
  
 
== Problem I ==
 
== Problem I ==
Line 182: Line 158:
 
题解:只要从源和终点分别预处理一遍最短路,就可以很快地处理变短了的情况:ds[v] + w + dt[u] < presumed。下面需要判断变长了还是不变。变长了的话可以证明删掉的这条边一定是在最短路的骨干道路上的。也就是说要走当前的最短路非走这条边不可。可以先把骨干网络求出来(用 ds[u] + w + dt[v] ?= presumed 判断边是否在骨干网络上),然后骨干网络一定是一个 DAG,问题转化成求 DAG 的桥。
 
题解:只要从源和终点分别预处理一遍最短路,就可以很快地处理变短了的情况:ds[v] + w + dt[u] < presumed。下面需要判断变长了还是不变。变长了的话可以证明删掉的这条边一定是在最短路的骨干道路上的。也就是说要走当前的最短路非走这条边不可。可以先把骨干网络求出来(用 ds[u] + w + dt[v] ?= presumed 判断边是否在骨干网络上),然后骨干网络一定是一个 DAG,问题转化成求 DAG 的桥。
  
我的做法是这样子的(参考毛子的某道题,当时好像是 kblack 提出的):拓补排序之后遍历点,维护一个计数器。对于每个点,计数器减去入度加上出度。如果计数器当前值为 1,那么可以断言出度为 1,而且这条出边是一个桥。证明的话努力感受一下就好了。
+
我的做法是这样子的(参考毛子的某道题,当时好像是 kblack 提出的):拓扑排序之后遍历点,维护一个计数器。对于每个点,计数器减去入度加上出度。如果计数器当前值为 1,那么可以断言出度为 1,而且这条出边是一个桥。证明的话努力感受一下就好了。
  
 
由于有重边,存边的时候加一个 id 字段会方便一点。
 
由于有重边,存边的时候加一个 id 字段会方便一点。

Latest revision as of 16:10, 13 October 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

Upsolved by dream_cloud & oxx1108

题意:给一个有向图,每次反转一条边(不叠加!),询问 S 到 T 最短路径是变短的还是变长了还是不变。

题解:分别从S和T出发做两次最短路。对于变长还是变短分情况讨。将一条u到v的边反向,变短的情况只有$ds[v]+w+dt[u]< ans$。变长的情况时,从S到T的最短路中如果去掉某条边之后S到T的最短路长度改变,也就是找出从S到T所有最短路,图另外取出来之后,也就是求这个子图的桥。剩下的就是不变的情况。

Problem G

Solved by oxx1108. 04:56:50(+1)

题意:两个蚂蚁在四面体上爬,求爬了一定长度后是否在同一个面上。

题解:展成面即可,化成60度坐标系,然后找到对应的正三角形位置算出属于哪个三角形(可以参数方程转换成直角坐标简单一些?)。 时间不够了,没想清楚就上了,写得非常丑,分了八个if……

Problem H

Upsolved by oxx1108.

题意:有两种作业,每种作业有一个完成区间,必须在这个区间完成,每天可以选择一种作业完成deadline最早的作业(如果没有就skip),问最多最少分别能做多少作业。

题解:网络流建图,最大很直接的就是二分图跑一下就行,最小的将所有第一类作业与起点连,第二类作业与终点连,然后都和中间的时间连,由于要限制每天只能完成一个作业,时间还要拆点。正确性在于是求最小割,最终的每条流无论选那一类作业都可以完成。

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,也就是有每组相等的点有唯一的根,那么剩下的事情就简单了,将所有规定和询问的位置都规约到最左的位置,看看是否有规定即可。

Problem K