Educational Codeforces Round 175 (Rated for Div. 2) 比赛记录
比赛连接
手速场，上蓝场，但是有点唐，C 想错了写了半个多小时，想到正解不到 \(10\) 分钟就写出来了，看到 D 后悔没先做 D 了，过于简单了。
赛时切掉了 A – D，也算是成功渡劫上蓝了!
过题记录：
A. FizzBuzz Remixed
很明显，\(\bmod 3 = \bmod 5\)，首先要找 \(3\) 和 \(5\) 的公倍数，然后找到下一个 \(\bmod 3 = 0\) 的地方，这中间取模为 \(0, 1, 2\) 的都是可以取的，因此循环节为 \(15\)，每一个循环节内有三个满足答案的，因此我们先暴力算到一个 \(15\) 的倍数，然后再加上剩下的 \(/ 15 \times 3\) 即可得到答案。
void solve()
{
int n;cin >> n;
int ans = 0;
while(n % 15 != 0) {
if(n % 15 <= 2) {
ans ++;
}
n --;
}
ans ++;
ans += n / 15 * 3;
cout << ans << "\n";
}
B. Robot Program
很明显，按照题意，只要回到 \(0\)，就重来，那只要回了一次 \(0\)，后面的过程就是一个以 \(0\) 为起点的循环问题，因此只需要把初始起点第一次到达 \(0\) 的时刻找到，总时间减掉这个时刻，然后再计算一下从 \(0\) 作为起点下一次回到 \(0\) 的所需时间，用剩余时间除一下即可得到答案。（赛时代码写得有点shi，慎重观看）
void solve()
{
int n, x, k;cin >> n >> x >> k;
string s;cin >> s;
int ans = 0;
int cnt = 0;
bool ck = false;
if(x == 0)ck = true;
if(x != 0) {
for(auto &i : s) {
cnt ++;
if(i == 'L') {
x --;
} else {
x ++;
}
if(x == 0) {
ans ++;
k -= cnt;
ck = true;
break;
}
}
}
if(!ck) {
cout << 0 << '\n';
return;
}
cnt = 0;
ck = false;
for(auto &i : s) {
cnt ++;
if(i == 'L') {
x --;
} else {
x ++;
}
if(x == 0) {
ck = true;
break;
}
}
if(!ck) {
cout << ans << '\n';
} else {
ans += (k / cnt);
cout << ans << '\n';
}
}
C. Limited Repainting
赛时铸币卡了半个小时的一个题。
题目要我们求的是代价的最小值，而代价又是所有的不合法的点的最大值，那么这个题就是一个“找最大值的最小值”问题，考虑二分。
我们首先考虑两种颜色何时会被计入代价：
- 蓝色：没有被染色。
- 红色：被染成蓝色。
一开始就是红色，我们又何时需要去把他变成蓝色呢？如果一个蓝色的点，和另一个蓝色的点，合并染色，可以减少一次染色次数，并且其间红色的代价更低，那么此时把红色染成蓝色就更优。
也就是说，假设答案为 \(x\) 是满足的，那么大于 \(x\) 的也一定满足，因为如果 \(x\) 是满足的，那么此时错误颜色的最大值一定 \(\leq x\)，那么对于所有大于 \(x\) 的，也可以用这种情况来满足，因此答案的可行性具有单调性，可以二分。
我们对答案进行二分，检查每一个二分到的值 \(mid\) 是否合法，检查的时候，对于每一个大于 \(mid\) 的蓝色块，优先考虑能否向前合并减少染色次数（前面有蓝色的块并且途中的红色块的值都小于这个 \(mid\)，那就可行），不可行就增加染色次数，看最后染色次数是否超过 \(k\)。
void init() {
for(int i = 1;i <= n;i ++) {
vis[i] = false;
}
}
bool check(int x) {
int cnt = 0;
int mx = 0;
bool ck = false;
for(int i = 1;i <= n;i ++) {
if(s[i] == 'R') {
mx = max(mx, a[i]);
} else if(a[i] > x){
if(!ck)cnt ++;
else if(mx > x)cnt ++;
mx = 0;
ck = true;
}
}
return cnt <= k;
}
void solve()
{
cin >> n >> k;
init();
cin >> s;
s = ' ' + s;
int mx = 0;
for(int i = 1;i <= n;i ++)cin >> a[i], mx = max(mx, a[i]);
int l = -1, r = mx + 1;
while(l + 1 != r) {
int mid = l + r >> 1;
if(check(mid))r = mid;
else l = mid;
}
cout << r << '\n';
}
D. Tree Jumps
讲真我个人觉得 D 比 C 简单多了，当然也可能是我 C 实在是太蠢了。
D 题是一棵有根树，除了第二层的结点只能连接根外，每个结点都可以连接非父结点构成一个合法序列，问有多少种合法序列。
那这不就很明显的一个 BFS 序嘛，然后按 BFS 序进行 DP。
记 \(ans_i\) 为以 \(i\) 作为结尾的序列的合法序列数量，记 \(ad_i\) 为以第 \(i\) 层作为结尾的合法序列数，第一层和第二层的 \(ans_i\) 均为 \(1\)，其余层的状态转移方程为 \(ans_i = ad_{d_{fa_i}} – ans_{fa_i}\)，\(ad\) 数组把每一层的加起来就行，最后枚举每个结点的 \(ans_i\) 求和即可。
void dfs(int st) { //其实这个dfs完全没必要，直接bfs求就行，实时求一下每个结点的层数
for(auto &i : g[st]) {
d[i] = d[st] + 1;
dfs(i);
}
}
void bfs(int st) {
queue<int> q;
q.push(st);
while(q.size()) {
int now = q.front();
q.pop();
for(auto &i : g[now]) {
int pre = ans[now];
int pred = ad[d[now]];
if(now == 1) {
ans[i] = pred % M;
} else {
ans[i] = (pred - pre) % M;
}
ad[d[i]] = (ans[i] + ad[d[i]]) % M;
q.push(i);
}
}
}
void init(int n) {
for(int i = 0;i <= n;i ++) {
g[i].clear();
ans[i] = 0;
ad[i] = 0;
}
}
void solve()
{
int n;cin >> n;
init(n);
for(int i = 2;i <= n;i ++) {
int x;cin >> x;
g[x].push_back(i);
}
d[1] = 0;
ans[1] = 1;
ad[0] = 1;
dfs(1);
bfs(1);
int res = 0;
for(int i = 1;i <= n;i ++) {
res = (res + ans[i]) % M;
}
cout << (res % M + M) % M << '\n';
}
来源链接：https://www.cnblogs.com/TianTianChaoFangDe/p/18743047
没有回复内容