题解：P11969 「ALFR Round 7」T2 Game

这道题使用博弈论，需要对

t

的奇偶性进行分类讨论。

Part 1 思路

当

t = 1

时，相当于只有先手一次操作机会。那么，想让字典序最小，只需要把

1

提到第一位即可。但要是

1

已经在第一位了，那我们就把

2

提到第一位，以此类推。形式化的，我们找到第一个

a_i \ne i

，将

i

放到第

i

个位置即可。
我们推广一下，当

t

为奇数且

t > 1

时，第

2

次操作后手只能将

1

挪作（目的是维持现状，否则先手就会把

2

再放到第二个位置上，更加不利），先手再把

1

挪回来，以此反复。所以，当

t

为奇数时，情况和

t = 1

是一样的。
再来考虑

t = 2

时的情况。此时先手后手各操作一次。先从后手开始考虑，后手肯定会把

n

放到第一位，让字典序最大。先手此时不可能将第一位更改成小于

n

的数，所以退而求其次，将第二位降低，越小越好。所以，先手会把

1

放到第二位。但是，如果

1

已经在第二位，那么我们不妨把

2

放到第三位，以此类推。形式化的，我们找到第一个

a_i \ne i - 1

且

i \ge 2

的，将

i - 1

放到第

i

位上。
接着推广一下，当

t

是偶数且

t > 2

，第

3

次操作先手唯一的策略就是把现在在第一位上的

n

移走（目的还是维持现状，因为如果不挪走

n

，那么后手就会将

n - 1

放到第二位上，更加不利），后手会再把

n

放回来，以此类推。所以，当

t

为偶数时，和

t = 2

的情况是一样的。

Part 2 代码

CPP

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int M = 1e5 + 10;
int n, t, a[M], p[M];

signed main() {
	
	cin >> t >> n;
	for (int i = 1; i <= n; i ++) cin >> a[i], p[a[i]] = i;
	if (t % 2 == 1) {
		for (int i = 1; i <= n; i ++) {
			if (i != a[i]) {
				int pos = p[i];
				swap(a[i], a[pos]);
				break ;
			}
		}
	}
	if (t % 2 == 0) {
		if (a[1] == n) {
			for (int i = 1; i <= n; i ++) cout << a[i] << " "; 
			return 0;
		}
		if (a[1] == 1 && a[2] == n) {
			for (int i = 3; i <= n; i ++) {
				if (a[i] != a[i - 1]) {
					int pos = p[i - 1];
					swap(a[i], a[pos]);
					break ;
				}
			}
			swap(a[1], a[2]);
			for (int i = 1; i <= n; i ++) cout << a[i] << " "; 
			return 0;			
		} 
		for (int i = 2; i <= n; i ++) {
			if (a[i] != i - 1) {
				int pos = p[i - 1];
				swap(a[pos], a[i]);
				break ;
			}
		}
		swap(a[1], a[p[n]]);
	}
	for (int i = 1; i <= n; i ++) cout << a[i] << " ";
	cout << "\n";
	
	return 0;
}

说明一下，代码中

p_i

表示的是

i

在

a

数组中的位置，这样查找方便。

Part 3 其他注意事项

我们考虑一种情况：若

t

为偶数且

a_1 = n

，那么直接输出原数组。原因：先手只能把

n

移走。假设先手没有移走

n

，后手就可以把

n - 1

移到第二个位置上，这样肯定不优于原数组，所以先手只能把

n

移走，后手再放回来，陷入死循环，所以直接输出原数组。
另外一种情况：若

t

为偶数且

a_1 = 1

且

a_2 = n

，先手只需要将

2

移到第三位上，后手便会把

n

放到第一位上，

1

也就到了第二位上，符合先手的需求。形式化的，我们只需要找到第一个

a_i \ne i - 1

且

i \ge 3

，将

i - 1

移到第

i

位上，交换第一位第二位即可。

题解：P11969 「ALFR Round 7」T2 Game

文章操作

Part 1 思路

Part 2 代码

Part 3 其他注意事项

相关推荐

评论

题解：P11969 「ALFR Round 7」T2 Game