Codeforces Round 911 (Div. 2)

A. Cover in Water

题意：

有n个单元格，有的空着有的被堵住，可以做两种操作：给一个空着的单元格放入水；将单元格的水移到另一个单元格。并且，若一个单元格左右两边都有水，它也会自动充满水。所有空着的单元格都要充满水，求最少的放入水的次数

思路：

若存在三个空着的单元格，则可以放入两次水实现水的无限再生
（类似于minecraft中三格水可以实现无限水的操作）

代码：

#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define endl "\n"

void solve(){
	int n;
    cin>>n;
    string s;
    cin>>s;
    int ans=0;
    int count=0;
    for(int i=0;i<n;i++){
        if(s[i]=='.'){
            count++;
            ans++;
        }else{
            if(count>=3){
                cout<<2<<endl;
                return ;
            }
            count=0;
        }
    }
    if(count>=3){
        cout<<2<<endl;
    }else
    cout<<ans<<endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t=1;
	
	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}

B. Laura and Operations

题意：

黑板上有三个数字123，有a个1，b个2，c个3，可以做操作：擦去1和2，写上3也可以同理写上1和2,请问是否能通过操作实现黑板上只有1或者只有2或者只有3

思路：

假设要实现黑板上只有1，可以将2和3抵消来生成1，可能还会剩余k个3，此时将一个1和一个3生成一个2，这个2和一个3生成回到一个1同时这个操作消耗掉了两个3，所以只要k是个偶数就能够实现

代码：

#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define endl "\n"

void solve(){
	int a,b,c;
    cin>>a>>b>>c;
    int num=max(b,c)-min(b,c);
    if(num%2==1){
        cout<<0<<" ";
    }else{
        cout<<1<<" ";
    }
    
    num=max(a,c)-min(a,c);
    if(num%2==1){
        cout<<0<<" ";
    }else{
        cout<<1<<" ";
    }

    num=max(b,a)-min(b,a);
    if(num%2==1){
        cout<<0<<" ";
    }else{
        cout<<1<<" ";
    }
    cout<<endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t=1;
	
	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}

C. Anji's Binary Tree

题意：

有一棵二叉树，每个节点有一个字母，U代表前往父节点，L代表前往左孩子，R代表前往右孩子，从节点1出发，通过修改几个节点的字母来到达叶子节点，求修改的最小次数

思路：

树上bfs,\(d_i\)代表到达节点最少要几次修改操作

代码：

#include <bits/stdc++.h>
using namespace std ;
const int MAXN=3e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define endl "\n"

int n;
string s;

struct node{
    int l,r;
}vertex[MAXN];

int ans;

void bfs(int t){
    queue <int > q;
    while(!q.empty()){
        q.pop();
    }
    q.push(t);
    int d[n+1];
    d[t]=0;
    while(!q.empty()){
        int st=q.front();
        q.pop();
        if(vertex[st].l==0&&vertex[st].r==0){
            ans=min(ans,d[st]);
            continue;
        }
        if(vertex[st].l>0){
            int tt=vertex[st].l;
            q.push(tt);
            if(s[st-1]!='L'){
                d[tt]=d[st]+1;
            }else{
                d[tt]=d[st];
            }
        }
        if(vertex[st].r>0){
            int tt=vertex[st].r;
            q.push(tt);
            if(s[st-1]!='R'){
                d[tt]=d[st]+1;
            }else{
                d[tt]=d[st];
            }
        }
    }
}

void solve(){
    cin>>n;
    cin>>s;
    int x,y;
    for(int i=1;i<=n;i++){
        cin>>x>>y;
        vertex[i].l=x;
        vertex[i].r=y;
    }
    ans=INF;
    bfs(1);
    cout<<ans<<endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t=1;
	
	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}