负担集训-Test16
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
-----------------------------------------------
咸鱼啊，越来越咸了...
-----------------------------------------------
C:
题意就是说给你一个矩阵，每个位置有一个数，要求每一行每一列都是严格递增的，然后要求对角线相邻的格子的数的奇偶性不同，现在已经钦定了一些位置的数，让你填剩下的位置，问总和最小是多少
首先发现除了只要一行或者一列的情况（这种情况特判一下）只要任意两个相邻的格子的奇偶性确定了，整个矩阵的奇偶性就都确定了，因此枚举一下前两个格子的奇偶性，就知道了整个棋盘的奇偶性。然后贪心就好，按这个顺序：第1行、第1列、第2行、第2列...这样
-----------------------------------------------
D：
题意就是给你一个二进制串r，问你满足恰好有n个元素且所有元素xor=0，且所有元素在[0,r)内的集合个数是多少。
r是由一个二进制串s重复k次得到的。
n<=7,|s|<=50,k<=10^5
首先考虑k=1的情况，我们强制集合中的元素个数升序排列，有一个DP：f[i][j]表示前i位，状态为j（j是一个长度为n的二进制串）的方案数，其中j的第p(p<n)位表示第p个数的前i位个第p+1个数的前i位大小关系（0表示=，1表示<），而第n位表示第n个数（最大的数）的前i位和r的前i位大小关系（0表示=，1表示<)，我们从高位向低位逐位确定，每次枚举哪些数选1。
然后不难发现这个递推每次只跟s这一位是多少有关，跟i无关，因此这个递推可以用一个矩阵乘法来表示（一个表示s这一位是0的转移矩阵，一个表示s这一位是1的转移矩阵），然后矩乘一下就可以求出答案了。
-----------------------------------------------
J：
题意是说现在一个串的大小就是每对相邻字符的ASCII码的差值之和，给出大小，求这个大小的最短（长度一样，字典序最小）的串。
预处理一下f[i][j]表示有i位，开头是j的字符串最大大小，然后逐位确定就行了。
-----------------------------------------------
记录：
一开始我们就各自看题，yyy看了f之后觉得可做，跟ljz商量了一下就会做了，然后就写写写，然后就a了，这个时候ljz跟gmr商量了一下觉得G是个sb题，写写写，然后WA了，然后两人想可想，觉得好像并不是sb题，就放弃了去想C，发现C还挺可做的，就写写写，就A了，然后继续跟榜，把EA了，然后ljz想了想，F好像也是个sb题，然后就让gmr写写写，然后就把FA了，然后YYY觉得D和G都会了，权衡了一下觉得G比较好写，于是写写写，然后发现算法是错的，过不了样例（mdzz），然后ljz好像会写H了，然后写写写，然后调调调，然后没有调出来，gg。
-----------------------------------------------
总结：
我们写题的效率有点低，而有些时候又会被错误算法浪费写题的时间，很多时候有些题就一直排队到底，都没有机会写。所以我们需要至少一个人提升代码能力，至少要保证会做的题能快速写出来。另外在开始写一个算法之前需要反复论证，确保正确性，尤其是比较难写的算法。
----------------------------------------------------------------------------------------------
评论 (0)
