BZOJ4975 区间翻转-Toy模板网

这篇具有很好参考价值的文章主要介绍了BZOJ4975 区间翻转。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目大意

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

数据范围

$q\leq 50\leq n,1\leq a_i\leq n$ ， $a_i$ 互不相同。

题解

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

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

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

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

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

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

时间复杂度为 $O(n^2)$ 。文章来源地址https://www.toymoban.com/news/detail-411108.html

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;
}