[数据结构与算法][cf] Codeforces Round #787 (Div. 3) FG待补

前言

传送门 :

A.

题意 :
给定$a$个狗粮,$b$个猫粮,$c$个杂粮
询问$x$只狗,$y$只猫是否可以都有吃的

思路 :
小学数学
Code :

void solve(){
	cin>>a>>b>>c>>x>>y;
	
	x-=a;
	y-=b;
	
	// cout<<x<<"/**/ "<<y<<" "<<c<<endl;
	x = max(0,x);
	y = max(0,y);
	
	if(x + y > c){
		cout<<"NO"<<endl;
		return;
	}
	
	cout<<"YES"<<endl;
	
}

B.

题意 :
给定一个长度$n$的数组$a[]$,询问是否可以在操作之后将数组变为严格上升的

思路 :
因为数据范围很小,考虑暴力

因为$/2$,使得$a[i]$变小

因此如果考虑从前往后枚举,会影响后面的操作,因此我们考虑从后往前枚举

对于$a[i]>=a[i+1]$,我们显然需要将$a[i]/2$直到$a[i]<a[i+1]$

那么什么时候停止呢 ?,因为数据都是正数

所以显然的当数据中有两个或者以上个$0$ 的时候必然是不行的

因此我们只需要判断这个即可,最后没开$ll$寄了一发

code :

const int N = 40;
ll a[N],n,b[N];


void solve(){
	cin>>n;
	for(int i=1;i<=n;i ++ ) cin>>a[i];
	
	//判断是否是严格
	int flag = 0 ;
	
	for(int i=2;i<=n;i++){
		if(a[i] <= a[i-1]){
			flag = 1;
			break;
		}
	}	
	
	if(!flag){
		cout<<0<<endl;
		return;
	}
	
	int ans = 0 ;
	
	a[n+1] = 1e12;
	
	//a[0] = 0;
	int cnt = 0 ;
	
	for(int i=n;i>=1;i--){
		while(a[i] >= a[i+1]){
			a[i]/=2;
			if(a[i] == 0 ){
				++cnt;
				if(cnt >= 2){
					cout<<-1<<endl;
					return;
					
				}				
				// cout<<-1<<endl;
				// return;
			}
			++ans;
		}
	}
	cout<<ans<<endl;
	
	
}

C.

题意 :
给定一个字符串含有$0,1,?$

• $0$,表示画不在了
• $1$,表示画还在
• $?$,表示不清楚

询问小偷的数量

思路 :
同样的因为时间复杂度保证了能在$t?n$的情况下做完

因此我们考虑枚举当前$i$为小偷,如果他是小偷的画

显然的 后面必然不存在$1$,前面必然不存在$0$

因此 前缀和+枚举即可

(编译器处理字符串的时候报错了,气死

Code :

const int N = 2e5+10;
int c1[N] ,c0[N] ,cc[N];

void solve(){
	string s;cin>>s;
	s = " "+s;
	
	int n = s.size();
	
	memset(c1,0,sizeof c1);
	memset(cc,0,sizeof cc);
	memset(c0,0,sizeof c0);
	
	/**
	1. 如果是小偷的话,后面必然不存在1,前面也必然不存在0 
	0. 如果是小偷的话,后面必然不存在1,前面也不存在0
	?  如果是小偷的话 后面必然不存在1,前面也不存在0
	**/
	
	for(int i=1;i<=n;i++){
		if(s[i] == '?') cc[i] = 1;
		else if(s[i] == '0') c0[i] = 1;
		else if(s[i] == '1') c1[i] = 1;
		cc[i] += cc[i-1];
		c0[i] += c0[i-1];
		c1[i] += c1[i-1];
		
	}
	
	int ans = 0 ;

	for(int i=1;i<n;i++){
		if(c0[i-1] == 0 && c1[n] - c1[i] == 0 ) ++ans;
	}
	
	cout<<ans<<endl;
	
	
	
}

D.

题意 :
给定一棵树,询问将其分为最少的链,并且输出链的个数和链上的节点

思路 :
首先,歪了一会树的直径

但是冷静思考之后,会发现,链的个数其实是确定的,就是叶子节点的个数

因为每个链最多只包含一个叶子节点

所以我们考虑从叶子节点开始往上找

因为叶子节点决定链的数量 同时又因为 根的不确定性

显然不管从哪里开始,虽然输出的结果不一样,但是答案都是正确的

具体操作, 并查集(非路径压缩) +枚举

Code :

const int N = 2e5+10;
vector<int> g[N];
int has_son[N];
int root;
int n;
vector<int> leaf;
int st[N];
int fa[N];


void clear(){
	for(int i=1;i<=n;i++)has_son[i] = 0 ;	
	leaf.clear();
	
	for(int i=1;i<=n;i++) st[i] = 0 ;
	
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		if(x == i){
			fa[x] = x;
			
			root = i ;
			continue;
		}
		// g[i].pb(x);
		fa[i] =  x;
		has_son[x] = 1;
	}
	
	
	int sz = 0 ;
	
	for(int i=1;i<=n;i++) if(!has_son[i])++sz,leaf.pb(i);
	cout<<sz<<endl;
	
	for(auto lf : leaf){
		vector<int> ans;
		

		int t = lf;
		while(1){
			if(st[t]) break;
			ans.pb(t);
			st[t] = 1;
			t = fa[t];
		}
		
		cout<<ans.size()<<endl;
		reverse(all(ans));
		for(auto x : ans)
		cout<<x<<" ";
		cout<<endl;
	}
	
	cout<<endl;
	
	
	clear();
}

E.

题意 :
给定一个长度为$n$的字符串,询问在完成最多$k$次操作之后,字典序最少的答案是什么

操作定义如下 :
选中一个$a[i]$将所有$a[j]=a[i]$都令其$a[i]?1$

思路 :
显然这题,大家都有想法

大致暴力思路如下 :

1. 考虑前面的,能变成$a$就变成$a$
2. 暴力修改所有与$a[i]$相同的

显然时间复杂度是不允许直接暴力修改的

但是又因为最大的总是能带动最小的这个性质,我们可以对第二步进行优化

对于每次枚举的$i$,我们只需要找到第一个不能变为$a$的点即可

然后计算前面有多少个可以变成$a$的,同时判断有多少个不能变成$a$的

具体操作看代码

code :

void solve(){
	cin>>n>>k;
	string s;cin>>s;
	
 	int maxn = 0 ;
 	
 	for(int i = 0 ; i<n ; i++ ){
 		int need = s[i] - 'a'; 
 		
 		if(need > k){//显然已经不能 'a'  了
 		
 			int cc  = need - k + maxn; //剩余的
 			
 			for(int j = 0 ;j < n; j ++){
 				if(s[j] - 'a'  <= maxn) s[j] = 'a'; //如果能被前面的带动的话
 				else if(s[j] - 'a' <= need && s[j] - 'a' >= cc) s[j] = 'a'+ cc;
 			}
 			cout<<s<<endl;
 			return;
 		}
 		//
 		maxn = max(maxn,need); 		
 	}
 
 
 
    for (int i = 0; i < n; ++i)
    {
        cout << 'a';
    }
    cout<<endl;

    return ;
}

FG待补

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖