A - Everybody Likes Good Arrays!
题意（构造）
给出序列a，需要使a中元素以相邻元素奇偶性不同排列，你可以进行若干操作：将一对相邻奇偶性相同的元素相乘
问最少需要多少次操作
思路
相当于消消乐，奇偶性相同的子序列一定只能保留一个，故观察什么时候奇偶性发生变化即可
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++) cin >> a[i];
int t = a[1] & 1, cnt = 0;
for (int i = 2; i <= n; i ++) {
if (a[i] % 2 == t) cnt ++;
else {
t = t ^ 1;
}
}
cout << cnt << endl;
}
B - Emordnilap
题意（计数）
给出一个长度为n的排列，然后将其倒转接在后面，问按照这样规定的n！个排列会产生多少逆序对
思路
模拟几个数字后可知，对于一个含有n个元素的序列，所有含有n个元素的排列的逆序对数量都相等，故只需要求出其中一种排列的逆序数量然后乘n！即可
如：
序列123 会产生6种不同排列
我们只需观察123321这个序列会产生多少个逆序
序列：123321
贡献：012210
据观察可知逆序数量等于有n-1个元素首项为1，公差为1的等差数列和乘2
void solve() {
int n;
cin >> n;
int x = (LL)n * (n - 1) % MOD; //求出每种会产生多少个逆序
for (int i = 1; i <= n; i ++) { //乘以n！
x = (LL)x * i % MOD;
}
cout << x << endl;
}
C - Quiz Master
题意（排序+双指针）
给出n个数字，上限m
问从这个n个数字中能将1~m全部整除的一组数的极差最小值为多少
思路
先将n个数字排序，然后用双指针求出极差最小的满足条件的区间l，r
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n + 1), cnt(m + 1, 0); //cnt数组为记录1~m中每个因子在区间内的数量
int num = 0; //num为记录l，r区间包含多少个因子
for (int i = 1; i <= n; i ++) cin >> a[i];
sort(a.begin() + 1, a.end());
auto ins = [&](int x) { //添加一个因子，若该因子数量恰好为一，则num加一
if (x < 1 || x > m) return ;
cnt[x] ++;
if (cnt[x] == 1) num ++;
};
auto del = [&](int x) { //删除一个因子，若该因子数量恰好为零，则num减一
if (x < 1 || x > m) return ;
cnt[x] --;
if (cnt[x] == 0) num --;
};
int l = 1, r = 0, ans = INF;
for (int l = 1; l <= n; l ++) { //枚举l，求能满足条件的l，r区间
while (num != m) {
if (r == n) break;
for (int i = 1; i <= sqrt(a[r + 1]); i ++) {
if (a[r + 1] % i == 0) {
ins(i);
if (a[r + 1] / i != i) {
ins(a[r + 1] / i);
}
}
}
r ++;
}
if (num == m) ans = min(a[r] - a[l], ans);
for (int i = 1; i <= sqrt(a[l]); i ++) {
if (a[l] % i == 0) {
del(i);
if (a[l] / i != i) del(a[l] / i);
}
}
}
if (ans == INF) cout << -1 << endl;
else cout << ans <<endl;
}