第46屆ICPC 東亞洲區域賽（澳門）

题目：A.So I'll Max Out My Constructive Algor...

题目链接：登录—专业IT笔试面试备考平台_牛客网

样例输入： 

1
2
4 3
2 1

样例输出：

4 3 1 2

题意：给定一个n*n的二维格点，每个格点有一个高度，任意两个格点的高度都是互不相同的，现在让我们找到一条路径使得这条路径经过所有的点一次，而且要保证路径中爬坡的次数要小于等于下坡的次数。

分析：其实我们发现题目中要求的条件非常弱，因为路径中爬坡的次数要么小于等于下坡的次数，要么就是大于下坡的次数，只有这两种情况，我们可以随便找一条路径，如果这条路径满足题目要求那么我们就输出这条路径，否则就反向输出这条路径。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=103;
int a[N][N];
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
		vector<int>p;
		for(int i=1;i<=n;i++)
		{
			if(i&1)
			for(int j=1;j<=n;j++)
				p.push_back(a[i][j]);
			else
			for(int j=n;j>=1;j--)
				p.push_back(a[i][j]);
		}
		long long cnt=0;
		for(int i=1;i<p.size();i++)
			cnt+=p[i]>p[i-1];
		if(cnt<=(1ll*n*n-1)/2)
			for(int i=0;i<p.size();i++)
			{
				printf("%d",p[i]);
				if(i!=p.size()-1)
					printf(" "); 
			}
		else
			for(int i=p.size()-1;i>=0;i--)
			{
				printf("%d",p[i]);
				if(i!=0)
					printf(" "); 
			}
		puts("");
	}
	return 0;
}

F.Sandpile on Clique

题目链接：登录—专业IT笔试面试备考平台_牛客网

样例1输入：

5
5 0 3 0 3

样例1输出：

3 3 1 3 1

样例2输入：

2
1 0

样例2输出：

Recurrent

简化题意：给定n个数，如果有一个数的值大于等于n-1，那么它就要将值减n-1，然后其余所有数的值都加1，问最后能不能使得数组恒定。如果能输出恒定数组，否则输出Recurrent

分析：如果数组最终能恒定那么操作的次数一定不会大于n-1，如果数组进行了n次操作，而一共有n个数，那么至少有一个数会+(n-1),因为n次操作代表平均每个数进行一次操作，也就是值减少n-1，那么也就是说一定存在一个数进行操作的次数是小于等于1的。那么它的值增加至少n-1，那么它又可以继续操作，按照这个方法推下去发现可以一直进行操作。

当然还有一种理解方式，就是我们可以发现无论对于哪个数进行一次操作，所有位置的数都会发生改变，那么如果某个位置的数出现了之前出现过的数，那么就说明存在循环节，因为这个时候除了这个位置以外的其他数也一定与之前完全相同，因为我们没办法只操作n-1个数，因为每个数最后的合理取值只有0~n-2，所以n-1就是最大循环节。

也就是判断总的操作次数是否大于等于n，如何判断当前数组是否还能继续操作呢？其实就是判断数组中的最大值是否大于等于n-1，这个我们可以直接用线段树来维护，对某个位置进行操作就等价于将这个点的值减少n-1，其余点的值+1，这个复杂度都是O(logn)的，所以总的复杂度就是O(nlogn)。

细节见代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=2e5+10;
int fu[N],du[N];
bool vis[N];//vis[i]=true/false表示第i号点在/不在环中 
struct node{
	int u,v;
}p[N];
int find(int x)
{
	if(x!=fu[x]) return fu[x]=find(fu[x]);
	return fu[x];
}
vector<int>pp[N];
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			fu[i]=i,vis[i]=false,du[i]=0,pp[i].clear();
		bool flag=false;
		for(int i=1;i<=m;i++)
			scanf("%d%d",&p[i].u,&p[i].v);
		for(int i=1;i<=m;i++)
		{
			int f1=find(p[i].u),f2=find(p[i].v);
			du[p[i].u]++;du[p[i].v]++;
			pp[p[i].v].push_back(p[i].u);
			pp[p[i].u].push_back(p[i].v);
			if(f1!=f2) fu[f1]=f2;
			else
			{
				flag=true;//找到环 
				queue<int>q;
				for(int j=1;j<=n;j++)
				{
					if(du[j]) vis[j]=true;
					if(du[j]==1) q.push(j);
				}
				while(!q.empty())
				{
					int t=q.front();
					vis[t]=false;
					q.pop();
					for(int j=0;j<pp[t].size();j++)
					{
						du[pp[t][j]]--;
						if(du[pp[t][j]]==1) q.push(pp[t][j]);
					}
				}
				for(int j=1;j<=i;j++)
					if(vis[p[j].u]&&vis[p[j].v]) printf("%d ",j);
				puts("");
				break;
			}
		}
		if(!flag) puts("-1");
	}
	return 0;
}

K.Link-Cut Tree

题目链接：登录—专业IT笔试面试备考平台_牛客网

样例输入：

2
6 8
1 2
2 3
5 6
3 4
2 5
5 4
5 1
4 2
4 2
1 2
4 3

样例输出：

2 4 5 6
-1

题意：给定一张图，包含n个点和m条边，第i条边的边权是2^i，让我们在图中找到一个边权和最小的环，如果能找到就输出这个环上的边的编号，否则输出-1.

分析：这道题直接贪心就行，我们知道=2^(n+1)-2，也就是说前i条边的边权和不如第i+1条边的边权和大。那么很容易能够想到我们应该尽量用编号小的边组成环，那么我们直接利用kruscal求最小生成树的思想直接从编号小的边开始建图，直至出现环为止，这个时候我们就形成了一个新的带环图，然后我们用拓扑排序把不在环上的点全部删掉，然后利用环上的点求一下环上的边即可。求的方法很简单，就是直接看一下当前在图上的边有哪些，选出来边的两端的点都是环上的点的边输出即可。

细节见代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=2e5+10;
int fu[N],du[N];
bool vis[N];//vis[i]=true/false表示第i号点在/不在环中 
struct node{
	int u,v;
}p[N];
int find(int x)
{
	if(x!=fu[x]) return fu[x]=find(fu[x]);
	return fu[x];
}
vector<int>pp[N];
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			fu[i]=i,vis[i]=false,du[i]=0,pp[i].clear();
		bool flag=false;
		for(int i=1;i<=m;i++)
			scanf("%d%d",&p[i].u,&p[i].v);
		for(int i=1;i<=m;i++)
		{
			int f1=find(p[i].u),f2=find(p[i].v);
			du[p[i].u]++;du[p[i].v]++;
			pp[p[i].v].push_back(p[i].u);
			pp[p[i].u].push_back(p[i].v);
			if(f1!=f2) fu[f1]=f2;
			else
			{
				flag=true;//找到环 
				queue<int>q;
				for(int j=1;j<=n;j++)
				{
					if(du[j]) vis[j]=true;
					if(du[j]==1) q.push(j);
				}
				while(!q.empty())
				{
					int t=q.front();
					vis[t]=false;
					q.pop();
					for(int j=0;j<pp[t].size();j++)
					{
						du[pp[t][j]]--;
						if(du[pp[t][j]]==1) q.push(pp[t][j]);
					}
				}
				for(int j=1;j<=i;j++)
					if(vis[p[j].u]&&vis[p[j].v]) printf("%d ",j);
				puts("");
				break;
			}
		}
		if(!flag) puts("-1");
	}
	return 0;
}