最后一周，训练记录

翻看这个礼拜的记录的时候。发现很多平凡的过程都变成了「生涯中的最后一次」。
这时才像被殴打了一样感到，一段时间快要结束。
让我守最后一班岗，以下：
11.21

最后一次听cdx讲专题。
主要是计数部分的一些杂题和trick的复习。
高斯消元

过程中存在将第i列非0的行替换到当前行的操作。
注意这个操作是在将原始矩阵转换成最简形式的过程当中做的。
类似答案为 \((x)^3\) 的情况

写成三个\sum之前的操作是将x写成多项式的形式。
这样子展开之后才是(x)^3。
展开之后尝试衔接「调换枚举顺序」、「刻画有值时的情况」一类的trick。
连续段dp

出乎意料的，在这一天之前完全没有听说过这个名字。
对于可以用「段」的概念来描述的状态，可以记f[j]表示使用了i个数，用这i个数组成了几段。
非常重要的，我们几乎不考虑这个段在原来的序列上长成什么样。只在意i、j这两个和状态有关的变量。
因为只考虑「段」，我们只需要在转移中考虑段之间的合并、扩张操作。
其实非常难理解。给出一个痛点：

• 由于不考虑原序列上的形状，即不考虑段之间的相对位置关系。我们在添加新段时，只考虑「可以在原来状态的j-1个空隙中添加」，而不是「在每一个空隙中添加会带来怎样的系数」。
  可以不怎么形象地理解成：扒开两个原有的段，在中间插入。
  

由于状态内包含的信息太少，对应到题意上，我们就需要判断状态的合法性。
比如：如果题意是在全0串上选择若干个位置1来组成段。
那么f[j]合法就需要满足 i + (j - 1) \leq n。即需要留出段与段之间的空隙。
考场上如果考到的话，有状态之后应该是好解决的。大概。
排列方案数dp

是在博客中经常写到的话题呢。
讲课时总结了几种思路。列举我理解的几种。

• 考虑一个前缀中的相对大小关系。
  
• 考虑已知前一个排列，向其中添加一个数的方案数。
  
  
  
  

这张图非常精炼，但是难以理解。
也许对应到题意里面才能大概知道在说什么。
11.23

提早回校打了最后一场cf。过掉四题，未留遗憾。
不知道在哪里看到过，div2稳切4题就有在所有强省稳稳拿到noip一等的水平。这场也给了我挺多的信心。
不过我一共只打过6场rated的cf，大概在3场还是4场中切过4题。样本数还是太少了。
C

以下称保证mex的区间为1类区间，保证min的区间为2类区间。
刻画条件可以得到：

• 所有1区间必须包含[0, k)中所有数，且必须不包含k。
  
• 所有2区间必须不包含[0, k)中所有数，且必须包含k。
  这个条件长得非常对称。
  手玩发现，一旦存在一个点，被1类和2类区间同时包含，这个点的值一定不在[0, k]内。
  不妨钦定所有交集的值为k+1，这样我们就确定了一部分的值。
  对于所有区间中剩下的部分，一定是只被1类或2类区间包含的。
  此时注意到题目保证一定存在构造解，这非常重要，省去了很多判断条件。
  我们对于1、2类区间中剩下的部分分开考虑：
  

对于2类区间，剩下的位置可以直接填k。
对于1类区间，我们将其贪心的按照r排序。
优先考虑在区间的前端填完[0, k - 1]。这样后面的空间可以留给后面的区间发挥。
由于题目保证一定有解。所以这样做肯定是对的。
11.24

这场打的还可以，挺符合期望的。
策略致胜☆纯。
B

由于特殊的边权，可以只考虑保留最小生成树。
然后考虑，添加k条边代表了什么。
一开始以为相当于将k条边权赋值为0，但比较错误。
反过来考虑，这k条边一定要使生成树上最大的k条树边在最短路中不被经过。
然后神秘手玩，发现几个性质：

• 加边一定是从1连到某个点。
  
• 相当于断掉最大的边后分成k+1个连通块，可以决定其中k个的起点。
  

知道了这个之后就比较好做了。
题解跟我们说起点一定是每个连通块的重心。但我赛时并不是这么考虑的。
考虑某个连通块中最大的边，还是由于特殊的边权，我们选起点的方式必须使最后的最短路方案中这条边被经过的次数最少。
发现选在这条边两侧时，次数分别是一个子树size和一个外子树size。所以可以递归地确定连通块内的起点。
具体实现是用set维护每个连通块内的点，将边拍到深度较大的点上考虑。
每次直接删除一侧的所有节点。均摊复杂度O(n \log n)。
说起来轻巧，其实每一步的转化在赛时都是挺困难的。
尤其是说成「连通块内选起点」这种明了的形式，在思考过程中其实是难做到的。
也就是一直在提到的，对题目条件的「刻画」。
目前在实践的方式是积极手玩，积极猜结论。在有不确定的做法时尽量代入样例中判断或者手捏样例判断。
毕竟在csp当中就狠狠吃了不手模直接写的亏。
手玩一些样例确实是将「纸面的题意」与「脑内的题意」对应起来的很好方式。
但是在剩余时间较少的时候效率往往不高。希望noip的时候可以时间足够。
A

这个题赛时反而没想出来。
其实也许比B需要更多的注意力。
将原矩阵扩展一行一列，最后一行表示每一列的异或和，最后一列同理。
题目中的两个操作就转化成了「交换这个矩阵的两行或两列」。
由于我们只在意最后每行每列的和，而交换两行时，同一列上只是变换了顺序，和不变。
于是我们就可以直接维护当前状态每一行每一列的顺序。
即每次只交换两个行/列的编号。
这个实现感觉非常聪明。以很巧妙的方式利用题意，避免了维护矩阵。
最害怕遇到的还是这种题。往往不会太难，但想不到就是完全不行，放在前两题很容易炸心态。
也许还是要逼自己理性的跳题。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！