USACO2024DEC G
ケロシ
·
·
个人记录
写了三个乱搞。
A
很明显对于每个颜色，从左往右贪是对的。
所以每次更新时，二分找右端点，并记录下一次更新是什么时候，并扔进桶里。
复杂度未知，反正冲过去了。
const int N = 1e5 + 5;
const int INF = 1e9 + 7;
int n, a[N], b[N], len;
vector<int> p[N], e[N];
int f[N];
void upd(int u, int k) {
f[u] = 0;
int l = 0, res = INF;
while(l < SZ(p[u])) {
f[u] ++;
int L = l, R = SZ(p[u]) - 1, pos = l;
while(L <= R) {
int mid = L + R >> 1;
if(p[u][mid] - p[u][l] <= k) {
pos = mid;
L = mid + 1;
}
else {
R = mid - 1;
}
}
if(pos + 1 < SZ(p[u])) chmin(res, p[u][pos + 1] - p[u][l]);
l = pos + 1;
}
if(res <= n) e[res].push_back(u);
}
void solve() {
cin >> n;
FOR(i, 1, n) cin >> a[i];
FOR(i, 1, n) b[++ len] = a[i];
sort(b + 1, b + len + 1);
len = unique(b + 1, b + len + 1) - b - 1;
FOR(i, 1, n) a[i] = lower_bound(b + 1, b + len + 1, a[i]) - b;
FOR(i, 1, n) p[a[i]].push_back(i);
FOR(i, 1, len) e[1].push_back(i);
int ans = 0;
FOR(k, 1, n) {
for(int x : e[k]) {
ans -= f[x];
upd(x, k);
ans += f[x];
}
cout << ans << endl;
}
}
B
考虑优化，不难发现转移是一车区间，暴力找这些区间。
复杂度未知，跑的还挺快。
（可能就是 $\log$ 的吧，可能每次翻倍
```cpp
const int N = 5e5 + 5;
const int P = 1e9 + 7;
int add(int x, int y) { return (x + y < P ? x + y : x + y - P); }
void Add(int & x, int y) { x = (x + y < P ? x + y : x + y - P); }
int sub(int x, int y) { return (x < y ? x - y + P : x - y); }
void Sub(int & x, int y) { x = (x < y ? x - y + P : x - y); }
int mul(int x, int y) { return (1ll * x * y) % P; }
void Mul(int & x, int y) { x = (1ll * x * y) % P; }
int fp(int x, int y) {
int res = 1;
for(; y; y >>= 1) {
if(y & 1) Mul(res, x);
Mul(x, x);
}
return res;
}
int n, pre[N][2], nxt[N][2], s1[N], s2[N];
int dp[N], g[N][2];
string s;
int S(int l, int r, int o) {
if(l > r) return 0;
if(! l) return g[r][o];
return sub(g[r][o], g[l - 1][o]);
}
void solve() {
cin >> n;
cin >> s; s = ' ' + s;
FOR(i, 1, n) pre[i][0] = (s[i] == 'R' ? i : pre[i - 1][0]);
FOR(i, 1, n) pre[i][1] = (s[i] == 'B' ? i : pre[i - 1][1]);
nxt[n + 1][0] = nxt[n + 1][1] = n + 1;
ROF(i, n, 1) nxt[i][0] = (s[i] == 'R' ? i : nxt[i + 1][0]);
ROF(i, n, 1) nxt[i][1] = (s[i] == 'B' ? i : nxt[i + 1][1]);
FOR(i, 1, n) s1[i] = s1[i - 1] + (s[i] == 'R');
FOR(i, 1, n) s2[i] = s2[i - 1] + (s[i] == 'B');
dp[0] = g[0][0] = 1;
FOR(i, 1, n) {
if(s[i] == 'X') Add(dp[i], dp[i - 1]);
int pos = i;
while(1) {
int len = i - pos + 1;
int l = pos - len;
if(l < 1) break;
if(s1[i] - s1[l - 1]) break;
if(s2[pos - 1] - s2[l - 1]) {
pos = nxt[l][1];
continue;
}
int pl = max(pre[l][0], pre[l][1]);
Add(dp[i], S(pl, l - 1, i % 2));
pos = pl;
}
if(pre[i][0]) {
int pl = pre[i][0];
int pr = min(i, nxt[pl][1]);
chmin(pr, (pl + i + 1) / 2);
int L = pl + 1, R = pr, pos = - 1;
while(L <= R) {
int mid = L + R >> 1;
int len = i - mid + 1;
int l = mid - len;
if(l >= 1 && ! (s2[mid - 1] - s2[l - 1])) {
pos = mid;
R = mid - 1;
}
else {
L = mid + 1;
}
}
if(pos != - 1) {
int len = i - pos + 1;
int ql = pos - len;
len = i - pr + 1;
int qr = pr - len;
Add(dp[i], S(ql - 1, qr - 1, i % 2));
}
}
g[i][0] = g[i - 1][0];
g[i][1] = g[i - 1][1];
Add(g[i][i % 2], dp[i]);
}
cout << dp[n] << endl;
}
```
## C
首先 $s_1 < t_2$ 且 $s_2 \ge t_1$ 时，这两个东西交换更优。所以按照 $s+t$ 排序。
然后看选还是不选，先写了一个 $n^2$ dp，看差分数组，发现转移是神秘贪
神秘贪好像就是某种反悔贪
贪心加入，如果超时就试试弹掉用时最久的
（好像挺有道理
正确性未知。反正过了就行（心虚
```cpp
const int N = 2e5 + 5;
int n;
struct Node {
ll s, t;
bool operator < (const Node & A) const {
return s + t < A.s + A.t;
}
} a[N];
void solve() {
cin >> n;
FOR(i, 1, n) cin >> a[i].s >> a[i].t;
sort(a + 1, a + n + 1);
ll sum = 0;
multiset<ll> S;
FOR(i, 1, n) {
if(a[i].s >= sum) {
S.insert(a[i].t);
sum += a[i].t;
}
else if(! S.empty()) {
ll mx = * S.rbegin();
if(a[i].t < mx && a[i].s >= sum - mx) {
S.erase(prev(S.end()));
S.insert(a[i].t);
sum -= mx;
sum += a[i].t;
}
}
}
cout << SZ(S) << endl;
}
```