锐单电子商城 ， 一站式电子元器件采购平台！

  • 电话：400-990-0325

购物车

SDNU_ACM_ICPC_2022_Winter_Practice_3th [个人赛]

时间：2023-03-13 20:30:00 7jb4继电器3th2040

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] || !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) {   rturn;
	}
	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;
}

锐单商城拥有海量元器件数据手册、IC替代型号，打造电子元器件IC百科大全！

相关文章