牛客周赛 Round 102 - 牛客题解 | 123hh2 = Keep moving forward

# 牛客周赛 Round 102

比赛链接

# A 小红的好 01 串

只有两种情况，要么以 1 开头要么以 0 开头

	#include<bits/stdc++.h>
	#define int long long
	#define in inline
	#define ri register
	#define _123hh2 0
	using namespace std;
	in int read()
	{
	int x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
	signed main()
	{
	int n=read();
	cout<<2;
	return _123hh2;
	}

# B 小红的 01 串距离

遍历找出三个 1 的位置，然后判断即可

	#include<bits/stdc++.h>
	#define int long long
	#define in inline
	#define ri register
	#define _123hh2 0
	using namespace std;
	in int read()
	{
	int x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
	signed main()
	{
	int t=read();
	while(t-->0)
	{
	int n=read();
	string awa;cin>>awa;
	int a=-1,b=-1,c=-1;
	for(int i=0;i<awa.size();i++)
	{
	if(awa[i]=='1')
	{
	if(a==-1) a=i;
	else if(b==-1) b=i;
	else c=i;
	}
	}
	if(c-b==b-a) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	}
	return _123hh2;
	}

# C 小红的好 01 串修改

字符串最终会有两种形态，跟 $A$ 题一样

所以遍历模拟操作，统计答案取 $\min$

	#include<bits/stdc++.h>
	#define int long long
	#define in inline
	#define ri register
	#define _123hh2 0
	using namespace std;
	in int read()
	{
	int x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
	signed main()
	{
	int t=read();
	while(t-->0)
	{
	int n=read();
	string awa;cin>>awa;
	string qwq=awa;
	if(n==1)
	{
	cout<<0<<endl;
	continue;
	}
	int ans1=0,ans2=0;
	for(int i=0;i<awa.size()-1;i++)
	{
	if(awa[i]!=(i%2+'0'))
	{
	ans1++;
	if(awa[i]=='0') awa[i]='1';
	else awa[i]='0';
	if(awa[i+1]=='0') awa[i+1]='1';
	else awa[i+1]='0';
	}
	}
	for(int i=0;i<qwq.size()-1;i++)
	{
	if(qwq[i]!=((i%2==0)+'0'))
	{
	ans2++;
	if(qwq[i]=='1') qwq[i]='0';
	else qwq[i]='1';
	if(qwq[i+1]=='1') qwq[i+1]='0';
	else qwq[i+1]='1';
	}
	}
	if(awa[awa.size()-1]==awa[awa.size()-2]&&qwq[qwq.size()-1]==qwq[qwq.size()-2])
	{
	cout<<-1<<endl;
	}
	else if(awa[awa.size()-1]==awa[awa.size()-2])
	{
	cout<<ans2<<endl;
	}
	else if(qwq[qwq.size()-1]==qwq[qwq.size()-2])
	{
	cout<<ans1<<endl;
	}
	else cout<<min(ans1,ans2)<<endl;
	}
	return _123hh2;
	}

# D 小红的华撃串

不难发现最终的字符串一定是 $0101$ 或 $1010$ 分成 4 大段的形式

枚举 $01$ 变化交界处，用前缀和快速求出操作数

	#include<bits/stdc++.h>
	#define int long long
	#define in inline
	#define ri register
	#define _123hh2 0
	using namespace std;
	in int read()
	{
	int x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
	int qzh0[501],qzh1[501];
	signed main()
	{
	int n=read();
	string awa;cin>>awa;
	for(int i=0;i<awa.size();i++)
	{
	if(awa[i]=='0')
	{
	qzh0[i+1]=qzh0[i]+1;
	qzh1[i+1]=qzh1[i];
	}
	else
	{
	qzh0[i+1]=qzh0[i];
	qzh1[i+1]=qzh1[i]+1;
	}
	}
	awa=" "+awa;
	int ans=1e9;
	for(int i=1;i<=n;i++)
	{
	for(int j=i+1;j<=n;j++)
	{
	for(int k=j+1;k<n;k++)
	{
	ans=min(ans,qzh1[i]+qzh0[j]-qzh0[i]+qzh1[k]-qzh1[j]+qzh0[n]-qzh0[k]);
	}
	}
	}
	for(int i=1;i<=n;i++)
	{
	for(int j=i+1;j<=n;j++)
	{
	for(int k=j+1;k<n;k++)
	{
	ans=min(ans,qzh0[i]+qzh1[j]-qzh1[i]+qzh0[k]-qzh0[j]+qzh1[n]-qzh1[k]);
	}
	}
	}
	cout<<ans;
	return _123hh2;
	}

# E 小红的 01 串（easy）

普通 $dp$ ，设 $dp[i]$ 表示数 $i$ 的最小长度

长度为 $n$ 的连续 1 串贡献为 \frac{n \times (n+1)}

若从 $dp[0]$ 转移过来，不需要使用 0 分隔连续 1 串

否则，需要多用一个 0 来分割连续的 1 串

	#include<bits/stdc++.h>
	#define int long long
	#define in inline
	#define ri register
	#define _123hh2 0
	using namespace std;
	in int read()
	{
	int x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
	const int maxn=2e5+5;
	int dp[maxn];
	void pre()
	{
	memset(dp,0x3f,sizeof(dp));
	dp[0]=0,dp[1]=1;
	for(int i=2;i<=200000;i++)
	{
	for(int j=1;j<=sqrt(2*i)+1;j++)
	{
	if(j*(j+1)/2>i) break;
	if(j*(j+1)/2==i) dp[i]=min(dp[i],j);
	dp[i]=min(dp[i],dp[i-(j*(j+1)/2)]+j+1);
	}
	}
	}
	signed main()
	{
	pre();
	int t=read();
	while(t-->0)
	{
	int n=read();
	cout<<dp[n]<<endl;
	}
	return _123hh2;
	}

# F 小红的 01 串（hard）

$E$ 题升级版，但升级在哪里？

在 $E$ 的基础上维护一个 $str$ 数组表示可能的构造方案

状态转移是一样的

	#include<bits/stdc++.h>
	#define int long long
	#define in inline
	#define ri register
	#define _123hh2 0
	using namespace std;
	in int read()
	{
	int x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
	const int maxn=2e5+5;
	int dp[maxn];
	string str[maxn];
	void pre()
	{
	memset(dp,0x3f,sizeof(dp));
	dp[0]=0,dp[1]=1;
	str[0]="",str[1]="1";
	for(int i=2;i<=200000;i++)
	{
	int pre=-1,J=-1;
	for(int j=1;j<=sqrt(2*i)+1;j++)
	{
	if(j*(j+1)/2>i) break;
	if(j*(j+1)/2==i)
	{
	if(dp[i]>j) dp[i]=j,pre=0,J=j;
	}
	if(dp[i-(j*(j+1)/2)]+j+1<dp[i])
	{
	dp[i]=dp[i-(j*(j+1)/2)]+j+1;
	pre=i-(j*(j+1)/2),J=j;
	}
	}
	if(pre==-1) continue;
	str[i]=str[pre];
	if(pre==0) for(int j=1;j<=J;j++) str[i]+="1";
	else
	{
	str[i]+="0";
	for(int j=1;j<=J;j++) str[i]+="1";
	}
	}
	}
	signed main()
	{
	pre();
	int t=read();
	while(t-->0)
	{
	int n=read();
	cout<<str[n]<<endl;
	}
	return _123hh2;
	}

# G 小红的双排列查询

典题，对于找一个区间有多少不同的出现且仅出现两次的数，可以用莫队 / 前缀和 + 树状数组 / 随机化哈希

这里提供随机化哈希的做法

	#include<bits/stdc++.h>
	#define int long long
	#define in inline
	#define ri register
	#define _123hh2 0
	using namespace std;
	in int read()
	{
	int x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
	const int maxn=3e5+5;
	const int mod=1e9+7;
	int awa[maxn];
	int qzh[maxn],qzpfh[maxn],qzlfh[maxn];
	int cal1[maxn],cal2[maxn],cal3[maxn];
	int Xor[maxn];
	int st[21][maxn];
	void pre(int n)
	{
	int t=log2(n)+1;
	for(ri int i=1;i<=n;i++) st[0][i]=awa[i];
	for(ri int i=1;i<t;i++)
	{
	for(ri int j=1;j<=n-(1<<i)+1;j++)
	{
	st[i][j]=max(st[i-1][j],st[i-1][j+(1<<(i-1))]);
	}
	}
	}
	in int query(int l,int r) {int k=log2(r-l+1);return max(st[k][l],st[k][r-(1<<k)+1]);}
	void deal(int l,int r)
	{
	vector<int> q;
	for(int i=l;i<=r;i++) q.push_back(awa[i]);
	sort(q.begin(),q.end());
	int f=0;
	for(int i=0;i<q.size();i+=2)
	{
	if(q[i]==q[i+1]&&q[i]==i/2+1) ;
	else {f=1;break;}
	}
	if(!f) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	}
	signed main()
	{
	int n=read(),q=read();
	for(int i=1;i<=n;i++)
	{
	awa[i]=read();
	qzh[i]=qzh[i-1]+awa[i];
	qzpfh[i]=qzpfh[i-1]+awa[i]*awa[i];
	qzlfh[i]=qzlfh[i-1]+awa[i]awa[i]awa[i];
	qzlfh[i]%=mod;
	Xor[i]=Xor[i-1]^awa[i];
	}
	pre(n);
	for(int i=1;i<=n;i++)
	{
	cal1[i]=cal1[i-1]+i*2;
	cal2[i]=cal2[i-1]+ii2;
	cal3[i]=cal3[i-1]+iii*2;
	cal3[i]%=mod;
	}
	while(q-->0)
	{
	int l=read(),r=read();
	if(((r-l+1)&1)\|\|(Xor[r]^Xor[l-1])!=0\|\|query(l,r)!=(r-l+1)/2) {cout<<"No"<<endl;continue;}
	if(n<=1000) {deal(l,r);continue;}
	if(qzh[r]-qzh[l-1]!=cal1[(r-l+1)/2]) {cout<<"No"<<endl;continue;}
	if(qzpfh[r]-qzpfh[l-1]!=cal2[(r-l+1)/2]) {cout<<"No"<<endl;continue;}
	if((qzlfh[r]-qzlfh[l-1]+mod)%mod!=cal3[(r-l+1)/2]) {cout<<"No"<<endl;continue;}
	cout<<"Yes"<<endl;
	}
	return _123hh2;
	}

Construction DP Simulation NowCoder Randomized Algorithm