由于太懒了，所以不想（会）写 \(\texttt{A B}\) 和 \(\texttt{F2}\)。
C Common Divisors 题解
题目大意
给定一个长度为 \(n\) 的数列 \(\{a_i\}\)，求 \(\sigma(\gcd\limits_{i\in[1,n]}\{a_i\})\)。
解题思路
先算出所有元素的最大公因数，如果最大公因数 \(g\) 为 \(1\)，即所有元素两两互质，则直接输出 \(1\)；否则输出 \(g\) 的因数个数。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e5 + 5;
int n;
ll a[N], g, ans;
inline ll gcd(ll a, ll b) {
if(a % b == 0) {
return b;
}
return gcd(b, a % b);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
g = a[1];
for(int i = 2; i <= n; i++) {
g = gcd(g, a[i]);
}
if(g == 1) {
cout << 1;
return 0;
}
for(ll i = 1; i * i <= g; i++) {
if(g % i == 0) {
if(i * i == g) {
ans++;
} else {
ans += 2;
}
}
}
cout << ans;
return 0;
}
D1 & D2 Remove the Substring
题目大意
给定一个字符串 \(s\) 和一个它的子序列 \(t\)，要求删除 \(s\) 的一个子串（连续的一段字符串），使得 \(t\) 仍然是它的子序列，求最多删除多长的子串。
解题思路
先找到 \(s\) 中最靠后的子序列 \(t\)，得到这个子序列每个字符在 \(s\) 中的位置 \(p_i\)，我们可以删除 \(p_0\) 前面的所有字符，将 \(p_0\) 这个字符换成最靠前的字符，删除 \(p_1\) 和 \(p_0\) 中间的字符，再将 \(p_1\) 这个字符换成最靠前的字符，删除 \(p_2\) 和 \(p_1\) 中间的字符，可以用 upper_bound 来解决。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
string s, t;
int pos, ans;
int p[N];
vector<int> a[30];
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> s >> t;
int n = s.size(), m = t.size();
for(int i = 0; i < n; i++) {
int k = s[i] - 'a';
a[k].push_back(i);
}
for(int i = 0; i <= 25; i++) {
sort(a[i].begin(), a[i].end());
}
pos = m - 1;
for(int i = n - 1; i >= 0; i--) {
if(s[i] == t[pos]) {
p[pos] = i;
pos--;
if(pos <= -1) {
break;
}
}
}
ans = p[0];
p[m] = n;
for(int i = 0; i < m; i++) {
int k = t[i] - 'a', pos;
if(i == 0) {
pos = upper_bound(a[k].begin(), a[k].end(), -1) - a[k].begin();
} else {
pos = upper_bound(a[k].begin(), a[k].end(), p[i - 1]) - a[k].begin();
}
p[i] = a[k][pos];
ans = max(ans, p[i + 1] - p[i] - 1);
}
cout << ans;
return 0;
}
E Boxers 题解
题目大意
给定一个长度为 \(n\) 的数列 \(\{a_i\}\)，对于每个 \(a_i\) 可以使得 \(a_i\gets a_i\pm1\)。
选出个数最多的方案，使得 \(a_i\neq a_j\ (i\neq j)\)。
解题思路
先将 \(\{a_i\}\) 从小到大排序，每个 \(a_i\) 在操作后要尽量的小，可以理解为越小它后面的元素能改变的方案越多，操作完之后如果其值没标记过，则标记它并且个数加 \(1\)。
注意当 \(a_i=1\) 时不能 \(a_i\gets a_i-1\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, ans, a[N];
bool vis[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; i++) {
if(a[i] - 1 >= 1 && !vis[a[i] - 1]) {
vis[a[i] - 1] = 1;
ans++;
} else if(!vis[a[i]]) {
vis[a[i]] = 1;
ans++;
} else if(!vis[a[i] + 1]) {
vis[a[i] + 1] = 1;
ans++;
}
}
cout << ans;
return 0;
}
F1 Complete the Projects 题解
题目大意
有 \(n\) 个项目，做第 \(i\) 个项目需要能力值至少为 \(a_i\)，做完后能力值会增加 \(b_i\)（可能为负），给定初始能力值，求是否能够做完所有的项目。
解题思路
先将所有项目按 a[i].x 从小到大排序，然后将所有 a[i].y \(\ge 0\) 的项目做完。得到新的 \(r\) 值。然后将所有 a[i].y 为负值的项目提取出来放到一个新的数组中，专门处理，假设有 \(m\) 个这样的项目用 \(b_m\) 保存，我们每次检查是否有项目可以最后完成即可。如果有第 \(i\) 个项目可以最后完成，就相当于我们的 \(r\) 值减去其它 \(m-1\) 个项目的 \(y\) 值后，依然有 \(r\ge\)a[i].x 且 \(r\ge\)abs(a[i].y)。这样确定了最后完成的项目后，我们再找是否有项目可以倒数第 \(2\) 完成即可，以此类推。最后如果完成的项目数 \(\text{sum}=n\) 说明我们完成了所有项目。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, r, sum, sub;
int vis[N];
struct node {
int x, y;
}a[N], b[N];
inline bool cmp(node x, node y) {
return x.x < y.x;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> r;
for(int i = 1; i <= n; i++) {
cin >> a[i].x >> a[i].y;
}
sort(a + 1, a + n + 1, cmp);
for(int i = 1; i <= n; i++) {
if(a[i].x <= r && a[i].y >= 0) {
r += a[i].y;
sum++;
}
if(a[i].y < 0) {
b[++m] = a[i];
}
}
bool flag = 0;
while(1) {
flag = 0;
for(int i = 1; i <= m; i++) {
if(vis[i]) {
continue;
}
sub = 0;
for(int j = 1; j <= m; j++) {
if(i == j) {
continue;
}
if(!vis[j]) {
sub += abs(b[j].y);
}
}
if(r - sub >= b[i].x && r - sub >= abs(b[i].y)) {
vis[i] = 1;
sum++;
flag = 1;
}
}
if(!flag) {
break;
}
}
if(sum == n) {
cout << "YES";
} else {
cout << "NO";
}
return 0;
}