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;
}