Party Game
Lord Kevin (purportedly a distant relative of Lord Kelvin) is holding a party to celebrate his recent entrance into the British nobility. The exact process whereby Kevin acquired his title is a matter of some dispute, and there are even whispered rumours of identity theft, but fortunately we need not concern ourselves with such unpleasantries here. All the invitees to Kevin’s party are British Lords with whom he hopes to ingratiate himself, and since Kevin has detected that these nobles are a rather reserved lot, he has invented a party game to facilitate interactions among his guests. As the Lords arrive at Kevin’s manor, they are numbered from 1 to n. Each Lord is given a lapel pin on which is written his unique identifying number, and he is asked to wear this pin throughout the evening. (Kevin, who is organizing the game but not participating in it, does not have an assigned number.) Once all the guests have assembled in the ballroom, Kevin takes a set of n cards on which are written the numbers 1 through n (one number per card), places them in his top hat, and then draws them out at random and distributes them to his guests, one per Lord. Now the party game is ready to begin.
The game consists of a sequence of rounds, each of which has three stages. In Stage 1, Kevin calls out “Match!”, at which point each Lord checks to see if the number on the card in his hand matches the number on his lapel pin. If so, the Lord is freed from the game and can move into the dining room to partake of the fine food (and drink) waiting there. In Stage 2, Kevin calls out “Hat!”, at which point each remaining Lord memorizes the number on the card in his hand, and then places the card in the brim of his top hat. In Stage 3, Kevin calls out “Snatch!”, at which point each Lord finds the other guest in the room whose lapel pin contains the number he has just memorized, and then snatches (or, more politely, gently takes) the card from that Lord’s hat. (Since British nobles are also called peers, Stage 3 is an example of a peer-to-peer protocol.) At the end of Stage 3, each Lord once again has a numbered card in his hand, ready for the next round to begin. Note that at the end of Stage 1, if all Lords have been freed from the game, the game is over, so obviously Kevin will skip the final Stages 2 and 3.
Kevin thinks that this game he has invented will be very fun for his guests, but he is a little worried that some of the Lords might stay trapped in the game forever, eventually dying of starvation. Given the initial distribution of numbered cards to guests, help Kevin determine whether or not the game will have such a dire outcome.
Input
The first line of input contains a single integer T (1≤T≤10), the number of test cases that follow. Each test case occupies two lines. The first line contains an integer n (1≤n≤1200), the number of guests at the party. The second line contains n distinct space-separated integers a1,a2,…,an, where ai (1≤i≤n) is the number on the card initially given to the Lord whose lapel pin contains the number i.
Output
The output consists of T lines, one per case. For each test case, output “All can eat.” if the game eventually ends, or “Some starve.” if the game never ends.
Sample Input 1
3
3
1 2 3
4
3 4 2 1
5
5 4 1 2 3
Sample Output 1
All can eat.
All can eat.
Some starve.
这个题目的解法，是我认为比较神奇的。
首先，理解题意，我们可知，首先，客人有个胸针，上面写着从1到n的顺序，此顺序就是入场顺序，然后，每个客人都会有张小卡片，卡片数字随机，但保证每个人的卡片数字不一样，并且是1-n中随机的数字。
接下来，就进行题目所示的游戏了，分为三个步骤，简单来说，就是每个人按照自己手中卡片的数字，去寻找胸针和卡片数字一样的人，并与它交换卡片，若手中的卡片与自己胸针的数字一样，那么就代表你可以退出这个游戏，胜利去吃东西，没有拿到自己胸针和卡片一样数字的人，继续进行交换。
如果所有客人最终都能将手中的卡片换成胸针上的数字，那么就输出All can eat 。反之若有客人经过N轮游戏后，还是无法将手中的卡片换成胸针上的数字，那么就输出Some starve.
本题刚开始，我的想法是并查集或者是连通图，但是，我按题意走完后，发现，不管是都能拿到，或者有人拿不到，都能构成连通图，于是，放弃此思路。
接着，我发现，似乎换2轮，就可以看出，哪些人能够换到自己的卡片，哪些人交换2次后，似乎进行了死循环，
(例如有3个人，胸针数字和卡片数字分别为（1，2）（2，3）（3，1）换完后变成（1，3）（2，1）（3，2）再换一次（1，2）（2，3）（3，1）即换回去了，这样的话，不论进行多少次交换，都无法满足换完后胸针与卡片数字相同。）
于是，我开始找规律（个人觉得，一般竞赛题，得找规律，若用模拟，像本题给的数据是不超过1s的时间，极有可能超时），在不断的修改程序与修改规律过程中，一直是错误答案，错到我怀疑人生。
最终，查看本题数据，发现N最大也不过是1200，所以改用模拟，结果出乎我意料的是，本题居然是运用模拟的方法过去的，这让我一下绝望了，我找了1个小时的规律，最后居然是用模拟出结果。
贴出AC代码。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int a[1500][2];
int moni(int n,int cnt)
{
for (int i = 1; i <= n; i++)
{
if (a[i][0] == i)
cnt++;
else
a[i][1] = a[a[i][0]][0];
}
int temp;
for(int i=1;i<=n;i++)
if (a[i][0] != i)
{
temp = a[i][1];
a[i][1] = a[i][0];
a[i][0] = temp;
}
return cnt;
}
int main()
{
int T;
cin >> T;
while (T--)
{
int flag = 1;
int n;
int cnt;
cnt = 0;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i][0];
if (a[i][0] == i)
cnt++;
}
if (cnt == n)
cout << "All can eat." << endl;
else
{
for (int i = 1; i <= n+1; i++)
{
cnt=moni(n, 0);
if (cnt == n)
{
cout << "All can eat." << endl;
flag=1;
break;
}
else
flag = 0;
}
}
if (flag == 0)
cout << "Some starve." << endl;
}
}
这题对于喜欢暴力的人或者喜欢模拟解题的人来说，是个很nice的选择，至今我还没找得到其中规律在哪，只能通过模拟AC题目。
Comments NOTHING