2020.10.01考试解题报告

总结

预计得分： \(100 + 30 + 30 + 0 = 160\)

实际得分： \(20 + 30 + 30 = 80\)

小结：

过了一整年还是这么垃圾，说明这一年一点长进都没有

真是出师不利，还是怪自己太菜

第一次考试就做得挺炸的，

题目思路

比赛链接： http://csp.ac/contest/37/

T1

手模发现当且仅当皮蛋先手且皮蛋拿着最大的数时皮蛋获胜。

注意要特判 \(n=2\) 的情况。对，就这样，没了（

但是一个特判特殊情况就值80分真的很扯淡。(ZQL写的)

\(n\) 偶 偶先 偶必胜：配对，然后发现规律

\(n\) 偶 奇先 偶必胜

\(n\) 奇 偶先 偶必胜：不过什么情况，对手都会有两张牌比我小，所以最后我一定会比他先出完

\(n\) 奇 奇先 奇必胜：奇先出一个1，然后所有数-1，相对位置不变，变成以奇为先手的上述情况

T2

发现每一行之间、每一列之间是互不影响的，但是行与列之间是有影响的。

对于每一行和每一列，只有最后一次对这一行或这一列的操作对其有贡献，所考虑倒序枚举每一行或列的最后一个操作。

应用等效替代的方法发现每次的格子数量可以直接计算。

T3

\(30\) 随便模拟

\(70\) 分找个最大值

\(100\) 分用 \(O(n)\) 每次找第 \(K\) 大值

查询一个序列的第 \(K\) 大值 \(O(n)\) 做法

1. \(\text{nth_element(a + 1, a + k, a + n + 1, cmp)}\)
2. 选取一个区间的任意一个元素，把比他小的元素放到左边，比他大的元素放到右边，查看左边的数有多少个，如果大k个，则第k大的数在左边，否则在序列的右边，重复这个过程，直到找到第k大值。

T4

将每一个数 \(-1\)，即可变为直接用区间和相乘的操作。

40pts

用 \(f_{i,j}\) 表示 \(A\) 串选 \(i\) 个，\(B\) 串中选 \(j\) 个，能获得的最小价值。

然后快乐 \(n^4\) 做 \(DP\)，枚举比 \(i,j\) 要小的 \(k,l\) 然后转移：

60pts

每次各删除 \(a,b\) 中的一段数时，一定有一边删除的个数为 \(1\)。

于是状态转移只需要枚举一维，复杂度变为 \(O(nm(n+m))\)

100pts

不想写= =

代码

咕咕咕

2020.10.01考试解题报告

原文：https://www.cnblogs.com/loceaner/p/qbxt_1001.html