2022年ICPC网络第二场 J(博弈论)

题目 很有意思的一个题，当时敲代码敲错了，然后ac了。纯纯的运气选手。 题意: 博弈论，给定一个数组。每次操作选择从数组头或数组尾删除一个数。但是要求每次删除的数必须比以前所有删除的数都大(第一次操作无所谓)。 思路: 我一看一千多个队伍都过了，我就知道肯定是结论题，而不是什么SG函数。然后猜了一个从两头找需要删多少次这一头不能再操作，然后看奇偶。结果敲错了，反而对了。 结论是如果两头的操作次数l和r都是偶数，则后手胜；否则先手胜。 ① 如果a1 = an, 先手无论选哪个，另一头再也不能选了。如果有一头是奇数次，先手直接选了，就可以必胜。但是如果都是偶数，那先手选哪个都不行。 ② 如果a1 != an(a1 > an或者an > a1实际是一样的)，讨论a1 > an. 如果a1(大的)这一头是奇数，直接先手胜。否则，大的这一头是偶数，先手会选择另一头an。这时候，妙的来了。如果后手选a1，先手就可以跟着他走a1这条偶数的路，如影相随，那么这条路就废了，他不会影响结果。那么就只看an这一边的奇偶性了，如果是奇数，先手胜；否则，后手胜。 综上，如果两头的操作次数l和r都是偶数，则后手胜；否则先手胜（只要有一边是奇数）。 代码:

#include
using namespace std;
const int N = 1e5+10;
int n,m,k,T;
bool flag;
int t1,t2;
int a[N];
void solve()
{
	cin>>n;
	for(int i=1;i>a[i];
	t1 = t2 = 0;
	flag = 1;
	if(n=1;--i)
		{
			if(a[i]>=a[i-1])
			{
				t2 = i;
				break;
			}
		}
		t2 = n-t2+1;
//		cout