Educational Codeforces Round 98 (Rated for Div. 2) A-E 题解
A. Robot Program
题意
给定 x , y x,y x,y ，一个机器人要从 ( 0 , 0 ) (0,0) (0,0)点走到 ( x , y ) (x,y) (x,y)点，每次操作能上下左右移动或者不动，且每次操作不能和上次操作相同，问最小操作次数。
思路
面 向 样 例 编 程
其实就是每次向下或向右走，先交替，若到底还需要向右走，则一开始就向右走，之后每走一秒停一秒。反之亦然，不影响答案。
答案为 x + y + m a x ( 0 , a b s ( x − y ) − 1 ) x + y + max(0, abs(x – y) – 1) x+y+max(0,abs(x−y)−1)
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int x, y;
cin >> x >> y;
cout << x + y + max(0, abs(x - y) - 1) << '\n';
}
return 0;
}
B. Toy Blocks
题意
有 n （ 2 ≤ n ≤ 1 0 5 ） n（2 \le n \le 10^5） n（2≤n≤105） 堆玩具，选取其中任意一堆，把这一堆所有（原题面就是加粗的）玩具都任意分配到其它堆上。
现给你每一堆分别有多少玩具，要达成的条件是，选取任意一堆，都能通过上述的操作，使得剩下的 n − 1 n-1 n−1 堆相等。问你最少加多少个玩具使条件成立。
思路
一开始漏了加粗的关键字，想半天搞不出来导致这场掉分了淦。
考虑任意一堆分配完都要使剩下的堆相等。且一定要达到原本最高的那一堆的高度。
即 a n s = m a x ( ⌈ s u m n − 1 ⌉ , m x ) ∗ ( n − 1 ) ans = max(\lceil \frac{sum}{n-1} \rceil ,mx) * (n-1) ans=max(⌈n−1sum⌉,mx)∗(n−1)
m x mx mx表示最高那一堆的高度。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll a[N];
int main() {
int T;
cin >> T;
while (T--) {
ll n;
cin >> n;
ll sum = 0;
for (int i = 1; i <= n; ++i) cin >> a[i], sum += a[i];
sort(a + 1, a + 1 + n);
ll ans = 0;
ll need = max((sum + n - 2) / (n - 1) * (n - 1), a[n] * (n - 1));
cout << need - sum << '\n';
}
return 0;
}
C. Two Brackets
题意
括 号 匹 配
不会有人不会括号匹配吧（
题意是给一个字符串，仅由括号组成，每次可以移除一对匹配上的括号，问你能移除多少对。
这不就是求有多少对括号匹配吗。
思路
可以直接堆栈模拟，当然懒狗直接用map了，其实两个cnt就解决了
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
map<int, int> mp;
int ans = 0;
string s;
cin >> s;
for (char ch : s) {
if (ch == '(') {
mp[1]++;
} else if (ch == '[') {
mp[2]++;
} else if (ch == ')') {
if (mp[1]) {
ans++;
mp[1]--;
}
} else if (ch == ']') {
if (mp[2]) {
ans++;
mp[2]--;
}
}
}
cout << ans << '\n';
}
return 0;
}
吐槽
这场的梯度真的离谱，C过的比B多贼多，到E直接难度起飞。
D. Radio Towers
题意
在 [ 1 , n ] [1,n] [1,n]每个城镇都有 1 2 \frac{1}{2} 21 的概率安装天线，你可以指定天线的辐射范围，至少会辐射天线所在的位置，左右对称（如天线2可以辐射 [ 2 , 2 ] [2,2] [2,2]或 [ 1 , 3 ] [1,3] [1,3]），问，安装的天线能使所有信号不相交且恰好覆盖 [ 1 , n ] [1,n] [1,n]的概率是多少。 m o d 998244353 mod\ 998244353 mod 998244353
思路
把整个看成一个01状态，每个状态的概率都是 1 2 n \frac{1}{2^n} 2n1
其实就是把 n n n 给划分成任意个奇数的方案数。
记方案数为 f f f , f ( i ) f(i) f(i)是所有 f ( i − 1 ) , f ( i − 3 ) … f(i-1),f(i-3)\dots f(i−1),f(i−3)… 的和，因为只能划分成奇数。
那么就是当前为奇数，则加上偶数的和，反之亦然。
整个过程其实就是个斐波那契。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
ll qpow(ll a, ll b) {
ll ret = 1;
a %= mod;
while (b) {
if (b & 1) {
ret = ret * a % mod;
}
a = a * a % mod;
b >>= 1;
}
return ret;
}
const int N = 2e5 + 10;
int main() {
int n;
cin >> n;
ll tmp = qpow(qpow(2, n), mod - 2);
ll ans = 0;
ll sum1 = 1, sum2 = 0;
for (int i = 2; i <= n; i++) {
if (i % 2) {
sum1 += sum2;
sum1 %= mod;
} else {
sum2 += sum1;
sum2 %= mod;
}
}
if (n % 2) {
ans = tmp * sum1 % mod;
} else {
ans = tmp * sum2 % mod;
}
cout << ans;
return 0;
}
E. Two Editorials
题意
现有 n n n 道题， m m m 个听题人，每个人想听 [ l , r ] [l,r] [l,r] 区间内的题的题解。
两个讲题人，每个人会讲 k k k 题（必须连续），对于每个听题人，他会选择重合题数多的那个讲题人去听。
对于每个人，他的满意度就是他听到的题数。
问讲题人如何选题，使满意度总和最大，输出最大满意度总和。
思路
考虑出题人区间和听题人区间的重合度和他们中间点位置的关系。
出题人区间中点从左到右移动。一开始，它逐渐接近听题人区间的中点，重合度上升，一直到两个中点重合过后，重合度开始下降。从这里我们可以看出，两个区间中点越近，重合度就越高。
那么我们根据中点排序所有听题人的区间，左边部分听第一个人，右边部分听第二个人。先枚举第一个人的讲题区间，并枚举听题人数，算出贡献。然后枚举第二个人的讲题区间，枚举听题人数，对应上刚才枚举保存的第一个人的贡献，加起来更新答案即可。
代码
#include <bits/stdc++.h>
using namespace std;
struct seg {
int l, r;
bool operator<(const seg &ano) const {
return l + r < ano.l + ano.r;
}
};
int main() {
int n, m, k;
cin >> n >> m >> k;
vector<seg> vec(m);
for (int i = 0; i < m; ++i) {
cin >> vec[i].l >> vec[i].r;
}
sort(vec.begin(), vec.end());
vector<int> sum(m + 1);
for (int i = 0; i < n - k + 1; ++i) {
int now = 0;
for (int j = m - 1; j >= 0; --j) {
now += max(0, min(i + k, vec[j].r) - max(vec[j].l, i + 1) + 1);
sum[j] = max(sum[j], now);
}
}
int ans = 0;
for (int i = 0; i < n - k + 1; ++i) {
int now = 0;
for (int j = 0; j < m; ++j) {
now += max(0, min(i + k, vec[j].r) - max(vec[j].l, i + 1) + 1);
ans = max(ans, now + sum[j + 1]);
}
}
cout << ans;
return 0;
}
By Boboge.
本文地址：https://blog.csdn.net/avgstuBoboge/article/details/110132463