A.Bobo String Construction

题意：给出一个01字符串t，要求构造一个长为n的01字符串s，使得新的字符串t+s+t不会有超过两个子串t

Solution

答案要么全0串要么全1串

带进去看看成不成立就行了

void solve()
{
	int n;cin>>n;
	string s0(n,'0');
	string s1(n,'1');
	string t;cin>>t;
	string t0=t+s0+t;
	if(t0.find(t,1)==t.size()+n)
	{
		cout<<s0<<"\n";
	}else
	{
		cout<<s1<<"\n";
	}
}

F.Election of the King

题意：有n个人参加国王选举，第i个人有一个政治倾向a[i]，a[i]越小，他就越左倾，反之则越右倾，这些人进行n-1轮筛选，每一轮筛选可以每个人可以对一个人投票，票数最高的人被淘汰，票数相同的话则淘汰最政治右倾的人，每个人都会投和自己的政治倾向差别最大的人，即|a[i]-a[j]|最大，如果有多个则投最政治右倾的人，问最后谁会成为国王。

Solution

双指针，令mid=(a[l]+a[r])/2，则mid以及它左边的人都会投第r个人，它右边的人都会投第l个人，在l和r中淘汰票数最高的，依次进行操作直到最后一个人剩下即可。

void solve()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	int l=1,r=n;
	while(l<r)
	{
		int mid=(b[l]+b[r])>>1;
		int pos=upper_bound(b+1,b+1+n,mid)-b;
		pos--;
		if(pos-l+1>=r-pos)r--;
		else l++;
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i]==b[l])
		{
			cout<<i<<"\n";
			return;
		}
	}
}

H.Merge the squares!

题意：给定1个由n*n个1*1的小正方形组成的正方形，每次可以合并相邻不超过50个正方形变成一个大正方形。问如何通过合

并得到一个大的n*n的大正方形，不限次数

Solution

对于一个正方形，如果他不能被直接合成，那么我们可以把他分成a*a，b*b,a*(a-b),(a-b)*a，对于两个正方形来说，它们最后肯定能变成1块正方形用于与矩形合成，对于两个矩形来说，如果它们最后需要合成的块数之和是小于等于48的，那么就满足条件可以合成，我们先预处理一下使得矩形满足条件的a的长度，然后用递归的方式来写即可。

void init()
{
	for(int i=2;i<=1000;i++)
	{
		for(int j=1;j<i;j++)
		{
			int a=j,b=i-j;
			int cnt=0;
			while(b)
			{
                cnt+=a/b;
                a%=b;
                swap(a,b);
            }
            if(cnt<=24)
            {
                t[i]=j;
                break;
            }
		}
	}
}


void dfs(int x,int y,int a,int b)
{
	if(a==1||b==1)return;
	if(a>b)
	{
		dfs(x,y,b,b);
		dfs(x,y+b,a-b,b);
	}else if(a<b)
	{
		dfs(x,y,a,a);
		dfs(x+a,y,a,b-a);
	}else
	{
		if(a==1)return;
		else if(a>7)
		{
			dfs(x,y,t[a],t[a]);
			dfs(x,y+t[a],a-t[a],t[a]);
			dfs(x+t[a],y,t[a],a-t[a]);
			dfs(x+t[a],y+t[a],a-t[a],a-t[a]);
		}
		ans.push_back({x,y,a});
	}
}

void solve()
{
	init();
	//for(int i=1;i<=1000;i++)cout<<t[i]<<" \n"[i==1000];
	int n;cin>>n;
	dfs(1,1,n,n);
	cout<<ans.size()<<"\n";	
	for(auto it:ans)
	{
		cout<<it.x<<" "<<it.y<<" "<<it.z<<"\n";
	}
}

J.Qu'est-ce Que C'est?

题意：给出一个长度n，问有多少个数组满足以下条件：

1.对于1<=i<=n，-m<=a[i]<=m

2.a的任意一个长度大于2的区间和都大于等于0

Solution

令dp[i+m][0/1]表示最小后缀和为i的合法方案，0/1表示当前或者上一个状态

我们考虑合法转移的条件是最小后缀和加上下一个数大于0,

对于-x来说，他可以由[x,x+1,...,m]转移而来

对于0来说，他可以由[-m,-m+1,...,m]转移而来

对于x来说，他可以由[x-m,x-m+1,...,m]转移而来

考虑到每个数都由一段区间的合法状态转移而来，我们可以通过前缀和处理来优化时间复杂度

void solve()
{
	int n,m;cin>>n>>m;
	int op=0;
	for(int i=-m;i<=m;i++)dp[i+m][0]=1;
	for(int i=-m+1;i<=m;i++)dp[i+m][0]=(dp[i+m-1][0]+dp[i+m][0])%mod;
	op^=1;
	for(int i=2;i<=n;i++)
	{
		for(int j=-m;j<=m;j++)
		{
			if(j<0)dp[j+m][op]=((dp[m+m][op^1]-dp[-j+m-1][op^1])%mod+mod)%mod;
			else {
				dp[j+m][op]=dp[m+m][op^1];
				if(j!=0)dp[j+m][op]=((dp[j+m][op]-dp[j+m-m-1][op^1])%mod+mod)%mod;
			}
			
		}
		for(int j=-m+1;j<=m;j++)
		{
			dp[j+m][op]=(dp[j+m-1][op]+dp[j+m][op])%mod;
			//cout<<dp[j+m][op]<<"\n";
		}
		op^=1;
		for(int j=-m;j<=m;j++)dp[j+m][op]=0;
	}
	cout<<dp[m+m][op^1]<<"\n";
}

L.We are the Lights

题意：有n*m盏灯构成的矩阵，最开始所有灯都是关着的，进行q次操作，每次操作可以 关上/打开 一行/一列 的灯，问进行了q次操作后还有多少灯是开着的

Solution

对于每一行来说

如果它从头到尾都没有进行操作，假设最后有x列灯最后的操作是开灯，则对答案的贡献是x

如果它最后的操作是开灯，假设最后有x列灯最后的操作是关灯，则对答案的贡献是m-x

如果它最后的操作是关灯，假设最后有x列灯最后的操作是开灯，则对答案的贡献是x

将操作存下来然后倒着遍历一遍即可

void solve()
{
	int n,m,q;cin>>n>>m>>q;
	for(int i=1;i<=q;i++)
	{
		cin>>s1[i]>>a[i]>>s2[i];
	}
	int off=0,on=0;
	int ans=0;
	for(int i=q;i>=1;i--)
	{
		if(s1[i]=="column")
		{
			if(c[a[i]]==0)
			{
				if(s2[i]=="on")c[a[i]]=1;
				else c[a[i]]=-1;
			}else continue;
			if(c[a[i]]==1)on++;
			else off++;
		}else
		{
			if(b[a[i]]==0)
			{
				if(s2[i]=="on")b[a[i]]=1;
				else b[a[i]]=-1;
			}else continue;
			if(b[a[i]]==1)ans+=m-off;
			else ans+=on;
		}
		//cout<<off<<"\n";
		//cout<<ans<<"\n";
	}
	for(int i=1;i<=n;i++)
	{
		if(b[i]==0)ans+=on;
	}
	cout<<ans<<"\n";
}