Codeforces Round 1003 (Div. 4)

A. Skibidus and Amog’u

题目大意

给你一个字符串，把末尾的us换成i

解题思路

删掉最后两个加上“i”即可

代码实现

#include <bits/stdc++.h>using i64 = long long;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int tt;std::cin >> tt;while (tt--) {std::string s;std::cin >> s;std::cout << s.substr(0, s.size() - 2) + "i" << "\n";}
}

B. Skibidus and Ohio

题目大意

给你一个字符串，如果存在相邻的字符相等则把后一个删除，并且可以把前一个换成任何字符，问字符串最短长度

解题思路

如果字符串存在相邻相等的字符则可以一直替换，所以答案为1，否则就是长度

代码实现

#include <bits/stdc++.h>using i64 = long long;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int tt;std::cin >> tt;while (tt--) {std::string s;std::cin >> s;int ans = s.size();for (int i = 1; i < ans; i++) {if (s[i] == s[i - 1]) {ans = 1;break;}}std::cout << ans << "\n";}
}

C1. Skibidus and Fanum Tax (easy version)

题目大意

给你两个数组ab，对于a的任意一个位置可以进行至多一次操作，使得$a_i=b_j-a_i$，问能否让a单调不递减，easy版本中b数组只有一个元素

解题思路

由于b只有一个元素，所以对于 $a_i$ 来说只有两个值，即 $a_i$ 和 $b_0-a_i$ ，如果较小值可以放入则用较小值，否则用较大值，如果较大值也不行则不能实现

代码实现

#include <bits/stdc++.h>using i64 = long long;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int tt;std::cin >> tt;while (tt--) {int n, m, f = 1;std::cin >> n >> m;std::vector<int> a(n), b(m);for (int i = 0; i < n; i++) {std::cin >> a[i];}for (int i = 0; i < m; i++) {std::cin >> b[i];}for (int i = 0; i < n; i++) {if (i == 0) {a[i] = std::min(a[i], b[0] - a[i]);} else {int minn = std::min(a[i], b[0] - a[i]), maxn = std::max(a[i], b[0] - a[i]);if (minn >= a[i - 1]) {a[i] = minn;} else if (maxn >= a[i - 1]) {a[i] = maxn;} else {f = 0;break;}}}if (f) {std::cout << "YES\n";} else {std::cout << "NO\n";}}
}

C2. Skibidus and Fanum Tax (hard version)

题目大意

给你两个数组ab，对于a的任意一个位置可以进行至多一次操作，使得$a_i=b_j-a_i$，问能否让a单调不递减

解题思路

当b中元素有多个的时候，暴力显然不行，但是不难发现，尽可能使用b中较小的元素是优的，这会让a中的元素尽可能的小，因此二分最小的满足 $b_{pos}-a_i\ge a_{i-1}$ 的位置即可

代码实现

#include <bits/stdc++.h>using i64 = long long;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int tt;std::cin >> tt;while (tt--) {int n, m, f = 1;std::cin >> n >> m;std::vector<int> a(n), b(m);for (int i = 0; i < n; i++) {std::cin >> a[i];}for (int i = 0; i < m; i++) {std::cin >> b[i];}std::sort(b.begin(), b.end());for (int i = 0; i < n; i++) {if (i == 0) {a[i] = std::min(a[i], b[0] - a[i]);} else {int l = 0, r = m - 1, pos = 0;while (l <= r) {int mid = (l + r) / 2;if (b[mid] - a[i] >= a[i - 1]) {r = mid - 1;pos = mid;} else {l = mid + 1;}}int minn = std::min(a[i], b[pos] - a[i]), maxn = std::max(a[i], b[pos] - a[i]);if (minn >= a[i - 1]) {a[i] = minn;} else if (maxn >= a[i - 1]) {a[i] = maxn;} else {f = 0;break;}}}if (f) {std::cout << "YES\n";} else {std::cout << "NO\n";}}
}

D. Skibidus and Sigma

题目大意

给你多个数组，你可以重新排列它们，之后按顺序拼接为一个新的大数组，求大数组的所有子数组最大和是多少

解题思路

将每个数组看作一个数（数组的和），显然数字大的放在越前面越好，自定义排序规则之后按位置算贡献即可

代码实现

#include <bits/stdc++.h>using i64 = long long;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int tt;std::cin >> tt;while (tt--) {int n, m;std::cin >> n >> m;std::vector<std::vector<int>> v(n, std::vector<int>(m));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {std::cin >> v[i][j];}}std::sort(v.begin(), v.end(), [&](std::vector<int> x, std::vector<int> y) { return std::accumulate(x.begin(), x.end(), 0ll) > std::accumulate(y.begin(), y.end(), 0ll); });i64 ans = 0, cnt = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {ans += v[i][j] * (n * m - cnt++);}}std::cout << ans << "\n";}
}

E. Skibidus and Rizz

题目大意

给你n个0和m个1，请你构造出一个01串，使得所有子串中01数量最大差值是k，不可能构造则输出-1

解题思路

先思考不可能的情况，显然二者数量差过大（整个串会超过）或者01数量不足的时候（连一起都不够）不满足。而一组01、10是较为平衡的，至多产生1的差值，可以用于中间平衡子串的部分，所以只需要在此基础上把0和1放在两侧即可，可以先输出k个0（假设 $n\ge m$），之后输出10直到没有0，再把剩下的1输出来

代码实现

#include <bits/stdc++.h>using i64 = long long;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int tt;std::cin >> tt;while (tt--) {int n, m, k;std::cin >> n >> m >> k;if (std::abs(n - m) > k || k > std::max(n, m)) {std::cout << "-1\n";} else {for (int i = 0; i < k; i++) {std::cout << (n < m ? "1" : "0");}for (int i = 0; i < std::max(n, m) - k; i++) {std::cout << (n < m ? "01" : "10");}for (int i = 0; i < std::min(n, m) - std::max(n, m) + k; i++) {std::cout << (n < m ? "0" : "1");}std::cout << "\n";}}
}

F. Skibidus and Slay

题目大意

给你一棵n个节点带权的树，问是否存在路径的点权众数（众数要超过一半以上的数量）为1~n

解题思路

简单观察就能发现，如果一条路径超过3个节点就不优了，更长的里有满足的众数显然可以在更短的时候找到，因此只需要枚举中间节点u，看u以及所有与u连的点中是否有相同的点权即可

代码实现

#include <bits/stdc++.h>int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int tt;std::cin >> tt;while (tt--) {int n;std::cin >> n;std::vector<int> a(n + 1);for (int i = 1; i <= n; i++) {std::cin >> a[i];}std::vector<std::vector<int>> g(n + 1, std::vector<int>());for (int i = 1; i < n; i++) {int u, v;std::cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}std::string ans = std::string(n + 1, '0');for (int u = 1; u <= n; u++) {std::map<int, int> mp;for (auto v : g[u]) {mp[a[v]]++;}mp[a[u]]++;for (auto [x, y] : mp) {if (y >= 2) {ans[x] = '1';}}}std::cout << ans.substr(1) << "\n";}
} 

G. Skibidus and Capping

题目大意

给你一个数组a，问有多少个数对ij（$i\le j$）满足 $lcm(a_i,a_j)$ 是半质数（可以分解为两个质数的积）

解题思路

要对答案做贡献总共只有以下几种情况：
1.两个不同的质数
2.一个是半质数，另一个是它的质因子
3.两个相等的半质数

代码实现

#include <bits/stdc++.h>using i64 = long long;
const int N = 2e5 + 10;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);// 埃氏筛预处理出所有质数与合数的最小质因子std::vector<i64> fac(N);for (int i = 2; i <= 2e5; i++) {if (!fac[i]) {for (int j = i * 2; j <= 2e5; j += i) {fac[j] = i;}}}int tt;std::cin >> tt;while (tt--) {i64 n, ans = 0;std::cin >> n;std::vector<i64> a(n), p(n + 1);for (int i = 0; i < n; i++) {std::cin >> a[i];p[a[i]]++;if (!fac[a[i]]) {ans++;}}// 两个质数ans = ans * (ans + 1) / 2;for (int i = 2; i <= n; i++) {if (!fac[i]) {ans -= p[i] * (p[i] + 1) / 2;      // 相同的质数需要减去} else {                               // i是合数，要为答案做贡献只能是半质数int x = i / fac[i];                // 如果i是半质数，那么它只会有两个质因子，fac[i]是较小的一个，x是另外一个if (!fac[x]) {                     // x是质数说明i能被分解为两个质数，满足定义ans += p[i] * (p[i] + 1) / 2;  // 相同的半质数ans += p[i] * p[x];            // 半质数和它的其中一个质因子if (x != fac[i]) {             // 半质数和另一个质因子（x不是半质数较小的质因子说明i不是质数的平方）ans += p[i] * p[fac[i]];}}}}std::cout << ans << "\n";}
}