Difference between revisions of "ACM-ICPC 2018 Qingdao Online Contest"

From EOJ Wiki
Jump to navigation Jump to search
 
(11 intermediate revisions by 4 users not shown)
Line 33: Line 33:
 
题意:$n \times m$ 的棋盘上,水彩笔涂了 $k$ 条不相交的线,求前 $i$ 行的黑块和黑联通块数量。
 
题意:$n \times m$ 的棋盘上,水彩笔涂了 $k$ 条不相交的线,求前 $i$ 行的黑块和黑联通块数量。
  
题解:将每条线记在左上角处,没对交点会在 “较低” 的线计算。这样就只需要记录上一行的横线和能影响到这两行的竖线,然后大力讨论接上的情况。讨论有点烦,不是特别好写,贡献不少罚时,浪费不少机时。
+
题解:将每条线记在左上角处,每对交点会在 “较低” 的线计算,可以证明这样交点数量是 $O(N)$ 的。这样就只需要记录上一行的横线和能影响到这两行的竖线,然后大力讨论接上的情况。讨论有点烦,不是特别好写,贡献不少罚时,浪费不少机时。
  
 
== Problem E ==
 
== Problem E ==
Line 39: Line 39:
 
== Problem F ==
 
== Problem F ==
  
Unsolved. 04:59 (-5)
+
Upsolved by ultmaster. 04:59 (-5)
 +
 
 +
题意:给一个 split graph,求最大团和最大独立集计数。
 +
 
 +
题解:首先要把 split graph 的团和独立集分出来。思路如下,把点按度数从大到小排序,然后把度数相等的点一批一批加进来。如果有一批不能完全加入,则至多只能加入一个点,而且后面的批次都不能加入了。证明如下:假设团的大小为 $k$,则团内点的度数 $\ge k-1$,团外点的度数 $\le k-1$。如果出现了第一批点(度数为 $d$)不能完全加进来,则至多只能加进来一个:因为 $d \ge k-1, d \le k-1$,所以 $d=k-1$,一旦加入一个 $k$ 就固定下来了。
 +
 
 +
分完以后就比较直观了。最大团计数初始有一个,然后枚举外面的点,一旦发现该点与团内 $n-1$ 个点相连,它就可以跟团内剩下的那个点换,计数加 1。最大独立集计数枚举团内的点,要看存不存在有一个点跟外面没有点相连,如果有独立集大小就是 $n-clique+1$,计数是团内不跟外面相连的点的个数;否则独立集大小是 $n-clique$,计数是团内跟外面只有一个点相连的点的个数 + 1。
 +
 
 +
实现的时候绝不要搞出 $n \sqrt {n}$,但有 log 是可以接受的。
 +
 
 +
ultmaster: 我把度数桶排了,结果度数为 0 的 vector 没清零。背锅。
  
 
== Problem G ==
 
== Problem G ==
Line 60: Line 70:
  
 
== Problem I ==
 
== Problem I ==
 +
 +
Upsolved by kblack.
 +
 +
题意:一个圆在 $(2r, 0)$ 以 $v$ 的速度向 $x$ 轴正方向运动,拿着另一个在 $(0, 0)$ 的圆,以不超过 $2v$ 的速度,用最快的方式将他移动到 $(d, 0)$。
 +
 +
题解:将运动的圆的半径放到 $2r$,这样变成自己的圆的点不进另一个圆中。最快的方式肯定是切着过去,切着过去的方程是 $2r\frac{d\theta}{dt} = v(\sqrt{3+\sin^2\theta}-\sin\theta)$,移项得 $\frac{2rd\theta}{v(\sqrt{3+\sin^2\theta}-\sin\theta)} = dt$,两边积分并移项可得 $\displaystyle \frac{2r}{v}\int_0^\phi{\frac{d\theta}{\sqrt{3+\sin^2\theta}-\sin\theta}} = t$,这样就可以通过切着走的角度 $\phi$ 计算时间了,这破玩意儿积不动的,只能自适应辛普森。接下来分两种情况,如果切着走完以后目标点已经被覆盖了,那么干脆以 $v$ 的速度跟着走会更快;否则需要切着走到 $\phi$ 然后直达目的地,这个溜走位置显然可以二分,算一通三角函数就好了。
 +
 +
kblack: 赛场上看错了题,虽然大部分点都想到了然后并没有卵用,甚至补题写了一个半小时怎么都调不对才发现这一点,这么看好像不怎么遗憾了呢。QAQQQ
  
 
== Problem J ==
 
== Problem J ==
Line 80: Line 98:
  
 
Solved by oxx1108. 00:10(+)
 
Solved by oxx1108. 00:10(+)
 +
 +
题意:签到
 +
 +
题解:签到
  
 
== Problem B ==
 
== Problem B ==
  
Unsolved.
+
Upsolved by dreamcloud.
 +
 
 +
题意:给一棵红黑树,定义红点代价为 0,黑节点代价为到最近的红节点祖先的距离。每次询问一个点集,允许修改一个黑节点为红节点,求点集中代价最大的节点的最小值。
 +
 
 +
题解:赛后过了好久,才惊奇地发现题意读错了,黑节点的代价读为了到最近的红节点的距离。尝试了上述的二分答案,果断超时。只需要对点集种的点按照代价从大到小排序,依次枚举前面的LCA。
 +
 
 +
Xiejiadong:题目读错了。题目复杂了好多。背锅。
  
 
== Problem C ==
 
== Problem C ==
  
 
Solved by Xiejiadong. 00:53(+1)
 
Solved by Xiejiadong. 00:53(+1)
 +
 +
题解:给一个程序,判断是否是死循环。
 +
 +
题解:死循环就是回到原来一个语句,且这个变量的值已经出现过。
 +
 +
直接暴力模拟。复杂度$O(n*256)$。
  
 
== Problem D ==
 
== Problem D ==
Line 118: Line 152:
  
 
Solved by dreamcloud. 00:48(+)
 
Solved by dreamcloud. 00:48(+)
 +
 +
题意:一条直线上有$n$个点,每相邻节点之间有红绿灯,每秒变换,走过两个相邻节点的时间也是1s,求所有点对的旅行代价之和。
 +
 +
题解:DP 一下就好了,枚举每个点奇时刻到底和偶时刻到达向后走总的旅游代价之和。
  
 
== Problem I ==
 
== Problem I ==
Line 126: Line 164:
  
 
Solved by oxx1108 && dreamcloud. 02:00(+5)
 
Solved by oxx1108 && dreamcloud. 02:00(+5)
 +
 +
题意:周期性按按钮,求亮着的情况按下的次数。
 +
 +
题解:周期 $a \times c$,周期只有 $a+c$ 个关键点,周期内乘系数再加上最后一段。边界没考虑清楚写自闭了……
  
 
== Problem K ==
 
== Problem K ==

Latest revision as of 00:27, 20 September 2018

ECNU Foreigners

代码

ultmaster: 题目比较。。正常的比赛。

Problem A

Solved by zerol. 00:12 (+)

温暖的签到。

Problem B

Solved by ultmaster. 02:14 (+)

题意:给一棵黑白树,定义白节点代价为 0,黑节点代价为到最近的白节点祖先的距离。每次询问一个点集,允许修改一个黑节点为白节点,求点集中代价最大的东西的最小值。

题解:二分答案,然后求超过答案的部分的 LCA。然后将这个点染白,检查超过答案的部分是不是被卡进答案范围内了。

Problem C

Solved by zerol. 00:35 (+)

题意:给一些指令,问是否有限步内结束。

题解:状态数很少,直接模拟,如果遇到重复状态就不停机了。

Problem D

Solved by kblack. 04:10 (+4)

题意:$n \times m$ 的棋盘上,水彩笔涂了 $k$ 条不相交的线,求前 $i$ 行的黑块和黑联通块数量。

题解:将每条线记在左上角处,每对交点会在 “较低” 的线计算,可以证明这样交点数量是 $O(N)$ 的。这样就只需要记录上一行的横线和能影响到这两行的竖线,然后大力讨论接上的情况。讨论有点烦,不是特别好写,贡献不少罚时,浪费不少机时。

Problem E

Problem F

Upsolved by ultmaster. 04:59 (-5)

题意:给一个 split graph,求最大团和最大独立集计数。

题解:首先要把 split graph 的团和独立集分出来。思路如下,把点按度数从大到小排序,然后把度数相等的点一批一批加进来。如果有一批不能完全加入,则至多只能加入一个点,而且后面的批次都不能加入了。证明如下:假设团的大小为 $k$,则团内点的度数 $\ge k-1$,团外点的度数 $\le k-1$。如果出现了第一批点(度数为 $d$)不能完全加进来,则至多只能加进来一个:因为 $d \ge k-1, d \le k-1$,所以 $d=k-1$,一旦加入一个 $k$ 就固定下来了。

分完以后就比较直观了。最大团计数初始有一个,然后枚举外面的点,一旦发现该点与团内 $n-1$ 个点相连,它就可以跟团内剩下的那个点换,计数加 1。最大独立集计数枚举团内的点,要看存不存在有一个点跟外面没有点相连,如果有独立集大小就是 $n-clique+1$,计数是团内不跟外面相连的点的个数;否则独立集大小是 $n-clique$,计数是团内跟外面只有一个点相连的点的个数 + 1。

实现的时候绝不要搞出 $n \sqrt {n}$,但有 log 是可以接受的。

ultmaster: 我把度数桶排了,结果度数为 0 的 vector 没清零。背锅。

Problem G

Solved by zerol. 02:50 (+)

题意:给一个数列,每次删除其中一个数,求出每一段的逆序对数量的最大值。强制在线。

题解:考虑新分裂出的两段,短的那段暴力计算,长的那段把短的那段以及删除掉的数的贡献从中扣除,复杂度 $O(n \log^2 n)$。

zerol: 自闭了近两小时,两度做成另一道题,所以根本过不了样例。背锅

Problem H

Solved by ultmaster. 00:55 (+)

题意:直线上红绿灯每秒变换,求所有点对的旅行代价。

题解:应该瞎 DP 一下就好了。奇偶搞错了自闭了好一会儿。

Problem I

Upsolved by kblack.

题意:一个圆在 $(2r, 0)$ 以 $v$ 的速度向 $x$ 轴正方向运动,拿着另一个在 $(0, 0)$ 的圆,以不超过 $2v$ 的速度,用最快的方式将他移动到 $(d, 0)$。

题解:将运动的圆的半径放到 $2r$,这样变成自己的圆的点不进另一个圆中。最快的方式肯定是切着过去,切着过去的方程是 $2r\frac{d\theta}{dt} = v(\sqrt{3+\sin^2\theta}-\sin\theta)$,移项得 $\frac{2rd\theta}{v(\sqrt{3+\sin^2\theta}-\sin\theta)} = dt$,两边积分并移项可得 $\displaystyle \frac{2r}{v}\int_0^\phi{\frac{d\theta}{\sqrt{3+\sin^2\theta}-\sin\theta}} = t$,这样就可以通过切着走的角度 $\phi$ 计算时间了,这破玩意儿积不动的,只能自适应辛普森。接下来分两种情况,如果切着走完以后目标点已经被覆盖了,那么干脆以 $v$ 的速度跟着走会更快;否则需要切着走到 $\phi$ 然后直达目的地,这个溜走位置显然可以二分,算一通三角函数就好了。

kblack: 赛场上看错了题,虽然大部分点都想到了然后并没有卵用,甚至补题写了一个半小时怎么都调不对才发现这一点,这么看好像不怎么遗憾了呢。QAQQQ

Problem J

Solved by kblack. 01:04 (+)

题意:周期性按按钮,求亮着的情况按下的次数。

题解:周期 $a \times c$,周期只有 $a+c$ 个关键点,周期内乘系数再加上最后一段。

Problem K

Solved by kblack. 00:14 (+)

温暖的签到。

One,Two,Three,AK

Problem A

Solved by oxx1108. 00:10(+)

题意:签到

题解:签到

Problem B

Upsolved by dreamcloud.

题意:给一棵红黑树,定义红点代价为 0,黑节点代价为到最近的红节点祖先的距离。每次询问一个点集,允许修改一个黑节点为红节点,求点集中代价最大的节点的最小值。

题解:赛后过了好久,才惊奇地发现题意读错了,黑节点的代价读为了到最近的红节点的距离。尝试了上述的二分答案,果断超时。只需要对点集种的点按照代价从大到小排序,依次枚举前面的LCA。

Xiejiadong:题目读错了。题目复杂了好多。背锅。

Problem C

Solved by Xiejiadong. 00:53(+1)

题解:给一个程序,判断是否是死循环。

题解:死循环就是回到原来一个语句,且这个变量的值已经出现过。

直接暴力模拟。复杂度$O(n*256)$。

Problem D

Unsolved.

Problem E

Unsolved.

Problem F

Unsolved.

Problem G

Solved by Xiejiadong. 03:21(+2)

题意:每次删除一个数,把序列分开,求每次删除以后每一段序列里面逆序对最多的数量是多少。

题解:每次都暴力的做。

用主席树预处理权值线段树。

枚举短的一段,暴力计算跨区间的逆序对数量,从这一段中分成两段,并减去。

口胡还是很轻松的。写起来巨恶心。还卡读入。

Problem H

Solved by dreamcloud. 00:48(+)

题意:一条直线上有$n$个点,每相邻节点之间有红绿灯,每秒变换,走过两个相邻节点的时间也是1s,求所有点对的旅行代价之和。

题解:DP 一下就好了,枚举每个点奇时刻到底和偶时刻到达向后走总的旅游代价之和。

Problem I

Unsolved.

Problem J

Solved by oxx1108 && dreamcloud. 02:00(+5)

题意:周期性按按钮,求亮着的情况按下的次数。

题解:周期 $a \times c$,周期只有 $a+c$ 个关键点,周期内乘系数再加上最后一段。边界没考虑清楚写自闭了……

Problem K

Solved by Xiejiadong. 00:15(+)

题意:签到。

题解:把二进制下位数相同的分为一组即可。统计组里最大的数量。