526互联

AtCoder Grand Contest 037

发布时间 2023-09-27 19:00:14作者: Zhou_JK

A - Dividing a String

可以发现，划分后的子串的长度不可能大于 \(2\)。令 \(f_{i,1/2}\) 表示到第 \(i\) 位，当前位置划分的子串长度为 \(1/2\) 的最大的 \(K\)，转移枚举一下 \(i-1,i-2\) 即可。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=200005;
int n;
char s[N];
int dp[N][3];
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++)
	{
		dp[i][1]=dp[i-1][2]+1;
		if(s[i]!=s[i-1]) dp[i][1]=max(dp[i][1],dp[i-1][1]+1);
		if(i-2>=0) dp[i][2]=dp[i-2][1]+1;
		if(i-2>=0&&(s[i]!=s[i-1]||s[i-1]!=s[i-2])) dp[i][2]=max(dp[i][2],dp[i-2][2]+1);
	}
	printf("%d",max(dp[n][1],dp[n][2]));
	return 0;
}

B - RGB Balls

考虑贪心，如果一个球能配对，我们肯定尽量让它配对是更优。对于 B，我们肯定让它跟 RG，GR 配对。R，G 同理，且对于 B 我们肯定让它与 R，G 匹配成 BR，BG 肯定不会使得答案更劣。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=200005;
int n,k;
int p[N];
int a[N];
pair<int,int> Min[N][20],Max[N][20];
void init()
{
	for(int i=1;i<=n;i++)
		Min[i][0]=Max[i][0]=make_pair(p[i],i);
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			Min[i][j]=min(Min[i][j-1],Min[i+(1<<(j-1))][j-1]);
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			Max[i][j]=max(Max[i][j-1],Max[i+(1<<(j-1))][j-1]);
	return;
}
int querymin(int l,int r)
{
	int k=log2(r-l+1);
	return min(Min[l][k],Min[r-(1<<k)+1][k]).second;
}
int querymax(int l,int r)
{
	int k=log2(r-l+1);
	return max(Max[l][k],Max[r-(1<<k)+1][k]).second;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&p[i]);
	for(int i=1;i<=n;i++)
		a[i]=p[i-1]>p[i];
	for(int i=1;i<=n;i++)
		a[i]+=a[i-1];
	init();
	int ans=0;
	bool flag=false;
	for(int r=k;r<=n;r++)
	{
		int l=r-k+1;
		if(a[l]==a[r])
		{
			flag=true;
			continue;
		}
		if(l==1)
		{
			ans++;
			continue;
		}
		if(querymin(l-1,r-1)==l-1&&querymax(l,r)==r) continue;
		ans++;
	}
	if(flag) ans++;
	printf("%d",ans);
	return 0;
}

C - Numbers on a Circle

考虑从后往前考虑所有操作，操作即为每次将一个点减去相邻两个数的和，问题转化成了最少操作几次能够使得所有位置的 \(a_i=b_i\)。

可以发现，从大到小操作肯定是比答案更劣的，每次将最大的那个减去相邻两个的数，直到它不是最大的或者 \(a_i=b_i\)，我们再操作次大的，可以用堆来维护这个东西

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N=200005;
int n;
int a[N],b[N];
priority_queue<pair<int,int>,vector<pair<int,int> > >q;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		scanf("%d",&b[i]);
	for(int i=1;i<=n;i++)
		q.push(make_pair(b[i],i));
	a[0]=a[n],b[0]=b[n];
	a[n+1]=a[1],b[n+1]=b[1];
	long long ans=0;
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		if(a[u]==b[u]) continue;
		int x=b[u-1]+b[u+1];
		if(a[u]>b[u])
		{
			printf("-1");
			return 0;
		}
		if(b[u]-a[u]<x)
		{
			printf("-1");
			return 0;
		}
		int t=(b[u]-a[u])/x;
		ans+=t;
		b[u]-=t*x;
		if(u==1) b[n+1]=b[1];
		if(u==n) b[0]=b[n];
		if(a[u]!=b[u]) q.push(make_pair(b[u],u));
	}
	printf("%lld",ans);
	return 0;
}

D - Sorting a Grid

考虑将 \(D\) 中 \((i,j)\) 的数标记为 \(i\)。

可以发现，\(C\) 的第 \(i\) 行的数的标记一定为 \(i\)，那么 \(B\) 的每一列标记一定是一个 \(1\sim n\) 的排列。

考虑构造出一种方案使得 \(B\) 的每一列标记一定是一个 \(1\sim n\) 的排列。将每一列的点看做左部的点，\(1\sim n\) 的标记看做右部点，如果第 \(i\) 行中标记为 \(j\) 的数，连一条 \(i\to j\) 的边，每次把配完的边删去，跑 \(m\) 次二分图匹配即可。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=105;
int n,m;
bool e[N][N];
int match[N];
bool vis[N];
bool dfs(int u)
{
	for(int v=1;v<=n;v++)
		if(e[u][v]&&!vis[v])
		{
			vis[v]=1;
			if(!match[v]||dfs(match[v]))
			{
				match[v]=u;
				return true;
			}
		}
	return false;
}
void KM()
{
	memset(match,0,sizeof(match));
	for(int i=1;i<=n;i++)
	{
		memset(vis,false,sizeof(vis));
		dfs(i);
	}
	return;
}
int a[N][N],b[N][N],id[N][N];
bool book[N][N];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
			id[i][j]=(a[i][j]-1)/m+1;
		}
	for(int k=1;k<=m;k++)
	{
		memset(e,0,sizeof(e));
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(!book[i][j]) e[i][id[i][j]]=1;
		KM();
		for(int j=1;j<=n;j++)
		{
			int u=match[j];
			for(int v=1;v<=m;v++)
				if(!book[u][v]&&id[u][v]==j)
				{
					book[u][v]=true;
					b[u][k]=a[u][v];
					break;
				}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			printf("%d ",b[i][j]);
		printf("\n");
	}
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<j;k++)
				if(b[j][i]<b[k][i]) swap(b[j][i],b[k][i]);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			printf("%d ",b[i][j]);
		printf("\n");
	}
	return 0;
}

E - Reversing and Concatenating

考虑贪心，我们肯定使得最小的那个字符在前缀出现的次数越多越好。可以用 \(1\) 次操作把原序列中最小的字符的最长连续段找出来，且要满足这个连续段的后缀是所有长度相等的连续段中最小的。

可以用一次操作将这个连续段放在序列的尾部，或者说如果尾部也有一个连续段，我们就可以每次将最小字符前缀的出现次数乘 \(2\)，直接暴力模拟直到操作次数 \(> k\) 或者全部都为最小的那个字符，可以证明这样的复杂度是对的。最后还需要一次操作将位置放到前面。

注意一些实现细节，具体可以看代码。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=5005;
int n,k;
string s;
int main()
{
	cin>>n>>k;
	cin>>s;
	char c='z'+1;
	int L=0,R=0;
	string tmp;
	for(int i=0;i<=n;i++)
		tmp+='z';
	for(int i=0,j=0;i<n;i=j)
	{
		j=i;
		while(j<n&&s[i]==s[j]) j++;
		if(s[i]<c) c=s[i],L=i,R=j-1,tmp=s.substr(j);
		else if(s[i]==c&&j-i>R-L+1) L=i,R=j-1,tmp=s.substr(j);
		else if(s[i]==c&&j-i==R-L+1&&s.substr(j)<tmp) L=i,R=j-1,tmp=s.substr(j);
	}
	if(k==1)
	{
		if(s[n-1]!=c)
		{
			string t=s;
			reverse(t.begin(),t.end());
			s+=t;
			s=s.substr(L,n);
			cout<<s; 
		}
		else
		{
			int cnt=0,now=n-1;
			while(now>=0&&s[now]==c) now--,cnt++;
			string t=s;
			reverse(t.begin(),t.end());
			string st=s+t;
			st=st.substr(now+1,n);
			t=s;
			reverse(t.begin(),t.end());
			s+=t;
			s=s.substr(L,n);
			cout<<min(st,s);
		}
		return 0;
	}
	if(R!=n-1)
	{
		int cnt=0,now=n-1;
		while(now>=0&&s[now]==c) now--,cnt++;
		string t=s.substr(0,now+1);
		reverse(t.begin(),t.end());
		if(cnt*2<R-L+1||(cnt*2==R-L+1&&tmp<t))
		{
			string t=s;
			reverse(t.begin(),t.end());
			s+=t;
			int r=(n-1-L)+n,l=r-n+1;
			s=s.substr(l,n);
			k--;
		}
	}
	int pre=n-1;
	while(pre>=0&&s[pre]==c) pre--;
	pre++;
	for(int i=1;i<k;i++)
	{
		string t=s;
		reverse(t.begin(),t.end());
		s+=t;
		int r=(n-1-pre)+n,l=r-n+1;
		s=s.substr(l,n);
		pre=n-1;
		while(pre>=0&&s[pre]==c) pre--;
		pre++;
		if(pre==0) break;
	}
	string t=s;
	reverse(t.begin(),t.end());
	s+=t;
	int l=pre,r=l+n-1;
	s=s.substr(l,n);
	cout<<s;
	return 0;
}

F - Counting of Subarrays

可以发现，一个区间属于等级 \(k\) 即为每次可以将连续的 \(L\) 个相等的 \(x\) 合并成一个 \(x+1\)，问最后能不能合并出一个 \(k\)。可以发现，一个区间合法的条件即为区间只有一个数或者将所有数合并成某个数后的个数 \(\ge L\)。

可以发现，我们肯定贪心的合并出尽可能多的数是最优的。

考虑从小到大将 \(x\) 加入序列中，刚开始序列为空。

对于一个 \(x\)，我们可以用 two-pointer 统计只包含 \(x\) 的合法区间方案数。注意某个点，它可能有比它小的某些数合并出来，还需要维护 \(lf\) 与 \(rf\)，分别表示某个数作为左端点和右端点的方案数（即某个点向左拓展和向右拓展的方案数）。

对于一个 \(x\) 的极长区间 \(a_1, a_2, \ldots , a_k\)。\(a_1, a_2, \ldots , a_{L-1}\) 可以作为第一个 \(x+1\) 的向左拓展的方案，\(a_{L\ldots 2L-1}\) 可以作为第二个 \(x+1\) 的向左拓展的方案，将 \(a_1, a_2, \ldots , a_{L-1}\) 对应的 \(lf\) 加起来即为第一个 \(x + 1\) 的 \(lf\) 了。\(rf\) 同理。

有可能 \(x\) 合成出来的 \(x + 1\) 还可以再合成，会重复计算，计算 \(x\) 时减去 \(x-2\) 合并出 \(x\) 的方案数即可。

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N=200005;
int n,l;
int a[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
int pre[N],nxt[N];
long long lf[N],rf[N];
vector<int>now;
long long solve(int x)
{
	long long res=0,sum=0;
	int len=now.size();
	int ppre=pre[now.front()],nnxt=nxt[now.back()];
	for(int i=0;i<len;i++)
	{
		if(i-l+1>=0) sum+=lf[now[i-l+1]];
		res+=sum*rf[now[i]];
	}
	static long long tlf[N],trf[N];
	for(int i=0;i<len;i++)
		tlf[now[i]]=lf[now[i]],trf[now[i]]=rf[now[i]],lf[now[i]]=rf[now[i]]=0;
	if(len<l)
	{
		nxt[ppre]=n+1,pre[nnxt]=0;
		return res;
	}
	int num=len/l;
	for(int i=l-1;i<len;i++)
	{
		int p=(i+1)/l-1;
		rf[now[p]]+=trf[now[i]];
	}
	for(int i=len-l;i>=0;i--)
	{
		int p=num-(len-i)/l;
		lf[now[p]]+=tlf[now[i]];
	}
	now.resize(num);
	for(int i=1;i<num;i++)
		pre[now[i]]=now[i-1],nxt[now[i-1]]=now[i];
	pre[now.front()]=ppre,nxt[ppre]=now.front();
	pre[nnxt]=now.back(),nxt[now.back()]=nnxt;
	for(int p:now)
		q.push(make_pair(x+1,p));
	sum=0;
	for(int i=0;i<num;i++)
	{
		if(i-l+1>=0) sum+=lf[now[i-l+1]];
		res-=sum*rf[now[i]];
	}
	return res;
}
int main()
{
	scanf("%d%d",&n,&l);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
		q.push(make_pair(a[i],i));
		pre[i]=i-1,nxt[i]=i+1;
		lf[i]=rf[i]=1;
	}
	vector<int>pos;
	long long ans=0;
	while(!q.empty())
	{
		int x=q.top().first;
		pos.push_back(q.top().second);
		q.pop();
		while(!q.empty()&&q.top().first==x) pos.push_back(q.top().second),q.pop();
		now.push_back(pos.front());
		for(int i=1;i<pos.size();i++)
		{
			if(nxt[pos[i-1]]!=pos[i]) ans+=solve(x),now.clear();
			now.push_back(pos[i]);
		}
		ans+=solve(x);
		now.clear();
		pos.clear();
	}
	printf("%lld",ans+n);
	return 0;
}