AtCoder Beginner Contest 418 - AtCoder题解 | 123hh2 = Keep moving forward

# AtCoder Beginner Contest 418

比赛链接

模拟即可

	#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();
	string awa;
	cin>>awa;
	if(awa.size()<3)
	{
	cout<<"No";
	return 0;
	}
	int len=awa.size();
	string qwq="";
	qwq+=awa[len-3];
	qwq+=awa[len-2];
	qwq+=awa[len-1];
	if(qwq=="tea") cout<<"Yes";
	else cout<<"No";
	return _123hh2;
	}

枚举区间计算答案取 $\max$

	#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()
	{
	double ans=0;
	string awa;cin>>awa;
	for(int i=0;i<awa.size();i++)
	{
	int f=0;
	if(awa[i]!='t') continue;
	for(int j=i;j<awa.size();j++)
	{
	if(awa[j]=='t') f++;
	if(j-i+1>=3&&awa[i]==awa[j])
	{
	ans=max(ans,(f-2.0)/(double)(j-i-1));
	}
	}
	}
	cout<<fixed<<setprecision(10)<<ans;
	return _123hh2;
	}

对于每个询问 $x$ ，对方肯定至少先把所有的茶包拿出不多于 $x-1$ 个，然后再拿出一个之后才能满足我方至少能选出 $x$ 个不同的茶包

将每种茶包按数量排序后，二分找到最大的小于 $x$ 的茶包数量，比 $x$ 小的可以前缀和计算，然后加上大于等于 $x$ 的茶包种类乘上 $x-1$ ，最后 $+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=3e5+5;
	struct A
	{
	int val,id;
	}awa[maxn];
	int qzh[maxn];
	bool cmp(A x,A y)
	{
	if(x.val==y.val) return x.id<y.id;
	else return x.val<y.val;
	}
	signed main()
	{
	int n=read(),q=read();
	for(int i=1;i<=n;i++) awa[i].id=i,awa[i].val=read();
	sort(awa+1,awa+1+n,cmp);
	for(int i=1;i<=n;i++) qzh[i]=qzh[i-1]+awa[i].val;
	while(q-->0)
	{
	int x=read();
	int l=1,r=n,ans=0;
	while(l<=r)
	{
	int mid=(l+r)/2;
	if(awa[mid].val<x) ans=mid,l=mid+1;
	else r=mid-1;
	}
	if(ans==n) cout<<-1<<endl;
	else cout<<(qzh[ans])+(n-ans)*(x-1)+1<<endl;
	}
	return _123hh2;
	}

由于有

$0+0=1、0+1=0、1+0=0、1+1=1$

不难发现任意操作顺序不改变最终答案

不妨设 $dp[i][0/1]$ 表示以位置 $i$ 结尾时，答案为 $0/1$ 的方案数

那么转移就是

$string[i]==1$ 时 $dp[i][0]=dp[i-1][0],dp[i][1]=dp[i-1][1]+1$

$string[i]==0$ 时 $dp[i][1]=dp[i-1][0],dp[i][0]=dp[i-1][1]+1$

最终答案就是所有的 $dp[i][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][2];
	signed main()
	{
	int n=read();
	string awa;
	cin>>awa;
	awa=" "+awa;
	dp[1][0]=(awa[1]=='0');
	dp[1][1]=(awa[1]=='1');
	int ans=dp[1][1];
	for(int i=2;i<=n;i++)
	{
	if(awa[i]=='1') dp[i][0]=dp[i-1][0],dp[i][1]=dp[i-1][1]+1;
	else dp[i][1]=dp[i-1][0],dp[i][0]=dp[i-1][1]+1;
	ans+=dp[i][1];
	}
	cout<<ans;
	return _123hh2;
	}