Codeforces Round 925 (Div. 3) - A、B、C、D、E

前言

本篇博客是Codeforces Round 925周赛的A、B、C、D、E五题的题解

A. Recovering a Small String

可以通过sum的大小分为三种情况，分别是：(1)aa? (2)a?z (3)?zz，这种方法时间复杂度要比三循环做法低很多

#include<bits/stdc++.h>using namespace std;void solve()
{int sum;cin >> sum;if(3 <= sum && sum <= 28){cout << 'a' << 'a';char r = 'a' - 1 + sum - 2;cout << r << endl;}else if(29 <= sum && sum <= 53){cout << 'a';char r = 'a' - 1 + sum - 27;cout << r;cout << 'z' << endl;}else if(54 <= sum && sum <= 78){char r = 'a' - 1 + sum - 52;cout << r << 'z' << 'z' << endl;}
}int main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--) solve();return 0;
}

B. Make Equal

直接用前缀判断即可，从头开始枚举前缀看是否能满足每个范围的水量

#include<bits/stdc++.h>using namespace std;const int N = 2e5 + 20;
int a[N];void solve()
{int n;cin >> n;int sum = 0;for(int i = 1; i <= n; i ++ ){cin >> a[i];sum += a[i];}int temp = sum / n;bool flag = true;int s = 0;for(int i = 1; i <= n; i ++ ){s += a[i];if(s < temp * i){flag = false;break;}}if(flag) cout << "YES" << endl;else cout << "NO" << endl;
}int main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--) solve();return 0;
}

C. Make Equal Again

枚举得到第一个与a1不同的位置，最后一个与an不同的位置，a1==an则取r - l + 1，否则取min(n + 1 - l, r)

#include<bits/stdc++.h>using namespace std;const int N  = 2e5 + 10;int a[N];void solve()
{int n;cin >> n;for(int i = 1; i <= n; i ++ ) cin >> a[i];int l = 1, r = n;while(l <= n && a[l] == a[1]) l ++;while(r >= 1 && a[r] == a[n]) r --;if(!r) cout << 0 << endl;else if(a[1] != a[n]) cout << min(n + 1 - l, r) << endl;else cout << r - l + 1 << endl;
}int main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--) solve();return 0;
}

D. Divisible Pairs

将所有{ai mod x, ai mod y}存入map，通过余数判断是否存在ai对应的aj，aj则是{(x - (a[i] % x)) % x, a[i] % y}对应的数，这样ai+aj恰好被x整除（余数相加被x整除），ai-aj恰好被y整除（余数恰好消掉）。但是在每次取ai后要使得mp[{a[i] % x, a[i] % y}] --，因为i严格小于j

#include<bits/stdc++.h>
#define pii pair<int, int>
#define ll long longusing namespace std;const int N  = 2e5 + 10;int a[N];void solve()
{int n, x, y;cin >> n >> x >> y;map<pii, int> mp;for(int i = 1;i <= n; i ++ ){cin >> a[i];mp[{a[i] % x, a[i] % y}] ++;}ll ans = 0;for(int i = 1; i <= n; i ++ ){mp[{a[i] % x, a[i] % y}] --; //i严格小于jans += mp[{(x - (a[i] % x)) % x, a[i] % y}];}cout << ans << endl;
}int main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--) solve();return 0;
}

E. Anna and the Valentine’s Day Gift

结果取决于最终数的长度，Anna要使长度尽可能小，翻转有后导0的数长度变小；Sasha要使长度尽可能大，将有后导0的数拼接在前可保住长度。所以从Anna每次让后导0最多的元素反转，Sasha每次让后导0最多的拼接在某个数前面，可以使用pair<后导0，总长>来存两者关系

#include<bits/stdc++.h>
#define pii pair<int, int>
#define ll long longusing namespace std;const int N  = 2e5 + 10;pii p[N]; //<后导0，总长>void solve()
{int n, m;cin >> n >> m;for(int i = 1; i <= n; i ++ ){string s;cin >> s;p[i] = {0, s.size()};while(s.back() == '0'){s.pop_back();p[i].first ++;}}sort(p + 1, p + 1 + n, greater<pii>()); //从大到小ll len = 0;for(int i = 1; i <= n; i ++ ){if(i % 2) len += p[i].second - p[i].first; //Sasha操作else len += p[i].second; //Anna操作}if(len > m) cout << "Sasha" <<endl;else cout << "Anna" << endl;
}int main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--) solve();return 0;
}