早上大概7点左右起床

然后...

7点45左右到的考场

8点进考场,前面各种试机啥的乱七八糟的

到8:15发题目

------------

T1

给你一个直线n个点,每个点有个高度h_i

你要对每个点求出最小的整数p,所有的j都要满足

h_j<=h_i+p-sqrt(|i-j|)

30%数据n<=1000

60%数据n<=30000

100%数据n<=100000,h_i<=10⁹

T2

R是一个二进制数,它是一个母串S重复k次得到

(例如S="101",k=2,则R="101101")

求0~R-1中找N个数,使得它们异或和为0的方案数

Test Data 1: N=3 |S|=10 k记不得了

Test Data 2: N=3 |S|<=50 k<=100000 (k记不得了)

Test Data 3,4,5: N=5 |S|<=50 k<=100000

Test Data 6: N=4 |S|<=50 k=20

Test Data 7,8,9,10: 3<=N<=7 |S|<=50 k<=100000

T3

给你n个建筑物和m个小怪的坐标

你要放一个炸弹,炸弹的半径不能超过R(允许自定义)

要求炸弹不能炸到任何一个建筑物但要炸尽量多的小怪

建筑物是半径为r_i的圆,相切不算炸到;小怪是点,边界上的算炸死

只求最多能炸掉几个小怪

20% N=0

20% M=2

20% M<=50

100% N<=10 M<=1000 R<=20000 所有坐标都在[-20000,20000]之内

所有点都是整数点

=================================

9:30左右 AC掉t1

大概去Linux下编译了下..

CE!

sort未定义!差点这100分炸了

(事实上是我忘了写#include<algorithm>了)

之后一直在做t2,然而不会做..

后来t2找了个规律啥的..

..反正N=3似乎过了

t3随机

考场上觉得自己没戏了

出来成绩

100 + 10 + 10 = 120

似乎waltz和NFLS神犇团都比我高

....

没救了

再这样要退役了

求R2D2翻盘

另外这轮似乎理论上是R1只是习惯叫做R2而已

===========================

t1题解:

我们注意到|i-j|取过根号后的数值最多就400

sort,求前400个高度数值(注意不是前400个高度)(所以两个1e9只算一个数值)

求出每个高度的最左端和最右端的位置

每个点暴力对这400个左右端点套一次公式即可,求出max

复杂度O(n sqrt(n)) 跑随机数据0.5s