USACO2024DEC G

写了三个乱搞。

A

很明显对于每个颜色，从左往右贪是对的。

所以每次更新时，二分找右端点，并记录下一次更新是什么时候，并扔进桶里。

复杂度未知，反正冲过去了。

CPP

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

n^2

dp 不难。

考虑优化，不难发现转移是一车区间，暴力找这些区间。

复杂度未知，跑的还挺快。

（可能就是

\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;
}

文章操作

A

B

C

相关推荐

评论

USACO2024DEC G