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