负担集训-Test15(多校联合训练-6)
负担集训-Test17

负担集训-Test16

YYY posted @ 2017年8月12日 00:53 in ACM with tags 懒得写了 , 185 阅读
-----------------------------------------------
咸鱼啊,越来越咸了...

-----------------------------------------------
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。
-----------------------------------------------
总结:
我们写题的效率有点低,而有些时候又会被错误算法浪费写题的时间,很多时候有些题就一直排队到底,都没有机会写。所以我们需要至少一个人提升代码能力,至少要保证会做的题能快速写出来。另外在开始写一个算法之前需要反复论证,确保正确性,尤其是比较难写的算法。
-----------------------------------------------
 

-----------------------------------------------

LOL

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter