B
Matches Game - POJ 2234 - Virtual Judge
Nim经典游戏，n每次从一堆火柴中随便取一个数字，最后取光者获胜。这种问题是每堆火柴数量不一样，不是零先赢，零后赢。
AC代码：
#include <iostream> #include <queue> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <cstring> #include <string> #include <map> #include <vector> #include <set> #include <stack> #include <numeric> #include <iomanip> 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 <iostream> #include <queue> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <cstring> #include <string> #include <map> #include <vector> #include <set> #include <stack> #include <numeric> #include <iomanip> using namespace std; const int INF = 0x3f3f3f3f; const int mod = 1000000007; int fa[1010]; pair<int, int> 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 <iostream> #include <queue> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <cstring> #include <string> #include <map> #include <vector> #include <set> #include <stack> #include <numeric> #include <iomanip> 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 <iostream> #include <queue> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <cstring> #include <string> #include <map> #include <vector> #include <set> #include <stack> #include <numeric> #include <iomanip> 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 <iostream> #include <queue> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <cstring> #include <string> #include <map> #include <vector> #include <set> #include <stack> #include <numeric> #include <iomanip> 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 <iostream> #include <queue> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <cstring> #include <string> #include <map> #include <vector> #include <set> #include <stack> #include <numeric> #include <iomanip> 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 <iostream> #include <queue> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <cstring> #include <string> #include <map> #include <vector> #include <set> #include <stack> #include <numeric> #include <iomanip> using namespace std; const int INF = 0x3f3f3f3f; const int mod = 1000000007; #define maxn 2010 vector<int> 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 <iostream> #include <queue> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <cstring> #include <string> #include <map> #include <vector> #include <set> #include <stack> #include <numeric> #include <iomanip> 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; }