Tag

递推,状压DP,最短路

A. 篮球比赛1

\(Milky\ Way\)的代码

#include <cstdio>

const int N = 2000, xzy = 1e9 + 7;

int a[N], f[N][N], g[N][N], n, m = 1023, ans;

//f[i][j]表示前i个数的xor和为j的方案数

//g[i][j]表示后n-i+1个数的and和为j的方案数

int main() {

	freopen("basketball1.in", "r", stdin);

	freopen("basketball1.out", "w", stdout);

	scanf("%d", &n);

	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);

	f[0][0] = 1;

	for (int i = 1; i <= n; ++i) { //前i个数

		for (int j = 0; j <= m; ++j)

			(f[i][j] += f[i-1][j]) %= xzy;

		for (int j = 0; j <= m; ++j) //前i-1个数的xor和为j

			(f[i][j^a[i]] += f[i-1][j]) %= xzy;

	}

	for (int i = n; i >= 1; --i) { //后n-i+1个数

		g[i][a[i]] = 1;

		for (int j = 0; j <= m; ++j)

			(g[i][j] += g[i+1][j]) %= xzy;

		for (int j = 0; j <= m; ++j) //后n-i个数的and和为j

			(g[i][j&a[i]] += g[i+1][j]) %= xzy;

	}

	for (int i = 1; i < n; ++i) //前i个数

		for (int j = 0; j <= m; ++j) //前i-1个数的xor和

			ans = (ans + 1LL * f[i-1][j] * g[i+1][j^a[i]] % xzy) % xzy;

	printf("%d\n", ans);

	fclose(stdin);

	fclose(stdout);

	return 0;

}

B. 篮球比赛2

题面

\(Milky\ Way\)的代码

#include <cstdio>

const int N = 25, M = 1048580, XZY = 1e9 + 7;

int f[N][M], n, k, l, m, ans;

int main() {

	freopen("basketball2.in", "r", stdin);

	freopen("basketball2.out", "w", stdout);

	scanf("%d%d%d", &n, &k, &l);

	m = (1 << k) - 1;

	f[0][0] = 1;

	for (int i = 1; i <= n; ++i) { //前i个数

		if (l > k) for (int j = 0; j <= m; ++j) //前i-1个数能取到的状态

			f[i][j] = 1LL * f[i-1][j] * (l - k) % XZY; //x>k

		for (int j = 0; j <= m; ++j) {

			(f[i][j] += f[i-1][j]) %= XZY; //x=0

			if (f[i-1][j]) for (int x = 1; x <= k && x <= l; ++x) //注意x要同时小于k和l

				(f[i][(j|(j<<x)|(1<<x-1))&m] += f[i-1][j]) %= XZY; //1<=x<=k

		}

	}

	for (int i = 0; i <= m; ++i)

		if (i >> k - 1 & 1) (ans += f[n][i]) %= XZY;

	printf("%d\n", ans);

	fclose(stdin);

	fclose(stdout);

	return 0;

}

C. 密室逃脱

题面

\(Lmsh7\)的代码

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <queue>

#include <algorithm>

using std::sort;

using std::queue;

using std::max;

using std::min;

typedef long long LL;

const int N = 105;

const int dx[] = {1, -1, 0, 0};

const int INF = 0X3f3f3f3f;

const int dy[] = {0, 0, -1, 1};

int n, m, cnt, stx, sty, edx, edy, ans = INF;

int a[N][N], f[N][N][11];

char s[N];

struct Node {

	int x, y, m;

} b[N * N];

inline void bfs() {

	memset(f, -1, sizeof(f));

	queue <Node> q;

	q.push(Node{stx, sty, 0});

	f[stx][sty][0] = 0;

	while(!q.empty()) {

		int ux = q.front().x, uy = q.front().y, um = q.front().m;

//		printf("%d %d %d\n", ux, uy, um);

		q.pop();

		for(int i = 0; i < 4; ++i) {

			int nowx = ux + dx[i], nowy = uy + dy[i], nowm = um;

			if(nowx < 1 || nowx > n || nowy < 1 || nowy > n) continue;

			if(a[nowx][nowy] == -1 || f[nowx][nowy][nowm] != -1) continue;

			if(a[nowx][nowy] == nowm + 1) ++nowm;

			f[nowx][nowy][nowm] = f[ux][uy][um] + 1;

			q.push(Node{nowx, nowy, nowm});

		}

	}

	return;

}

void dfs(int x, int y) {//x -> cnt, y -> sum

	if(x == cnt + 1) {

		bfs();

//		printf("f[%d][%d][%d] = %d\n", edx, edy, m, f[edx][edy][m]);

		if(f[edx][edy][m] != -1) {

			ans = min(ans, f[edx][edy][m] + y);

		}

		return;

	}

	a[b[x].x][b[x].y] = -1;

	dfs(x + 1, y);

	a[b[x].x][b[x].y] = 0;

	dfs(x + 1, y + 1);

	return;

}

int main() {

	freopen("maze.in", "r", stdin);

	freopen("maze.out", "w", stdout);

	scanf("%d %d", &n, &m);

	for(int i = 1; i <= n; ++i) {

		scanf("%s", s + 1);

		for(int j = 1; j <= n; ++j) {

			if(s[j] == 'K') {

				stx = i, sty = j;//璧风偣

			} else if(s[j] == 'T') {

				edx = i, edy = j;//缁堢偣

			} else if(s[j] == 'S') {

				b[++cnt].x = i;

				b[cnt].y = j;//鐗规畩鎴块棿

			} else if(s[j] == '.') {

				a[i][j] = 0;

			} else if(s[j] == '#') {

				a[i][j] = -1;

			} else {

				a[i][j] = s[j] - '0';

			}

		}

	}

	dfs(1, 0);

	if(ans == INF) puts("impossible");

	else printf("%d\n", ans);

	fclose(stdin);

	fclose(stdout);

	return 0;

}

巴特西

「NOIP模拟赛」Round 2

Tag

A. 篮球比赛1

B. 篮球比赛2

C. 密室逃脱

最新文章

热门文章