Contestant'. Rank 753. Rating +35.
A. Unit Array
题意
给定一个由 \(1, -1\) 组成的数组 \(a\)，定义操作为选择一个元素，并将其改为它的相反数。
现在，输出最小的操作数，使最后的数组满足下面的条件：
\(a_1 + a_2 + \ldots + a_n \ge 0\)
\(a_1 \cdot a_2 \cdot \ldots \cdot a_n = 1\)
思路
我们简化一下条件：
\(1\) 的个数大于等于 \(-1\) 的个数；
\(-1\) 的个数为偶数
因而，我们分讨即可。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
int p = 0;
for(int i=0;i<n;i++){
int cur;
cin >> cur;
if(cur == 1) p ++;
}
int q = n - p;
if(p >= q && q % 2 == 0){
cout << 0 << '\n';
}else{
int ans = 0;
if(p < q) {
ans += (q - p + 1) / 2;
q -= (q - p + 1) / 2;
}
if(q % 2 == 1) ans ++;
cout << ans << '\n';
}
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}但是分讨后式子得推一下（
B. Maximum Strength
题意
给定两个大数 \(L, R\)，找出 \(a, b\)，满足 \(L \leq a \leq b \leq R\)，并且 \(a\) 与 \(b\) 的所有位之差的绝对值之和最大，输出这个最大值。
思路
我们考虑贪心。
首先，对于单独一位，不难发现 \(9 - 0\) 得到的差值最大，那么我们自然希望能构造尽可能多的 \(9, 0\)。
我们不妨将其放在最后几位，构造形如 \(\ldots000, \dots999\) 的数。
如何构造？举个例子：
114514 114810你会发现，\(1145\)\(\color{rgb(124,179,66)}{99}\)\(, 1148\)\(\color{rgb(124,179,66)}{00}\) 即为我们需要的构造。
因而，我们得到下面的结论：
以字符串方式读入大数，循环补齐前导0；
从头开始遍历，找出第一个不相同的位置，记录差值 \(dis\)；
从第一个不相同的位置的下一个位置开始，每一位差值都视为 \(9\)；
最后的答案就是 \(dis\) 加上若干个 \(9\)
证明是显然的。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
string a, b;
cin >> a >> b;
int n = max(a.size(), b.size());
int difa = n - a.size(), difb = n - b.size();
for(int i=0;i<difa;i++) a = "0" + a;
for(int i=0;i<difb;i++) b = "0" + b;
int ans = 0;
for(int i=0;i<n;i++){ //找出第一个不同的位置，前面先算0
if(ans != 0){
ans += 9;
continue;
}
if(a[i] == b[i]) continue;
ans = abs(a[i] - b[i]);
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}群友：如果你觉得这是数位 \(dp\)，那你一定是学算法学魔怔了
C. Game with Reversing
题意
定义在两个长度相等的字符串 \(S, T\) 上的博弈：
\(Alice\) 可选定任意一个字符串的任意一个元素，并将其替换为任意一个字符；
\(Bob\) 可选定任意一个字符串，并将其整个翻转
定义任意一个玩家必须执行对应的操作，输出让两个字符串变为相同需要的操作总和。
为此，\(Alice\) 会让两个字符串变得尽可能相同，而 \(Bob\) 相反，会让两个字符串变得尽可能不同。
思路
我们考虑翻转操作的特点：
对同一个字符串执行两次翻转，等于没有翻转；
对不同的两个字符串各执行一次翻转，等效于没有翻转（因为如果翻转后相等，那么就等价于翻转前相等）
因而，我们不难发现，\(Bob\) 执行两次操作就约等于没操作，他只能让两个字符串在某个顺序要变为一致时，提前翻转一下，来让操作数变多一点。
我们考虑只翻转 \(T\)，那么，我们只需分别统计让 \(S\) 变为 \(T\) 和 翻转 \(T\) 所需的操作数，然后针对奇偶性分讨即可。
注意，分讨的时候，如果翻转后两个字符串一致，最后的操作数是 \(2\)，而非 \(0\) (\(Alice\) 随便选一个，改成一样的字符，然后由 \(Bob\) 翻转)。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
string a, b;
cin >> a >> b;
string c = b;
reverse(all(c));
int cnt1 = 0 , cnt2 = 0;
for(int i=0;i<n;i++){
if(a[i] != b[i]) cnt1 ++;
}
for(int i=0;i<n;i++){
if(a[i] != c[i]) cnt2 ++;
}
if(cnt1 != 0) {
if (cnt1 % 2 == 0) cnt1 = cnt1 * 2;
else cnt1 = (cnt1 - 1) * 2 + 1;
}
if(cnt2 != 0) {
if (cnt2 % 2 == 1) cnt2 = cnt2 * 2;
else cnt2 = (cnt2 - 1) * 2 + 1;
}else cnt2 = 2;
cout << min(cnt1, cnt2) << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}Bob: 我博弈了个寂寞