Codeforces Round 986 (Div. 2) CF2028 代码集

• Codeforces Round 986 (Div. 2) CF2028 代码集
  • CF2028A - Alice's Adventures in ''Chess''
  • CF2028B - Alice's Adventures in Permuting
  • CF2028C - Alice's Adventures in Cutting Cake
  • CF2024D - Alice's Adventures in Cards
  • CF2024E - Alice's Adventures in the Rabbit Hole
  • CF2024F - Alice's Adventures in Addition

CF2028A - Alice's Adventures in ''Chess''

int n, a, b;
string s;
void solve() {
	cin >> n >> a >> b;
	cin >> s; s = ' ' + s;
	int x = 0, y = 0;
	REP(_, 100) {
		FOR(i, 1, n) {
			if(x == a && y == b) {
				cout << "YES" << endl;
				return;
			}
			if(s[i] == 'W') x --;
			if(s[i] == 'E') x ++;
			if(s[i] == 'N') y ++;
			if(s[i] == 'S') y --;
		}
	}
	cout << "NO" << endl;
}

CF2028B - Alice's Adventures in Permuting

ll n, b, c;
void solve() {
	cin >> n >> b >> c;
	if(! b) {
		if(c <= n - 3) {
			cout << - 1 << endl;
		}
		else {
			cout << (c < n ? n - 1 : n) << endl;
		}
		return;
	}
	ll res = n;
	if(c < n) {
		res -= (n - 1 - c) / b + 1;
	}
	cout << res << endl;
}

CF2028C - Alice's Adventures in Cutting Cake

const int N = 2e5 + 5;
int n, m;
ll v, a[N], s[N];
int f[N], g[N];
void solve() {
	cin >> n >> m >> v;
	FOR(i, 1, n) cin >> a[i];
	FOR(i, 1, n) s[i] = s[i - 1] + a[i];
	FOR(i, 1, m) {
		int p = f[i - 1];
		while(p <= n && s[p] - s[f[i - 1]] < v) p ++;
		if(p > n) {
			cout << - 1 << endl;
			return;
		}
		f[i] = p;
	}
	g[0] = n + 1;
	FOR(i, 1, m) {
		int p = g[i - 1];
		while(p >= 1 && s[g[i - 1] - 1] - s[p - 1] < v) p --;
		g[i] = p;
	}
	ll ans = 0;
	FOR(i, 0, m) chmax(ans, s[g[i] - 1] - s[f[m - i]]);
	cout << ans << endl;
}

CF2024D - Alice's Adventures in Cards

const int N = 2e5 + 5;
int n, a[N], b[N], c[N];
PII pre[N];
set<PII> S1, S2, S3;
void add(int i) {
	S1.insert({a[i], i});
	S2.insert({b[i], i});
	S3.insert({c[i], i});
}
void solve() {
	cin >> n;
	FOR(i, 1, n) cin >> a[i];
	FOR(i, 1, n) cin >> b[i];
	FOR(i, 1, n) cin >> c[i];
	S1.clear(); S2.clear(); S3.clear();
	pre[n] = {0, 0};
	add(1);
	FOR(i, 2, n) {
		auto h = * S1.rbegin();
		if(FI(h) > a[i]) {
			pre[i] = {SE(h), 1};
			add(i);
			continue;
		}
		h = * S2.rbegin();
		if(FI(h) > b[i]) {
			pre[i] = {SE(h), 2};
			add(i);
			continue;
		}
		h = * S3.rbegin();
		if(FI(h) > c[i]) {
			pre[i] = {SE(h), 3};
			add(i);
			continue;
		}
	}
	if(! FI(pre[n])) {
		cout << "NO" << endl;
		return;
	}
	vector<pair<char, int>> ans;
	int u = n;
	while(u != 1) {
		if(SE(pre[u]) == 1) ans.push_back({'q', u});
		if(SE(pre[u]) == 2) ans.push_back({'k', u});
		if(SE(pre[u]) == 3) ans.push_back({'j', u});
		u = FI(pre[u]);
	}
	reverse(ans.begin(), ans.end());
	cout << "YES" << endl;
	cout << SZ(ans) << endl;
	for(auto h : ans) cout << FI(h) << " " << SE(h) << endl;
}

CF2024E - Alice's Adventures in the Rabbit Hole

const int N = 2e5 + 5;
const int P = 998244353;
const int INF = 1e9 + 7;
typedef Modint<P> mint;
int n;
int fi[N], ne[N << 1], to[N << 1], ecnt;
int d[N], son[N];
mint f[N], g[N], ans[N];
void add(int u, int v) {
	ne[++ ecnt] = fi[u];
	to[ecnt] = v;
	fi[u] = ecnt;
}
void dfs1(int u, int fa) {
	son[u] = - 1;
	for(int i = fi[u]; i; i = ne[i]) {
		int v = to[i];
		if(v == fa) continue;
		dfs1(v, u);
		if(son[u] == - 1 || d[v] < d[son[u]]) son[u] = v;
	}
	if(son[u] == - 1) {
		d[u] = 0;
		f[u] = g[u] = 0;
	}
	else if(u != 1) {
		int v = son[u];
		d[u] = d[v] + 1;
		mint x = mint(1) - f[v] / 2;
		f[u] = mint(1) / 2;
		g[u] = g[v] / 2;
		f[u] /= x, g[u] /= x;
	}
}
void dfs2(int u, int fa) {
	for(int i = fi[u]; i; i = ne[i]) {
		int v = to[i];
		if(v == fa) continue;
		ans[v] = f[v] * ans[u] + g[v];
		dfs2(v, u);	
	}
}
void solve() {
	cin >> n;
	FOR(i, 1, n) fi[i] = 0; ecnt = 0;
	REP(_, n - 1) {
		int u, v;
		cin >> u >> v;
		add(u, v);
		add(v, u);
	}
	dfs1(1, 0);
	ans[1] = 1;
	dfs2(1, 0);
	FOR(i, 1, n) cout << ans[i] << " "; cout << endl;
}

CF2024F - Alice's Adventures in Addition

const int N = 2e5 + 5;
const int M = 1e4 + 5;
const int V = 1e2 + 5;
int n, m, a[N], p[N], len;
PII b[N];
bitset<M> S, T, A, B[V];
void solve() {
	cin >> n >> m;
	FOR(i, 1, n) cin >> a[i];
	len = 0;
	FOR(i, 1, n) {
		if(a[i] == 1 && FI(b[len]) == 1) SE(b[len]) ++;
		else b[++ len] = {a[i], 1}; 
	}
	if(FI(b[len]) == 1 && SE(b[len]) > 1) {
		SE(b[len]) --;
		b[++ len] = {1, 1};
	}
	FOR(i, 0, len) p[i] = i % V;
	S.reset(); T.reset(); B[p[0]].reset();
	B[p[0]][0] = 1; T[0] = 1;
	FOR(i, 1, len) {
		if(FI(b[i]) == 0) S = T;
		B[p[i]].reset();
		B[p[i]] |= S;
		int res = 1;
		ROF(j, i, 1) {
			res *= FI(b[j]);
			if(res >= M) break;
			B[p[i]] |= B[p[j - 1]] << res;
			if(res == 0) break;
		}
		if(FI(b[i]) == 1) {
			A = B[p[i]];
			FOR(j, 1, SE(b[i]) - 1)
				B[p[i]] |= A << j;
		}
		T |= B[p[i]];
	}
	cout << (B[p[len]][m] ? "YES" : "NO") << endl;
}