今天是韬神组织的一场考试，觉得题挺好的，就是数据……2333；
保证样例可以卡掉已知正确性错误算法,但不保证样例可以卡掉已知复杂度错误算法。
论题面的这玩意是什么鬼，那第一题dfs染色到底对不对呢；
保证所有数据在 Linux 下生成
这个还是很良心，支持diff了；
看题
协调：
总感觉，随便染一下就可以满足条件；
绿色：
emm，怎么又是种树啊；
好像真的又是贪心；
开放：
期望，听着劝退；
有什么办法的不枚举每一种方案解决啊；
等概率均匀随机生成一个 prufer 序列。并根据该序列生成一棵树
这个提示的用处是什么呢？
共享：
极长上升子序列？最长上升子序列？DP？
极长上升子序列的第一个数前面一定没有比它小的数；
极长上升子序列的最后一个数后面一定没有比它大的数；
设(f_{i,j})为以(i)结尾长度为(j)的上升子序列的个数；
(i)转移到(k)必须要两者之间没有位于(a_i)和(a_k)之间的数；
(n^3)可以有45pts，还有(∀i, f (i) = 1)的10pts，先写这题吧；
所以今天会是cy难度吗？
写题
共享：
| 期望时间 | 实际时间 |
|---|---|
| (40min) | (60min) |
| 期望得分 | 实际得分 |
|---|---|
| ([55,100]pts) | (85pts) |
先(n^2)预处理哪些可以转移到下一个，然后写了一个(n^3)的DP；
小样例过了，大样例却WA了，思考了半天，确认自己的思路没问题，后来发现是取模不到位；
感觉(n=3500)过的有点慢，试着卡了卡转移的上界，减少一些无意义的转移；
现在比较稳定了，应该不是很好卡，手造了极限随机数据，感觉还行；
(after test.)
(70pts)，还可以；
等等，为什么记忆化搜索过了？为什么暴搜也过了？！
然后在我们上英语课时，韬神，思齐等人齐心协力对着代码卡把记忆化搜索卡到了(70pts)，把爆搜卡到了$ 20pts$；
韬神：竟然放过了指数级暴力，我很抱歉；
但是我升到了85pts
协调：
| 期望时间 | 实际时间 |
|---|---|
| (30min) | (30min) |
| 期望得分 | 实际得分 |
|---|---|
| (20pts+) | (100pts) |
保险起见，先写一个(20pts)的暴力；
然后选择写(bfs)染色；
样例能过，但是样例好小，不放心；
算了，应该没问题吧；
距离下考还有(15min)，我用一个四个点的完全图hack了自己；
光速写了一个新的染色方法，看运气了；
(after test.)
噢，被我自己hack的bfs染色有90pts；
本来韬神发现有这么多人过，想要大家都讲讲做法，结果惊恐发现都是乱搞
绿色：
| 期望时间 | 实际时间 |
|---|---|
| (80min) | (100min) |
| 期望得分 | 实际得分 |
|---|---|
| (20pts) | (0pts) |
因为感觉第三题不是很可做的样子，有感觉这题是贪心所以决定多花点时间想想这一题；
第一小肯定是所有的负数加起来；
然后可以把负数取反，那样就都是往里面加数了；
但是怎么保证加数的单调性和方案不重复呢，是不是要排序；以上都是正解思路
好像并不可行；然后就这样没了！！！其实只要想清楚更新方法，来解决单调性的问题就好了，所以现在想来好难过
断了上面的思路后思考不出其他了，最后只能暴力收场；期间收获cy惊吓×1
(end.)
开放：
| 期望时间 | 实际时间 |
|---|---|
| (20min) | (20min) |
| 期望得分 | 实际得分 |
|---|---|
| (20pts) | (0pts) |
(O(n!))枚举方案，模拟题意；
(end.)
总结
-
第四题DP剪枝写的不错，用不容易出错的代码拿到了比较不错的分数；
-
终于是碰到了一道结论题，遗憾的是并没有发现这个结论，不过好在最后15min自己hack自己后没有放弃，还写了另一种染色方法，最后还是通过了；
-
第二题挺可惜的，几乎要想到正解了，也许以后把思路写下来会更好，因为一些想法有时候是直觉，零零散散容易忘记脑海中出现过这个思路，可能整理在一起会更容易想出怎么做；
-
犯了两个低级错误，开小数组和有部分运算没有取模，导致丢了40pts的暴力分；