首页 > 代码库 > Codeforces Round #264 (Div. 2)
Codeforces Round #264 (Div. 2)
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; }
Codeforces Round #264 (Div. 2)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。