C. Cherry Picking
这道题用了一个类似 ODT 的题思路。
首先我们可以想到是,如果删除某些选手,只有可能会导致区间的合并,不会导致区间的分裂。所以我们可以枚举一下$x $的值,然后找到需要删除的点。用set
维护相同且相邻区间,找到删除点所在的区间后,给区间长度减一。如果区间长度为空后,就将该区间两侧的区间进行合并。同时在维护一下当前所有为 1 的区间长度。
#include <bits/stdc++.h>
using namespace std;
using ldb = long double;
using ll = long long;
using vi = vector<int>;
const int inf = 1e9;
struct Seg {
int l, r, tag;
mutable int len;
Seg(int l = 0, int r = 0, int tag = 0, int len = 0)
: l(l), r(r), tag(tag), len(len) {};
bool operator<(const Seg &b) const {
return l < b.l;
}
};
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<array<int, 3>> a(n);// {val, idx, tag}
for (int i = 0; i < n; i++)
cin >> a[i][0], a[i][1] = i;
string s;
cin >> s;
for (int i = 0; i < n; i++)
a[i][2] = (s[i] == '1');
set<Seg> seg;
multiset<int> cnt;
for (int i = 1, l = 0, tag = a[l][2]; i <= n; i++) {
if (i == n) {
seg.emplace(l, i - 1, tag, i - l);
if (tag == 1) cnt.insert(i - l);
} else if (a[i][2] != tag) {
seg.emplace(l, i - 1, tag, i - l);
if (tag == 1) cnt.insert(i - l);
l = i, tag = a[l][2];
}
}
sort(a.begin(), a.end());
int res = 0;
for (int x = 1, i = 0; x <= 2e5; x++) {
if (cnt.empty() or seg.empty()) break;
while (i < n and a[i][0] < x) {
auto [val, idx, tag] = a[i];
auto it = prev(seg.upper_bound(Seg(idx)));
assert(it->l <= idx and idx <= it->r and it->tag == tag);
if (tag == 1)
cnt.erase(cnt.find(it->len));
it->len--;
if (tag == 1 and it->len > 0)
cnt.insert(it->len);
if (it->len == 0) {
Seg cur(inf, -inf, -1, 0);
if (it != seg.begin()) {
auto L = prev(it);
cur.l = min(cur.l, L->l);
cur.r = max(cur.r, L->r);
cur.len += L->len;
cur.tag = L->tag;
if (L->tag == 1) cnt.erase(cnt.find(L->len));
seg.erase(L);
}
if (next(it) != seg.end()) {
auto R = next(it);
cur.l = min(cur.l, R->l);
cur.r = max(cur.r, R->r);
cur.len += R->len;
cur.tag = R->tag;
if (R->tag == 1) cnt.erase(cnt.find(R->len));
seg.erase(R);
}
seg.erase(it);
if (cur.tag != -1) {
seg.insert(cur);
if (cur.tag == 1) cnt.insert(cur.len);
}
}
i++;
}
if (not cnt.empty() and *cnt.rbegin() >= k)
res = max(res, x);
}
cout << res << "\n";
return 0;
}
H. Page on vdome.com
签到题
#include <bits/stdc++.h>
using namespace std;
#define ll long long
using vi = vector<int>;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
if(n < 10) cout << n + 1;
else cout << 10;
return 0;
}
K. Tasks and Bugs
简单模拟题
#include <bits/stdc++.h>
using namespace std;
using ldb = long double;
using ll = long long;
using vi = vector<int>;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
map<int, vector<int>> e;
while (getline(cin, s)) {
s += "@";
vector<int> a;
int cnt = 0, f = 0;
for (auto i: s) {
if (isdigit(i)) {
f = 1;
cnt = cnt * 10 + i - '0';
} else {
if (f) a.push_back(cnt);
cnt = f = 0;
}
}
for (int i = 1; i < a.size(); i++)
e[a[i]].push_back(a.front());
}
for (auto [id, v]: e) {
cout << "CS-" << id << ": ";
for (int f = 0; auto y: v) {
if (f) cout << ", ";
cout << "CS-" << y, f = 1;
}
cout << "\n";
}
return 0;
}
O. Mysterious Sequence
首先通过二维 dp,求出$X_n = a X_1 + b X_2 \(中的\)a,b\(然后解方程求出\)X_2 $,然后再重新递推出整个序列。
#include <bits/stdc++.h>
using namespace std;
using ldb = long double;
using ll = long long;
using vi = vector<int>;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(20);
ldb A, B;
cin >> A >> B;
int n;
cin >> n;
vector<ldb> a(n + 1);
cin >> a[1] >> a[n];
if(n == 2){
for(int i = 1; i <= n; i ++)
cout << a[i] << "\n";
return 0;
}
vector<array<ldb,2>> k(n + 1);
k[1] = {1, 0};
k[2] = {0, 1};
for(int i = 3; i <= n; i ++){
k[i][0] = k[i - 1][0] * A + k[i - 2][0] * B;
k[i][1] = k[i - 1][1] * A + k[i - 2][1] * B;
}
a[2] = (a[n] - k[n][0] * a[1]) / k[n][1];
for(int i = 3; i < n ; i ++)
a[i] = A * a[i - 1] + B * a[i - 2];
for(int i = 1; i <= n; i ++)
cout << a[i] << "\n";
return 0;
}
标签:Standings,cur,3rd,Cup,int,cnt,len,tag,using
From: https://www.cnblogs.com/PHarr/p/18371649