AtCoder Beginner Contest 264

A - "atcoder".substr()

Problem Statement

题意：截取字符串 atcoder的[L,R]一段并输出。

Solution

题解：

用string.substr直接写

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


int main()
{
	string s = "?atcoder";
	int l,r;
	cin>>l>>r;
	cout<<s.substr(l,r-l+1)<<endl;
	return 0;
}

B - Nice Grid

Problem Statement

题意：给你一个图，由黑白块组成。

给你一个坐标问你是黑的还是白的

Solution

思路：直接暴力模拟

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


int main()
{
	int n,m;
	cin>>n>>m;
	if(n==15||n==1||m==15||m==1)cout<<"black\n";
	else if(n==2||n==14)cout<<"white\n";
	else if(n==3||n==13)
	{
		if(m==2||m==14)cout<<"white\n";
		else cout<<"black\n";
	}
	else if(n==4||n==12)
	{
		if(m==3||m==13)cout<<"black\n";
		else cout<<"white\n";
	}
	else if(n==5||n==11)
	{
		if(m==2||m==4||m==14||m==12)cout<<"white\n";
		else cout<<"black\n";
	}
	else if(n==6||n==10)
	{
		if(m==3||m==5||m==13||m==11)cout<<"black\n";
		else cout<<"white\n";
	}
	else if(n==7||n==9)
	{
		if(m==2||m==4||m==6||m==10||m==12||m==14)cout<<"white\n";
		else cout<<"black\n";
	}
	else
	{
		if(n%2)cout<<"black\n";
		else cout<<"white\n";
	}

	return 0;
}

C - Matrix Reducing

Problem Statement

题意：给你两个矩阵，问你能否通过对第一个矩阵删除任意行和任意列得到第二个矩阵。

Solution

思路：数据范围只有10，直接暴力，二进制枚举选第一个矩阵的哪几个即可，再check是不是和第二个矩阵长得一样。

#include<bits/stdc++.h>
using namespace std;
const int N = 15;
int a[N][N],b[N][N];

int main()
{
	int h1,w1,h2,w2;
	cin>>h1>>w1;
	for(int i = 1;i<=h1;i++)
		for(int j = 1;j<=w1;j++)
			cin>>a[i][j];
	cin>>h2>>w2;
	for(int i = 1;i<=h2;i++)
		for(int j = 1;j<=w2;j++)
			cin>>b[i][j];
	for(int i = 0;i<(1<<h1);i++)
	{
		for(int j = 0;j<(1<<w1);j++)
		{
			vector<int>x,y;
			for(int k = 0;k<h1;k++)
				if((i>>k)&1)x.push_back(k+1);

			for(int k = 0;k<w1;k++)
				if((j>>k)&1)y.push_back(k+1);

			if((int)x.size()!=h2||(int)y.size()!=w2)continue;
			bool ok = true;
			for(int k = 1;k<=h2;k++)
			{
				for(int l = 1;l<=w2;l++)
				{
					if(a[x[k-1]][y[l-1]]!=b[k][l])
					{
						ok = false;
						break;
					}
				}
				if(!ok)break;
			}
			if(ok)
			{
				cout<<"Yes\n";
				return 0;
			}
		}
	}
	cout<<"No\n";
	return 0;
}

D - "redocta".swap(i,i+1)

Problem Statement

思路：给你一个字符串，你可以交换相邻两个位置的字符，问你至少交换多少次可以得到字符串atcoder.

Solution

思路：bfs。

当前串可以通过交换任意两个字符得到新串，代价为1，那可以考虑bfs写。

用map记录这个串有没有得到过，因为如果得到过，由现在的转移到得到过的串一定不会更优。

最后输出答案。

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

int main()
{
	string s;
	cin>>s;
	unordered_map<string,int>mp;
	mp[s] = 0;
	queue<string>q;
	q.push(s);
	while(!q.empty())
	{
		string t = q.front();
		q.pop();
		if(t=="atcoder")
		{
			cout<<mp[t]<<endl;
			return 0;
		}
		for(int i = 0;i<6;i++)
		{
			string cur = t;
			swap(cur[i],cur[i+1]);
			if(!mp[cur])
			{
				mp[cur] = mp[t]+1;
				q.push(cur);
			}
		}
	}
	return 0;
}

E - Blackout 2

Problem Statement

题意：

一个国家由N个城市和M个发电厂。

一共由N+M个建筑，1,2...N个是城市，N+1,N+2...M个是发电厂。

这个国家由E条电线，告诉你这E条线的连接。

一个城市称为有电当且仅当可以到达至少一个发电厂。

现在有Q个事件，每次删去一条电线，询问删去后还有多少个城市有电。

Solution

思路：正向不好考虑，因为还要删边。我们考虑离线+反向加边。这样原本有电的不会变成没有电，就好处理很多。

那么我们要如何判断一个城市是否有电？

并查集。每次令父亲是大的那个,这样保证如果连到发电厂(>n),能被识别。还要注意记录每个并查集的大小，这样连接的时候才知道要加上几个。为什么这样是可以的呢？因为每个并查集只有一个父亲，那我们又令父亲是最大的，如果最大的都<=n，那说明没有电，如果此时连上了一个>n的，说明整个并查集的元素都可以有电。

即：

如果fx<=n&&fy>n,cnt += sz[fx],fa[fx] = fy

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
bool ok[N];
map<int,pair<int,int>>mp;
int evt[N];
vector<int>edge[N*2];
int fa[N],ans[N],sz[N];
int find(int x)
{
	if(x==fa[x])
		return x;
	return fa[x] = find(fa[x]);
}
int main()
{
	int n,m,e;
	cin>>n>>m>>e;
	for(int i = 1;i<=n+m;i++)
		fa[i] = i;
	for(int i = 1;i<=n;i++)
		sz[i] = 1;
	for(int i = 1;i<=e;i++)
	{
		int x,y;
		cin>>x>>y;
		mp[i] = {x,y};
	}
	int q;
	cin>>q;
	set<int>s;
	for(int i = 1;i<=q;i++)
	{
		cin>>evt[i];
		s.insert(evt[i]);
	}
	int cnt = 0;
	for(int i = 1;i<=e;i++)
	{
		if(s.find(i)==s.end())
		{
			auto t = mp[i];
			int x = t.first,y = t.second;
			int fx = find(x),fy = find(y);
			if(fx>fy)swap(fx,fy);
			if(fx!=fy)
			{
				if(fx<=n&&fy>n)
					cnt += sz[fx];
				fa[fx] = fy;
				sz[fy] += sz[fx]; 
			}
		}
	}


	for(int i = q;i>=1;i--)
	{
		ans[i] = cnt;
		auto t = mp[evt[i]];
		int x = t.first,y = t.second;
		int fx = find(x),fy = find(y);
		if(fx>fy)swap(fx,fy);
		if(fx!=fy)
		{
			if(fx<=n&&fy>n)
					cnt += sz[fx];
			fa[fx] = fy;
			sz[fy] += sz[fx]; 
		}
	}


	for(int i = 1;i<=q;i++)
		cout<<ans[i]<<endl;

	return 0;
}