AtCoder Beginner Contest 303

A - Similar String

Problem Statement

题意：给你两个串判断是不是相似的。

相似：不一样的字符中1和l相似，0和o相似，一样的字符就肯定是相似的。

Solution

题解：按照题意模拟。

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	cin>>n;
	string s,t;
	cin>>s>>t;
	s = "?"+s;
	t = "?"+t;
	bool ok = true;
	for(int i = 1;i<=n;i++)
	{
		if(s[i]!=t[i])
		{
			if(s[i]=='0'&&t[i]=='o')continue;
			if(s[i]=='o'&&t[i]=='0')continue;
			if(s[i]=='1'&&t[i]=='l')continue;
			if(s[i]=='l'&&t[i]=='1')continue;
			ok = false;
			break;
		}
	}
	if(ok)cout<<"Yes\n";
	else cout<<"No\n";
	return 0;
}

B - Discord

Problem Statement

题意：判断有多少对人心情不好。

心情不好：两个人从来没站在过对方边上就说这对人心情不好。

Solution

题解：每出现一对用map记录。最后暴力for一下判断答案。

#include<bits/stdc++.h>
using namespace std;
const int N = 100;
map<pair<int,int>,int>mp;
int a[N][N];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i = 1;i<=m;i++)
	{
		for(int j = 1;j<=n;j++)
			cin>>a[i][j];
		for(int j = 1;j<=n;j++)
		{
			if(j==1)mp[{a[i][j],a[i][j+1]}]++,mp[{a[i][j+1],a[i][j]}]++;
			else if(j==n)mp[{a[i][j],a[i][j-1]}]++,mp[{a[i][j-1],a[i][j]}]++;
			else mp[{a[i][j],a[i][j-1]}]++,
				 mp[{a[i][j],a[i][j+1]}]++,
				 mp[{a[i][j-1],a[i][j]}]++,
				 mp[{a[i][j+1],a[i][j]}]++;
		}
	}
	int ans = 0;
	for(int i = 1;i<=n;i++)
	{
		for(int j = i+1;j<=n;j++)
		{
			if(mp[{i,j}]==0&&mp[{j,i}]==0)
				ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

C - Dash

Problem Statement

题意：给你一个二维平面，初始状态，在(0,0),生命值为H。有M个物资背放在平面上的一些点处，用于恢复生命值。当且仅当生命值严格小于K，才能用，用完物资之后，生命值恢复到K。

Solution

题解：模拟

#include<bits/stdc++.h>
using namespace std;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m,h,k;
string s;
map<pair<int,int>,int>mp;
int main()
{
	cin>>n>>m>>h>>k;
	cin>>s;
	for(int i = 1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		mp[{x,y}]++;
	}
	int x = 0,y = 0;
	bool ok = true;
	for(int i = 0;i<n;i++)
	{
		if(s[i]=='R')x+=1;
		if(s[i]=='L')x-=1;
		if(s[i]=='U')y+=1;
		if(s[i]=='D')y-=1;
		h--;
		if(h<0)
		{
			ok = false;
			break;
		}
		if(h<k&&mp[{x,y}])
			h = k,mp[{x,y}]--;
	
	}
	if(ok)cout<<"Yes\n";
	else cout<<"No\n";
	return 0;
}

D - Shift vs. CapsLock

Problem Statement

题意:键盘上有三个键：'a'和Shift和Caps Lock。

按每个键位有不同花费。

给出目标串，问你达到目标串的最小花费。

Solution

题解：记忆化搜索DP。

我们分类讨论一下：

设flag表示当前是否开了大写,c表示当前要输出的字符

花费:'a' = x，Shift+'a' = y，Caps Lock = z

定义：\(dp[idx][flag]\)为目前为第\(idx\)个字符，当前是否开了大写

状态：

①flag == true, c = ’A‘

min(x,z+y)

②flag == false,c = 'A'

min(y,z+x)

①flag == true, c = ’a‘

min(y,z+x)

②flag == false,c = 'a'

min(x,z+y)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5+10;
int  ans = 1e9;
ll dp[N][2];
int n;
int x,y,z;
string s;
ll dfs(int idx,int flag)
{	if(idx>n)
	{
		return 0ll;
	}
	ll &res = dp[idx][flag];
	if(~dp[idx][flag])return res;
	res = 0;
	if(s[idx]=='A'&&flag==1)
	{
		res = min(x+dfs(idx+1,1),z+y+dfs(idx+1,0));
	}
	else if(s[idx]=='A'&&flag== 0)
	{
		res = min(y+dfs(idx+1,0),z+x+dfs(idx+1,1));
	}
	else if(s[idx]=='a'&&flag==1)
	{
		res = min(y+dfs(idx+1,1),z+x+dfs(idx+1,0));
	}
	else if(s[idx]=='a'&&flag==0)
	{
		res = min(x+dfs(idx+1,0),z+y+dfs(idx+1,1));
	}
	return res;
}
int main()
{
	cin>>x>>y>>z;
	cin>>s;
	n = s.size();
	s = "?"+s;
	memset(dp,-1,sizeof(dp));
	cout<<dfs(1,0);
	return 0;
}

E - A Gift From the Stars

Problem Statement

题意：一个图有\(k+1\)个点和\(k\)条边称之为k星级，当且仅当它有一个点用一条边连接了其他\(k\)个点。

高桥对图进行以下操作：选择图中两个度数为1的且没有连接的点使得他们连起来。操作之后，它随机将\(1\)到\(N\)分配给图中每一个点，结果图是一棵树\(T\)。找到原来的图(连接之前的)，输出他们的星级。

Solution

题解：找菊花图。对于k级星星就是一个度数为\(k\)的点，向\(k\)个度数为\(1\)的点各连了一条边。我们发现，高桥在连接时，只会连接两个度数为1的点，那新连的点的度数\(<=2\)。

所以结论是：最后图中度数\(>2\)的点，它一定原本就是一个\(k\)级星星的中心，我们将所有这样的点以及与它们直接相邻的点归入\(k>=3\)级的星星后，剩下的点都属于\(2\)级的星星。到\(2\)级星星的有\(3\)个点，最后答案加入剩下的点除以\(3\)个\(2\)即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int d[N],cnt,a[N];
int main()
{
	int n;
	cin>>n;
	int s = n;
	for(int i = 1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		d[x]++,d[y]++;
	}
	for(int i = 1;i<=n;i++)
	{
		if(d[i]>2)
		{
			a[++cnt] =  d[i],s-=(d[i]+1);
		}
	}
	for(int i = 1;i<=s/3;i++)
		a[++cnt] = 2;
	sort(a+1,a+1+cnt);
	for(int i = 1;i<=cnt;i++)
		cout<<a[i]<<" ";
	return 0;
}