Codeforces Round 993 (Div. 4)

2024.12.15 rank289 +123：1381->1504

A

Cube is given an integer $n$. She wants to know how many ordered pairs of positive integers $(a,b)$ there are such that $a=n-b$. Since Cube is not very good at math, please help her!

B

A string consisting of only characters ‘p’, ‘q’, and ‘w’ is painted on a glass window of a store. Ship walks past the store, standing directly in front of the glass window, and observes string $a$. Ship then heads inside the store, looks directly at the same glass window, and observes string $b$.

Ship gives you string $a$. Your job is to find and output $b$.

C

Ball is the teacher in Paperfold University. The seats of his classroom are arranged in $2$ rows with $m$ seats each.

Ball is teaching $a+b+c$ monkeys, and he wants to assign as many monkeys to a seat as possible. Ball knows that $a$ of them only want to sit in row $1$, $b$ of them only want to sit in row $2$, and $c$ of them have no preference. Only one monkey may sit in each seat, and each monkey’s preference must be followed if it is seated.

What is the maximum number of monkeys that Ball can seat?

D

Given a sequence of positive integers, a positive integer is called a mode of the sequence if it occurs the maximum number of times that any positive integer occurs. For example, the mode of $[2,2,3]$ is $2$. Any of $9$, $8$, or $7$ can be considered to be a mode of the sequence $[9,9,8,8,7,7]$.

You gave UFO an array $a$ of length $n$. To thank you, UFO decides to construct another array $b$ of length $n$ such that $a_i$ is a mode of the sequence $[b_1,b_2,\dots ,b_i]$ for all $1\le i\le n$.

However, UFO doesn’t know how to construct array $b$, so you must help her. Note that $1\le b_i\le n$ must hold for your array for all $1\le i\le n$.

E

Wave is given five integers $k$, $l_1$, $r_1$, $l_2$, and $r_2$. Wave wants you to help her count the number of ordered pairs $(x,y)$ such that all of the following are satisfied:

• $l_1\le x\le r_1$.
• $l_2\le y\le r_2$.
• There exists a non-negative integer $n$ such that $\frac{y}{x}=k^n$.

G1

This is the easy version of the problem. The key difference between the two versions is highlighted in bold.

A group of $n$ spiders has come together to exchange plushies. Initially, each spider has $1$ plushie. Every year, if spider $i$ has at least one plushie, he will give exactly one plushie to spider $r_i$. Otherwise, he will do nothing. Note that all plushie transfers happen at the same time. In this version, if any spider has more than $1$ plushie at any point in time, they will throw all but $1$ away.

The process is stable in the current year if each spider has the same number of plushies (before the current year’s exchange) as he did the previous year (before the previous year’s exchange). Note that year $1$ can never be stable.

Find the first year in which the process becomes stable.

------------------------独自思考分割线------------------------

• nice！！

A

1. 发现答案为n-1。

B

1. 首先字符反转，p/q再反转。

C

1. 贪心a,b,再贪心c。

D

1. 比较有意思的构造。

E

1. 暴力思路肯定会T，考虑优化：发现合法的对于每个k，合法区间$l_1\le l\le r\le r_1$。
2. 同时k的取值很小。考虑两次二分找合法范围。

G1

1. 模拟过程找到循环。

------------------------代码分割线------------------------

A

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cout << fixed << setprecision(6);int T = 1;cin >> T;while (T--)_();return 0;
}void _()
{int n;cin >> n;cout << n - 1 << endl;
}

B

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cout << fixed << setprecision(6);int T = 1;cin >> T;while (T--)_();return 0;
}void _()
{string s;cin >> s;reverse(s.begin(), s.end());for (auto &v : s)if (v - 'w')v = v == 'p' ? 'q' : 'p';cout << s << endl;
}

C

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cout << fixed << setprecision(6);int T = 1;cin >> T;while (T--)_();return 0;
}void _()
{int m, a, b, c;cin >> m >> a >> b >> c;int res = 0, n1 = m, n2 = m;res += min(n1, a);n1 -= min(n1, a);res += min(n2, b);n2 -= min(n2, b);res += min(n1 + n2, c);cout << res << endl;
}

D

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cout << fixed << setprecision(6);int T = 1;cin >> T;while (T--)_();return 0;
}void _()
{int n;cin >> n;vector<int> a(n);map<int, int> has, in;for (int &v : a)cin >> v, has[v] = 1;queue<int> no_has;for (int i = 1; i <= n; i++)if (!has[i])no_has.push(i);for (int i = 0; i < n; i++)if (i){if (a[i] == a[i - 1] || in[a[i]]){cout << no_has.front() << ' ';in[no_has.front()] = 1;no_has.pop();}elsecout << a[i] << ' ', in[a[i]] = 1;}elsecout << a[i] << " ", in[a[i]] = 1;cout << endl;
}

E

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cout << fixed << setprecision(6);int T = 1;cin >> T;while (T--)_();return 0;
}void _()
{int k, l1, r1, l2, r2;cin >> k >> l1 >> r1 >> l2 >> r2;int base = 1;int res = 0;for (; l1 * base <= r2; base *= k){int l = l1 - 1, r = r1 + 1;while (r - l - 1){int mid = l + r >> 1;if (mid * base <= r2)l = mid;elser = mid;}// bug2(l, l * base);int u = l;if (u < l1)continue;l = l1 - 1, r = u + 1;while (r - l - 1){int mid = l + r >> 1;if (mid * base >= l2)r = mid;elsel = mid;}if (r > u)continue;res += u - r + 1;}cout << res << endl;
}

G1

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cout << fixed << setprecision(6);int T = 1;cin >> T;while (T--)_();return 0;
}void _()
{int n;cin >> n;vector<int> a(n + 1);map<int, int> has;for (int i = 1; i <= n; i++){cin >> a[i];has[a[i]]++;}vector<int> no_has;for (int i = 1; i <= n; i++)if (!has[i])no_has.push_back(i);for (int i = 2;; i++){if (no_has.size() == 0){cout << i << endl;return;}vector<int> vec;for (auto v : no_has){has[a[v]]--;if (has[a[v]] == 0)vec.push_back(a[v]);}no_has = vec;}
}