投稿
  1. 首页
  2. 随笔

SDNU

魔纹布•2022-12-17•随笔•阅读24

SDNU,第1张

SDNU

B

Matches Game - POJ 2234 - Virtual Judge

Nim经典游戏，n堆火柴每次从某一堆里随便取个数，最后取光者获胜，这类题就是每一堆火柴个数异或，非零先手赢，零后手赢

AC代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int m;
void solve() {
	int x = 0;
	for (int i = 1; i <= m; i++) {
		int a;
		cin >> a;
		x ^= a;
	}
	if (x == 0) {
		cout << "No" << endl;
	}
	else {
		cout << "Yes" << endl;
	}
	return;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	while (cin >> m) {
		solve();
	}
	return 0;
}

C

Wireless Network - POJ 2236 - Virtual Judge

从题目看就是并查集，从一台电脑出发然后找坐标内能连接的电脑，然后放在一个集合里，证明这个集合里的电脑能直接或者间接的连接在一起，如果是修复电脑的话就把它添加到对应的集合里

AC代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
int fa[1010];
pair p[1010];
bool vis[1010][1010];
bool vis1[1010];
int get(int x) {
	return x == fa[x] ? x : fa[x] = get(fa[x]);
}
int dis(int x1, int y1, int x2, int y2) {
	return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}
void solve() {
	int n, d;
	cin >> n >> d;
	for (int i = 1; i <= n; i++) {
		fa[i] = i;
	}
	for (int i = 1; i <= n; i++) {
		cin >> p[i].first >> p[i].second;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dis(p[i].first, p[i].second, p[j].first, p[j].second) <= d * d) {
				vis[i][j] = true;
				vis[j][i] = true;
			}
		}
	}
	char op;
	while (cin >> op) {
		if (op == 'O') {
			int j;
			cin >> j;
			vis1[j] = true;
			for (int i = 1; i <= n; i++) {
				if (i == j || !vis1[i] || !vis[j][i]) {
					continue;
				}
				int x = get(j), y = get(i);
				if (x != y) {
					fa[x] = y;
				}
			}
		}
		else {
			int j, k;
			cin >> j >> k;
			int x = get(j), y = get(k);
			if (x == y) {
				cout << "SUCCESS" << endl;
			}
			else {
				cout << "FAIL" << endl;
			}
		}
	}
	return;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}

D

Cooking - AtCoder abc204_d - Virtual Judge

首先理解题意，就是两口锅做饭，每一个菜都有它对应的烹饪时间，就要将菜分成两个数列，使得两个数列都要在总时间一半左右才是最优的，可能是一个大于总时间的二分之一另一个小于，或者两个都等于总时间的二分之一，就变成了01背包问题，就把菜往包里装就好了

AC代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
int dp[100010];
void solve() {
	int n;
	cin >> n;
	int sum = 0;
	int a[110];
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		sum += a[i];
	}
	int sum1 = sum;
	sum >>= 1;
	for (int i = 1; i <= n; i++) {
		for (int j = sum; j - a[i] >= 0; j--) {
			dp[j] = max(dp[j], dp[j - a[i]] + a[i]);
		}
	}
	cout << sum1 - dp[sum] << endl;
	return;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}

E

Balanced Lineup - POJ 3264 - Virtual Judge

前几场出过的题，线段树顺便保存区间最大值和最小值

AC代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
int fa[50010], maa, mii;
struct node {
	int l, r, maxn, minn;
}poi[50010 << 2];
void build(int i, int l, int r) {
	poi[i].l = l;
	poi[i].r = r;
	poi[i].maxn = 0;
	poi[i].minn = INF;
	if (l == r) {
		fa[l] = i;
		return;
	}
	build(i << 1, l, (l + r) / 2);
	build(i << 1 | 1, (l + r) / 2 + 1, r);
	return;
}
void update(int x) {
	if (x == 1) {
		return;
	}
	int f = x >> 1;
	poi[f].maxn = max(poi[f << 1].maxn, poi[f << 1 | 1].maxn);
	poi[f].minn = min(poi[f << 1].minn, poi[f << 1 | 1].minn);
	update(f);
	return;
}
void query(int i, int l, int r) {
	if (l == poi[i].l && r == poi[i].r) {
		maa = max(maa, poi[i].maxn);
		mii = min(mii, poi[i].minn);
		return;
	}
	i = i << 1;
	if (l <= poi[i].r) {
		if (r <= poi[i].r) {
			query(i, l, r);
		}
		else {
			query(i, l, poi[i].r);
		}
	}
	i += 1;
	if (r >= poi[i].l) {
		if (l >= poi[i].l) {
			query(i, l, r);
		}
		else {
			query(i, poi[i].l, r);
		}
	}
}
void solve() {
	int n, q;
	cin >> n >> q;
	build(1, 1, n);
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		poi[fa[i]].maxn = x;
		poi[fa[i]].minn = x;
		update(fa[i]);
	}
	int t, y;
	while (q--) {
		cin >> t >> y;
		maa = 0;
		mii = INF;
		query(1, t, y);
		cout << maa - mii << endl;
	}
	return;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}

F

POW - AtCoder abc205_c - Virtual Judge

一开始蒙圈了，还用快速幂开long long乘完了再比较，又取模什么的总是差两分，最后发现他们的幂都是相等的，这样只需要比较一下底数就好了，分多种情况要考虑清楚，幂是偶数就不考虑正负号了，直接取绝对值比较，要是奇数的话就需要考虑正负号，

AC代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int INF = 0x3f3f3f3f;
const long long mod = 1000000007;
void solve() {
	long long a, b, c;
	cin >> a >> b >> c;
	if (c % 2 == 0) {
		a = abs(a);
		b = abs(b);
		if (a > b) {
			cout << ">" << endl;
		}
		else if (a == b) {
			cout << "=" << endl;
		}
		else {
			cout << "<" << endl;
		}
	}
	else {
		if (a >= 0 && b < 0) {
			cout << ">" << endl;
		}
		else if (a < 0 && b >= 0) {
			cout << "<" << endl;
		}
		else if (a == b) {
			cout << "=" << endl;
		}
		else {
			if (a > b) {
				cout << ">" << endl;
			}
			else if (a == b) {
				cout << "=" << endl;
			}
			else {
				cout << "<" << endl;
			}
		}
	}
	return;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}

H

Common Subsequence - POJ 1458 - Virtual Judge

LCS最长公共子序列模板题

AC代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
int lcs[10010][10010];

void solve() {
	string s1, s2;
	while (cin >> s1 >> s2) {
		int len1 = s1.length();
		int len2 = s2.length();
		for (int i = 0; i <= len1; i++) {
			for (int j = 0; j <= len2; j++) {
				if (i == 0 || j == 0) continue;
				if (s1[i - 1] == s2[j - 1]) {
					lcs[i][j] = lcs[i - 1][j - 1] + 1;
				}
				else {
					lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
				}
			}
		}
		cout << lcs[len1][len2] << endl;
	}
	return;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}

K

Tour - AtCoder abc204_c - Virtual Judge

这个题就是图论里把有向图存下后遍历每个点，深搜看这个点能到哪些点，好像会，但不全会QAQ

AC代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
#define maxn 2010
vector G[maxn];
bool vis[maxn];
int ans;
void dfs(int v) {
	if (vis[v]) {
		return;
	}
	vis[v] = true;
	ans++;
	for (int u : G[v]) {
		dfs(u);
	}
}
void solve() {
	int n, m;
	cin >> n >> m;
	while (m--) {
		int x, y;
		cin >> x >> y;
		G[--x].push_back(--y);
	}
	ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			vis[j] = false;
		}
		dfs(i);
	}
	cout << ans << endl;
	return;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}

M

Kth Excluded - AtCoder abc205_d - Virtual Judge

这个题就是给出一个数列，然后在自然数里去掉数列里的数，然后找新的自然数里第多少个数是啥，这个就用到差分数组和前缀和，然后二分，找到第一个不小于要查找数的数，定位后要在定位的前面那个找，不然会得到错误答案

AC代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
long long a[100010], b[100010];
void solve() {
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; i++) {
		b[i] = a[i] - a[i - 1] + b[i - 1] - 1;
	}
	while (q--) {
		long long x;
		cin >> x;
		int y = lower_bound(b + 1, b + 1 + n, x) - b;
		cout << x + a[y - 1] - b[y - 1] << endl;
	}
	return;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}

欢迎分享，转载请注明来源：内存溢出

原文地址:https://54852.com/zaji/5713470.html

赞 (0)
打赏 微信扫一扫微信扫一扫 支付宝扫一扫支付宝扫一扫
魔纹布魔纹布一级用户组
00
上一篇 2022-12-17
下一篇2022-12-17

发表评论

登录后才能评论

评论列表（0条）

    保存