codeforces round #805 ABCDEFG

文章目录

直接模拟即可

#include
// #pragma GCC optimize(2)
using namespace std;
typedef long long ll;
ll solve(){
	string s;
	cin>>s;
	s[0]-=1;
	while(s[0]=='0'&&s.size()!=1) s.erase(s.begin());
	cout<
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	system("pause");
}

使用set存储出现过的字符，当set的大小等于3时，答案加一

在这里插入代码片`#include
// #pragma GCC optimize(2)
using namespace std;
typedef long long ll;
ll solve(){
	string s;
	cin>>s;
	int res=1;
	setse;
	for( int i=0;i
		if(se.count(s[i])) continue;
		else{
			if(se.size()==3){
				res++;
				se.clear();
			}
			se.insert(s[i]);
		}
	}
	return res;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		cout< 
C 
找到每个数值最早的出现位置和最晚的出现位置，对于询问（x,y），如果x的最早出现位置大于y的最晚出现位置则输出yes，反之输出no 
#include
// #pragma GCC optimize(2)
using namespace std;
typedef long long ll;
//check whether x is behind y
ll solve(){
	int n,k;
	cin>>n>>k;
	mapminn,maxx;
	vectorv(n);
	for( int i=0;i
		cin>>v[i];
	}
	for( int i=0;i
		maxx[v[i]]=max(maxx[v[i]],i);
		if(minn.count(v[i])==0) minn[v[i]]=i;
		else minn[v[i]]=min(minn[v[i]],i);		
	}
	for( int i=0;i
		int x,y;
		cin>>x>>y;
		if(minn.count(x)==0||minn.count(y)==0) cout<<"NO"<<"n";
		else{
			if(minn[x]
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	system("pause");
}
 
D 
直接模拟即可，既从价值最高的字符开始，看是否可以删除。 
#include
// #pragma GCC optimize(2)
using namespace std;
typedef long long ll;
ll solve(){
	string s;
	int p;
	cin>>s>>p;
	int val=0;
	vectorcnt(26);
	for( int i=0;i
		val+=s[i]-'a'+1;
		cnt[s[i]-'a']+=1;
	}
	for( int i=25;i>=0;i--){
		if(val-cnt[i]*(i+1)>p){
			val-=cnt[i]*(i+1);
			cnt[i]=0;
		}
		else {
			int sum=cnt[i];
			while(val-(sum-cnt[i])*(i+1)>p) cnt[i]--;
			break;
		}
	}
	string res;
	for( int i=0;i
		if(cnt[s[i]-'a'])res+=s[i],--cnt[s[i]-'a'];
	}
	cout<
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	system("pause");
}
 
E 
这种集合划分的问题，一般可以转化成图来求解，类似的有二分图匹配，网络流问题。
 对于此问题，可以将所给的数据抽象成一张图，对于点对（x,y），在图中对应一条边。
 若使问题成立，需要满足以下条件： 
首先，每个数字出现且仅出现两次，既转换后的图是一个所有点度均为2的图。
若1成立，则易证，整张图由若干个环组成，即每个点在且仅在一个环中。
在2的基础上，只需要检查每个环是否由偶数个点构成即可。（不理解可以举例或作图试一下） 
#include
// #pragma GCC optimize(2)
using namespace std;
typedef long long ll;
ll solve(){
	int n;
	cin>>n;
	vector>v(n);
	vector>g(n);
	for( int i=0;i
		cin>>v[i].first>>v[i].second;
		v[i].first--,v[i].second--;
		int x=v[i].first,y=v[i].second;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	vectordeg(n);
	for( auto it:v){
		if(it.first>=n||it.second>=n) return false;
		else{
			deg[it.first]++;
			deg[it.second]++;
		}
	}
	for( auto it:deg){
		if(it!=2) return false;
	}
	vectorvis(n);
	auto dfs=[&](auto self, int rt )->int{
		vis[rt]=1;
		int res=1;
		for( auto it:g[rt]){
			if(vis[it]) continue;
			res+=self(self,it);
		}
		return res;
	};
	for( int i=0;i
		if(!vis[i]){
			int x=dfs(dfs,i);
			if(x%2) return false;
		}
	}
	return true;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		if(solve()) cout<<"YES"< 
F 
首先，不论是a或者是b，若其中的某个数x是偶数，则将x替换为x/2不会对答案造成影响，因此，将ab数组进行预处理，将偶数变为奇数。
 之后使用贪心算法，从大到小遍历b中的每个数（假设当前遍历到的数为x），看是否在a中出现，若出现，则将其从a中删除。反之，则令x=x/2，并再次查看。 
#include
// #pragma GCC optimize(2)
using namespace std;
typedef long long ll;
ll solve(){
	int n;
	cin>>n;
	vectora(n),b(n);
	for( int i=0;i
		cin>>a[i];
		while(a[i]%2==0) a[i]/=2;
	}
	for( int i=0;i
		cin>>b[i];
		while(b[i]%2==0) b[i]/=2;
	}
	sort(a.begin(),a.begin()+n);
	sort(b.begin(),b.begin()+n);
	multisetse;
	for( auto it:a){
		se.insert(it);
	}
	for( int i=b.size()-1;i>=0;i--){
		int x=b[i];
		while(x){
			auto it=se.find(x);
			if(it==se.end()){
				x/=2;
				continue;
			}
			else {
				se.erase(it);
				break;
			}
		}
	}
	if(se.empty()) return true;
	else return false;
	
}
int main(){
	int t;
	cin>>t;
	while(t--){
		if(solve()) cout<<"YES"< 
G 
本题我是用的是倍增法LCA求解，也有另一种做法，cf上有大佬使用dfs序查看一个点是否为另一个点的祖先。
 这里只讲倍增LCA的做法。 
对于一个集合，如果其满足题目中的条件（是一个passable集合），那么在树上来看，这个集合的所有数一定分布在一条链上（有些抽象，可以画图看一下）。 
由于集合是无序的，为了让问题更好解决，可以按照每个点的高度（到根的距离）排序。之后找到距离跟最近的结点，用这个结点为根部，还原整条链。 
还原的方法是：将整条链看成两条链的拼接，从高度较小的点（离根近）向高度较大的点遍历，然后将每个点加入到两条链中的一条。 
注意，本题有一种情况需要特殊判断，即集合呈现出“人”字形，这种情况在题目的样例中也有出现，需要特殊处理，对应代码中的check函数的倒数第二句。 
#include
// #pragma GCC optimize(2)
using namespace std;
typedef long long ll;
int main(){
	int n;
	cin>>n;
	vector>tr(n+1);
	for( int i=0;i
		int x,y;
		cin>>x>>y;
		tr[x].push_back(y);
		tr[y].push_back(x);
	}
	vectorh(n+1);
	auto get_h=[&](auto self,int rt,int fa)->void{
		h[rt]=h[fa]+1;
		for( auto it:tr[rt]){
			if(it==fa) continue;
			self(self,it,rt);
		}
	};
	get_h(get_h,1,0);
	vector>lca(n+1,vector(18));
	auto get_lca=[&](auto self,int rt,int fa)->void{
		lca[rt][0]=fa;
		for( int i=1;i<18;i++){
			lca[rt][i]=lca[lca[rt][i-1]][i-1];
		}		
		for( auto it:tr[rt]){
			if(it==fa) continue;
			self(self,it,rt);
		}	
	};
	get_lca(get_lca,1,0);
	auto LCA=[&](int x,int y)->int{
		if(h[x]>h[y]) swap(x,y);
		for( int i=17;i>=0;i--){
			if(h[lca[y][i]]>=h[x]) y=lca[y][i]; 
		}
		if(x==y) return x;
		for( int i=17;i>=0;i--){
			if(lca[x][i]!=lca[y][i]){
				x=lca[x][i];y=lca[y][i];
			}
		}
		return lca[x][0];
	};
	auto check=[&]()->int{
		int n;
		cin>>n;
		vector>v(n);
		for( int i=0;i
			cin>>v[i].second;
			v[i].first=h[v[i].second];
		}
		sort(v.begin(),v.begin()+n);
		int h1=v[0].second,t1=v[0].second;
		int h2=0,t2=0;
		for( int i=1;i
			int b=v[i].second;
			if(LCA(b,t1)==t1){
				t1=b;
			}
			else if(h2==0){
				h2=t2=b;
			}
			else if(LCA(b,t2)==t2){
				t2=b;
			}
			else return false;
		}
		if(h2!=0&&LCA(t1,t2)!=h1&&LCA(LCA(t1,t2),h1)==h1) return false;
		return true;
	};
	int t;
	cin>>t;
	while(t--){
		if(check()) {
			cout<<"YES"<<"n";
		}
		else {
			cout<<"NO"<<"n";
		}
	}
	
	system("pause");
}

                
                
                
        
        

  
    
      
        
      
      
        
          暑期编程PK赛
          
        
        得CSDN机械键盘等精美礼品！

codeforces round #805 ABCDEFG

C/C++/C#相关栏目本月热门文章