今年

真的不知道能不能考好

信仰

支持我进省队吧

不想就此退役呢

最后一次机会,狠狠拼一把

也算--

对得起金中河西的初赛名额呢

(不然的话,就真的已经OI再见了啊...)

来谈谈今天的题目吧

t1:

给你一个树(森林)有n个点,每个节点有一个花费s_i和一个贡献p_i

你要选k个点,保证如果x选了那么x的父亲r_i(r_i<i)也必须选(r为0表示没有父亲)

给定所有的s,p,r,求出Σp/Σs的最大值(必须选k个点,保留三位小数)

30%数据 n<=20

50%数据 n<=100

100%数据 n<=2500,s_i,p_i<=10000,0<=r_i<i

t2:

给你两颗树,第二颗树是第一颗上加了一个叶子

求这个叶子是哪个,如果有多个输出在第二颗上的最小的编号

10%数据 n<=8

30%数据 n<=200

60%的数据 n<=2000

100%的数据 n<=100000

t3:

给你俩等长的字符串,长度为N

我们定义,f(i,j,k)表示第一个字符串的第i到j个字符拼接而成的字符串接上第二个字符串第j到第k个字符拼接而成的字符串

例如

A="ABCDE"

B="DAEBC"

那么f(2,3,5)就是"BCEBC"

要求出所有f中最大的回文字符串的长度

PS:i<=j<=k

再PS:如果A或B中包含一个回文,那么我们也可以将它计入答案,也就是说如果

A="ABCBA"

B="DEFGH"

我们可以输出5,因为A是个回文串..也就是说,输出max(A中最大回文串,B中最大回文串,AB拼接出来的最大回文串)

10% N<=10

30% N<=200

50% N<=2000

100% N<=100000

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

考试开始的时候,感觉t1的30分反正要写,就写了

一直感觉t3的题意不明白啊..是不是A中取第一个B取全部就能达到n+1的最大值了啊(我以为A或者B中是回文串,或者总和是就行..)

然后问了两遍,第二次善良的老师解释给我了题意..

接下来始终不会t1所以t2,t3来回切题看,t2想到了一个hash,感觉能拿60分

我们考虑每个点,那么它周边的所有点有一个度数

我们计算每个点周边的度数平方的和,然后作为它的hash值

暴力删叶子,排序..

均摊复杂度O(n^2 log n),理论可过60分

当然hash被卡就滚粗了

t3想到了一个错误的解法

等于是给你一个长度为n+1的字符串,每次更新一个点,从第2个到第n个,每次求整个字符串的最大长度

大概双hash一下单调队列

后来发现不对..

假设某个点x为开始可以无限扩展,答案是n+1,那么在出现这一个答案的刹那,可能还有个点比它的上一次的答案要大而扩展性很弱,所以排在单调队列的前端..

还有个2个半小时,看着90分,决定冲一发190分

感谢@Ahdoc 教我如何用hash判断回文..

然后..

想到一个解法

每个点为中心,二分它能跑多远,然后把另一个数组停在相应位置匹配上,再二分看到底能跑多远..

可以证明这是对的,因为在那个点之外匹配的话答案就已经锁定那么小了,如果在那个点之内匹配的话答案不会增大

这样的话,我拍对以后还有半小时

测了个大数据,3s...

卡常数mode开启!

最后卡到考试结束还是1.05s左右感觉要跪啊..好多hash函数都被我强行手动inline了感觉好233....

不管了

出了考场,刷了2小时的兰因璧月..回去看分数

发现..

20 + 30 + 100!

t3给过了好评,突然发现我提出题目有问题的题目都给AC了呢[NOIP 斗地主;JSOI R2 D1T1;JSOI R3 D1T3]

t1的数据只给了20差评,我们几个集体去找出题组..

要回10分..

30 + 30 + 100 = 160

居然比waltz高

waltz:

0 + 50 + 100 = 150(waltz:论t1乱弄常数优化的危害性..)

据说有人AK了呢

希望后天能翻盘啊...