Codeforces Round 964 (Div. 4)
锐评
感觉F题应该是可以做出来的，但是赛时没有想到阶乘预处理导致计算组合数超时，算是重大失误，还有C提交了三发才找到问题所在
A. A+B Again?
题意
给定一个两位数正整数 n ，求其数位之和。
输入描述
第一行包含一个整数 t ( 1 \leq t \leq 90 ) - 测试用例的数量。
每个测试用例的唯一一行包含一个两位数正整数 n ( 10 \leq n \leq 99 )。
输出描述
输出
对于每个测试用例，输出一个整数 - n 的数字之和。
样例输入
8
77
21
40
34
19
84
10
99
样例输出
14
3
4
7
10
12
1
18
思路
签到题不多说了
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n, m;
void solve() {
cin >> n;
cout << n / 10 + n % 10 << "\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
cin >> _;
while (_--) {
solve();
}
return 0;
}
B. Card Game
题意
Suneet 和斯拉夫玩纸牌游戏。游戏规则如下
- 每张牌的整数值介于 1 和 10 之间。
- 每位玩家收到 2 张牌，牌面朝下(因此玩家不知道自己的牌)。
- 游戏采用回合制，由个回合组成。在一个回合中，双方随机抽取一张未翻开的牌并翻开。翻开的牌中数字严格意义上更大的一方获胜。如果数字相等，则无人获胜。
- 如果一名玩家赢得的回合数最多(即严格意义上大于另一名玩家)，则该玩家赢得游戏。如果相等，则无人获胜。
由于 Suneet 和 Slavic 并不是最好的朋友，您需要计算 Suneet 最终成为赢家的可能性有多少。
为了更好地理解，请查看注释部分。
输入描述
第一行包含一个整数 t ( 1 \leq t \leq 10^4 ) - 测试用例的数量。
每个测试用例的第一行也是唯一一行包含 4 个整数 a_1 、 a_2 、 b_1 、 b_2 ( 1 \leq a_1, a_2, b_1, b_2 \leq 10 )，其中 a_1 和 a_2 分别代表 Suneet 拥有的卡片， b_1 和 b_2 分别代表 Slavic 拥有的卡片。
输出描述
对于每个测试案例，输出一个整数--考虑到所有可能的游戏，Suneet 会赢的游戏数量。
样例输入
5
3 8 2 6
1 1 1 1
10 10 2 2
1 1 10 10
3 8 7 2
样例输出
2
0
4
0
2
思路
按照题目所说的模拟即可，你A1和B1比的时候A2和B2比，A1和B2比的时候A2和B1比，注意先用A1还是先用A2，不同顺序的结果也是不一样
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n, m;
void solve() {
int a1, b1, a2, b2;
cin >> a1 >> a2 >> b1 >> b2;
int ans = 0;
//a1 : b1 a2 : b2
if (a1 > b1)
if (a2 >= b2) ans ++;
else if (a1 == b1)
if (a2 > b2) ans ++;
//a1 : b2 a2 : b1
if (a1 > b2)
if (a2 >= b1) ans ++;
else if (a1 == b2)
if (a2 > b1) ans ++;
//a2 : b1 a1 : b2
if (a2 > b1)
if (a1 >= b2) ans ++;
else if (a2 == b1)
if (a1 > b2) ans ++;
//a2 : b2 a1 : b1
if (a2 > b2)
if (a1 >= b1) ans ++;
else if(a2 == b2)
if (a1 > b1) ans ++;
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
cin >> _;
while (_--) {
solve();
}
return 0;
}
C. Showering
题意
作为一名计算机科学专业的学生，亚历克斯面临着一个严峻的挑战--洗澡。他努力每天洗澡，但尽管他尽了最大努力，却总是遇到困难。他需要花 s 分钟洗澡，而一天只有 m 分钟！
他已经为一天安排了 n 项任务。任务 i 被表示为一个时间间隔 (l_i , r_i) ，这意味着亚历克斯很忙，不能在这个时间间隔内(严格来说是在 l_i 和 r_i 之间的任意时间点)洗澡。**没有两项任务重叠。
在所有 n 个时间间隔内，亚历克斯当天能洗澡吗？换句话说，亚历克斯是否有一个长度至少为 s 的空闲时间间隔？
在第一个测试案例中，亚历克斯可以在一天的前 3 分钟洗澡，并且不会错过任何任务。
输入描述
第一行包含一个整数 t ( 1 \leq t \leq 10^4 ) - 测试用例数。
每个测试用例的第一行包含三个整数 n 、 s 和 m ( 1 \leq n \leq 2 \cdot 10^5 ; 1 \leq s, m \leq 10^9 )--即亚历克斯已经计划好的时间间隔数、亚历克斯洗澡的时间以及一天的分钟数。
接着是 n 行，其中的 i 行包含两个整数 l_i 和 r_i ( 0 \leq l_i < r_i \leq m )--第 i 个任务的时间间隔。没有两个任务重叠。
输入的附加限制： 对于每 i > 1 有 l_i > r_{i-1} 。
所有测试用例中 n 的总和不超过 2 \cdot 10^5 。
输出描述
对于每个测试用例，如果 Alex 可以为该测试用例洗澡，则输出 "YES" (不带引号)，否则输出 "NO" (也不带引号)。
您可以在任何情况下输出 "YES "和 "NO" (例如，字符串 "yEs"、"yes "和 "Yes "将被识别为肯定回答)。
样例输入
4
3 3 10
3 5
6 8
9 10
3 3 10
1 2
3 5
6 7
3 3 10
1 2
3 5
6 8
3 4 10
1 2
6 7
8 9
样例输出
YES
YES
NO
YES
思路
你需要将每一个任务区间的左右端点同时记录下来即可，然后判断前一个的结束时间和到后一个的开始时间中间能否洗澡，最后再判断第一个任务开始和最后一个任务结束两头的时间够不够。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 9;
int n, m, t;
pair<int,int>p[N];
void solve() {
cin >> n >> t >> m;
int sum = 0;
for (int i = 1; i <= n; ++ i) {
cin >> p[i].first >> p[i].second;
}
sort(p + 1, p + 1 + n);
if (p[1].first >= t) {
cout << "YES\n";
return;
}
int last = 0;
for (int i = 2; i <= n; ++ i) {
if (p[i].first - p[i - 1].second >= t) {
cout << "YES\n";
return;
}
last = p[i].second;
}
if (m - p[n].second >= t) {
cout << "YES\n";
return ;
}
cout << "NO\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
cin >> _;
while (_--) {
solve();
}
return 0;
}
D. Slavic's Exam
题意
斯拉夫的考试非常难，他需要您的帮助才能通过考试。下面是他正在苦苦思索的问题：
存在一个字符串 s ，它由小写英文字母和可能是零个或多个 "? " 组成。
要求斯拉夫人将每个 "? " 改为小写英文字母，使字符串 t 成为字符串 s 的子序列(不一定连续)。
输出任何这样的字符串，如果没有符合条件的字符串存在，则说不可能。
输入描述
第一行包含一个整数 t ( 1 \leq t \leq 10^4 ) - 测试用例数。
每个测试用例的第一行包含一个字符串 s ( 1 \leq |s| \leq 2 \cdot 10^5 和 s 仅由小写英文字母和 "?"
每个测试用例的第二行包含一个字符串 t （ 1 \leq |t| \leq |s| 且 t 仅由小写英文字母组成）—该字符串应该是字符串 s 的子串。
所有测试用例中 |s| 的总和不超过 2 \cdot 10^5 ，其中 |x| 表示字符串 x 的长度。
输出描述
对于每个测试用例，如果不存在语句中描述的字符串，则输出 "NO" (不带引号)。
否则，输出 "YES" (不带引号)。然后，输出一行 -- 符合所有条件的字符串。
您可以在任何情况下输出 "YES "和 "NO" (例如，字符串 "yEs"、"yes "和 "Yes "将被视为肯定回答)。
如果可能有多个答案，则可以输出其中任何一个。
样例输入
5
?????
xbx
ab??e
abcde
ayy?x
a
ab??e
dac
paiu
mom
样例输出
YES
xabax
YES
abcde
YES
ayyyx
NO
NO
思路
是比较简单的字符串匹配问题
- 用上去先去遍历i遍历s字符串，j遍历T字符串当两个字符相同时j++
- 当还是字符串是？时将t对应的字符赋给当前遍历到的？
- 如果最后能将T字符串编辑完那代表是可以的，请时将剩余的S字符串后面带有？的部分随便赋成字母即可
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 9;
int n, m;
void solve() {
string s, t;
cin >> s >> t;
int j = 0;
bool ok = false;
for (int i = 0; i < s.size(); ++ i) {
if (s[i] == t[j]) {
j ++;
}else if (s[i] == '?') {
s[i] = t[j];
j ++;
}
if (j == t.size()) {
break;
}
}
if (j == t.size()) {
cout << "YES\n";
for (int k = j; k < s.size(); ++ k) {
if (s[k] == '?') s[k] = 'a';
}
cout << s << "\n";
}
else cout << "NO\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
cin >> _;
while (_--) {
solve();
}
return 0;
}
E. Triple Operations
题意
艾维在黑板上写下了从 l 到 r (含)的所有整数。
在一次运算中，她做了以下操作：
- 在黑板上选出两个数字 x 和 y ，擦掉它们，然后在它们的位置上写下数字 3x 和 \lfloor \frac{y}{3} \rfloor 。(这里的 \lfloor \bullet \rfloor 表示四舍五入到最接近的整数）。
要使黑板上的所有数字都等于 0 ，艾维最少需要进行多少次运算？我们可以证明这总是可能的。
输入描述
第一行包含一个整数 t ( 1 \leq t \leq 10^4 ) - 测试用例的数量。
每个测试用例的唯一一行包含两个整数 l 和 r ( 1 \leq l < r \leq 2 \cdot 10^5 )。
输出描述
对于每个测试用例，输出一个整数 - 使电路板上的所有数字等于 0 所需的最少运算次数。
样例输入
4
1 3
2 4
199999 200000
19 84
样例输出
5
6
36
263
思路
说是四舍五入到最近的整数实际上还是下位除法
- 不难想到最优也一定是先变成一个0，然后用0去不断地×3，其他数不断的÷3最后全为0
- 最开始我想的是从最小的两个数里边选一个让它先变成0，后来发现只要他们÷3的次数一样选哪个结果不变，所以我们就默认去选最小的
- 我们先将最小的两个数操作一下，最小的不断÷3，第二小的不断×3直到最小的为0，再算第二小的数×3后能被3除多少次。往后从l+2开始看每个数能除以多少次3，结果累加，但是这样朴素的算法会超时。
- 所以我们就从三的幂数开始算，由于输入范围是2e5，所以我们将幂数算到14即可，3的14次方有七位，我们算当前的幂数的结果和当前幂数-1后的结果，取这个范围和我们l+2到r的范围的交集，有多少个数我们去将结果累加。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 9;
const int MOD = 998244353;
#define int long long
//快速幂
int qmi(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
//求逆元
int inv(int x) {return qmi(x, MOD - 2, MOD);}
int l, r;
void solve() {
cin >> l >> r;
int ans = 0;
int t = l, t1 = l + 1;
while (t) {
ans ++;
t /= 3;
t1 *= 3;
}
while (t1) {
ans ++;
t1 /= 3;
}
l += 2;
for (int i = 1; i <= 14; ++ i) {
int m = qmi(3, i, MOD);
m --;
int k = qmi(3, i - 1, MOD);
if (k > r) break;
int count = max(0ll, min(m, r) - max(l, k) + 1);
ans += count * i;
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
cin >> _;
while (_--) {
solve();
}
return 0;
}
F. Expected Median
题意
Arul 有一个二进制数组 ^{\text{∗}} 。长度为 n 的 a 数组。
他将取长度为 k 的所有子序列 ^{\text{†}} ( k 为奇数)，并求出它们的中位数。 k 为奇数），并找出它们的中位数 ^{\text{‡}} 。
所有这些值的和是多少？
由于这个和可能非常大，因此输出它的模数 10^9 + 7 。换句话说，打印这个和除以 10^9 + 7 的余数。
^{\text{∗}} 二进制数组是一个只由 0 和 1 组成的数组。
^{\text{†}} 如果 b 可以从 a 中删除几个元素(可能是零，也可能是全部元素)，那么数组 b 就是数组 a 的子序列。子序列不必是连续的。
^{\text{‡}} 长度为奇数的数组 k 的中位数是排序后的第 \frac{k+1}{2} 个元素。
输入描述
第一行包含一个整数 t ( 1 \leq t \leq 10^4 ) - 测试用例数。
每个测试用例的第一行包含两个整数 n 和 k ( 1 \leq k \leq n \leq 2 \cdot 10^5 ，** k 为奇数**)，分别是数组的长度和子序列的长度。
每个测试用例的第二行包含 n 个整数 a_i ( 0 \leq a_i \leq 1 ) - 数组元素。
保证所有测试用例中 n 的总和不超过 2 \cdot 10^5 。
输出描述
打印每个测试用例的总和取模 10^9 + 7 。
样例输入
8
4 3
1 0 0 1
5 1
1 1 1 1 1
5 5
0 1 0 1 0
6 3
1 0 1 0 1 1
4 3
1 0 1 1
5 3
1 0 1 1 0
2 1
0 0
34 17
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
样例输出
2
5
0
16
4
7
0
333606206
思路
已知子序列长度是K中位数的位置是排序后第(K+1)/2，我们可以直接将数组进行排序，然后从第一个中位值到最后一个中位值遍历，左边和右边都取(K-1)/2个数，用组合数学去计算，将组合数结果相乘，最后累加在模1e 9+7。由于要算很多次组合数，所以可以将阶乘预处理出来，否则会超时。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int N = 1e6 + 9;
const int MOD = 1e9 + 7;
//快速幂
int qmi(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
//求逆元
int inv(int x) {return qmi(x, MOD - 2, MOD);}
int n, k, a[N];
int f[N];
void C_init() {
f[0] = 1;
for (int i = 1; i <= N; ++ i) {
f[i] = f[i - 1] * i % MOD;
}
}
int C(int n,int m)
{
if(m == 0) return 1;
if(n == m) return 1;
if(n < m) return 0;
int res = 1;
int res2 = 1;
res = res * f[n] % MOD;
res2 = res2 * f[n-m] % MOD * f[m] % MOD;
res = res * inv(res2) % MOD;
return res;
}
void solve() {
cin >> n >> k;
for (int i = 1; i <= n; ++ i) cin >> a[i];
sort(a + 1, a + 1 + n);
int t = (k + 1) / 2;
int m = (k - 1) / 2;
int ans = 0;
for (int i = t; i <= n && i + m <= n; ++ i) {
ans = (ans + (a[i] * (C(i - 1, m) * C(n - i, m)) % MOD) % MOD) % MOD;
//cout << C(i - 1, m) << " " << C(n - i, m) << "----\n";
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
cin >> _;
C_init();
while (_--) {
solve();
}
return 0;
}
