每日资讯：Educational Codeforces Round 123 (Rated for Div. 2)

2023-03-14 19:52:42 来源：博客园

(相关资料图)

Educational Codeforces Round 123 (Rated for Div. 2)

A Doors and Keys

Solution:

模拟

void solve(){string s;cin >> s;s = " " + s;int r, g , b;r = g = b = 0;for (int i = 1;i <= 6;i ++) {if(s[i] == "r") r = 1;if(s[i] == "g") g = 1;if(s[i] == "b") b = 1;if(s[i] == "R" && !r) {cout << "NO" << endl;return;}if(s[i] == "G" && !g) {cout << "NO" << endl;return;}if(s[i] == "B" && !b) {cout << "NO" << endl;return;}}cout << "YES" << endl;}

B Anti-Fibonacci Permutation

Solution:

考虑逆序排列一定符合要求，每次交换最后一个元素和倒数第二个元素即可

void solve(){int n;cin >> n;vector a(n + 1);for (int i = 1;i <= n;i ++) a[i] = n - i + 1;int last = n;for (int i = 1;i <= n;i ++) {for (int j = 1;j <= n;j ++) {cout << a[j] << " ";}cout << endl;swap(a[last],a[last - 1]);last --;}}

C

Solution:

本题$x > 0$所以考虑给每个可能的最大的子段加上$k * x $即可。

求最大子段的过程用DP实现，定义$f_{i}$为长度为$i$时的最大字段和。

void solve(){int n, x;cin >> n >> x;vector a(n + 1);vector s(n + 2);for (int i = 1;i <= n;i ++) cin >> a[i];for (int i = 1;i <= n;i ++) {s[i] = s[i - 1] + a[i];}vector f(n + 1,-1e15);f[0] = 0;for (int i = 1;i <= n;i ++) {for (int j = i;j <= n;j ++) {f[i] = max(f[i], s[j] - s[j - i]);}}// for (int i = 1;i <= n;i ++) {cout << f[i] << " ";} cout << endl;for (int k = 0;k <= n;k ++) {int mx = -1e9;for (int i = 1;i <= n;i ++) {mx = max(mx, f[i] + min(k , i) * x);}cout << max(mx, ll(0)) << " ";}cout << endl;}

D

Solution:

呜呜呜自己确实没想到这么做，正难则反，正着考虑会发现状态很多且很难找到符合复杂度的递推关系，所以我们反着考虑，因为最后一次染色肯定会覆盖之前的染色，我们只需要考虑，到最后一次染色之前，出现了多少个可以更新的状态即可。

void solve(){int n , m, k , q;cin >> n >> m >> k >> q;int ans = 1;vector fn(n + 1);vector fm(m + 1);vector cnt(q + 1);for (int i = 1;i <= q;i ++) {cin >> cnt[i].first >> cnt[i].second;}int nowx = 0;int nowy = 0;for (int i = q;i >= 1;i --) {if(nowx == n || nowy == m) continue;int x, y;x = cnt[i].first, y = cnt[i].second;int t = 1;if(fn[x] == 0)fn[x] = 1, nowx++,t = k;if(fm[y] == 0) fm[y] = 1, nowy++,t = k;ans = ans * t % mod;}cout << ans << endl;

E

Solution:

这题怎么说呢，感觉在纸上画画就会比较清楚了。

我的思路是这样的，先想到最后一个点右下的所有点，都是可以走到的点，必然被加入到答案里去，再考虑前面的点，第一个转角之前是无法改变状态的，但是在转角之后，每一个前进的方向都可以往他的相反方向加入一个$n - cnt_{R}$或者$n - cnt_{D}$，所以就有式子了，转角前的点答案全算上去，因为算最后右下覆盖的点的时候，多算了一个最终的点，前面减一就可以了。

void solve(){int n;string s;cin >> n >> s;int len = s.length();s = " " + s;int fx = 1;int fy = 1;for (int i = 1;i <= len;i ++) {if(s[i] == "R") fx ++;else fy ++;}int ans = 1;if(fx == 1 || fy == 1) {cout << n << endl;return ;}int l = 2;while(s[l] == s[l - 1])l ++;ans += l - 2;for (int i = l;i <= len;i ++) {if(s[i] == "R") ans += (n - fy);else ans += (n - fx);ans ++;}ans += (n - fx + 1) * (n - fy + 1);cout << ans << endl;}

关键词：