A. Submission Bait

锐评

菜就多练好吧，第二题思路想到了没码出来，C题没看明白：=是什么意思。A题还WA一发。

题意

爱丽丝和鲍勃在大小为 n 的数组 a 中进行游戏。

他们轮流进行运算，爱丽丝先开始。不会运算的一方将输掉比赛。一开始，变量 mx 被设置为 0 。

在一次操作中，玩家可以

选择 i ( 1≤i≤n )这样的索引 ai≥mx ，并将 mx 设置为 ai。然后将 ai 设为 0 。

判断爱丽丝是否有一个获胜的策略。

输入描述

第一行包含一个整数 t (1 \leq t \leq 10^3) - 测试用例的数量。

对于每个具体的测试用例：

第一行包含一个整数 n (2 \leq n \leq 50) - 数组的大小。
第二行包含 n 个整数 a_1, a_2, \ldots, a_n (1 \leq a_i \leq n) - 数组的元素。

样例输入

样例输出

YES
NO
YES
NO
YES

样例说明

在第一个测试案例中，爱丽丝可以选择 i=1 ，因为 a_1=2 \ge mx=0 。

爱丽丝操作后， a=[0,1] 和 mx=2 。鲍勃无法进行任何操作。爱丽丝获胜。

在第二个测试案例中，爱丽丝没有获胜策略。

例如，如果爱丽丝选择 i=1 ，那么在爱丽丝的操作之后， a=[0,1] 和 mx=1 ： a=[0,1] 和 mx=1 。那么，由于 a_2=1 \ge mx=1 ，鲍勃可以选择 i=2 。鲍勃操作后 a=[0,0] 和 mx=1 。爱丽丝无法进行任何操作。鲍勃获胜。

思路

可以得到如果A直接选最大的，只要最大的数量是奇数就可以，我就是这么WA的，忽略了A可以选别的来增加她的胜算。对于每一个数出现的次数，实际上奇数是对Alice有利的，从后向前找第一个数只出现了奇数次，只要能找到那么就能赢，否则就不能，也就是看有没有数出现了奇数次。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}

int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}

int n, a[N], cnt[N];

void solve() {
	cin >>n;
    for (int i = 1; i <= n; ++ i) cin >> a[i];
    sort(a + 1, a + 1 + n);
    map<int,int>mp;
    for (int i = n; i >= 1; -- i) {
        mp[a[i]] ++;
    }
    for (auto i : mp) {
        if (i.first && i.second % 2 == 1) {
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) solve();
	return 0;
}

B. Array Craft

题意

对于大小为 m 的数组 b ，我们可以这样定义：

b 的最大前缀位置是满足 b_1+\ldots+b_i=\max_{j=1}^{m}(b_1+\ldots+b_j) 的最小索引 i ；
b 的最大后缀位置是满足 b_i+\ldots+b_m=\max_{j=1}^{m}(b_j+\ldots+b_m) 的大索引 i 。

给你三个整数 n 、 x 和 y ( x > y )。请构造一个大小为 n 的数组 a 以满足以下条件：

对于所有的 1 \le i \le n ， a_i 要么是 1 要么是 -1 ；
a 的最大前缀位置是 x ；
a 的最大后缀位置是 y 。

如果有多个数组满足条件，则打印任意一个。可以证明，在给定的条件下，这样的数组总是存在的。

输入描述

第一行包含一个整数 t（1 \leq t \leq 10^4），表示测试用例的数量。

对于每个测试用例：

只有一行，该行包含三个整数 n、x 和 y（满足 2 \leq n \leq 10^5 以及 1 \leq y < x \leq n）。

确保所有测试用例中所有 n 的总和不超过 10^5。

样例输入

样例输出

1 1
1 -1 1 1
1 1 -1 1 1 -1

思路

实际上这个题最开始想的是对的，后面不知道怎么又想到全 -1 全 1 了，再后面发现了就摆了，因为我构造的还挺麻烦的分了好几步，所以也没做出来，实际上我们可以得知y一定是小于x，（这是给的条件，当时我就没看到qwq）因此 x 和 y 之间包含的公共部分自然是越大越好，两边是越小越好，只有这样才能将端点约束在 x 和 y

x 之所以没有停留在绿色部分是因为即使加上绿色部分红色部分对它的好处更大。
而没有继续相见走是因为后面的过程中没有一个是让它更大的。
因此x向后的第一个元素肯定是 -1, 当然也不是越小越好，要不然如果绿色太低，即使加上红色也不能回正，还不如只要一个-1。
因此绿色部分尽量趋近于零即可，这样满足了所有要求，即-1 和 1来回交替。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}

int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}

int n, a;

void solve() {
	cin >> n;
    int x, y;
    cin >> x >> y;
    for (int i = 1; i <= n; ++ i) {
        if (i < y) a = (y - i) & 1 ? -1 : 1;
        else if (i <= x) a = 1;
        else {
            a = (i - x) & 1 ? -1 : 1;
        }
        cout << a << " ";
    }
    cout << "\n";
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _ ;
	while (_ --) solve();
	return 0;
}

C. Mad MAD Sum

题目大意

我们将数组中的 \operatorname{MAD}（最大重复出现数）定义为数组中至少出现两次的最大数字。具体来说，如果没有至少出现两次的数字，\operatorname{MAD} 的值就是 0。

例如，\operatorname{MAD}([1, 2, 1]) = 1、\operatorname{MAD}([2, 2, 3, 3]) = 3、\operatorname{MAD}([1, 2, 3, 4]) = 0。

给你一个大小为 n 的数组 a。初始化变量 sum 设置为 0。

下面的过程将依次循环执行，直到 a 中的所有数字都变成 0：

设置 sum := sum + \sum_{i=1}^{n} a_i；
设 b 为大小为 n 的数组。设 b_i := \operatorname{MAD}([a_1, a_2, \ldots, a_i]) 代表所有的 1 \leq i \leq n，然后用 b_i 替换 a_i 对于所有的 1 \leq i \leq n。

求过程结束后 sum 的值。

输入描述

首行提供一个整数 t（1 \leq t \leq 2 \times 10^4），代表测试用例的数量。

对于每一个测试用例：

第一行展示一个整数 n（1 \leq n \leq 2 \times 10^5），指示数组 a 的长度。
接下来的第二行含有 n 个整数 a_1, a_2, \ldots, a_n（每个满足 1 \leq a_i \leq n），这些整数以空格分隔，构成数组 a 的元素。

需保证所有测试用例中所有 n 的累计总和不超过 2 \times 10^5。

输出描述

对于每个测试用例，在新行中输出 sum 的值。

样例输入

样例输出

思路

b数组是前i个数中，中出现次数大于等于2的最大的数。由此我们可以得出经过一次操作以后，得到的新数组一定是单调不减。此时还有可能出现数量为一的数。，所以我们要再进行一次操作，那样这些只出现一次都数都会被左边替代，这样的话得到的数的出现次数都是大于2。往后就是非零部分向右移动。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}

int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}

int n, a[N];

void solve() {
	cin >>n;
    int sum = 0;
    for (int i = 1; i <= n; ++ i) cin >> a[i];
    map<int,int>mp;
    for(int i = 1; i < 3; ++ i) {
        for (int i = 1; i <= n; ++ i) sum += a[i];
        int mad = 0;
        for (int i = 1; i <= n; ++ i) {
            mp[a[i]] ++;
            if (mp[a[i]] == 2) mad = max(a[i], mad);
            a[i] = mad;
        }
        mp.clear();
    }
    for (int i = 1; i <= n; ++ i) {
        sum += (n - i + 1ll) * a[i];
    }
    cout << sum << "\n";
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) solve();
	return 0;
}

D. Grid Puzzle

题目大意

给你一个大小为 n 的数组 a。

有一个 n \times n 网格。在第 i 行中，第一个 a_i 单元格为黑色，其他单元格为白色。换句话说，注意单元格 (i,j) 位于第 i 行和第 j 列中，(i,1), (i,2), \ldots, (i,a_i) 单元格是黑色的，而 (i,a_i+1), \ldots, (i,n) 单元格是白色的。

您可以按照任意顺序多次进行以下操作：

将 2 \times 2 子网格染成白色；
将整行染白。注意，不能将整列染白。

找出将所有单元格染白的最少操作次数。

输入描述

第一行包含一个整数 t ( 1 \leq t \leq 10^4 ) - 测试用例的数量。

对于每个测试用例

第一行包含一个整数 n ( 1 \leq n \leq 2 \cdot 10^5 ) - 数组的大小 a 。
第二行包含 n 个整数 a_1, a_2, \ldots, a_n ( 0 \leq a_i \leq n )。

保证所有测试用例中 n 的总和不超过 2 \cdot 10^5 。

输出描述

对于每个测试用例，输出一个整数 - 将所有单元格染白的最少操作次数。

样例输入

10
1
0
4
2 4 4 2
4
3 2 1 0
3
0 3 0
3
0 1 3
3
3 1 0
4
3 1 0 3
4
0 2 2 2
6
1 3 4 2 0 4
8
2 2 5 2 3 4 2 4

样例输出

思路

实际上操作二已经是非常优秀的，所以我们只在一些特殊的情况下进行操作一。如果 ai 比较大的话，那我们一定要是执行操作2。是样例中给的2 4 4 2，这个样例是可以转化的。如果我们只执行操作二的话，他至少需要4次，但是如果执行操作一他只需要3次。类似于这样的结构就可以进行转化。两个ai小于等于二，只要它们的距离是偶数，并且中间最大值不超过四，都可以进行这样的转化，他们最后得到的结果比只执行操作二要少一次。这两个ai之间的数一定是大于等于3的，或者没有。因此不用担心全是1和2的极端情况。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}

int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}

int n, a[N];

void solve() {
	cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i];
    vector<int> dp(n +1, 1e9);
    dp[0] = 0;
    int j = 0, maxn = 0;
    for (int i = 1; i <= n; ++ i) {
        if (a[i] == 0) dp[i] = dp[i - 1];
        dp[i] = min(dp[i], dp[i - 1] + 1);
        if (a[i] <= 2 && j && maxn <= 4 && (i - j + 1) % 2 == 0) {//a[i] <= 2并且在这之前有a[i]<=2 并且他们之间所有的值都小于等于4并且他们之间的长度是偶数
            dp[i] = min(dp[i], dp[j - 1] + i - j);
        }
        if (a[i] <= 2) {
            j = i;
            maxn = 0;
        }else {
            maxn = max(maxn, a[i]);
        }
    }
    cout << dp[n] << "\n";
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) solve();
	return 0;
}