负担集训-Test8

--------------------------------------------------
...

--------------------------------------------------
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的
--------------------------------------------------