Codeforces Round #264 (Div. 2)
题目链接
A：注意特判正好的情况，其他就一个个去判断记录最大值即可
B：扫一遍，不够的用钱去填即可，把多余能量记录下来
C：把主副对角线处理出来，然后黑格白格只能各选一个最大的放即可
D：转化为DAG最长路问题，每个数字记录下在每个序列的位置，如果一个数字能放上去，那么肯定是每个序列上的数字都是在之前最末尾数字的后面
立即学习“前端免费学习笔记（深入）”；
E：大力出奇迹，预处理出树，然后每次查询从当前位置一直往上找到一个符合的即可，如果没有符合的就是-1
代码：
A：
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int n, s;int main() { scanf("%d%d", &n, &s); int x, y; int flag = 1; int ans = 0; for (int i = 0; i < n; i++) { scanf("%d%d", &x, &y); if (x == s) { if (y == 0) { ans = max(ans, y); flag = 0; } } else if (x < s) { ans = max(ans, (100 - y) % 100); flag = 0; } } if (flag) printf("-1\n"); else printf("%d\n", ans); return 0;}B：
#include <cstdio>#include <cstring>const int N = 100005;typedef long long ll;int n;ll h[N];int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%lld", &h[i]); ll now = 0; ll ans = 0; for (int i = 1; i <= n; i++) { if (h[i] > h[i - 1]) { ll need = h[i] - h[i - 1]; if (now >= need) { now -= need; } else { ans += need - now; now = 0; } } else { now += h[i - 1] - h[i]; } } printf("%lld\n", ans); return 0;}C：
#include <cstdio>#include <cstring>const int N = 2005;typedef long long ll;int n;ll g[N][N], zhu[N + N], fu[N + N];int main() { scanf("%d", &n); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%lld", &g[i][j]); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { zhu[i - j + n] += g[i][j]; fu[i + j] += g[i][j]; } } ll b = -1, w = -1; int bx, by, wx, wy; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { ll sum = zhu[i - j + n] + fu[i + j] - g[i][j]; if ((i + j) % 2 == 0) { if (b < sum) { b = sum; bx = i + 1; by = j + 1; } } else { if (w < sum) { w = sum; wx = i + 1; wy = j + 1; } } } } printf("%lld\n", b + w); printf("%d %d %d %d\n", bx, by, wx, wy); return 0;}D：
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N = 1005;struct Num { int v[10], la;} num[N];bool cmp(Num a, Num b) { return a.la < b.la;}int n, k, dp[N][N];bool judge(int i, int j) { for (int x = 0; x < k; x++) { if (num[i].v[x] < num[j].v[x]) return false; } return true;}int main() { scanf("%d%d", &n, &k); for (int i = 0; i < k; i++) { int tmp; for (int j = 1; j <= n; j++) { scanf("%d", &tmp); num[tmp].v[i] = j; } } for (int i = 0; i <= n; i++) { int maxv = 0; for (int j = 0; j < k; j++) { maxv = max(maxv, num[i].v[j]); } num[i].la = maxv; } sort(num, num + n + 1, cmp); /* for (int i = 0; i <= n; i++) { for (int j = 0; j < k; j++) { printf("%d ", num[i].v[j]); } printf("\n"); }*/ for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { dp[i][j] = max(dp[i][j], dp[i - 1][j]); if (judge(i, j)) { dp[i][i] = max(dp[i][i], dp[i][j] + 1); } } } int ans = 0; for (int i = 0; i <= n; i++) ans = max(ans, dp[n][i]); printf("%d\n", ans); return 0;}E：
#include <cstdio>#include <cstring>#include <vector>using namespace std;const int N = 100005;int n, q, val[N], f[N];vector<int> g[N];void dfs(int u, int fa) { f[u] = fa; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (v == fa) continue; dfs(v, u); }}int gcd(int a, int b) { while (b) { int tmp = a % b; a = b; b = tmp; } return a;}int query(int u) { int v = val[u]; u = f[u]; while (u) { if (gcd(val[u], v) > 1) return u; u = f[u]; } return -1;}int main() { scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++) scanf("%d", &val[i]); int u, v; for (int i = 1; i < n; i++) { scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); int tp, a, b; while (q--) { scanf("%d%d", &tp, &a); if (tp == 1) { printf("%d\n", query(a)); } else { scanf("%d", &b); val[a] = b; } } return 0;}
