小米商城网站建设,珠海营销网站建设,网站开发 动易,免费的旅游网站模板题目大意
两人博弈#xff0c;有一个 nnn 的排列 a1,a2,…,ana_1,a_2,\dots,a_na1,a2,…,an#xff0c;每次操作为选择长度为 4x24x24x2 或 4x34x34x3 的区间#xff0c;将其翻转#xff0c;要求翻转后字典序大于翻转前。第一个不能操作的输。Q 先手#xff0c;T 后…题目大意
两人博弈有一个 nnn 的排列 a1,a2,…,ana_1,a_2,\dots,a_na1,a2,…,an每次操作为选择长度为 4x24x24x2 或 4x34x34x3 的区间将其翻转要求翻转后字典序大于翻转前。第一个不能操作的输。Q 先手T 后手判断谁赢。
题解
非常经典的结论题。
可以全排列对每个排列暴力求然后打表找规律。这是一种策略在面对博弈结论题时异常好用。
正解
发现一个区间翻转后区间内顺序对和逆序对的数量会交换。
题目给定的 4x24x24x2 和 4x34x34x3 这俩奇奇怪怪的数不得不让人想到一些特殊的性质。
观察区间长度为 4x24x24x2 的数对总数为 (4x2)(4x1)2(2x1)(4x1)\dfrac{(4x2)(4x1)}{2}(2x1)(4x1)2(4x2)(4x1)(2x1)(4x1)为奇数。
区间长度为 4x34x34x3 的数对总数为 (4x3)(4x2)2(2x1)(4x3)\dfrac {(4x3)(4x2)}{2}(2x1)(4x3)2(4x3)(4x2)(2x1)(4x3)为奇数。
也就是说翻转后区间的顺序对数量奇偶性一定改变。
最终无法操作的状态为 n,n−1,n−2,…,1n,n-1,n-2,\dots,1n,n−1,n−2,…,1顺序对为 000.
只需要保证当前顺序对个数为奇数就可以立于不败之地。
由于每次操作顺序对奇偶性必定改变所以最初的序列就已经决定了结果。
若最初顺序对为奇数Q 胜利。否则T 胜利。
求顺序对使用树状数组时间复杂度 O(nlogn)O(n\log n)O(nlogn).
代码
#include bits/stdc.h
using namespace std;
#define lowbit(x) x(-x)
int n, tr[100005];
void update(int x, int val) {for (; x n; x lowbit(x)) tr[x] val;
}
int getsum(int x) {int sum 0;for (; x; x - lowbit(x)) sum tr[x];return sum;
}
int main() {scanf(%d, n);int cnt 0;for (int i 1, x; i n; i) scanf(%d, x), cnt getsum(x), update(x, 1);if (cnt 1) printf(Q);else printf(T);return 0;
}END
