ACM/ICPC乌鲁木齐2017解题报告

两位队友的博客:

http://hzwer.com/

http://kuribohg.github.io/

BEH三题是我写的,其余题目鸣谢二位大腿。

A:Banana

开始样例错了。
代码:

B:Out-out control cars

题意:两个三角形匀速直线运动,问是否会撞上。

题解:只需单独计算每个三角形的某个顶点是否会和另一个三角形撞上,进一步地,只需要计算每个三角形的每个顶点是否与另一个三角形的每一条边撞上。方法就是计算一下相对速度(建立一个坐标系,相当于三角形静止,顶点匀速直线运动),然后问题转化为射线和线段相交,解二元一次方程组即可。

代码:

C:Coconut

代码:

D:Hack Portals

题意:数轴上有一堆点。你可以每秒走长度1,也可以静止。每个点有一个出现时间,你必须按任意顺序访问所有的点(在其出现之后),你一开始在0,最后回到坐标K,问最少需要多少秒。坐标均为整数,点数和坐标不超过1000,出现时间不超过32768.
题解:枚举一开始在0静止的时长。然后一定是:先走到没被访问的最右点,再走到没被访问的最左点……直到完成。该过程可以O(n)模拟,见代码。
代码:

E:Half-consecutive Numbers

题意:定义序列t[i]=i*(i+1)/2,每次给定一个n,问t序列第n项以后的第一个完全平方数是什么,n<=10^16。
题解:i和i+1/2互质,故要么i=n^2, i+1=2m^2,或者i=2m^2, i+1=n^2。枚举n,n不超过10^8,  打表。
代码:

F:Islands

题解:缩点之后,所有块的入度、出度取max。
代码:

G:Query on String

题意:给字符串S,T,T的长度不超过10.每次询问S[l..r]中有多少个T,或者改S的一位。

题解:先预处理一下,就变成了区间和查询。改S的一位至多影响10个值,用树状数组即可。
代码:

H:Skiing

题意:DAG最长路。DAG是题目保证的……
题解:随便写。我抄了个SPFA的板子。
代码:

I:Colored Graph

题意:给一张N个点完全图,求把每条边黑白染色,最少生成多少个纯色三角形。

代码:

J:Our Journey of Dalian Ends

题意:一张无向图,求从1走到N,必须经过K,每个节点至多经过一次的最短路。

题解:费用流。

代码:

发表评论

电子邮件地址不会被公开。 必填项已用*标注