Codeforces Round #785 (Div. 2)

2022/5/2 23:46:28

编程Tag： div int long define DP void Codeforces Solve 785

本文主要是介绍Codeforces Round #785 (Div. 2)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

由于鄙人能力有限只做了三道题

签到题没啥好说的

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=5e4+5; 
void solve();
int main(){
	int T;cin>>T;
	while(T--)solve();
     return 0;
}
void solve(){
	string s;
	cin>>s;
	ll sum=0,len=s.size();
	for(int i=0;i<len;i++)
	sum+=(s[i]-'a'+1);
	if(!(len&1))
		cout<<"Alice "<<sum<<endl;
	else {
		int minn=min(s[0]-'a',s[len-1]-'a')+1;
		//cout<<"minn="<<minn<<endl;
		if(minn>sum-minn)
			cout<<"Bob "<<minn<<endl;
		else cout<<"Alice "<<sum-2*minn<<endl;
	}
}

这种字符串出现次数类的题目一般都是维护一个last数组表示该字符前一个出现的位置在哪

通过观察发现如果一个字符前后位置差小于该字符串所有出现字符的个数

选择这个子串那么一定会出现至少有一个字符出现0次但是当前字符出现了两次

所以依次判断就好

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
int T;
map<char,int>mp;
void solve();
int main(){
	cin>>T;
	while(T--)solve();
     return 0;
}
void solve(){
	string s;
	cin>>s;
	int len=s.size(),tot=0;
	mp.clear();
	for(int i=0;i<len;i++)
	if(!mp.count(s[i]))mp[s[i]]=1,tot++;
	tot++;
	mp.clear();
	for(int i=0;i<len;i++){
		if(!mp.count(s[i]))mp[s[i]]=i;
		else {
			if(i-mp[s[i]]+1<tot)
			{
				cout<<"NO"<<endl;
				return ;
			}else mp[s[i]]=i;
		}
	}
	cout<<"YES"<<endl;
}

这个题和整数分解很像不过就是多了一个组成的数是回文数这个条件

推荐一个很好的整数分解的：

https://www.cnblogs.com/wzxbeliever/p/16063096.html

这个题多的就是要找到比n小的最大的数假设为t 输出dp[n][t]就好

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=4e4+5;
const int mod=1e9+7;
ll dp[maxn][500];
int a[6],n;
vector<int>Q;
void ck(int);
void calc();
int main(){
	int T;
	cin>>T;
	Q.push_back(0);
	for(int i=1;i<=4e4;i++)
	ck(i);
	calc();
	while(T--){
		scanf("%d",&n);
		int t,L=1,R=Q.size()-1;
		while(L<=R){
			int mid=L+R>>1;
			if(Q[mid]<=n)t=mid,L=mid+1;
			else R=mid-1;
		}
		printf("%lld\n",dp[n][t]);
	}
     return 0;
}
void ck(int now){
	int cnt=0,x=now;
	while(x)a[++cnt]=x%10,x/=10;
	for(int i=1;i<=(cnt/2);i++)
	if(a[cnt-i+1]!=a[i])return;
	Q.push_back(now);
}
void calc(){
	for(int i=1;i<=4e4;i++){
		int pp=1,tt;
		for(int j=1;j<Q.size();j++){
			int to=Q[j];
			if(i>=to&&pp)tt=j;
			else pp=0;
			if(i<to)
				dp[i][j]=dp[i][tt];
			else if(i>to)
			dp[i][j]=(dp[i-to][j]+dp[i][j-1])%mod;
			else dp[i][j]=(dp[i][j-1]+1)%mod;
		}
	}
}

这篇关于Codeforces Round #785 (Div. 2)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Codeforces Round #785 (Div. 2)

相关编程文章