Homework Introduction

#include <bits/stdc++.h>
using namespace std;
int n, vis[15], a[15];

void print() {
	for (int i = 1; i <= n; i++) {
		printf("%5d", a[i]);
	}
	cout << '\n';
}

void dfs(int x) { //向第x个格子放数
	//终止条件，x走到n+1
	if (x > n) {
		print();
		return;
	}
	for (int i = 1; i <= n; i++) {
		//判断i是否能用
		if (vis[i] == 0) {
			vis[i] = 1;
			a[x] = i;
			dfs(x + 1);
			vis[i] = 0;
		}
	}
}

int main() {
	cin >> n;
	dfs(1);
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n, k, a[25], vis[25];

void print() {
	for (int i = 1; i <= k; i++) {
		printf("%3d", a[i]);
	}
	cout << '\n';
}

void dfs(int x, int id) {
	if (x > k) {
		print();
		return;
	}
	//13 25 1 4 2
	for (int i = id + 1; i <= n; i++) {
		if (vis[i] == 0) {
			vis[i] = 1;
			a[x] = i;
			dfs(x + 1, i);
			vis[i] = 0;
		}
	}
}

int main() {
	cin >> n >> k;
	dfs(1, 0);
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n, a[10];

void dfs(int x, int sum, int cnt) {
	if (sum == n) {
		for (int i = 1; i <= cnt; i++) {
			if (i == cnt)
				cout << a[i] << "\n";
			else
				cout << a[i] << "+";
		}
		return;
	}
	for (int i = 1; i < n; i++) {
		if (sum + i <= n && i >= a[x - 1]) {
			a[x] = i;
			dfs(x + 1, sum + i, cnt + 1);
		}
	}
}

int main() {
	cin >> n;
	dfs(1, 0, 0);
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 25;
int n, k, a[N], res;

int f(int x) {
	if (x < 2)
		return 0;
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)
			return 0;
	}
	return 1;
}

void dfs(int x, int sum, int id) {
	if (x > k) {
		if (f(sum) == 1)
			res++;
		return;
	}
	for (int i = id + 1; i <= n; i++) {
		dfs(x + 1, sum + a[i], i);
	}
}

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	dfs(1, 0, 0);
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n, m, book[1005][1005];

int nxt[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int cnt = 0;
char mat[1005][1005];

void dfs(int x, int y) {
	for (int i = 0; i < 4; i++) {
		int nx = x + nxt[i][0];
		int ny = y + nxt[i][1];
		if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
			if (book[nx][ny] == 0 && mat[nx][ny] != '0') {
				book[nx][ny] = 1;
				dfs(nx, ny);
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> mat[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (mat[i][j] != '0' && book[i][j] == 0) {
				book[i][j] = 1;
				dfs(i, j);
				cnt++;
			}
		}
	}
	cout << cnt << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
char mat[N][N];
int n, m, cnt, book[N][N];
int pos[N * N][2];

int nxt[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
int ans[N][N];

void dfs(int x, int y) {
	for (int i = 0; i < 4; i++) {
		int nx = x + nxt[i][0];
		int ny = y + nxt[i][1];
		if (nx >= 1 && nx <= n && ny >= 1 && ny <= n) {
			if (book[nx][ny] == 0 && mat[nx][ny] != mat[x][y]) {
				book[nx][ny] = 1;
				cnt++;
				pos[cnt][0] = nx;
				pos[cnt][1] = ny;
				dfs(nx, ny);
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> mat[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (book[i][j] == 0) {
				book[i][j] = 1;
				cnt = 1;
				pos[1][0] = i;
				pos[1][1] = j;
				dfs(i, j);
				for (int k = 1; k <= cnt; k++) {
					ans[pos[k][0]][pos[k][1]] = cnt;
				}
			}
		}
	}
	while (m--) {
		int x, y;
		cin >> x >> y;
		cout << ans[x][y] << '\n';
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
char mat[N][N];
int n, m, book[N][N], cnt, ans[100005];

int nxt[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, -1, -1, -1, 1, 1, -1, 1, 1};

void dfs(int x, int y) {
	cnt++;
	for (int i = 0; i < 8; i++) {
		int nx = x + nxt[i][0];
		int ny = y + nxt[i][1];
		if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
			if (mat[nx][ny] == '*' && book[nx][ny] == 0) {
				book[nx][ny] = 1;

				dfs(nx, ny);
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> mat[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (mat[i][j] == '*' && book[i][j] == 0) {
				cnt = 0;
				book[i][j] = 1;
				dfs(i, j);
			//	cout << i << " " << j << " " << cnt << endl;
				ans[cnt]++;
			}
		}
	}
	int res1 = 0, res2 = 0;
	for (int i = 1; i <= 100000; i++) {
		if (ans[i] > 0) {
			res1++;
			res2 = max(res2, i * ans[i]);
		}
	}
	cout << res1 << " " << res2 << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 705;

struct node {
	int x, y, val;
} a[N * N];

int n, m, mat[N][N], book[N][N], nxt[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, 1, -1, -1, 1, -1, -1};

bool cmp(node a, node b) {
	return a.val > b.val;
}

void dfs(int x, int y) {
	for (int i = 0; i < 8; i++) {
		int nx = x + nxt[i][0];
		int ny = y + nxt[i][1];
		if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
			if (book[nx][ny] == 0 && mat[nx][ny] <= mat[x][y]) {
				book[nx][ny] = 1;
				dfs(nx, ny);
			}
		}
	}
}

int main() {
	cin >> n >> m;
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> mat[i][j];
			a[++cnt] = {i, j, mat[i][j]};
		}
	}
	sort(a + 1, a + cnt + 1, cmp);
	int res = 0;
	for (int i = 1; i <= cnt; i++) {
		if (book[a[i].x][a[i].y] == 0) {
			res++;
			dfs(a[i].x, a[i].y);
		}
	}
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int res = 0, n, m, book[55][55];
int a[55][55];

int nxt[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 1, -1, -1, -1};

void dfs(int x, int y, int sum) {
	res = max(res, sum);
	if (x > n)
		return;
	if (y > m) {
		dfs(x + 1, 1, sum);
		return;
	}
	if (book[x][y]) {
		dfs(x, y + 1, sum);
	} else {
		for (int i = 0; i < 8; i++) {
			int nx = x + nxt[i][0];
			int ny = y + nxt[i][1];
			if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
				book[nx][ny]++;
			}
		}
		dfs(x, y + 1, sum + a[x][y]);
		for (int i = 0; i < 8; i++) {
			int nx = x + nxt[i][0];
			int ny = y + nxt[i][1];
			if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
				book[nx][ny]--;
			}
		}
		dfs(x, y + 1, sum);
	}
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		cin >> n >> m;
		memset(book, 0, sizeof(book));
		res = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cin >> a[i][j];
			}
		}
		dfs(1, 1, 0);
		cout << res << endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int n, m, a[N][N];
int cnt = 0;
int book[N][N], pos[N * N][2];

int nxt[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};

void dfs(int x, int y, int D) {
	for (int i = 0; i < 4; i++) {
		int nx = x + nxt[i][0];
		int ny = y + nxt[i][1];
		if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
			if (abs(a[nx][ny] - a[x][y]) <= D && book[nx][ny] == 0) {
				book[nx][ny] = 1;
				dfs(nx, ny, D);
			}
		}
	}
}

int check(int x) {
	memset(book, 0, sizeof(book));
	book[pos[1][0]][pos[1][1]] = 1;
	dfs(pos[1][0], pos[1][1], x);
	for (int i = 1; i <= cnt; i++) {
		if (book[pos[i][0]][pos[i][1]] == 0)
			return 0;
	}
	return 1;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int x;
			cin >> x;
			if (x == 1) {
				pos[++cnt][0] = i;
				pos[cnt][1] = j;
			}
		}
	}
	int l = 0, r = 1e9;
	int ans = -1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) {
			r = mid - 1;
			ans = mid;
		} else
			l = mid + 1;
	}
	cout << ans << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n, a[70], sum, maxx, t[60], minn = 1e9;

void dfs(int len, int lenth, int need, int id) {
	if (need == 0) {
		cout << lenth << endl;
		exit(0);
	}
	if (len == lenth) {
		dfs(0, lenth, need - 1, maxx);
		return;
	}
	for (int i = id; i >= minn; i--) {
		if (t[i] == 0 || len+i>lenth)
			continue;
		t[i]--;
		dfs(len + i, lenth, need, i);
		t[i]++;
		if (len == 0)
			break;
		if (len + i == lenth)
			break;
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		sum += a[i];
		t[a[i]]++;
		maxx = max(maxx, a[i]);
		minn = min(minn, a[i]);
	}
	for (int i = maxx; i <= sum / 2; i++) {
		if (sum % i != 0)
			continue;
		dfs(0, i, sum / i, maxx);
	}
	cout << sum << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

struct node {
	double x, y;
} p[20];
int n;
double res = 10000000;
int book[25];

void dfs(int cnt, double dis, int x) {
 //   cout<<cnt<<" "<<dis<<" "<<x<<endl;
 	if(dis>=res)return;
	if (cnt >= n) {
		res = min(res, dis);
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (!book[i]) {
			book[i] = 1;
			dfs(cnt + 1, dis + sqrt((p[x].x - p[i].x) * (p[x].x - p[i].x) + (p[x].y - p[i].y) * (p[x].y - p[i].y)), i);
			book[i] = 0;
		}
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> p[i].x >> p[i].y;
	}
	p[0] = {0, 0};
	dfs(0, 0, 0);
	cout << fixed << setprecision(2) << res << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int a[25], n, k, book[25], res = 1e9;

void dfs(int x, int cost) {
	if(cost>=res)return;
	if (x > n) {
		res = min(res, cost);
		return;
	}
	for (int i = 1; i <= k; i++) {
		book[i] += a[x];
		dfs(x + 1, max(cost, book[i]));
		book[i] -= a[x];
	}
}

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	sort(a+1,a+n+1,greater<int>());
	dfs(1, 0);
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
int f[25][25][25];

int dfs(int a, int b, int c) {
	if (a <= 0 || b <= 0 || c <= 0)
		return 1;
	else if (a > 20 || b > 20 || c > 20)
		return dfs(20, 20, 20);
	else if (f[a][b][c] != -1)
		return f[a][b][c];
	else if (a < b && b < c)
		f[a][b][c] = dfs(a, b, c - 1) + dfs(a, b - 1, c - 1) - dfs(a, b - 1, c);
	else
		f[a][b][c] = dfs(a - 1, b, c) + dfs(a - 1, b - 1, c) + dfs(a - 1, b, c - 1) - dfs(a - 1, b - 1, c - 1);
	return f[a][b][c];
}

signed main() {
	int a, b, c;
	memset(f, -1, sizeof(f));
	while (cin >> a >> b >> c) {
		if (a == -1 && b == -1 && c == -1)
			break;
		printf("w(%lld, %lld, %lld) = %lld\n", a, b, c, dfs(a, b, c));
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int mat[105][105], n, m, res;

int nxt[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
int f[105][105];

int dfs(int x, int y) {
	if (f[x][y])
		return f[x][y];
	int tmp = 1;
	for (int i = 0; i < 4; i++) {
		int nx = x + nxt[i][0];
		int ny = y + nxt[i][1];
		if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
			if (mat[nx][ny] < mat[x][y]) {
				tmp = max(tmp, dfs(nx, ny) + 1);
			}
		}
	}
	f[x][y] = tmp;
	return tmp;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> mat[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			res = max(res, dfs(i, j));
		}
	}
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int a[505][505], f[505][505][15];

int nxt[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};

int dfs(int x, int y, int c) {
	if (f[x][y][c])
		return f[x][y][c];
	int res = 1;
	for (int i = 0; i < 4; i++) {
		int nx = x + nxt[i][0];
		int ny = y + nxt[i][1];
		if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
			if (a[nx][ny] > a[x][y]) {
				res = max(res, dfs(nx, ny, c) + 1);
			} else if (c > 0) {
				res = max(res, dfs(nx, ny, c - 1) + 1);
			}
		}
	}
	f[x][y][c] = res;
	return res;
}

int main() {
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			ans = max(ans, dfs(i, j, k));
		}
	}
	cout << ans << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[1005], f[1005][2][35];

int dfs(int tim, int pos, int c) {
	if (tim > n)
		return 0;
	if (f[tim][pos][c])
		return f[tim][pos][c];
	if (a[tim] == pos) {
		f[tim][pos][c] = max(f[tim][pos][c], dfs(tim + 1, pos, c) + 1);
		if (c)
			f[tim][pos][c] = max(f[tim][pos][c], dfs(tim + 1, pos ^ 1, c - 1));
	} else {
		f[tim][pos][c] = max(f[tim][pos][c], dfs(tim + 1, pos, c));
		if (c)
			f[tim][pos][c] = max(f[tim][pos][c], dfs(tim + 1, pos ^ 1, c - 1) + 1);
	}
	return f[tim][pos][c];
}

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> a[i],a[i]--;
	cout << dfs(1, 0, k) << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, k;
int a[N];
int f[N][4][25];

int judge(int a, int b) {
	if (a == b)
		return 0;
	//1为H 2为S，3为P
	else if (a == 1 && b == 2)
		return 1;
	else if (a == 2 && b == 3)
		return 1;
	else if (a == 3 && b == 1)
		return 1;
	else
		return 0;
}

int dfs(int x, int t, int c) {
	if (x > n)
		return 0;
	if (f[x][t][c])
		return f[x][t][c];
	int tmp = 0;
	tmp = max(tmp, dfs(x + 1, t, c) + judge(t, a[x]));
	if (c) {
		for (int i = 1; i <= 3; i++) {
			if (i == t)
				continue;
			tmp = max(tmp, dfs(x + 1, i, c - 1) + judge(i, a[x]));
		}
	}
	f[x][t][c] = tmp;
	return tmp;
}

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		char ch;
		cin >> ch;
		if (ch == 'H')
			a[i] = 1;
		else if (ch == 'S')
			a[i] = 2;
		else if (ch == 'P')
			a[i] = 3;
	}
	int res = 0;
	res = dfs(1, 0, k + 1);
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, N;
int e[40], res = 1e9;
map<int, int>mp;

void dfs(int x, int status, int lim, int cnt) {
//	cout << x << " " << status << " " << lim << " " << cnt << endl;
	if (lim == n / 2 && x > lim) {
		if (mp.count(status))
			mp[status] = min(mp[status], cnt);
		else
			mp[status] = cnt;
		return;
	} else if (lim == n && x > lim) {
		if (mp.count(N ^ status) || status == N) {
			res = min(res, cnt + mp[N ^ status]);
		}
		return;
	}
	dfs(x + 1, status ^ e[x], lim, cnt + 1);
	dfs(x + 1, status, lim, cnt);
}

signed main() {
	cin >> n >> m;
	N = (1LL << n) - 1LL;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		e[x] = (e[x] | (1LL << (y - 1)));
		e[y] = (e[y] | (1LL << (x - 1)));
	}
	for (int i = 1; i <= n; i++) {
		e[i] = (e[i] | (1LL << (i - 1)));
	}
	dfs(1, 0, n / 2, 0);
	dfs(n / 2 + 1, 0, n, 0);
	cout << res << endl;
	return 0;
}

Problem

Please claim the assignment to see the problems.
Status
Live...
Problem
32
Open Since
2025-4-28 0:00
Deadline
2025-5-6 23:59
Extension
24 hour(s)
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. 蜀ICP备2022005482号-4
  3. Worker 0, 42ms
  4. Powered by Hydro v4.19.1 Community