炼石计划 10 月 14 日 CSP-S 十连测 #4

AisDaeun 4 2023-10-29

体育课

考虑dfs搜索剪枝,如果到当前位之和已经超过了sum,则当前选择必不可能。

注意到:每位的贡献次数是n次二项式系数,所以直接杨辉三角预处理系数数组。

#include <bits/stdc++.h>
int read() {
	int x = 0; bool fl(0); char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) fl = ch == '-';
	for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
	return fl ? -x : x;
}
int pre[13][13], arr[13];
bool vis[13];
int n, sum;
void dfs(int cur, int cnt) {
	cnt += arr[cur] * pre[n][cur];
	if (cnt > sum) return;
	if (cur == n && cnt == sum) {
		for (int i = 1; i <= n; i++) std::cout << arr[i] << ' ';
		exit(0);
	}
	for (int i = 1; i <= n; i++) if (!vis[i]) {
		vis[i] = true;
		arr[cur + 1] = i;
		dfs(cur + 1, cnt);
		vis[i] = false;
	}
}
signed main() {
	freopen("p.in", "r", stdin);
	freopen("p.out", "w", stdout);
	std::ios::sync_with_stdio(false);
	n = read(), sum = read();
	pre[1][1] = 1;
	for (int i = 2; i <= n; i++)
		for (int j = 1; j <= i; j++) 
			pre[i][j] = pre[i - 1][j - 1] + pre[i - 1][j];
	dfs(0, 0);
	return 0;
}

宝石交易

桌面国王

#include <bits/stdc++.h>
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
struct node {int d1, d2, d3, d4;} tree[N << 2];
node operator + (node ls, node rs) {
	using std::min;
	return {
		min(INF, min(ls.d1 + rs.d1, ls.d2 + rs.d3) + 1),
		min(INF, min(ls.d1 + rs.d2, ls.d2 + rs.d4) + 1),
		min(INF, min(ls.d4 + rs.d3, ls.d3 + rs.d1) + 1),
		min(INF, min(ls.d4 + rs.d4, ls.d3 + rs.d2) + 1)
	};
}
bool inaccessible[2][N];
void build(int p, int l, int r) {
	if (l == r) {
		auto &[d1, d2, d3, d4] = tree[p];
		d1 = d4 = 0, d2 = d3 = 1;
		if (inaccessible[0][l]) d1 = d2 = d3 = INF;
		if (inaccessible[1][l]) d2 = d3 = d4 = INF;
		return;
	}
	int mid = (l + r) >> 1, ls = p << 1, rs = p << 1 | 1;
	build(ls, l, mid), build(rs, mid + 1, r);
	tree[p] = tree[ls] + tree[rs];
}
int L, R;
node query(int p, int l, int r) {
	if (L <= l && r <= R) return tree[p];
	int mid = (l + r) >> 1, ls = p << 1, rs = p << 1 | 1;
	if (L > mid) return query(rs, mid + 1, r);
	if (R <= mid) return query(ls, l, mid);
	return query(ls, l, mid) + query(rs, mid + 1, r);
}
signed main() {
	freopen("go.in", "r", stdin);
	freopen("go.out", "w", stdout);
	using std::cin, std::cout;
	std::ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i <= 1; i++) for (int j = 1; j <= n; j++) {
		char ch; cin >> ch;
		inaccessible[i][j] = ch == 'X';
	}
	build(1, 1, n);
	for (int i = 1; i <= m; i++) {
		int x, y; cin >> x >> y;
		auto getPos = [n] (int x) {return x > n ? x - n : x;};
		L = getPos(x), R = getPos(y);
		using std::swap;
		if (L > R) swap(L, R), swap(x, y);
		auto [d1, d2, d3, d4] = query(1, 1, n);
		int ans = x <= n ? (y <= n ? d1 : d2) : (y <= n ? d3 : d4);;
		if (ans == INF) ans = -1;
		cout << ans << '\n';
	}
	return 0;
}

乌鸦喝水

小结

官方题解:2023暑期CSP-S_NOIP模拟赛3 题解.pdf"