目录
B. Marin and Anti-coprime Permutation
C. Shinju and the Lost Permutation
杂谈
神秘的排列掉分场，C题WA到最后没考虑到循环的问题，?和?
?的关系也得判断，D题暴力过pretest，然后就理所当然地被 fst 干掉了......（开场前忘记报名了，开场10分钟后补报了这个掉分场hhh，上分路漫漫啊）
A. Marin and Photoshoot
题目大意：任意大于等于 2 的一段男性人数不能超过女性人数（0代表男性，1代表女性），求在当前安排下最少还需要邀请多少人才能达到要求。
解题思路：可以发现在两个 0 之间必须要有两个 1，也就是组成 0110 这样的序列（如果没有 1 显然不行，如果只有一个 1，那么长度为 3 的 010 序列就不满足要求），这样直接模拟即可。
AC代码：
#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define mid (l + r >> 1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
const int INF = 0x3f3f3f3f;
const ll LLF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1000000007;
const int N = 105;
char s[N];
int main(){
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while(t--){
int n;
cin >> n >> s + 1;
int pos = 0, ans = 0;
for(int i = 1; i <= n; i++){
if(s[i] == '0'){
if(pos != 0) ans += max(0, 2 - (i - pos) + 1);
pos = i;
}
}
cout << ans << endl;
}
return 0;
}B. Marin and Anti-coprime Permutation
题目大意：对于一个排列，定义美丽的排列当且仅当排列满足，其中?
?表示排列的第 i 位。求给定 n 个数字的排列中有多少个排列是美丽的排列，由于数字较大，答案对998244353取模。
解题思路：考虑什么情况下最大公约数会等于 1，由于是排列，不会出现相同的数字，就不可能出现 gcd(3, 6, 9) 这样的情况，因此只要出现奇数，gcd 就一定为 1，那么就好办了，可以分奇偶讨论：如果 n 是奇数，那么不论怎么排列，总存在至少一个??为奇数，这样直接输出 0 即可；如果 n 是偶数，那么有?
?个数是奇数，
?个数是偶数，将奇数安排在偶数位置，偶数安排在奇数位置，这样每个?
?均为偶数，gcd 就不为 1 了，根据排列组合知识，这样的方案数为?
。
AC代码：
#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define mid (l + r >> 1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
const int INF = 0x3f3f3f3f;
const ll LLF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int N = 1005;
ll fac[N];
void init(){
fac[0] = 1;
for(int i = 1; i <= N; i++){
fac[i] = fac[i - 1] * i % mod;
}
}
int main(){
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
init();
while(t--){
int n;
cin >> n;
if(n & 1) cout << 0 << endl;
else cout << fac[n / 2] * fac[n / 2] % mod << endl;
}
return 0;
}C. Shinju and the Lost Permutation
题目大意：对于一个排列，可以进行 n - 1 次循环操作，第 i 次循环后排列变为
?，再定义排列的能量为排列的前缀最大值数组的不同元素的个数，举个例子，对于排列?
，前缀最大值数组为
，排列的能量为 4，因为有4个不同元素。给出每次循环操作后的排列能量（
?表示第 i 次循环后的排列能量），问是否能够找到一个初始排列满足给出的排列能量。
解题思路：根据循环和排列能量的特点，由于每次循环只有一个数放到最前面，排列能量增量不可能大于 1，又由于排列中每个数都是不同的，并且在 n - 1 次循环下，排列最大值一定会到第一个位置，即排列能量总会有一次为 1，并且只有一次为 1。满足上述这两个特性的排列能量序列就一定能找到一个初始排列，否则一定找不到。这里还要注意一个细节，因为是个循环，那么??和?
也得满足上面的特性，可以让?
?这样从 1 位置开始判断就不会漏掉这种细节。
AC代码：
#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define mid (l + r >> 1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
const int INF = 0x3f3f3f3f;
const ll LLF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1000000007;
const int N = 100005;
int c[N];
int main(){
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int f = 0;
for(int i = 1; i <= n; i++){
cin >> c[i];
if(c[i] == 1) f++;
}
c[0] = c[n];
if(f != 1){
cout << "NO" << endl;
continue;
}
int flag = 0;
for(int i = 1; i <= n; i++){
if(c[i] > c[i - 1] + 1) flag = 1;
}
if(flag) cout << "NO" << endl;
else cout << "YES" << endl;
}
return 0;
}D1. 388535 (Easy Version)
题目大意：首先给出??和?
，然后可以得到一个?
?长度的排列，且排列中最小值为?
，最大值为?
，然后选择一个数 x，使排列中的数?
，得到新序列。问当题目给定这样一个新序列时，求 x 的值为多少，如果有多个答案，输出任意答案即可。
解题思路：将每个数看成二进制，从最高位开始，对于当前位，如果新序列和原序列中的 1 的个数不相等，那么说明 x 二进制中的该位一定得是 1，才能使得异或后原序列该位转换成新序列的该位，这样对于每一位进行判断，然后不相等就让 x 加上该位，最终得到的 x 就是答案。
AC代码：
#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define mid (l + r >> 1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
const int INF = 0x3f3f3f3f;
const ll LLF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1000000007;
const int N = 200005;
int a[N];
int main(){
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while(t--){
int l, r;
cin >> l >> r;
for(int i = l; i <= r; i++) cin >> a[i];
int ans = 0;
for(int j = 16; j >= 0; j--){
int cnt0 = 0, cnt1 = 0;
for(int i = l; i <= r; i++){
if(a[i] >> j & 1) cnt0++;
if(i >> j & 1) cnt1++;
}
if(cnt0 != cnt1) ans += (1 << j);
}
cout << ans << endl;
}
return 0;
}