开个新号，这次做出了三道题，上分！！+82+82。

A. Erasing Zeroes

题意：给你一个由 0\texttt{0} 和 1\texttt{1} 组成的字符串，为了让字符串中所有的 1\texttt{1} 都连续，你需要至少删掉多少个 0\texttt{0} ？

解析：大水题，找到最左边的 1\texttt{1} 和最右边的 1\texttt{1} 的位置，然后在这段区间内统计 0\texttt{0} 的个数即可。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn=110;
int t,n;
char s[110];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		int l=0,r=0,ans=0;
		scanf("%s",s+1);
		int len=strlen(s+1);
		for(int i=1;i<=len;i++)
			if(s[i]=='1')
			{
				l=i;
				break;
			}
		for(int i=len;i>=1;i--)
			if(s[i]=='1')
			{
				r=i;
				break;
			}
		for(int i=l;i<=r;i++)
			if(s[i]=='0')
				ans++;
		printf("%d\n",ans);
	}
	return 0;
}

B. National Project

题意：你要修一条长度为 nn 的路，每天你只能修一个单位长度，或者选择不修。你修路的质量与天气正相关。天气具有周期性，一个周期由 gg 天好天气和 bb 天坏天气构成。如果要保证修的路有 ⌈n2⌉\lceil{\frac{n}{2}}\rceil 的长度是好的，那么你至少要花多少天？

解析：简单模拟，分类讨论情况即可。首先如果 ⌈n2⌉≤g\lceil{\frac{n}{2}}\rceil\le g，那么直接花 nn 天就够了；否则如果 ⌈n2⌉ mod g=0\lceil{\frac{n}{2}}\rceil\bmod g=0，那么答案为 p×g+(p−1)×b,p=⌊⌈n2⌉g⌋p\times g+(p-1)\times b,p=\lfloor\frac{\lceil{\frac{n}{2}}\rceil}{g}\rfloor，否则答案为 p×(g+b)+⌈n2⌉ mod gp\times (g+b)+\lceil{\frac{n}{2}}\rceil\bmod g。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn=1e4;
long long t,n,g,b;
int main()
{
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld%lld%lld",&n,&g,&b);
		long long num=(n+1)/2;
		long long p=num/g;
		if(num<=g)
		{
			printf("%lld\n",n);
			continue;
		}
		long long ans=0;
		if(num%g)
		{
			ans=1ll*p*(g+b);
			ans+=num%g;
		}
		else
			ans=1ll*p*(g+b)-b;
		printf("%lld\n",max(ans,n));
	}
	return 0;
}

C. Perfect Keyboard

题意：Polycarp\texttt{Polycarp} 有一个特制的键盘，该键盘只有一行由 2626 个字母构成。Polycarp\texttt{Polycarp} 为了输入密码方便，所以他的密码在键盘上每相邻两个字符都相邻。现在给出 Polycarp\texttt{Polycarp} 的密码，尝试构造出他的键盘，如果不行则输出 −1-1。

解析：一道较简单的构造题。用 vis[i]vis[i] 代表字母表中的第 ii 个字母是否已经被安排好位置了，用 p[i][0]p[i][0] 代表字母表中的第 ii 个字母在键盘上的前一个字母，用 p[i][1]p[i][1] 代表字母表中的第 ii 个字母在键盘上的后一个字母。遍历一遍密码，用 qq 表示这一位的字母遍号，rr 表示下一位的字母遍号，先将 vis[q]=1vis[q]=1，如果 rr 已经被安排位置了，就看看是否在键盘上与 qq 相邻，否则标记为无解；如果没有被安排位置，就给他安排位置，如果前面有位置就安排前面，否则就后面，如果都没有位置就标记无解。最后找到最前面的字母，依次输出，再将字母表中没有被安排位置的字母输出即可。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn=210;
int t,len,p[31][2];
char s[maxn];
bool vis[31];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		bool flag=1;
		memset(p,0,sizeof(p));
		memset(vis,0,sizeof(vis));
		scanf("%s",s+1);
		len=strlen(s+1);
		for(int i=1;i<len;i++)
		{
			int q=s[i]-'a'+1;
			vis[q]=1;
			int r=s[i+1]-'a'+1;
			if(vis[r])
			{
				if(r==p[q][0]||r==p[q][1])
					continue;
				else
				{
					flag=0;
					break;
				}
			}
			else
			{
				if(!p[q][0])
				{
					p[q][0]=r;
					p[r][1]=q;
				}
				else if(!p[q][1])
				{
					p[q][1]=r;
					p[r][0]=q;
				}
				else
				{
					flag=0;
					break;
				}
			}
		}
		vis[s[len]-'a'+1]=1;
		if(!flag)
			printf("NO\n");
		else
		{
			printf("YES\n");
			int f=s[1]-'a'+1;
			while(p[f][0])
				f=p[f][0];
			while(f)
			{
				printf("%c",f+'a'-1);
				f=p[f][1];
			}
			for(int i=1;i<=26;i++)
				if(!vis[i])
					printf("%c",i+'a'-1);
			printf("\n");
		}
	}
	return 0;
}

D. Fill The Bag

题意：你有一个容量为 nn 的背包和 mm 件物品，第 ii 件物品的大小为 aia _i，且保证 aia _i 都是 22 的非负整数幂，你可以将每件物品分成 22 个大小相同的物品，你需要用物品将背包装满，请问你至少要分割物品几次？

解析：一道很好的贪心和二进制题。我们首先用一个数组 cnt[i]cnt[i] 记录 a[i]a[i] 是 22 的几次幂，然后枚举 nn 在二进制下的每一位，如果第 ii 位为 11，就将 cnt[i]−−cnt[i]--，如果 cnt[i]=0cnt[i]=0，就要考虑分割物品，往后面找到第一个位置 jj 满足 cnt[j]>0cnt[j]>0，然后将容量为 2j2 ^j 的物品分割至 2i2 ^i，即将所有 i∼j−1i\sim j-1 的 cntcnt 值都加 11，将 cnt[j]−−cnt[j]--，同时统计答案。最后看看是否 cnt[i]≥2cnt[i]\ge 2，由于 22 个容量为 2i2 ^i 的物品与 11 个容量为 2i+12 ^{i+1} 的物品等效，而第 ii 位已经遍历过了，所以将 22 个容量为 2i2 ^i 的物品换成 11 个容量为 2i+12 ^{i+1} 的物品，即将 cnt[i+1]+=cnt[i]2cnt[i+1]+=\frac{cnt[i]}{2}，cnt[i]÷=2cnt[i]\div=2。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn = 101010;
long long cnt[70],n,ans;
int t,m,a[maxn];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		ans=0;
		scanf("%lld%d",&n,&m);
		for(int i=0;i<64;i++)
			cnt[i]=0;
		for(int i=1;i<=m;i++)
		{
			scanf("%d",&a[i]);
			for(int j=0;j<=30;j++)
				if(a[i]==(1<<j))
					cnt[j]++;//分解每一位，用数组存储指数
		}
		bool flag=true;
		for(int i=0;i<64;i++)
		{
			if(n&(1ll<<i))//如果n第i位上为1
			{
				if(cnt[i])
					cnt[i]--;//有盒子直接减
				else
				{
					int p=0;
					for(int j=i+1;j<64;j++)//找比它大的盒子
						if(cnt[j])
						{
							p=j;
							break;
						}
					if(!p)
						flag=false;//找不到标记退出
					else
					{
						cnt[p]--;//大盒子用1个
						for(int j=p-1;j>=i;j--)
						{
							cnt[j]++;
							ans++; //分解盒子
						}
					}
				}
			}
			if(!flag)
				break;
			if(cnt[i]>=2)
			{
				cnt[i+1]+=cnt[i]/2;//因为用2个2^i盒子和1个2^(i+1)盒子等效，而第i位已经遍历过了，所以把剩下的盒子全换成大盒子
				cnt[i]/=2;
			}
		}
		if(flag)
			printf("%lld\n",ans);
		else
			printf("-1\n");
	}
}

E. Erase Subsequences

题意：给你两个字符串 ss 和 pp，判断 pp 是否能由 ss 中的两个不相交子序列构成。

解析：

首先我们来看下题目中的一些概念(之前我一直天真的以为子串和子序列是一个东西)

子串

子串是指字符串中任意连续的一段字符构成的字符串。

子序列

子序列是指字符串中任意删去一些字符后，剩下的字符按顺序构成的字符串。

两者的区别就在于子串要求连续，而子序列不要求。

接下来来分析一下：这是一道很好的匹配型 dp\texttt{dp} 题。

在 ss 中不好找到 22 个子序列，于是我们在 tt 中找。设子序列分别为 aa 和 bb，由于 a,ba,b 在 tt 中连续，所以我们枚举 tt 的每一个端点，断点前半段就是 aa，后半段就是 bb。

然后就是让 aa 和 bb 在 ss 中是匹配，我们定义 dp[i][j]dp[i][j] 为构造到 aa 的第 ii 位，bb 的第 jj 位时在 ss 中的最小位置。

然后令 xx 为字符串 ss 的第 dp[i−1][j]dp[i-1][j] 位后的第一个 a[i]a[i] 位置，令 yy 为字符串 ss 的第 dp[i][j−1]dp[i][j-1] 位后的第一个 b[j]b[j] 位置，那么满足 dp[i][j]=min⁡(x,y)dp[i][j]=\min(x,y)。

接下来就是如何解决在 ss 中去找某一位置后的某一字符最近出现的位置，这就用到了一个不怎么出名但是很强的数据结构：

序列自动机

序列自动机能经过 O(nlogn)\texttt{O(nlogn)} 的预处理后可以 O(1)\texttt{O(1)} 查询上述问题，名字看起来很高大上，其实只用一个数组即可实现：

定义 nex[i][j]nex[i][j] 为字符串 ss 第 ii 位后最近的字符 jj 出现的位置。初始化如下所示(通俗易懂，就不讲解了)：

for(int i=1;i<=26;i++)
	nex[n][i]=n+1;//第n个位置后无任何字符，设置为不合法
for(int i=n;i>=1;i--)
{
	for(int j=1;j<=26;j++)
		nex[i-1][j]=nex[i][j];
	nex[i-1][s[i]-'a'+1]=i;
}

然后顺便给出即可序列自动机解决问题的代码板子：

求子序列个数：

int dfs(int x)//代表字符串第x位
{
    if(f[x])
        return f[x];//记忆化
    for(int i=1;i<=26;i++)
        if(nex[x][i]<=n)
            f[x]+=dfs(nex[x][i]);//如果第x位后有字符i，加上这部分的贡献
    return ++f[x];//第x位结束的子序列依然是子序列，最后加上这一个
}

求两个串的公共子序列个数，即对 22 个串分别构造 nexnex 数组即可：

int dfs(int x,int y)//串1的第x位，串2的第y位
{
    if(f[x][y])
        return f[x][y];//记忆化
    for(int i=1;i<=26;i++)
        if(nex1[x][i]<=n&&nex2[y][i]<=m)
            f[x][y]+=dfs(nex1[x][i],nex2[y][i]);
    return ++f[x][y];
}//思路大同小异

求一个串的回文子序列个数，即对原串和反串分别构造 nexnex 数组，但是在 dfsdfs 中我们需要注意：由于需要保证 x+y≤n+1x+y\le n+1，说明有两种情况，当 x+y=n+1x+y=n+1 时此子序列为奇串，否则为偶串。这时我们会发现一个很严重的问题，当 dfsdfs 到一个偶串时，可能会有奇串会被漏掉(如自动机只能找到 abbaabba，不能找到 abaaba)。因此对于奇串我们就通过递归加上，偶串则手动加上：

int dfs(int x,int y)
{
    if(f[x][y])
        return f[x][y];
    for(int i=1;i<=26;i++)
        if(nex1[x][i]<=n&&nex2[y][i]<=n)
        {
            if(nex1[x][i]+nex2[y][i]>n+1)
                continue;
            if(nex1[x][i]+nex2[y][i]<n+1)//偶串
                f[x][y]++;
            f[x][y]+=dfs(nex1[x][i],nex2[y][i]);
        }
    return ++f[x][y];
}

然后就很好做了，状态转移方程变为：

dp[i][j]=min⁡(nex[dp[i−1][j]][a[i]],nex[dp[i][j−1]][b[j]]) dp[i][j]=\min(nex[dp[i-1][j]][a[i]],nex[dp[i][j-1]][b[j]])

最后只需判断 dp[lena][lenb]dp[len _a][len _b] 是否小于等于 lenslen _s 即可。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn=410;
int T,len1,len2;
int nex[maxn][31];
int dp[maxn][maxn];
char s[maxn],t[maxn];
void ready(int n)//构造序列自动机
{
	for(int i=1;i<=26;i++)
		nex[n][i]=n+1;//第n个位置后无任何字符，设置为不合法
	for(int i=n;i>=1;i--)
	{
		for(int j=1;j<=26;j++)
			nex[i-1][j]=nex[i][j];
		nex[i-1][s[i]-'a'+1]=i;
	}
}
bool check(int n)//n代表a串长
{
	int m=len2-n;//m代表b串长
	dp[0][0]=0;
	for(int i=0;i<=n;i++)
		for(int j=0;j<=m;j++)
		{
			if(!i&&!j)
				continue;
			dp[i][j]=len1+1;
			if(i&&dp[i-1][j]<len1)
				dp[i][j]=min(dp[i][j],nex[dp[i-1][j]][t[i]-'a'+1]);
			if(j&&dp[i][j-1]<len1)
				dp[i][j]=min(dp[i][j],nex[dp[i][j-1]][t[n+j]-'a'+1]);
		}
	return dp[n][m]<=len1;
}
void solve()
{
	scanf("%s%s",s+1,t+1);
	len1=strlen(s+1);
	len2=strlen(t+1);
	ready(len1);
	for(int i=1;i<=len2;i++)
		if(check(i))
		{
			printf("YES\n");
			return ;
		}
	printf("NO\n");
	return ;
}
int main()
{
	scanf("%d",&T);
	while(T--)
		solve();
	return 0;
}