BZOJ4975: [Lydsy1708月赛]区间翻转（博弈&逆序对）

2023-08-04 08:43:10

4975: [Lydsy1708月赛]区间翻转

Time Limit: 1 Sec Memory Limit: 256 MB
Submit: 265 Solved: 140
[Submit][Status][Discuss]

Description

小Q和tangjz正在一个长度为n的序列a_1,a_2,...,a_n上玩一个有趣的关于区间翻转的游戏。小Q和tangjz轮流行动

，小Q先手。每次行动方玩家需要选择一个长度为4x+2或4x+3的区间[l,r](1<=l<=r<=n)，其中x是该玩家自行选择

的非负整数，然后将a_l,a_{l+1},...,a_{r-1},a_r翻转，例如1 3 2 5 4翻转会得到4 5 2 3 1。为了防止游戏无

限进行下去，他们规定每次操作之后得到的新序列的字典序必须比操作前的序列大。最先不能采取任何行动的玩家

将会输掉这局游戏。假设小Q和tangjz都会采取最优策略行动，请写一个程序判断谁会获得这局游戏的胜利。

Input

第一行包含一个正整数n(1<=n<=50)，表示序列的长度。

第二行包含n个互不相同的正整数a_1,a_2,...,a_n(1<=a_i<=n)，分别表示序列中的每个元素。

Output

输出一行一个字符，若小Q胜利，输出"Q"；若tangjz胜利，输出"T"（不含引号）。

Sample Input

4
4 2 1 3

Sample Output

思路：给出4x+2，4x+3，是因为这两个长度里的逆序对+顺序对=(L-1)*L/2=奇数。由于最后这个序列会变为有大到小，即顺序对为0，而且每次翻转满足这个区间的顺序对奇偶性改变，所以如果最开始顺序对为奇数，先手胜。

#include<bits/stdc++.h>

using namespace std;

int a[],cnt,N;

int main()

{

    scanf("%d",&N);

    for(int i=;i<=N;i++) scanf("%d",&a[i]);

    for(int i=;i<=N;i++)

     for(int j=i+;j<=N;j++)

      if(a[j]>a[i]) cnt++;

    if(cnt&) puts("Q");

    else puts("T");

    return ;

}