中石油第八次 取石子

## 题面 题目描述 一天早上，机房里出现了n堆石子（雾），Tweetuzki和Miffoury开始把石子运到机房外面（Tweetuzki先开始）。不过他们觉得这样太无聊了，于是决定：每个人每次只搬运某堆中的石子，且搬运的数量必须是1或者是一个质数，如果谁没有办法继续搬运（也就是没有石子了），那么ta将会在明天开篇的《***-YC列传》中饰演公主的角色（大雾。 当然，在ta们的得到石子的来源之前，有连续的T个早上，ta们都会遇上类似的情况，即本题有多组数据。 输入 第一行一个数T，表示数据组数。 对于每组数据，输入会先给出一个数n，表示石子的堆数，加下来会给出n个数，表示每堆石子个数。 输出 T行，每行一个数表示答案，表示下周开篇的《***-YC列传》中的公主（即Tweetuzki或Miffoury）。 ## 思路 很明显这是个nim博弈，但是10的6次方的数据范围如果直接预处理SG值的话大概会超时，一眼也看不出来有啥规律。 于是在打了个0-1000的SG值的表，然后发现规律： |n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |...| | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------:| -----------: | |sg(n)| 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 4 |...| 很明显，每个数的SG值是这个数对4求余，于是就可以直接nim和了。 注意这个题数据略大，直接cin会超时 代码 ```cpp #include<iostream> #include<algorithm> #include<queue> #include<cstring> #include<set> #include<cstdio> #pragma warning(disable: 4996) using namespace std; typedef int ll; int ans = 0; int main() { int t; cin >> t; while (t > 0) { t--; int n; cin >> n; for (int i = 1; i <= n; i++) { int num; scanf("%d",&num); num %= 4; ans ^= num; } if (ans == 0) { cout << "Tweetuzki\n"; } else cout << "Miffoury\n"; ans = 0; } return 0; } ```