Codeforces Round 925 (Div. 3)

Codeforces Round 925 (Div. 3)

A. Recovering a Small String

题意：给出一个整数n，为三个26个字母的位置序号的和，输出字典序最小的三个字符的字符串。

思路：直接倒推，顺一遍，后面的字母尽可能大。

AC code：

void solve() {cin >> n;string s = "";if (n > 27) {n -= 26;s += 'z';if (n > 26) {s += 'z';n -= 26;s += char('a' + n - 1);} else {s += char('a' + n - 1 - 1);s += 'a';}}else {s += 'a';s += 'a';n -= 2;s += char('a' + n - 2 + 1);cout << s << endl;return;}reverse(s.begin(),s.end());cout << s << endl;
}

B. Make Equal

题意：n杯水，首先一定能平分，前面的水可以往后匀，是否可以通过这种方式使得n杯水平分。

思路：贪心，从前往后捋，高出平均值记录一下，少了就去些。

AC code：

void solve() {cin >> n;vector<int> a(n, 0);int mx = 0;for (int i = 0; i < n; i ++) cin >> a[i], mx += a[i];int aver = mx / n, now = 0;for (int i = 0; i < n; i ++) {if (a[i] != aver) {if (a[i] >= aver) {now += a[i] - aver;} else {now -= (aver - a[i]);if (now < 0) {cout << "NO" << endl;return;}}}}if (!now) {cout << "YES" << endl;return;}cout << "NO" << endl;
}

C. Make Equal Again

题意：通过一次操作，操作为选择任意长度区间变为同一个数，将长度为n的数组a的所有元素相同，最小化区间的元素数量。

思路：注意只能操作一次，那么就仨情况了，前半，后半，中间，记录开头连续相同的数量，和结尾连续相同的数量，取最大，若首尾相等则相加，答案则为除了这些相等的头尾的其余元素。

AC code：

void solve() {cin >> n;map<int, int> mp;for (int i = 1; i <= n; i ++) cin >> a[i], mp[a[i]] ++;int ans = INF;int cnt = 1, cnt2 = 1;int l = 1, r = n;int st = a[1];for (int i = 2; i <= n; i ++) {if (a[i] == st) cnt ++;else break;}ans = min(ans, n - cnt);st = a[n];for (int i = n - 1; i >= 1; i --) {if (a[i] == st) cnt2 ++;else break;}ans = min(ans, n - cnt2);if (a[1] == a[n]) ans = min(ans, n - cnt - cnt2);ans = max(0LL, ans);cout << ans << endl;
}

D. Divisible Pairs

题意：找出数组中符合条件的元素对，条件为 $a_i+a_j$被x整除， $a_i-a_j$被y整除。

思路：根据条件可以得知：

• $a_i-a_j$被y整除即 $a_i$ % y == 0 && $a_j$ % y == 0

• $a_i+a_j$被x整除即 （$a_i$%x+ $a_j$%x）% x == 0

由以上条件，用map<pair<int, int>, int>来记录每个元素对应xy取模，以第一个条件为基准，定一个元素通过第二个条件找另一个成对元素是否存在，详见代码。

AC code：

void solve() {cin >> n >> x >> y;for (int i = 1; i <= n; i ++) cin >> a[i];sort(a+1, a+n+1);map<PII, int> mp;for (int i = 1; i <= n; i ++) {mp[{a[i] % x, a[i] % y}] ++;}int ans = 0;for (int i = 1; i <= n; i ++) {int t = (x - (a[i] % x)) % x;ans += mp[{t, a[i] % y}];if (a[i] % x == t) ans --;}cout << ans / 2 << endl;
}

E. Anna and the Valentine’s Day Gift

题意：A和B对一个n数组中的元素进行轮流操作，A先手

• 当A出手时，选择任意一个元素倒转，若倒转后有前置零则消除
• 当B出手时，选择任意两个不同的元素进行拼接成一个新元素，原序列数量-1

A的获胜条件为最后留下的元素位数小于m，反之B获胜，双方博弈，谁能胜。

思路：

• 重点只在于一个元素是否有可能通过倒置操作减少位数，即末尾是否有连续的0，且对于一个元素倒置最多减少一次位数

• 我们可以计算每个元素初始后置0的数量，然后根据这个进行排序

• 轮到A时则去优先消除后置0多的元素，轮到B则优先可以合并两个元素来保一个后置0

AC code：

int find(int x) {int cnt = 0;while (x) {cnt ++;x /= 10;}return cnt;
}
int find_0(int x) {int cnt = 0;while (x % 10 == 0 && x != 0) {cnt ++;x /= 10;}return cnt;
}void solve() {cin >> n >> m;vector<PII> a(n);for (int i = 0; i < n; i ++) {int x; cin >> x;a[i].second = x;a[i].first = find_0(x);}sort(a.begin(), a.end());int ans = 0;for(int i = 0; i < n; i ++) {int t = a[i].second;ans += find(t);if (i % 2 != (n - 1) % 2) continue;ans -= find_0(t);}if (ans > m) cout << "Sasha" << endl;else cout << "Anna" << endl;
}

F. Chat Screenshots

题意：初始可能会有一个排序序列代表n个用户，用户会发送这个序列，发送的时候把自己调到第一个，即在原序列的基础上，每个用户发送的序列自己都是在第一位的，通过k名用户发送的序列，判断是否可能存在一个初始的序列。

思路：

• 如果可能存在这样的序列，那么不会存在除当前用户之外的序列顺序出现矛盾的情况。

• 这里可以直接存图，判断是否是一个拓扑排序即是否不存在环，存在则有矛盾条件。

• 存图是注意一是不需要存每个用户序列的第一个元素，因为真假存疑，二是除了第一个元素之外序列顺序存，维护前后元素即可。

AC code：

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define db double
#define pb push_back
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;typedef long long LL;
typedef pair<char, int> PCI;
typedef pair<int, int> PII;
const int N = 2e5+10, M = 2001;
const int INF = 0x3f3f3f3f3f, mod = 998244353;
int T, n, k;
vector<int> g[N];
int d[N];void solve() {for (int i = 1; i <= n; i ++) {g[i].clear(), d[i] = 0;}cin >> n >> k;while (k --) {vector<int> ca(n);for (int i = 0; i < n; i ++) cin >> ca[i];for (int i = 1; i < n - 1; i ++) {g[ca[i]].pb(ca[i + 1]);d[ca[i + 1]] ++;}}queue<int> q;for (int i = 1; i <= n; i ++) {if (d[i] == 0) q.push(i);}int cnt = 0;while (!q.empty()) {auto t = q.front();q.pop();cnt ++;for (auto u : g[t]) {d[u] --;if (d[u] == 0) q.push(u);}}if (cnt == n) cout << "YES" << endl;else cout << "NO" << endl;
}signed main() {fast();T = 1;cin >> T;while (T --) {solve();}return 0;
}