1 条题解
-
0
Solution
首先,这里输入很奇葩。我们可以把它拆成一个序列,设序列长度为 。
假设 。可以证明,Xuan 总是会获胜。
- 如果 Xuan 能够使得 并让 Xiang 面对一个必输的局面,Xuan 就会赢。
- 假设通过使 能够获得所有必胜的局面。然后,如果我们 ,那么可以从该局面过渡到的所有局面都是必胜的。因此,将 所得到的局面是必败的。所以,初始局面是必胜的。
接下来,考虑当给定一个满足 的局面。根据上述证明,Xuan 和 Xiang 不应该给出最大两个元素差为 或更大的局面。综上,我们可以假设 的最大两个元素的差为 。
然后,我们发现每一步操作都会将 减少 。
当 时,该局面无法进行操作,因此可以根据输入中 和 的奇偶性差异来确定赢家。
复杂度为 。
但是输入不是有序,进行排序。复杂度为 。
std 和这里的说法有些不同,std 写法更为简洁。
Code
#include <bits/stdc++.h> using namespace std; int n, m; int a[300020]; int main() { cin >> n >> m; for (int i = 1; i <= n * m; i++) { cin >> a[i]; } sort(a + 1, a + n * m + 1); for (int i = 1; i <= n * m; i++) { a[i] -= i - 1; } if (a[n * m] == a[n * m - 1] && (a[n * m] % 2 == 0)) puts("Xiang"); else puts("Xuan"); return 0; }
- 1
信息
- ID
- 717
- 时间
- 1500ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 87
- 已通过
- 5
- 上传者