A:暴力模拟
#include<bits/stdc++.h> using namespace std; int a, b; int main() { scanf("%d%d", &a, &b); int delta = 1, x = 0; while(1) { if(x == 0) { if(a < delta) { puts("Vladik"); return 0; } a -= delta; ++delta; x ^= 1; } else { if(b < delta) { puts("Valera"); return 0; } b -= delta; ++delta; x ^= 1; } } return 0; }
B:先写了个sort竟然pp了，过了十分钟感觉不太好，又写了个基数排序
#include<bits/stdc++.h> using namespace std; const int N = 20010; int n, m; int p[N], a[N], b[N]; bool cp(int i, int j) { return i < j; } int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; ++i) scanf("%d", &p[i]); while(m--) { int l, r, x, temp; scanf("%d%d%d", &l, &r, &x); for(int i = l; i <= r; ++i) a[i] = p[i], b[p[i]] = 1; temp = p[x]; int pos1 = l, pos2 = 1; while(pos1 <= r) { while(!b[pos2]) ++pos2; b[pos2] = 0; a[pos1] = pos2; ++pos1; } if(a[x] == temp) puts("Yes"); else puts("No"); } return 0; }
C:dp什么的滚吧。。。dp[i]表示到i的最大值，那么我们枚举i-1每个数选不选，转移一下即可
#include<bits/stdc++.h> using namespace std; const int N = 5010; int n; int a[N], l[N], r[N], f[N], vis[N]; int main() { scanf("%d", &n); for(int i = 1; i <= n; ++i) { scanf("%d", &a[i]); r[a[i]] = i; if(!l[a[i]]) l[a[i]] = i; } for(int i = 1; i <= n; ++i) { f[i] = max(f[i], f[i - 1]); int cur = 0; memset(vis, 0, sizeof(vis)); int last = 1 << 29; for(int j = i; j >= 0; --j) { if(last == j) f[i] = max(f[i], f[j] + cur); if(r[a[j]] > i) break; if(!vis[a[j]]) { cur ^= a[j]; vis[a[j]] = 1; last = min(last, l[a[j]] - 1); } } } printf("%d ", f[n]); return 0; }
D:没看懂题目
E：很不错的一道题 我们用线段树维护每一层的值和并查集 然后查询的时候把并查集复原合并 太巧妙了 这个并查集复原想了很长时间 思路是这个样子的：因为对于两块东西 原来是不相连的
但是build完和query完并查集都会变 那么我们在build的时候用并查集维护每个节点的连通性 保存两侧的当前并查集中的根是谁。 查询的时候把根的fa赋成自己 因为这个fa代表了原来的连通块
然后之后的节点合并改变了根 那么我们想要回到原来的状态把根赋成单独的一块就行了 然后要注意更新ret要在外面更新 因为可能下面和上面会连接 否则并查集不能及时地更新
#include<bits/stdc++.h> using namespace std; #define id(i, j) (i - 1) * m + j const int N = 1000010; struct data { int sum, l[12], r[12], L, R; } tree[N]; int n, m, q; int fa[N], a[12][N]; int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]);//fa[x] = find(fa[x]); } void connect(int x, int y) { int a = find(x), b = find(y); if(a == b) return; fa[a] = b; } data merge(data x, data y, int mid) { if(!x.sum) return y; if(!y.sum) return x; data ret; ret.sum = x.sum + y.sum; for(int i = 1; i <= n; ++i) { fa[x.l[i]] = x.l[i]; fa[x.r[i]] = x.r[i]; fa[y.l[i]] = y.l[i]; fa[y.r[i]] = y.r[i]; } for(int i = 1; i <= n; ++i) if(a[i][mid] == a[i][mid + 1]) { if(find(x.r[i]) != find(y.l[i])) connect(x.r[i], y.l[i]), --ret.sum; } for(int i = 1; i <= n; ++i) { ret.l[i] = find(x.l[i]); ret.r[i] = find(y.r[i]); } ret.L = x.L; ret.R = y.R; return ret; } void build(int l, int r, int x) { if(l == r) { for(int i = 1; i <= n; ++i) if(a[i][l] == a[i - 1][l]) { fa[id(i, l)] = tree[x].l[i] = tree[x].r[i] = tree[x].l[i - 1]; } else fa[id(i, l)] = tree[x].l[i] = tree[x].r[i] = id(i, l), ++tree[x].sum; tree[x].L = l; tree[x].R = r; return; } int mid = (l + r) >> 1; build(l, mid, x << 1); build(mid + 1, r, x << 1 | 1); tree[x] = merge(tree[x << 1], tree[x << 1 | 1], mid); } data query(int l, int r, int x, int a, int b) { if(l > b || r < a) return tree[0]; if(l >= a && r <= b) { for(int i = 1; i <= n; ++i) fa[id(i, l)] = tree[x].l[i], fa[id(i, r)] = tree[x].r[i]; return tree[x]; } int mid = (l + r) >> 1; data L = query(l, mid, x << 1, a, b); data R = query(mid + 1, r, x << 1 | 1, a, b); return merge(L, R, mid); } int main() { scanf("%d%d%d", &n, &m, &q); for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) scanf("%d", &a[i][j]); build(1, m, 1); while(q--) { int l, r; scanf("%d%d", &l, &r); printf("%d ", query(1, m, 1, l, r).sum); } return 0; }