Codeforces Round #149 (Div. 2)_html/css_WEB-ITnose

This round is really simple. .
I won’t talk about A and B


C. The question says that the number of legal points will not exceed 10^5
Then just discretize it directly and run bfs after it is done

Just use map for discretization

#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. Note that pressing the button in the question will result in directly adjacent A little change, not indirect

So there is an idea.

For a state, if the value of some points is the same as the corresponding value of the a array.

Then press these points. After pressing, these points will definitely not appear to be the same as the corresponding values ​​in a.

Use a queue to do it, and each time you press the points that need to be pressed Put it in the queue, and then if a new point that needs to be pressed appears after pressing, add it to the end of the queue

Finally, if all the points are pressed, the same value as in a will still appear

It is about to output -1

Why is it right to do this? Just think about it and you will know

For a state, pressing the illegal point will cause it to become legal. If you have passed, then these pressed ones must be legal, and any changes will be legal.

If some of the changes around you become illegal, then these illegal ones must still be pressed. If you think so , the situation of -1 actually does not exist (it seems that there is no -1 in the data)

When pressing, just simulate it directly with the adjacency list, because each point can only be pressed once, so each edge Maximum of two visits

#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 A very old question, a variant of a certain USACO question

Building a line segment tree by bits is this question

#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;}