BZOJ4975 区间翻转

题目大意

有一个长度为$n$的序列a1,a2,…,ana_1,a_2,\\dots,a_na1​,a2​,…,an​。小$Q$和小$T$在玩游戏。两人轮流操作，小$Q$先手。对于每次操作，玩家需要选择一个长度为$4x+2$或$4x+3$的区间$[l,r]$，其中$x$是玩家自行选择的非负整数。然后将al,al+1,…,ar−1,ara_l,a_{l+1},\\dots,a_{r-1},a_ral​,al+1​,…,ar−1​,ar​翻转。每次操作之后得到的新序列的字典序必须比操作前的序列大。第一个不能继续操作的玩家输。假设小$Q$和小$T$都采取最优策略，问谁会获胜。如果小$Q$获胜，则输出$Q$；如果小$T$获胜，则输出$T$。

数据范围

q≤50≤n,1≤ai≤nq\\leq 50\\leq n,1\\leq a_i\\leq nq≤50≤n,1≤ai​≤n，aia_iai​互不相同。

题解

首先，我们知道在区间翻转后，该区间的顺序对和逆序对的数量互换。

观察题目所给的选择范围$4x+2$和$4x+3$。

• $4x+2$的区间内的顺序对和逆序对的和为(4x+2)(4x+1)2=(2x+1)(4x+1)\\dfrac{(4x+2)(4x+1)}{2}=(2x+1)(4x+1)2(4x+2)(4x+1)​=(2x+1)(4x+1)
• $4x+3$的区间内的顺序对和逆序对的和为(4x+3)(4x+2)2=(4x+3)(2x+1)\\dfrac{(4x+3)(4x+2)}{2}=(4x+3)(2x+1)2(4x+3)(4x+2)​=(4x+3)(2x+1)

我们发现，区间内的顺序对和逆序对的和一定为奇数。那么一次翻转之后，整个序列的顺序对和逆序对的奇偶性都取反。

在游戏结束时，$a$序列是递减序列，顺序对的个数为$0$。那么如果当前的顺序对的个数是偶数，则不管你怎么旋转，接下来的顺序对的个数一定是奇数，对手在翻回偶数，当到$0$时你就输了。如果当前的顺序对的个数是奇数，则你一定会胜利。

所以，我们可以先算出顺序对的个数。如果为奇数，则先手必胜；如果为偶数，则后手必胜。

时间复杂度为O(n2)O(n^2)O(n2)。

code

#include<bits/stdc++.h>
using namespace std;
int n,fl=0,a[55];
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=n;i++){for(int j=1;j<i;j++){if(a[i]>a[j]) ++fl;}}if(fl%2==1) printf("Q");else printf("T");return 0;
}