Educational Codeforces Round 150 (Rated for Div. 2)¶
比赛链接: https://codeforces.com/contest/1841
2025-03-19
VP 赛时只过了AB，C题花了好长时间才弄出来。
学习一下C的简单的写法，然后看看DE。试下能不能尽量把人数大于2000的题都学习一下。。
A¶
一定要读好题目啊，我A错了一发。。
急了，题都没读明白就交了。
B¶
没啥说的，虽然代码一开始写也是错的。。cin>>x[i] 写成了 cin>>x[q] ，就很搞笑了，找了半天。。
void ChatGptDeepSeek()
{
int q;
cin >> q;
vector<int> x(q);
for (int i = 0; i < q; i++)
cin >> x[i];
int lst = 0;
bool ok = true;
for (int i = 0; i < q; i++) {
// cerr << "lst:" << lst << " \n";
if (!ok) {
if (x[i] <= x[0] && x[i] >= lst) {
cout << "1";
lst = x[i];
} else
cout << "0";
continue;
}
if (x[i] >= lst) {
cout << "1";
lst = x[i];
} else if (ok && x[i] <= x[0]) {
cout << "1";
ok = false;
lst = x[i];
} else
cout << "0";
}
cout << '\n';
}
C¶
我的思路¶
我们可以枚举把每一个位置改成每一种字符的答案，首先我们计算去掉这个位置时的答案。肯定去掉自己本身的贡献。
但是可能去掉这一位，前面有的位的贡献会从负变为正。这种情况只出现在暂时没有遇到比自己大的位的位上，且去掉的这个数字必须是后缀的唯一最大值。如果存在这种情况，则需更新当前的后缀最大值。
然后可以计算当前这一位替换为其他字符的贡献。如果改的比当前的后缀最大值小，或者相等，那么不会影响前面的答案，只需增加当前位的贡献。
若更新得更大了，假设更新为 \(j\) ，则前面的在 \([suf_{now},j-1]\) 的位的贡献会由正变成负。
然后就模拟就行了。。
void ChatGptDeepSeek()
{
string s;
cin >> s;
s = " " + s;
int n = s.size() - 1;
vector<vector<int>> pre(n + 1, vector<int>(5));
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1];
pre[i][s[i] - 'A']++;
}
vector<int> suf(n + 1);
suf[n] = s[n] - 'A';
for (int i = n - 1; i >= 1; i--) {
suf[i] = max(suf[i + 1], s[i] - 'A');
}
vector<int> val { 1, 10, 100, 1000, 10000 };
ll ans = 0;
for (int i = 1; i <= n; i++) {
if (s[i] - 'A' >= suf[i])
ans += val[s[i] - 'A'];
else
ans -= val[s[i] - 'A'];
}
ll res = ans;
vector<int> cnt(5); // 每一种会被影响的 有多少个
for (int i = 1; i <= n; i++) {
ll now = ans;
if (s[i] - 'A' == suf[i])
now -= val[s[i] - 'A'];
else
now += val[s[i] - 'A'];
int now_suf = suf[i];
if (s[i] - 'A' == suf[i]) {
if (pre[n][s[i] - 'A'] - pre[i - 1][s[i] - 'A'] == 1) {
int sec = 0;
for (int j = s[i] - 'A' - 1; j >= 0; j--) {
if (pre[n][j] - pre[i - 1][j]) {
sec = j;
break;
}
}
now_suf = sec;
for (int j = sec; j < suf[i]; j++) {
now += cnt[j] * 2 * val[j];
}
}
}
for (int j = 0; j < 5; j++) {
if (j == s[i] - 'A')
continue;
if (j == now_suf) {
res = max(res, now + val[j]);
} else if (j > now_suf) {
// now_suf,j-1 之间的 ,减去
ll sub = 0;
for (int k = now_suf; k < j; k++) {
sub += 2LL * cnt[k] * val[k];
}
res = max(res, now + val[j] - sub);
} else if (j < now_suf) {
res = max(res, now - val[j]);
}
}
for (int j = 0; j < s[i] - 'A'; j++)
cnt[j] = 0;
cnt[s[i] - 'A']++;
}
cout << res << '\n';
}
DP¶
翻转字符串。。这样就是看前面有没有更大的字符了。。会简单很多。
好好好，看了题解就很爽了。。
\(dp_{0/1,i}\) 表示当前是否修改，最大值是 \(i\) ，只需要先翻转字符串，就变成了需要看前面的最大的字符。
constexpr int val[] { 1, 10, 100, 1000, 10000 };
void ChatGptDeepSeek()
{
string s;
cin >> s;
vector<vector<int>> dp(2, vector<int>(5, -1e9 + 1));
dp[0][0] = 0;
reverse(s.begin(), s.end());
for (int i = 0; i < s.size(); i++) {
vector ndp = vector<vector<int>>(2, vector<int>(5, -1e9 + 1));
int x = s[i] - 'A';
for (int j = 0; j < 5; j++) {
for (int k = 0; k < 5; k++) {
ndp[1][max(k, j)] = max(ndp[1][max(k, j)], dp[0][j] + (k < j ? -1 : 1) * val[k]);
}
ndp[0][max(x, j)] = max(ndp[0][max(x, j)], dp[0][j] + (x < j ? -1 : 1) * val[x]);
ndp[1][max(x, j)] = max(ndp[1][max(x, j)], dp[1][j] + (x < j ? -1 : 1) * val[x]);
}
dp = ndp;
}
cout << max(*max_element(dp[0].begin(), dp[0].end()), *max_element(dp[1].begin(), dp[1].end())) << '\n';
}
D¶
感觉我这回写的DP很对啊。。。
题解很对，很简单，但我的哪里错了呢？
题解的思路是
先把所有相交的线段给合成一个线段，然后最后的答案其实就是从这里选若干个不相交的线段出来。所以可以按 r 排序，能拿就拿。
void ChatGptDeepSeek()
{
int n;
cin >> n;
vector<int> l(n), r(n);
for (int i = 0; i < n; i++)
cin >> l[i] >> r[i];
vector<pair<int, int>> res;
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++) {
if (l[i] > r[j] || l[j] > r[i])
continue;
res.push_back({ min(l[i], l[j]), max(r[i], r[j]) });
}
sort(res.begin(), res.end(), [](pair<int, int> x, pair<int, int> y) { return x.second < y.second; });
int R = -1, ans = 0;
for (auto [l, r] : res) {
if (l > R) {
ans++;
R = r;
}
}
cout << n - 2 * ans << '\n';
}
改对了。。虽然没啥用。。对拍大法好啊。
void ChatGptDeepSeek()
{
int n;
cin >> n;
vector<pair<int, int>> a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i].first >> a[i].second;
sort(a.begin() + 1, a.end());
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 1e9 + 1));
vector<int> ans(n + 1, 0);
ans[0] = 0;
dp[0][0] = -1;
// dp[i][j]表示答案是j 的最小的 r
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1];
ans[i] = max(ans[i - 1], ans[i]);
// if (a[i].second < a[i + 1].first)
// continue;
/* 去前面找和自己相交的 */
for (int j = 1; j < i; j++) {
assert(ans[i] >= ans[j]);
if (a[j].second < a[i].first)
continue;
for (int k = 0; k <= ans[j]; k++) {
if (dp[j][k] < a[j].first) {
dp[i][k + 1] = min(dp[i][k + 1], max(a[i].second, a[j].second));
ans[i] = max(ans[i], k + 1);
}
}
}
for (int j = 1; j <= ans[i]; j++)
assert(dp[i][j] <= dp[i][j + 1]);
}
cout << n - ans[n] * 2 << '\n';
// cout << n << '\n';
}
又是两小时写一个题目。
E¶
六百六十六，我要直接抄题解了。。。抄完这题就先不看了。。
要求出每一个长度的段的数量。
.... 笑死了，抄题解都超不明白。。。还是早点休息吧。再也不想这样抄题解了。。
using ll = long long;
struct seg{
int l, r;
};
bool operator <(const seg &a, const seg &b){
return a.l < b.l;
}
void ChatGptDeepSeek()
{
map<seg, int> mp;
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
ll m;
cin >> m;
mp[{ 0, n }] = n;
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&a](int x, int y) {
return a[x] > a[y];
});
vector<ll> cnt(n + 2);
int j = 0;
for (int i = n; i >= 0; i--) {
while (j < n && a[ord[j]] >= i) {
auto it = mp.upper_bound({ ord[j], -1 });
--it;
auto tmp = it->first;
cnt[tmp.r - tmp.l] += it->second - i;
mp.erase(it);
if (tmp.l != ord[j])
mp[{ tmp.l, ord[j] }] = i;
if (ord[j] + 1 != tmp.r)
mp[{ ord[j] + 1, tmp.r }] = i;
j++;
}
}
ll ans = 0;
for (int i = n; i > 0; --i) {
long long t = min(cnt[i], m / i);
ans += t * 1ll * (i - 1);
m -= t * 1ll * i;
if (t != cnt[i] && m > 0) {
ans += m - 1;
m = 0;
}
}
cout << ans << '\n';
}