社区讨论

关于abcE题

LLiQXing
学术版参与者 3已保存回复 10

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
10 条
当前快照
1 份
快照标识符
@lo1ywqw0
此快照首次捕获于
2023/10/23 05:15
2 年前
此快照最后确认于
2023/11/03 05:39
2 年前
查看原帖
写了两种做法，
一种是提前算出每次操作会增加多少个一，直接加在ans 上面，然后根据每次删除的数，更改每次增加的一的数量。只能对12个点
CPP
int n;
string a;
int ans;
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>a;
	up(i,0,a.size()-2){
		if(a[i]!='1'&&a[i+1]!='1'){
			cout<<-1;
			exit(0);
		}
	}
	int sum=0;
	up(i,0,a.size()-2){
		if(a[i]=='1'&&a[i+1]!='1')sum=(sum+a[i+1]-'1')%mod;
	}
	ans=a.size()-1;
	dn(i,a.size()-1,1){
		ans=(ans+sum)%mod;
		sum=(sum-(a[i]-'1'));
	}
	cout<<ans;
	return 0;
}
然后又写了一个递推的做法，感觉本质上是一样的，却能对。
CPP
int n;
string a;
int ans;
int f[N];
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>a;
	up(i,0,a.size()-2){
		if(a[i]!='1'&&a[i+1]!='1'){
			cout<<-1;
			exit(0);
		}
	}
	f[n-1]=1;
	dn(i,n-2,0){
		f[i]=(f[i+1]*(a[i+1]-'0')+1)%mod;
	}
	if(a[0]=='1')cout<<f[0]-1<<endl;
	else cout<<f[1];
	return 0;
}

回复

共 10 条回复，欢迎继续交流。

正在加载回复...