关于abcE题
查看原帖
关于abcE题
750240
Hellsing_Alucard楼主2023/8/5 21:45

写了两种做法,

一种是提前算出每次操作会增加多少个一,直接加在ans 上面,然后根据每次删除的数,更改每次增加的一的数量。只能对12个点

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;
}

然后又写了一个递推的做法,感觉本质上是一样的,却能对。

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;
}
2023/8/5 21:45
加载中...