AtCoder Beginner Contest 309

A - Nine

Problem Statement

题意：给你两个数问你是否在图上是相邻的。

Solution

思路：按照图写下关系即可。

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

int main()
{
	int a,b;
	cin>>a>>b;
	if((a==1&&b==2)||(a==2&&b==3)||(a==4&&b==5)||(a==5&&b==6)||(a==7&&b==8)||(a==8&&b==9))
		cout<<"Yes\n";
	else cout<<"No\n";


	return 0;
}

B - Rotate

Problem Statement

题意：给你\(N\times N\)的矩阵，让你把外围的顺时针转一格。输出旋转后的结果。

Solution

思路：模拟。记得输入是字符，然后避免覆盖问题，可以开一个新数组记答案。

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
char a[N][N],b[N][N];
int u[N],d[N],l[N],r[N];
int main()
{
	int n;
	cin>>n;
	for(int i = 1;i<=n;i++)
		for(int j = 1;j<=n;j++)
			cin>>a[i][j];
	for(int j = 2;j<=n;j++)
		b[1][j] = a[1][j-1];
	for(int i = 2;i<=n;i++)
		b[i][n] = a[i-1][n];
	for(int j = n-1;j>=1;j--)
		b[n][j] = a[n][j+1];
	for(int i = n-1;i>=1;i--)
		b[i][1] = a[i+1][1];
	for(int i = 2;i<=n-1;i++)
		for(int j = 2;j<=n-1;j++)
			b[i][j]  = a[i][j];
	for(int i = 1;i<=n;i++)
	{
		for(int j = 1;j<=n;j++)
		{
			cout<<b[i][j];
		}
		cout<<endl;
	}

	return 0;
}

C - Medicine

Problem Statement

题意：给你\(N\)种药，对于第\(i\)种药药在接下来\(a_i\)天吃\(b_i\)片。问你第几天的药片总数小于等于\(K\)。

Solution

思路：先sort，然后直接模拟

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5+10;
struct ty
{
	int day,num;
}a[N];

bool cmp(ty a,ty b)
{
	return a.day<b.day;
}

int main()
{
	int n,k;
	cin>>n>>k;
	ll sum = 0;
	for(int i = 1;i<=n;i++)
	{
		cin>>a[i].day>>a[i].num;
		sum += a[i].num;
	}
	sort(a+1,a+1+n,cmp);
	int now = 1;
	int idx = 1;
	while(sum>k)
	{
		while(a[idx].day==now&&idx<=n)
			sum-=a[idx].num,idx++;
		now++;
	}
	cout<<now<<endl;

	return 0;
}

D - Add One Edge

Problem Statement

题意：给你\(N1+N2\)个点和\(M\)条边。

告诉你边的连接关系，问你加一条边使得\(1\)到\(N1+N2\)的距离最远

Solution

思路：对\(1\)到\(N1\)和\(N1+1\)到\(N1+N2\)做一次\(dijkstra\),并记录\(ans1\)为从\(1\)开始能走到的最远的路程，同理\(ans2\)记录\(N1+N2\)的，最终答案就是\(ans1+ans2+1\)

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10;

vector<int>edge[N];
set<pair<int,int>>q;//记录的是不在c中的点的信息

int dist[N];
int n1,n2,m;
int ans1,ans2,tmp;
inline void dijkstra(int s)
{
	memset(dist,127,sizeof(dist));
	dist[s] = 0;
	q.clear();
	for(int i = 1;i<=n1;i++)
	{
		q.insert({dist[i],i});
	}
	while(!q.empty())
	{

		int x = q.begin()->second;//离起点最近的点的下标
		if(dist[x]<(1<<30))
			ans1 = max(ans1,dist[x]);
		q.erase(q.begin());
		for(auto y:edge[x])
		{
			if(dist[x]+1<dist[y])
			{
				q.erase({dist[y],y});
				dist[y]= dist[x]+1;
				q.insert({dist[y],y});
			}
		}
	}
}


inline void dijkstra2(int s)
{
	memset(dist,127,sizeof(dist));
	dist[s] = 0;
	q.clear();
	for(int i = n1+1;i<=n1+n2;i++)
	{
		q.insert({dist[i],i});
	}
	while(!q.empty())
	{
		int x = q.begin()->second;//离起点最近的点的下标
		if(dist[x]<(1<<30))
			ans2 = max(ans2,dist[x]);
		q.erase(q.begin());
		for(auto y:edge[x])
		{
			if(dist[x]+1<dist[y])
			{
				q.erase({dist[y],y});
				dist[y]= dist[x]+1;
				q.insert({dist[y],y});
			}
		}
	}
}
int main()
{
	
	cin>>n1>>n2>>m;
	for(int i = 1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		edge[x].push_back(y);
		edge[y].push_back(x);
	}

	dijkstra(1);
	dijkstra2(n1+n2);
	cout<<ans1+ans2+1<<endl;
	return 0;
}

E - Family and Insurance

Problem Statement

题意：一个家族包含人标号1~N。对于\(i>=2\)的编号的人给定他们的父亲\(p_i\)。

现在买\(M\)次保险，编号\(x_i\)的人买第\(i\)个保险，保险覆盖他的下\(y_i\)代后代。

问：有多少人知道被保险覆盖一次？

Solution

思路：我们维护以某个点为父亲能覆盖的最大的后代代数，即\(num[x] = max(num[x],y+1)\)。

以父子关系建图，然后再从根1开始\(dfs\)，对于每个点\(x，for\)他们的儿子y，取\(num[y] = (num[y],num[x]-1)\)，再去\(dfs(y)\)

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
int n,m;
int num[N];
vector<int>edge[N];

int dfs(int x)
{
	int ans = 0;
	if(num[x])ans++;
	for(auto y:edge[x])
	{
		num[y] = max(num[y],num[x]-1);
		ans += dfs(y);
	}
	return ans;
}

int main()
{
	cin>>n>>m;
	for(int i = 2;i<=n;i++)
	{
		int x;
		cin>>x;
		edge[x].push_back(i);
	}
	for(int i = 1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		num[x] = max(num[x],y+1);
	}
	cout<<dfs(1)<<endl;
	return 0;
}