AtCoder Beginner Contest 391（A~E题题解）

A - Lucky Direction

思路：纯模拟的一个水题

#include <bits/stdc++.h>  
using namespace std;  
#define int long long  
string s;
signed main() 
{   cin>>s;for(int i=0;i<s.size();i++){char c=s[i];if(c=='N'){cout<<"S";}else if(c=='S'){cout<<"N";}else if(c=='E'){cout<<"W";}else if(c=='W'){cout<<"E";}
}return 0;  
}

 B - Seek Grid

思路：数据很小，直接写一个n的四次方的代码即可，暴力模拟

#include <bits/stdc++.h>  
using namespace std;  
#define int long long  
char a[55][55];
char b[55][55];
signed main() 
{   int n,m;cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>a[i][j];}}for(int i=1;i<=m;i++){for(int j=1;j<=m;j++){cin>>b[i][j];}}for(int i=1;i<=n-m+1;i++){for(int j=1;j<=n-m+1;j++){if(a[i][j]==b[1][1]){int flag=1;for(int k=i;k<=i+m-1;k++){for(int l=j;l<=j+m-1;l++){if(a[k][l]!=b[k-i+1][l-j+1]){flag=0;break;}}}if(flag==1){cout<<i<<" "<<j<<"\n";return 0;}}}}return 0;  
}

 C - Pigeonhole Query

 思路：我们可以用cnt数组去统计每个鸽巢的鸽子的数量，如果变成2，则大于1的鸽巢数量+1，如果减去变成1则大于1的鸽巢数量-1

最终即为结果

#include <bits/stdc++.h>  
using namespace std;  
#define int long long  
int n;
int q;
int flag;
int p,h;
int cnt[1000005];
map<int,int> mp;//鸽子~鸽巢 
signed main() 
{   cin>>n;for(int i=1;i<=n;i++){cnt[i]=1;mp[i]=i;}cin>>q;int ans=0;for(int i=1;i<=q;i++){cin>>flag;if(flag==1){cin>>p>>h;cnt[mp[p]]--;if(cnt[mp[p]]==1)ans--;mp[p]=h;cnt[h]++;if(cnt[h]==2)ans++;}else{cout<<ans<<"\n";}}return 0;  
}

 D - Gravity

 思路：我们可以将思路转变一下，先去求出每个方块的消除时间，然后去比对他问的时间，如果消除时间小于提问的时间就是已经被消除了，否则就是还在

我们可以去统计每一列都有多少方块，那么能消除的行数，也就是每一列方块的最小个数，这个应该都能理解吧

那我们同理应该能明白，每一行删除都是一个特定的时间，当前行内的方块的最高的高度，就是当前行的删除时间

一但出现某一列的方块为0，就结束循环，因此我们应当注意上面红字还有一个特判如果消除时间为0，那就证明一直没有被消除，因此也是yes

#include <bits/stdc++.h>  
using namespace std;  
#define int long long  
int n,w;
int q;
int t,a;
int x,y;
vector<pair<int,int>> col[200005];//表示每一列的每一行在什么位置 
int te[200005];//表示每个方块消失的时间 
signed main() 
{   cin>>n>>w;for(int i=1;i<=n;i++){cin>>x>>y;col[x].push_back(make_pair(y,i));}for(int i=1;i<=w;i++){sort(col[i].begin(),col[i].end());}for(int k=1;k<=n;k++)//第k次消除{int maxn=0;for(int i=1;i<=w;i++){if(col[i].size()<k){maxn=-1;break;}maxn=max(maxn,col[i][k-1].first);;}if(maxn==-1)break;for(int i=1;i<=w;i++){te[col[i][k-1].second]=maxn;}}cin>>q;for(int i=1;i<=q;i++){cin>>t>>a;if(te[a]==0||t<te[a]){cout<<"Yes\n";}else{cout<<"No\n";}}return 0;  
}

E - Hierarchical Majority Vote

思路：我们可以将这道题看做是一个树上dp的问题，每个父节点都有三个子节点，然后从根节点向下深搜，再将结果返回根节点即可

我们来看定义dp[i][j]表示i结点变换为j这个数，所需要的最小操作数 ，我们在统计父节点的时候，如果想让这个点为1只需要有两个点为1即可，如果为0，就只需要两个点为0即可，因此我们在统计当前点颜色为c的时候，只要将这几个点的颜色变为c的情况累加起来，并且减去最大的这个价值即可

ans[i]表示i点在没有经过操作的时候应当为的数字

然后最后输出dp[root][ans[root]^1]即可，root为根节点

#include <bits/stdc++.h>  
using namespace std;  
#define int long long  
int n,len;
string s;
vector<int> e[5000005];//存储每个的子节点 
int dp[5000005][2];//dp[i][j]表示将下标为i的点变为j所需的最小操作次数 
int ans[5000005];//原本应该的结果 
void dfs(int v)
{if(v<=n){if(s[v]=='1'){dp[v][0]=1;}else{dp[v][1]=1;}ans[v]=s[v]-'0';return;}int cnt=0;for(int u:e[v]){dfs(u);cnt+=ans[u];}if(cnt>=2){ans[v]=1;}else{ans[v]=0;}for(int c=0;c<=1;c++){int sum=0;int maxn=0;for(int u:e[v]){sum+=dp[u][c];maxn=max(maxn,dp[u][c]);}dp[v][c]=sum-maxn;}
}
signed main() 
{   cin>>n;cin>>s;n=s.size();len=n;s=" "+s;for(int i=1;i+2<=len;i+=3){len++;e[len].push_back(i);e[len].push_back(i+1);e[len].push_back(i+2);} dfs(len);cout<<dp[len][ans[len]^1];return 0;  
}