Difference between revisions of "ICPC Asia-Kharagpur Onsite Contest 2019"

From EOJ Wiki
Jump to navigation Jump to search
 
(6 intermediate revisions by the same user not shown)
Line 8: Line 8:
  
 
Solved by bingoier. 01:49 (+)
 
Solved by bingoier. 01:49 (+)
 +
 +
打表找规律题,发现小的往大的中间交错插入是最优的。
  
 
== Problem C ==
 
== Problem C ==
  
 
Solved by yanghong. 04:31 (+1)
 
Solved by yanghong. 04:31 (+1)
 +
 +
结论题, k>0 时删除两条边
  
 
== Problem D ==
 
== Problem D ==
Line 20: Line 24:
  
 
Solved by bingoier. 03:56 (+1)
 
Solved by bingoier. 03:56 (+1)
 +
 +
因为每种颜色之间相互独立,可以分开考虑。
 +
 +
维护每两个相同颜色之间的距离,一正一反做个FFT取大的一半即是对答案的贡献。
  
 
== Problem F ==
 
== Problem F ==
  
 
Solved by yanghong. 01:00 (+3)
 
Solved by yanghong. 01:00 (+3)
 +
 +
随机算法。 每次询问三个数, 有四种情况:
 +
 +
1. 0, 所以三个数全0, 则相当于只用一次询问就得到了三个数
 +
 +
2. 3, 三个数全1, 只用一次询问
 +
 +
3. 1,随机顺序询问三个数中的数, 期望2.5次得到三个数
 +
 +
4. 2, 期望2.5次得到三个数
 +
 +
总的期望询问次数少于90000次
  
 
== Problem G ==
 
== Problem G ==
Line 42: Line 62:
  
 
Solved by bingoier. 00:26 (+)
 
Solved by bingoier. 00:26 (+)
 +
 +
二分签到题。
  
 
== Problem K ==
 
== Problem K ==
  
 
Solved by yanghong. 01:13 (+1)
 
Solved by yanghong. 01:13 (+1)
 +
 +
负超几何分布
  
 
== Problem L ==
 
== Problem L ==

Latest revision as of 15:13, 19 October 2020

Problem A

Solved by Once. 00:21 (+)

可能碰撞的两个小球的速度和位置的乘积是相同的。用 set 维护之后枚举即可。

Problem B

Solved by bingoier. 01:49 (+)

打表找规律题,发现小的往大的中间交错插入是最优的。

Problem C

Solved by yanghong. 04:31 (+1)

结论题, k>0 时删除两条边

Problem D

Unsolved. (-3)

Problem E

Solved by bingoier. 03:56 (+1)

因为每种颜色之间相互独立,可以分开考虑。

维护每两个相同颜色之间的距离,一正一反做个FFT取大的一半即是对答案的贡献。

Problem F

Solved by yanghong. 01:00 (+3)

随机算法。 每次询问三个数, 有四种情况:

1. 0, 所以三个数全0, 则相当于只用一次询问就得到了三个数

2. 3, 三个数全1, 只用一次询问

3. 1,随机顺序询问三个数中的数, 期望2.5次得到三个数

4. 2, 期望2.5次得到三个数

总的期望询问次数少于90000次

Problem G

Solved by Once. 00:30 (+)

枚举坐不坐火车的情况,计算。

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Solved by bingoier. 00:26 (+)

二分签到题。

Problem K

Solved by yanghong. 01:13 (+1)

负超几何分布

Problem L

Solved by Once. 02:26 (+1)

二分答案,之后由于体积只有 2 和 1 的情况,所以可以贪心,先放体积为 2 的,再放体积为 1 的。