C/C++教程

Codeforces Round #785 (Div. 2)

本文主要是介绍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)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航