2025.5.10
|
10
|
0
|
2025.5,data_learning,算法训练

814 字
|
38 分钟

P1019 [NOIP 2000 提高组] 单词接龙

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

int n, ans = 0;
string arr[25];
int syb[25];
char c;


void dfs(string cur, string front) {
	ans = max(ans, int(cur.size()));
	for (int i = 1; i <= n; i++) {
		if (syb[i] >= 2) {
			continue;
		}
		int cs = front.size();

		int fs = cur.size();
		int as = arr[i].size();
		int mxlen = min(fs, as) - 1;
		for (int j = 1; j <= mxlen ; j++) {
			if (cur.substr(fs - j) == arr[i].substr(0, j)) {
				string newcur = cur + arr[i].substr(j);
				syb[i]++;
				dfs(newcur, arr[i]);
				syb[i]--;
				break;
			}
		}
	}
	return;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	cin >> c;
	for (int i = 1; i <= n; i++) {
		if (arr[i][0] == c) {
			syb[i]++;
			dfs(arr[i], arr[i]);
			syb[i]--;
		}
	}
	cout << ans;
	return 0;
}

P5194 [USACO05DEC] Scales S

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

int n, c, arr[1005];
ll sum[1005];
int ans = 0;

void dfs(int sid, ll cal) {

	if (sid >= 1 && cal + sum[sid] <= c) {
		if (cal + sum[sid] > ans) {
			ans = cal + sum[sid];
		}
		return;
	}
	if (cal > ans) {
		ans = cal;
	}
	for (int i = sid; i >= 1; i--) {
		if (cal + arr[i] <= c) {
			dfs(i - 1, cal + arr[i]);
		}
	}
}

int main() {
	cin >> n >> c;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		sum[i] = sum[i - 1] + arr[i];
	}
	dfs(n, 0);
	cout << ans;
	return 0;
}

P1378 油滴扩展

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


int n;
double a1, b1, a2, b2;
int ssyb[10];
double ans;
pair<double, double> arr[10];
vector<pair<pair<double, double>, double>> syb;

double r(double x, double y) {
	double cr, temp1, temp2, temp3;
	vector<pair<pair<double, double>, double>> cur = syb;
	temp1 = min(abs(x - a1), abs(x - a2));
	temp2 = min(abs(y - b1), abs(y - b2));
	cr = min(temp1, temp2);
	while (cur.size()) {
		temp1 = cur.back().first.first;
		temp2 = cur.back().first.second;
		temp3 = cur.back().second;
		cur.pop_back();
		if ((x - temp1) * (x - temp1) + (y - temp2) * (y - temp2) <= temp3 * temp3) {
			return 0;
		}
		cr = min(cr, sqrt((x - temp1) * (x - temp1) + (y - temp2) * (y - temp2)) - temp3);
	}
	return cr;
}

void dfs(double sum, int cnt) {
	if (cnt >= n) {
		ans = max(ans, sum);
		return;
	}

	for (int i = 1; i <= n; i++) {
		if (!ssyb[i]) {
			ssyb[i] = 1;
			double rr = r(arr[i].first, arr[i].second);
			syb.push_back({{arr[i].first, arr[i].second}, rr});
			dfs(sum + rr * rr, cnt + 1);
			ssyb[i] = 0;
			syb.pop_back();
		}
	}
}

int main() {
	cin >> n >> a1 >> b1 >> a2 >> b2;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i].first >> arr[i].second;
	}
	ans = 0;
	dfs(0, 0);

	double tt = (abs(a1 - a2) * abs(b1 - b2)) - ans * M_PI;
	int ttt = (tt + 0.5) / 1;

	cout << ttt;
	return 0;
}

P3956 [NOIP 2017 普及组] 棋盘

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

int m, n, x, y, c, color[107][107], ans = 0x3f3f3f3f, opt[107][107];
bool vis[107][107];

void dfs(int x, int y, int p) {
	if (opt[x][y] && p >= opt[x][y]) {
		return;
	}
	opt[x][y] = p;
	if (x == m && y == m) {
		ans = min(ans, p);
		return;
	}
	if (((x == m - 1 && y == m) || (x == m && y == m - 1)) && color[m][m] == 0) {
		ans = min(ans, p + 2);
		return;
	}
	vis[x][y] = 1;
	//向右一格
	if (!vis[x][y + 1] && color[x][y + 1]) {
		if (color[x][y] == color[x][y + 1]) {
			dfs(x, y + 1, p);
		} else {
			dfs(x, y + 1, p + 1);
		}
	}
	//向下一格
	if (!vis[x + 1][y] && color[x + 1][y]) {
		if (color[x][y] == color[x + 1][y]) {
			dfs(x + 1, y, p);
		} else {
			dfs(x + 1, y, p + 1);
		}
	}
	//向左一格
	if (!vis[x][y - 1] && color[x][y - 1]) {
		if (color[x][y] == color[x][y - 1]) {
			dfs(x, y - 1, p);
		} else {
			dfs(x, y - 1, p + 1);
		}
	}
	//向上一格
	if (!vis[x - 1][y] && color[x - 1][y]) {
		if (color[x][y] == color[x - 1][y]) {
			dfs(x - 1, y, p);
		} else {
			dfs(x - 1, y, p + 1);
		}
	}

	//向右两格
	if (!vis[x][y + 2] && color[x][y + 2]) {
		if (color[x][y] == color[x][y + 2]) {
			dfs(x, y + 2, p + 2);
		} else {
			dfs(x, y + 2, p + 3);
		}
	}
	//向右下角一格
	if (!vis[x + 1][y + 1] && color[x + 1][y + 1]) {
		if (color[x][y] == color[x + 1][y + 1]) {
			dfs(x + 1, y + 1, p + 2);
		} else {
			dfs(x + 1, y + 1, p + 3);
		}
	}
	//向下两格
	if (!vis[x + 2][y] && color[x + 2][y]) {
		if (color[x][y] == color[x + 2][y]) {
			dfs(x + 2, y, p + 2);
		} else {
			dfs(x + 2, y, p + 3);
		}
	}
	//向左下角一格
	if (!vis[x + 1][y - 1] && color[x + 1][y - 1]) {
		if (color[x][y] == color[x + 1][y - 1]) {
			dfs(x + 1, y - 1, p + 2);
		} else {
			dfs(x + 1, y - 1, p + 3);
		}
	}
	//向左两格
	if (!vis[x][y - 2] && color[x][y - 2]) {
		if (color[x][y] == color[x][y - 2]) {
			dfs(x, y - 2, p + 2);
		} else {
			dfs(x, y - 2, p + 3);
		}
	}
	//向左上角一格
	if (!vis[x - 1][y - 1] && color[x - 1][y - 1]) {
		if (color[x][y] == color[x - 1][y - 1]) {
			dfs(x - 1, y - 1, p + 2);
		} else {
			dfs(x - 1, y - 1, p + 3);
		}
	}
	//向上两格
	if (!vis[x - 2][y] && color[x - 2][y]) {
		if (color[x][y] == color[x - 2][y]) {
			dfs(x - 2, y, p + 2);
		} else {
			dfs(x - 2, y, p + 3);
		}
	}
	//向右上角一格
	if (!vis[x - 1][y + 1] && color[x - 1][y + 1]) {
		if (color[x][y] == color[x - 1][y + 1]) {
			dfs(x - 1, y + 1, p + 2);
		} else {
			dfs(x - 1, y + 1, p + 3);
		}
	}
	vis[x][y] = 0;
}



int main() {
	cin >> m >> n;

	for (int i = 1; i <= n; i++) {
		cin >> x >> y >> c;
		color[x][y] = c + 1;
	}

	dfs(1, 1, 0);
	if (ans == 0x3f3f3f3f) {
		cout << "-1" << endl;
	} else {
		cout << ans << endl;
	}

	return 0;
}

P1032 [NOIP 2002 提高组] 字串变换

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

string a, b;
string arr1[10], arr2[10];
int ans = 0x3f3f3f3f;
int n = 1;

struct node {
	string s;
	int cnt;
};

map<string, bool> vis;

void bfs(node nd) {
	queue<node> q;
	q.push(nd);
	while (q.size()) {
		string s = q.front().s;
		int cnt = q.front().cnt;
		q.pop();
		if (cnt > 10 || cnt >= ans) {
			continue;
		}
		if (vis[s]) {
			continue;
		}
		vis[s] = true;
		if (s == b) {
			ans = min(ans, cnt);
			continue;
		}
		for (int i = 1; i <= n; i++) {
			int sz = arr1[i].size();
			if (sz > s.size()) {
				continue;
			}
			for (int j = 0; j <= s.size() - sz; j++) {
				if (s.substr(j, sz) == arr1[i]) {
					node nnd;
					string ns = s.substr(0, j) + arr2[i] + s.substr(j + sz);
					nnd.s = ns;
					nnd.cnt = cnt + 1;
					q.push(nnd);
				}
			}
		}
	}
}


int main() {
	cin >> a >> b;
	while (cin >> arr1[n] >> arr2[n]) {
		n++;
	}
	n--;

	node nd;
	nd.s = a;
	nd.cnt = 0;
	bfs(nd);
	if (ans == 0x3f3f3f3f) {
		cout << "NO ANSWER!" << endl;
	} else {
		cout << ans << endl;
	}
	return 0;
}

P1126 机器人搬重物

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

int n, m, a1, b1, a2, b2, ans = 0x3f3f3f3f;
int arr[55][55];
int syb[55][55][5]; // x, y, direction

int fxt[5][5] = {
	{0, 0, 0, 0, 0},
	{0, 0, 2, 1, 1}, // North
	{0, 2, 0, 1, 1}, // South
	{0, 1, 1, 0, 2}, // West
	{0, 1, 1, 2, 0}  // East
};

struct Node {
	int time, x, y, dir;
};

const int dx[] = {0, -1, 1, 0, 0}; // North, South, West, East
const int dy[] = {0, 0, 0, -1, 1};

bool isValid(int x, int y) {
	if (x < 1 || y < 1 || x + 1 > n || y + 1 > m)
		return false;
	return !arr[x][y] && !arr[x][y + 1] && !arr[x + 1][y] && !arr[x + 1][y + 1];
}

void bfs(int start_dir) {
	memset(syb, 0x3f, sizeof(syb));
	queue<Node> q;
	q.push({0, a1, b1, start_dir});
	syb[a1][b1][start_dir] = 0;

	while (!q.empty()) {
		Node cur = q.front();
		q.pop();

		// 到达终点
		if (cur.x == a2 && cur.y == b2) {
			ans = min(ans, cur.time);
			continue;
		}

		// 剪枝：当前路径不是最优
		if (cur.time > ans)
			continue;
		if (cur.time > syb[cur.x][cur.y][cur.dir])
			continue;

		// 尝试所有转向
		for (int new_dir = 1; new_dir <= 4; ++new_dir) {
			if (new_dir == cur.dir)
				continue;
			int cost = fxt[cur.dir][new_dir];
			int new_time = cur.time + cost;

			if (new_time < syb[cur.x][cur.y][new_dir]) {
				syb[cur.x][cur.y][new_dir] = new_time;
				q.push({new_time, cur.x, cur.y, new_dir});
			}
		}

		// 尝试移动1-3步
		for (int step = 1; step <= 3; ++step) {
			int nx = cur.x + dx[cur.dir] * step;
			int ny = cur.y + dy[cur.dir] * step;

			// 检查路径上的每一步和终点
			bool canMove = true;
			for (int s = 1; s <= step && canMove; ++s) {
				int tx = cur.x + dx[cur.dir] * s;
				int ty = cur.y + dy[cur.dir] * s;
				if (!isValid(tx, ty))
					canMove = false;
			}
			if (!isValid(nx, ny))
				canMove = false;

			if (canMove) {
				int new_time = cur.time + 1;
				if (new_time < syb[nx][ny][cur.dir]) {
					syb[nx][ny][cur.dir] = new_time;
					q.push({new_time, nx, ny, cur.dir});
				}
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			cin >> arr[i][j];

	cin >> a1 >> b1 >> a2 >> b2;
	char c;
	cin >> c;

	int dir;
	if (c == 'N')
		dir = 1;
	else if (c == 'S')
		dir = 2;
	else if (c == 'W')
		dir = 3;
	else
		dir = 4;

	bfs(dir);

	cout << (ans == 0x3f3f3f3f ? -1 : ans) << endl;
	return 0;
}

P1928 外星密码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

int num, n;
string s;
string temp;
vector<int> arr;

int main() {
	cin >> s;
	int l, r;

	int i = 0;

	while (i < s.size()) {
		if (s[i] == '[') {
			arr.push_back(i);
			i++;
		} else if (s[i] == ']') {
			r = i;
			l = arr.back();
			arr.pop_back();
			temp.clear();
			int n = l + 1;
			int num = 0;
			while (isdigit(s[n])) {
				num = num * 10 + s[n] - '0';
				n++;
			}
			n = n - l - 1;
			for (int j = 1; j <= num; j++) {
				temp += s.substr(l + n + 1, r - l - 1 - n);
			}
			s = s.substr(0, l) + temp + s.substr(r + 1);
			i = i - 1 - n + (r - l - 1 - n) * (num - 1);
		} else {
			i++;
		}

	}
	cout << s;
	return 0;
}

P1205 [USACO1.2] 方块转换 Transformations

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
char arr[15][15];
char tar[15][15];
char fz[15][15];
int n;
bool can = false;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> tar[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			fz[i][j] = arr[i][n - j + 1];
		}
	}
	// 1
	can = true;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (arr[i][j] != tar[j][n - i + 1]) {
				can = false;
				break;
			}
		}
	}
	if (can) {
		cout << 1;
		return 0;
	}
	// 2
	can = true;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (arr[i][j] != tar[n - i + 1][n - j + 1]) {
				can = false;
				break;
			}
		}
	}
	if (can) {
		cout << 2;
		return 0;
	}
	// 3
	can = true;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (arr[i][j] != tar[n - j + 1][i]) {
				can = false;
				break;
			}
		}
	}
	if (can) {
		cout << 3;
		return 0;
	}
	// 4
	can = true;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (fz[i][j] != tar[i][j]) {
				can = false;
				break;
			}
		}
	}
	if (can) {
		cout << 4;
		return 0;
	}


	// 5
	can = true;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (fz[i][j] != tar[j][n - i + 1]) {
				can = false;
				break;
			}
		}
	}
	if (can) {
		cout << 5;
		return 0;
	}

	can = true;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (fz[i][j] != tar[n - i + 1][n - j + 1]) {
				can = false;
				break;
			}
		}
	}
	if (can) {
		cout << 5;
		return 0;
	}

	can = true;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (fz[i][j] != tar[n - j + 1][i]) {
				can = false;
				break;
			}
		}
	}
	if (can) {
		cout << 5;
		return 0;
	}

	// 6
	can = true;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (arr[i][j] != tar[i][j]) {
				can = false;
				break;
			}
		}
	}
	if (can) {
		cout << 5;
		return 0;
	}
	cout << 7;
	return 0;
}

P5657 [CSP-S2019] 格雷码

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

int main() {
    int n;
    ull k;
    cin >> n >> k;
    k++; // 将输入k转换为1-based索引
    string s;
    for (int m = n; m >= 1; m--) {
        ull mid = 1ULL << (m - 1); // 使用位运算避免精度问题
        if (k > mid) {
            s += '1';
            k = (1ULL << m) - k + 1; // 调整k的位置
        } else {
            s += '0';
        }
    }
    cout << s;
    return 0;
}

卡片翻转

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;


const int mod = 998244353;
int n, arr1[200005], arr2[200005];
int dp[200005][2];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr1[i] >> arr2[i];
	}
	dp[1][0] = 1;
	dp[1][1] = 1;

	for (int i = 2; i <= n; i++) {
		//当前的正面和前一张的两面都相等
		if (arr1[i] == arr1[i - 1] && arr1[i] == arr2[i - 1]) {
			dp[i][0] = 0;
		} else if (arr1[i] == arr1[i - 1]) { //当前正面和前面正面相等
			dp[i][0] = dp[i - 1][1] % mod;
		} else if (arr1[i] == arr2[i - 1]) { //当前正面和前面反面相等
			dp[i][0] = dp[i - 1][0] % mod;
		} else { //当前正面和前面正反面都不相等
			dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
		}

		//当前的反面和前一张的两面都相等
		if (arr2[i] == arr1[i - 1] && arr2[i] == arr2[i - 1]) {
			dp[i][1] = 0;
		} else if (arr2[i] == arr1[i - 1]) { //当前反面和前面正面相等
			dp[i][1] = dp[i - 1][1] % mod;
		} else if (arr2[i] == arr2[i - 1]) { //当前反面和前面反面相等
			dp[i][1] = dp[i - 1][0] % mod;
		} else { //当前反面和前面正反面都不相等
			dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
		}
	}
	cout << (dp[n][0] + dp[n][1]) % mod;

	return 0;
}
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇