20160504之吐槽=。=

今天就滚粗了=。=喵

今天是CTSC2016 Day2。

直接说题吧。

T1:单调上升路径

给一个n个点( \(2 \le n \le 500\) ,且n为偶数)的完全无向图,要求给每条边分配一个1到 \(\frac{n(n-1)}{2}\) 的权值,使得这个图最长的单调上升路径最短。

所谓单调上升路径就是从一个点出发可以重复的经过任何点然后到达一个点,使得经过的边权值按顺序排列是单调递增的。

输入一行一个整数n。

输出 \(\frac{n(n-1)}{2}\) 个整数,按顺序代表每条边(一个三角矩阵)

这题由于是偶数所以正解还比较简单(至少我听懂了=。=然而要想出来还是算了),就是我们不断地找不同的完美匹配,然后按顺序分配这些个边就可以了。至于怎么找不同的完美匹配需要构造一个奇怪的啥啥矩阵好像也挺好构造的=。=

这道题非常良心的地方有三点,第一点就是给了一个附加数据把n在100以内的奇怪矩阵全部构造出来了=。=然而我并没有看出来,第二点是在题目里给了一个证明,告诉我们这个路径长度下界是n-1,并且给出了在O(mlogm)时间内求出一个路径长度的算法(然而我也没看出来=。=),第三点是给了一个部分分,这样只要一直按顺序输出1到m也能得30分(每个点3分),(然而我依然没看出来)。最后我交了一个随机输出的算法,得了6分QAQ。

T2:香山的树

给定一个长度n(<=50),一个数k(<=1e15),和一个初始字符串s,求从s开始第k小(s是第一小)的长度小于等于n的严格循环最小字符串。

所谓严格循环最小字符串,就是我们把这个字符串循环移位,保证不能得到字典序大于等于原字符串的字符串。

如果没有这样的字符串,输出-1。

输入第一行为两个数n,k。

第二行为一个字符串s。

输出一行一个字符串,为目标字符串。

正解是奇奇怪怪的kmp数组dp加上什么奇怪的容斥原理直接统计数量,然而AC的大神是奇怪的暴力+乱搞,就水过了=。=我等蒟蒻只能%%%

反正我是直接从原字符串O(nk)的暴力递推过去的,过了k小于等于1e6的3个点,得30分

T3:科学考察队

这是一道提交答案题。

现在有个n个点m条边的有向图,有p个小队要从s点走到t点去,每条边有个边权w,如果w为正表示经过这条边会得到w的钱,如果w为负表示经过这条边会花w的钱,每条边还会有一个列表,列表中的小队不能通过这条边。

如果一个小队经过了这条边,第二个(或者是同一个)小队经过这条边时将不会得到钱(也不会花钱),求一个收益尽可能大的行动方案。

第一个点很小,直接手推,得10分。

第二个点是只有一个小队,然后图是强联通的,正解是乱搜=。=

三四五边的限制都是分组的,要不就是奇数偶数,或者%3得多少之类的分一下,然后正解好像是胡乱dp。

然后五六七还是啥的好像可以跑费用流。

八九十是越来越奇怪的网格图(8是常规的按顺序来的,9是胡乱顺序的,10是胡乱顺序+胡乱编号+胡乱抠点),好像用奇怪的dp可以解决。

然而以上2-10所有点都可以暴力跑spfa,有正环直接删边,跑过一条把边权全改成0,这么乱搞,我就随便每个点搞了一条路径,最后总分28,有个大神这么乱搞5小时然后得80分全场最高(我等蒟蒻仍然只能%%%)


于是我两天一共115,Ag线125于是就Cu滚粗了。

明天就是APIO2016Day0了,于是继续加油喵。

20160504

Yukimai

发表评论