20160502之吐槽=。=

额,今天下雨了。

嗯……白天下了一天,晚上就停了。

今天是CTSC2016 Day1。早上起来吃了点包子(原因是被昨天食堂吓出后遗症了。然而事实上也许是昨天有人抗议了(?)今天中午和晚上的食堂都相当不错,有好多牛肉盖饭啊,炸鸡饭啊,包子,披萨和意大利面啥的,不同的窗口都不一样。)然后就步行前往考场。接下来说题。

T1:时空旅行

(此题时间5秒,内存1G,20个点)

题目ryz出的,描述起来相当复杂。

就是说小R现在要去时空旅行,他要前往s时空的(x, y, z)坐标处并对某个星球进行考察。他可以自由选择目标地点的y坐标和z坐标,然而目标时空s和x坐标是给定的。去一次的花费是目标地点和待考察星球的欧几里得距离d的平方加上对该星球进行考察的费用c(给定)。

这些时空都是怎么来的呢,是发展来的。一开始我们在0号时空,此时我们只有地球一个星球(坐标为0, 0, 0,费用给定),接下来有n-1个操作分别得到其他的n-1个时空,每次操作可以从之前的某个时空增加或删除一个星球得到。

对于每次考察,求最小费用。

输入第一行为3个整数n, m, c0,代表有n个时空,m次询问,在地球进行考察的费用为c0。 \((0 < n,m \le 5 \times {10^5}, \, 0 \le {c_0} \le 10^{12})\)

接下来n-1行代表时空1到n-1,对于每一行有以下两种情况:

0 fr id x y z c:表示当前时空在fr的基础上增加了id号星球,其坐标为(x, y, z),花费为c \((0 < id < n, \, |x|, |y|, |z| \le {10^6}, \, 0 \le c \le 10^{12})\)

1 fr id:表示当前时空在fr的基础上删除了id号星球。

接下来m行每行包括两个整数s, x表示一次询问,就是要去s号时空并且x坐标为x。

输出m行,每行一个整数代表最小花费。


有一个点是n和m都小于等于100的直接暴力解决。还有20分保证所有询问的x一定,于是我就搞了个可持久化线段树水了一发,合计25分。

下午讲题听标算大概是搞出一个一次函数关系,然后用平衡树维护一下凸包,还要把询问排序然后分治处理……总之相当麻烦,然而还有共计14位大神获得了AC。

T2:萨菲克斯·阿瑞

(此题7秒,20个点)

这题是杜教出的,全场最高分60,没有AC。

题目只有一句话,求由m种字符构成,长度为n,第i个字符出现次数不超过 \({c_i}\) 的字符串后缀数组有多少种。

答案对1e9+7取模。

输入第一行为两个整数n, m \((n, m \le 500)\)

第二行为m个整数,第i个表示 \({c_i}(0 \le {c_i} \le n, \sum{c_i} \ge n)\)

输出一个整数,表示答案。

第一个点n,m小于等于6,直接暴力枚举字符串,得了5分。

不过后来听讲题接下来的两个点(n, m小于等于10)可以枚举后缀数组判断可不可行,然而我没想出来QAQ。

标算是弄一些奇怪的组合数还有容斥原理乱七八糟的一堆。反正得高分的集体找规律=。=

T3:NOIP10合1

这是一道提交答案题(picks出的)。

给定有n个点m条边的有向图,求u到v的权值和恰好为w的路径有多少条,结果对p取模。

多组询问。

第一个点直接推组合数就可以解决,不过暴力推会挂空间(50000*50000),因此我用了一些奇怪的滚动数组技巧(然而最后100000个询问我过了99999个……就得了9分,不知道是循环写错了还是咋的)。

第二个点和第三个点是个完全背包问题,然而我没看出来,跑了跑暴力加上骗分啥的,合计8分。

后面就是奇怪的矩阵问题了,又是特征多项式什么乱七八糟的完全听不懂……

(值得注意的是后面给了一个良心点固输0给4分!于是我合计21分)

(顺便一提复测延迟了30min,不知道评测出了啥问题(叫你出5秒7秒还都20个点))


然后就是吃晚饭,就回来了。总之今天考的还算可以吧,明天没考试,后天加油~

20160502

Yukimai

(^=。=^)

发表评论