CVBB ACM Team

题意:给定一个$01$串，问最少删掉多少个$0$使得所有$1$组成连续的一段。

题解:扫一遍把第一个$1$和最后一个$1$中间的$0$全删了即可。

题意:天气$g$天好$b$天坏，无限循环，每天可以动工也可以不动工，一共需要动工$n$天，要求至少一半（向上取整）的天数是在好天气动工的，问最少需要多少天才能完工。

题解:保证有好天就动工，有坏天就不动，算一下达到一半需要到哪天，如果天数不够做满$n$天即可。

题意:给定一个小写字母组成的相邻字母不相同的字符串，问是否存在一个小写字母的排列，使得如果两个小写字母在字符串中相邻，那么他们在这个排列中也相邻，若存在则输出这个排列。

题解:使用链表来记录每个字母前后的字母，遍历一遍字符串，如果发现冲突则无解，否则从最左端或最右端遍历一遍链表输出即可。

题意:给出$n$个物品，每个物品体积都是$2$的次幂，你可以把一个体积大于$1$的物品分解成$2$个体积为一半的物品，问恰好塞满体积为$m$的背包最少要分解几次，或判断无解。

题解:显然如果物品体积总和比$m$还小肯定无解。否则按位考虑$m$，贪心的从低位开始，如果这一位有的话就算上，如果没有的话就找到最小的一个比他大的并把他分解到这一位有为止。每次遍历完一位，将这一位每两个“合并”成一个大的带到下一位，多余的舍弃即可。

题意:问能否从字符串中$s$找到两个不重叠的子序列（可以为空）组成字符串$t$。$(|s|, |t| \le 400)$

题解:状态设计tql，太菜了想不到啊。首先肯定要枚举$t$的分割点，将$t$分为两个字符串，然后如果设$f[i][j]$为是否能匹配前一个字符串到第$i$位且匹配后一个字符串到第$j$位，转移是$O(n)$的，那么总复杂度是$O(n^4)$的会TLE。因此要换一个状态设计，同样还是要枚举分割点，设$f[i][j]$表示考虑到$s$的第$i$位在第一个字符串匹配了$j$个字符的情况下第二个字符串最多能匹配多少个字符。转移的话有三种，直接贴代码，很直观。

bool suc = false;
for(int i = 1;i < m;i++){
	memset(f, -0x3f, sizeof(f)), f[0][0] = 0;
	for(int j = 0;j < n;j++){
		for(int k = 0;k <= i;k++){
			if(f[j][k] < 0) continue;
			if(t[k + 1] == s[j + 1]) f[j + 1][k + 1] = max(f[j + 1][k + 1], f[j][k]);//和第一个字符串匹配 
			f[j + 1][k] = max(f[j + 1][k], f[j][k]);//都不匹配 
			if(t[i + f[j][k] + 1] == s[j + 1]) f[j + 1][k] = max(f[j + 1][k], f[j][k] + 1);//和第二个字符串匹配 
		}
	}
	if(f[n][i] == m - i){
		suc = true, puts("YES");
		break;
	}
}
if(!suc) puts("NO");

题意:$n \times m$的方格中，一开始每个方格颜色都是$0$。$q$个操作每次将一个方格变成另一种颜色，保证每次颜色的序号单调不减。问每次操作后的连通块数量，颜色相同才能组成一个连通块，$0$也是一种颜色。$(1 \le n, m \le 300,1 \le q \le 2 \cdot 10^6)$

题解:使用并查集正着来一次反着来一次。对于每一个方格当它被染上新的颜色，需要新建一个节点代表他，这样总结点个数是$O(q)$的。考虑每次操作相当于进行了对新颜色的一次连接和对旧颜色的一次断开，那么我们先正着来一次解决新颜色连接所带来的增量，再反着来一次解决对旧颜色断开所带来的减量（当然要取相反数），最后由于我们求的是差分，前缀和一下就可以了。

题意:这题太难了，摸了

题解:也摸了