这个round真的太简单了。。
A，B就不说了
C 题目说了合法的点不会超过10^5个
那么直接离散化，完了跑bfs就行了
离散化用map就行
#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <cstdlib>#include <ctime>#include <set>#include <vector>#include <map>#define MAXN 111#define MAXM 55555#define INF 1000000007using namespace std;int xa, ya, xb, yb;int n;struct node { int r, x, y;}p[111111];struct P { int x, y;}f[111111];bool cmp(node x, node y) { if(x.r != y.r) return x.r < y.r; if(x.x != y.x) return x.x < y.x; return x.y < y.y;}map<long long, int> mp;long long getnum(long long x, long long y) { return x * (long long)INF + y;}int xx[] = {0, 0, 1, -1, 1, 1, -1, -1};int yy[] = {1, -1, 0, 0, -1, 1, -1, 1};int vis[111111];int q[111111];int ans[111111];bool ok(int mv) { if(!mv) return false; if(vis[mv]) return false; return true;}void bfs() { int h = 0, t = 0; vis[1] = 1; q[t++] = 1; while(h < t) { int u = q[h++]; for(int i = 0; i < 8; i++) { int tx = f[u].x + xx[i]; int ty = f[u].y + yy[i]; int mv = mp[getnum(tx, ty)]; if(ok(mv)) { ans[mv] = ans[u] + 1; q[t++] = mv; vis[mv] = 1; } } } if(!ans[2]) printf("-1\n"); else printf("%d\n", ans[2]);}int main(){ scanf("%d%d%d%d", &xa, &ya, &xb, &yb); int idx = 2; mp[getnum(xa, ya)] = 1; mp[getnum(xb, yb)] = 2; f[1].x = xa; f[1].y = ya; f[2].x = xb; f[2].y = yb; scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d%d%d", &p[i].r, &p[i].x, &p[i].y); } sort(p, p + n, cmp); for(int i = 0; i < n; i++) { for(int j = p[i].x; j <= p[i].y; j++) { long long tmp = getnum(p[i].r, j); if(!mp[tmp]) { mp[tmp] = ++idx; f[idx].x = p[i].r; f[idx].y = j; } } } if(xa == xb && ya == yb) { printf("0\n"); return 0; } bfs(); return 0;}D . 注意题目中 按钮按下会导致的是 直接相邻的点变化，不是间接的
那么有种想法就是。
立即学习“前端免费学习笔记（深入）”；
对于一个状态，如果其中有的点的值是跟a数组相应的值相同。
那么就去按这些点， 按过之后这些点肯定不会再出现跟a中相应的值相同了
用一个队列去搞，每次把需要按的点放到队列里，然后假如按完出现了新的需要按的点，就加入队列尾部
最后如果按完所有的点还是会出现与a中相应值相同的情况
就要输出-1了
为啥这么搞能对， 想一下就知道
对于一个状态，按非法点会导致其变成合法，如果周围有被按过的，那么这些被按过的一定是合法的，再变化也是合法的，
如果周围有的变化成了非法的，那么这些非法的一定还能按，那要是这么想的话，-1的情况实际是不存在的（看数据里好像也没有-1）
按的时候直接邻接表模拟就行了，因为每个点只能被按一次，所以每条边最多访问两次
#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <cstdlib>#include <ctime>#include <set>#include <vector>#include <map>#define MAXN 111#define MAXM 55555#define INF 1000000007using namespace std;vector<int>g[111111], ans;int n, m;int a[111111], q[111111], vis[111111], tmp[111111];int h = 0, t = 0;void gao() { for(int i = 0; i < t; i++) vis[q[i]] = 1; while(h < t) { int u = q[h++]; if(tmp[u] != a[u]) continue; ans.push_back(u); tmp[u]++; for(int i = 0; i < g[u].size(); i++) { int v = g[u][i]; tmp[v]++; if(a[v] == tmp[v]) { if(!vis[v]) { q[t++] = v; vis[v] = 1; } } } } for(int i = 1; i <= n; i++) { if(a[i] == tmp[i]) { printf("-1\n"); return ; } } printf("%d\n", ans.size()); for(int i = 0; i < ans.size(); i++) printf("%d ", ans[i]);}int main(){ int u, v; scanf("%d%d", &n, &m); for(int i = 0; i < m; i++) { scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); } for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); if(a[i] == 0) { q[t++] = i; } } if(t == 0) { printf("0\n"); } else gao(); return 0;}E 非常老的题， USACO某个题的变种
按位建线段树就是此题了
#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <cstdlib>#include <ctime>#include <set>#include <vector>#include <map>#define lch(x) x<<1#define rch(x) x<<1|1#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define MAXN 111111#define MAXM 55555#define INF 1000000007using namespace std;int n, m;int cover[20][4 * MAXN];int sum[20][4 * MAXN], a[20][MAXN];void up(int b, int rt) { sum[b][rt] = sum[b][lch(rt)] + sum[b][rch(rt)];}void build(int b, int l, int r, int rt) { if(l == r) { sum[b][rt] = a[b][l]; return; } int m = (l + r) >> 1; build(b, lson); build(b, rson); up(b, rt);}void down(int b, int rt, int l, int r) { if(cover[b][rt]) { cover[b][lch(rt)] ^= 1; cover[b][rch(rt)] ^= 1; int m = (l + r) >> 1; sum[b][lch(rt)] = m - l + 1 - sum[b][lch(rt)]; sum[b][rch(rt)] = r - m - sum[b][rch(rt)]; cover[b][rt] = 0; }}void update(int b, int L, int R, int l, int r, int rt) { if(L <= l && R >= r) { cover[b][rt] ^= 1; sum[b][rt] = r - l + 1 - sum[b][rt]; return; } down(b, rt, l, r); int m = (l + r) >> 1; if(L <= m) update(b, L, R, lson); if(R > m) update(b, L, R, rson); up(b, rt);}int query(int b, int L, int R, int l, int r, int rt) { if(L <= l && R >= r) return sum[b][rt]; down(b, rt, l, r); int m = (l + r) >> 1; int ret = 0; if(L <= m) ret += query(b, L, R, lson); if(R > m) ret += query(b, L, R, rson); return ret;}int main(){ int op, x, y, z; scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d", &x); for(int j = 0; j < 20; j++) { if(x & (1 << j)) { a[j][i] = 1; } } } for(int i = 0; i < 20; i++) build(i, 1, n, 1); scanf("%d", &m); for(int i = 0; i < m; i++) { scanf("%d", &op); if(op == 1) { scanf("%d%d", &x, &y); long long sum = 0; for(int j = 0; j < 20; j++) { sum += (long long)(1<<j) * (long long)(query(j, x, y, 1, n, 1)); } printf("%I64d\n", sum); } else { scanf("%d%d%d", &x, &y, &z); for(int j = 0; j < 20; j++) { if(z & (1 << j)) { update(j, x, y, 1, n, 1); } } } } return 0;}
