负担集训-Test8
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
--------------------------------------------------
...
--------------------------------------------------
A:
题意就是说，给你一个n*n的矩阵，每个位置要么是一个小写英文字母，要么是一个问号，现在你有一个空白的矩阵，你可以进行2*n次染色，每次染色就是把某一行或者某一列全部变成某种英文字母，每一行、每一列只能染色一次，这样每个格子都会刚好被染色两次，那么后一次的会覆盖前一次的，现在要求你把空白矩阵染成之前给出的矩阵的样子，对应位置如果是问号表示对这个位置的颜色没有要求，输出任意一种方案，保证有解。
n<=3000
可以把染色的过程倒过来，这样就相当于一个格子被染色之后颜色就不会再变化了，因此染完一行或者一列之后可以把这一行（列）的所有格子全部变成问号，表明之后怎么染都没有关系了。然后每次染色因为染了就不能再改了，因此就选择那些一行（列）都是同一个颜色的行（列）去染，染了之后就把对应位置改成问号，这样就有可能产生新的只有一种颜色的行（列），这样不断地做就行了。
--------------------------------------------------
E：
题意是说，这样的排列被称为合法的：任意两个相邻的数的差大于等于这两个数中的较小者，并且有一些位置特已经钦定了，现在问合法的长度为n的排列个数
n<=27且n是奇数
首先解一下不等式可以得到一个数p旁边的数的取值范围是[1,p/2]∪[2*p,n]
设k=(n-1)/2，我们把<=k的数叫做小数，>k的数叫做大数，那么我们不难发现这个序列一定是大小大小大小...这样的，也就是奇数位都是大数，偶数位都是小数
而且n是奇数，所以两头都是大数
另外又设p=(k+1)/2，我们发现[1,p]内的数可以与任意大数相邻，因此他们的方案数可以最后乘以一个p!来确定，那么就只剩下最多20个数了，于是我们状压DP一下：
设f[i][j][s]表示前i个数（不算<=p的数），当前位置的数是j（要空一些偶数位置给<=p的数，因此若j=0的话表示这是一个空位），已经选了的数是s（s是一个二进制串）。暴力转移一下就行了
不过这样会爆空间，然后我们仔细想一想发现第一维是没有用的，因此直接转移就可以了
这道题T到死..要加一些优化...
第一是枚举转移的时候直接用lowbit枚举
第二是每次记录一下一个s对应的f[i][s]是否为0，然后枚举的时候如果上一个f[i][s]=0就直接跳过
--------------------------------------------------
I:
一道交互题。题意是说，现在你在赌博，初始你有160个筹码，每次可以选择押一定的筹码，如果赢了就会归还本金并且多给你一些钱，如果输了本金就被吃掉了。规定如果筹码输完了，或者赌的次数超过200次，就输了，如果筹码达到了200个以上，就赢了，要求赢得游戏，每次输出一个要押的筹码数，然后系统会输入一个这一次赌博之后的筹码数。
输赢的规则是这样的：现在有一个数列x满足x[i]=(487237*x[i-1]+1011807) mod 2^20,（但是x[1]是不知道的）第k次赌博，系统会查询x[k]的二进制位有多少个1，是奇数的话就是玩家赢，否则就是玩家输。
显然我们只需要知道x[1]是多少就可以预测每
一次的输赢了。
首先预处理出0~2^20内每个数的输赢，然后用倍增求出如果i是x[1]，那么之后32场的输赢，这样就可以大概保证每个数的特征都是不一样的，然后先玩32场，每次都押1块，看一下输赢，然后就可以反推出x[1]是多少，然后就知道之后每一场的输赢了，那么会输的话就押1块，会赢的话就全部押就好了。
--------------------------------------------------
L:
题意就是说，给你一个长度为n的全是字母a的字符串，每次按以下规则操作：
如果开头是a的话，就删去开头两个字母，并且在末尾添加上bc
如果开头是b的话，就删去开头两个字母，并且在末尾添加上a
如果开头是c的话，就删去开头两个字母，并且在末尾添加上aaa
问你要多少次才能把字符串变得只有一个字母
n<=100000
假设当前有k个a，不难发现如果k是偶数的话，就会在k次操作之后变成k/2个a，如果k是奇数的话，就会在k+1次操作之后变成(3*k+1)/2个a，因此就不断地去搞就行了，k<=1000000的情况下都是能很快到达1的
--------------------------------------------------
评论 (0)
