Codeforces Round 905 (Div. 3) 补题报告

本文主要是介绍Codeforces Round 905 (Div. 3) 补题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 AC情况

A	B	C	D	E	F	G1	G2
$\color{green}\texttt{Accepted}$	$\color{green}\texttt{Accepted}$	$\color{green}\texttt{Accepted}$	$\color{green}\texttt{Accepted}$	$\color{green}\texttt{Accepted}$	-	-	-

2 题解

A. Morning

Problem - A - Codeforces | Morning - 洛谷

题目描述

输入 $t$ 组数据。

每组数据有一个四位密码。现在密码输入设备上有一个数列1234567890，初始时光标指向1。

在 $1$ 秒内，你可以：

按下光标以显示当前数字；
将光标移动到任何相邻的数字。

请计算输入给定的四位密码所需的最少秒数。

题解

模拟即可，注意把0看做10来处理，这样从数字 $i$ 移动到数字 $j$ 所需的秒数就是 $\left|i - j\right|$ ，最后再加上显示数字的时间 $4$ 即可。

代码如下：

#include <bits/stdc++.h>
#define endl '\n'
#define file(FILENAME) freopen(FILENAME ".in", "r", stdin), freopen(FILENAME ".out", "w", stdout)
#define CLOSE ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int n, t;
int main() {CLOSE;cin >> t;while (t--) {cin >> n;int a = n / 1000, b = n / 100 % 10, c = n / 10 % 10, d = n % 10;  //拆分数字if (a == 0) a = 10;  //10替换0if (b == 0) b = 10;if (c == 0) c = 10;if (d == 0) d = 10;int ans = 4 + abs(a - 1) + abs(b - a) + abs(c - b) + abs(d - c);  //移动时间+显示时间cout << ans << endl; }return 0;
}

B. Chemistry

Problem - B - Codeforces | Chemistry - 洛谷

题目描述

输入 $t$ 组数据。

每次输入 $n$ 和 $k$ ，和一个仅包含小写字母的字符串 $s$ （ $\left|s\right| = n$ ）。问在 $s$ 中删除 $k(0\le k < n)$ 个字符后，将 $s$ 重新排列，能否构成一个回文串。

题解

回文串的特征：

最多只存在一个字母出现次数为奇数；
其余字母出现次数均为偶数。

我们可以从出现奇数次的字母入手，如果出现奇数次，删去一个，使它成为偶数；不能删了，就记录下奇数的个数。

如果最后出现奇数次的字母的个数大于 $1$ ，那么一定不是回文串。

代码如下：

#include <bits/stdc++.h>
#define endl '\n'
#define file(FILENAME) \freopen(FILENAME ".in", "r", stdin), freopen(FILENAME ".out", "w", stdout)
#define CLOSE                    \ios::sync_with_stdio(false); \cin.tie(0);                  \cout.tie(0)
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int n, k, t, cnt[N];
char s[N];
int main() {CLOSE;cin >> t;while (t--) {memset(cnt, 0, sizeof cnt);cin >> n >> k;cin >> s;for (int i = 0; i < n; i++)  //记录出现次数cnt[s[i]]++;int flag = 0;for (int i = 'a'; i <= 'z'; i++) {if (cnt[i] % 2 != 0) {  //出现奇数次if (k) {  //能删则删k--;cnt[i]--;} else  //不能删，记录个数flag++;}}cout << (flag <= 1 ? "YES\n" : "NO\n");}return 0;
}

C. Raspberries

Problem - C - Codeforces | Raspberries - 洛谷

题目描述

输入 $t$ 组数据。

每次给定数组 $a_1,a_2,\dots,a_n$ 和一个数 $k(2\le k\le 5)$ 。

每次操作你可以照顾到一个索引 $i(1\le i\le n)$ ，令 $a_i=a_i+1$ 。

问经过若干次操作后，能否使 $\prod_{i=1}^n a_i \mod k = 0$ 。

题解

观察发现， $k$ 的取值范围是 $2\sim 5$ ，除去 $2\times 2$ 以外，其他数分解质因数都还是本身。

分类讨论：

$\in \{2,3,5\}$ ：找到一个 $d_{min}(a_i+d_i\equiv 0 (\mod k)(1\le i\le n))$ ，也就是找到最小的一个大于 $a_i$ 且与它最近的 $k$ 的倍数与 $a_i$ 的差，则可知 $d_{min}= \min\left(\lceil\frac{a_i}{k}\rceil k - a_i\right)$
$k = 4$ ：有一下几种情况：
1. 存在 $a_i\mod 4=0(1\le i\le n)$ ，答案为 $0$
2. 存在 $a_i\mod 2 = 0,a_j\mod 2=0(1\le i,j\le n,i\ne j)$ ，答案为 $0$
3. 仅存在一个 $a_i\mod 2=0(1\le i\le n)$ ，再凑出一个偶数即可满足情况2，单位 $1$
4. 存在 $a_i\mod 4=1(1\le i\le n)$ ，答案为 $1$
5. 全部是奇数，则凑出两个偶数即可满足情况2，答案为 $2$
分别用变量记录各自所需的 $a_i$ 出现的次数即可，注意判断顺序，答案小的优先。

代码如下：

#include <bits/stdc++.h>
#define endl '\n'
#define file(FILENAME) \freopen(FILENAME ".in", "r", stdin), freopen(FILENAME ".out", "w", stdout)
#define CLOSE                    \ios::sync_with_stdio(false); \cin.tie(0);                  \cout.tie(0)
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int t, n, k, a;
int main() {CLOSE;cin >> t;while (t--) {cin >> n >> k;int ans = 0, p1 = 0, p2 = 0, p3 = 0, p4 = 0;for (int i = 1; i <= n; i++) {cin >> a;if (k != 4)  ans = min(ans, (a / k + (a % k != 0)) * k - a);  //k不是4，找d的最小值else {  //k = 4if (a % 4 == 0) p1++;  //记录情况1else if (a % 2 == 0) p2++;  //记录情况2、3else if ((a + 1) % 4 == 0) p3++;  //记录情况4else p4++;  //记录情况5}}if (k != 4) cout << ans << endl;else {if (p1 > 0) cout << 0 << endl;  //判断情况1else if (p2 >= 2) cout << 0 << endl;  //判断情况2else if (p2 == 1) cout << 1 << endl;  //判断情况3else if (p3 > 0) cout << 1 << endl;  //判断情况4else cout << 2 << endl;  //判断情况5}}return 0;
}

D. In Love

Problem - D - Codeforces | In Love - 洛谷

题意描述

现在给出 $q$ 次操作：

$+\ l\ r$ ：在不去重集合中加入片段 $(l, r)$
$-\ l\ r$ ：在不去重集合中删除一个片段 $(l, r)$

每次操作后，判断集合中是否存在一对片段不重合。

题解

我们只需要判断相隔最小的两个片段是否重合即可。如果不重合，则至少存在一对；如果重合，那么其他的片段也必然重合。

而一对不重合的片段 $l_1,r_1)$ 和 $l_2, r_2)$ 满足 $r_1<l_1$ 。

所以，我们可以分开存储左端点 $l$ 和右端点 $r$ 。如果 $r_{min}<l_{max}$ ，则存在；反之，不存在。

能够快速排序和删除，还要满足不去重的特性，multiset是最佳的选择。

注意， $l$ 每次取最大值，而multiset默认升序排序，但我们知道， $\forall a<b<0,-a>-b$ ，可以保存 $- l$ 的值，删除使用时取相反数即可。

代码如下：

#include <bits/stdc++.h>
#define endl '\n'
#define file(FILENAME) \freopen(FILENAME ".in", "r", stdin), freopen(FILENAME ".out", "w", stdout)
#define CLOSE                    \ios::sync_with_stdio(false); \cin.tie(0);                  \cout.tie(0)
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int n, l, r;
map<int, int> visl, visr;
char k;
multiset<int> L, R;
int main() {CLOSE;cin >> n;for (int i = 1; i <= n; i++) {cin >> k >> l >> r;if (k == '+') {L.insert(-l);visl[l]++;R.insert(r);visr[r]++;} else {int t = L.erase(-l);t = R.erase(r);visl[l]--, visr[r]--;if (visl[l]) L.insert(-l);if (visr[r]) R.insert(r);}cout << (-(*L.begin()) > *R.begin() ? "YES\n" : "NO\n");}return 0;
}

E. Look Back

Problem - E - Codeforces | Look Back - 洛谷

题目描述

输入 $t$ 组数据。

给定一个数组 $a_1,a_2,\dots,a_n$ 。

可进行操作：找到一个索引 $i(1\le i\le n)$ ，令 $a_i = a_i\times 2$ 。

问最少进行多少次操作，能使数组成为一个非递减数组。

题解

$Log_i$ ：表示 $a_i$ 需要乘上 $2^i$ （即需要操作 $i$ 次）， $Log_i\in \N$ 。

从左往右对 $a_i(1\le i\le n)$ 操作。

先令 $Log_i=Log_{i-1}(2\le i\le n)$ 。

分类讨论：

$a_i>a_{i - 1}$ ：说明 $Log_i$ 过大，要让操作次数尽可能小且仍要满足条件，则设 $Log_i$ 要减去 $k(k\in \N)$
$\begin{aligned} a_i&\ge a_{i - 1}\times 2^{k} \\ 2^{k}&\ge \frac{a_{i}}{a_{i-1}} \\ \log_2\left(2^{k}\right)&\ge \log_2\left(\frac{a_{i}}{a_{i-1}}\right) \\ k&\ge \log_2\left(\frac{a_{i}}{a_{i-1}}\right) \\ \because k\in \N,a_i\times 2^{Log_{i - 1}-k}\ge a_{i - 1},\\ \therefore k&= \left\lfloor\log_2\left(\frac{a_{i}}{a_{i-1}}\right)\right\rfloor \end{aligned}$
注意， $Log_i$ 不能为负数，所以应是
$Log_i=\max\left(0,Log_{i-1}-\left\lfloor\log_2\left(\frac{a_{i}}{a_{i-1}}\right)\right\rfloor\right)$
$a_i<a_i-1$ ：同理，设 $Log_i$ 要加上 $k(k\in \N)$
$\begin{aligned} a_i \times 2^{k} &\ge a_{i - 1} \\ 2^{k}&\ge \frac{a_{i - 1}}{a_{i}} \\ \log_2\left(2^{k}\right)&\ge \log_2\left(\frac{a_{i-1}}{a_{i}}\right) \\ k&\ge \log_2\left(\frac{a_{i-1}}{a_{i}}\right) \\ \because k\in \N,a_i\times 2^{Log_{i - 1}+k}\ge a_{i - 1},\\ \therefore k&= \left\lceil\log_2\left(\frac{a_{i-1}}{a_{i}}\right)\right\rceil \end{aligned}$
由此可得
$Log_i=\max\left(0,Log_{i-1}+\left\lceil\log_2\left(\frac{a_{i-1}}{a_{i}}\right)\right\rceil\right)$

$\sum_{i=1}^nLog_i$ 就是操作总次数。

代码如下：

#include <bits/stdc++.h>
#define endl '\n'
#define file(FILENAME) \freopen(FILENAME ".in", "r", stdin), freopen(FILENAME ".out", "w", stdout)
#define CLOSE                    \ios::sync_with_stdio(false); \cin.tie(0);                  \cout.tie(0)
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int t, n;
ll a[N], Log[N];
int main() {CLOSE;cin >> t;while (t--) {cin >> n;ll ans = 0;for (int i = 1; i <= n; i++) {cin >> a[i];if (i > 1) {if (a[i] > a[i - 1])Log[i] =max((ll)0, Log[i - 1] -(ll)floor(log2(a[i] * 1.0 / a[i - 1])));elseLog[i] =max((ll)0,Log[i - 1] + (ll)ceil(log2(a[i - 1] * 1.0 / a[i])));ans += Log[i];}}cout << ans << endl;}return 0;
}