【ECNU71】一个游戏（水题）

点此看题面

大致题意： \(n\)种元素，有若干组将\(x\)元素转化为\(y\)元素的操作。问对于所有可能的元素拥有状况，改变转化操作的顺序，是否会影响转化后最终的结果。

水题

虽说是这么水的题，但毕竟还是模拟赛题，所以照例写一下题解吧。。。

首先，若对于两组转化操作\((a,b),(c,d)\)，\(a,b,c,d\)各不相同，显然它们是互不影响的。

否则，我们分下面几类考虑：

\((a,b),(a,c)\)，显然，先\((a,b)\)则\(a\)会变成\(b\)，先\((a,c)\)则\(a\)会变成\(c\)，是有影响的。
\((a,b),(b,c)\)，显然，先\((a,b)\)则\(a\)最终会变成\(c\)，先\((b,c)\)则\(a\)最终仍是\(b\)，是有影响的。
\((a,b),(c,b)\)，无论先哪一个，最终\(a,c\)都会变成\(b\)，无影响。

总结一下，我们先把所有转化操作去重。

然后，枚举每一个转化关系\((x,y)\)，若\(x\)在之前某个转化操作中出现过，或\(y\)在之前某个转化关系前一项出现过，就说明会影响结果。

代码

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define V 100

using namespace std;

int n,sx[V+5],sy[V+5],vis[V+5][V+5];

int main()

{

	RI Tt,i,x,y,f;scanf("%d",&Tt);W(Tt--)

	{

		memset(sx,0,sizeof(sx)),memset(sy,0,sizeof(sy)),memset(vis,0,sizeof(vis));//清空

		for(scanf("%d",&n),f=i=1;i<=n;++i)

			scanf("%d%d",&x,&y),!vis[x][y]&&(sx[x]||sx[y]||sy[x])&&(f=0),sx[x]=sy[y]=vis[x][y]=1;//读入，去重后判断

		puts(f?"Lucky dxw!":"Poor dxw!");//输出答案

	}return 0;

}

巴特西

【ECNU71】一个游戏（水题）

水题

代码

最新文章

热门文章