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  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  <br> <br> <p></p> <p>D. Note that pressing the button in the question will result in directly adjacent A little change, not indirect </p> <p> So there is an idea. </p> <p>For a state, if the value of some points is the same as the corresponding value of the a array. </p> <p>Then press these points. After pressing, these points will definitely not appear to be the same as the corresponding values ​​in a. </p> <p>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 </p> <p> Finally, if all the points are pressed, the same value as in a will still appear </p> <p>It is about to output -1</p> <p>Why is it right to do this? Just think about it and you will know</p> <p>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. </p> <p> 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) </p> <p> 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 </p> <p><br> </p> <p></p> <pre name="code" class="sycode">#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  <br> <br> <p></p> <p><br> </p> <p><br> </p> <p>E A very old question, a variant of a certain USACO question</p> <p>Building a line segment tree by bits is this question</p> <p><br> </p> <p> </p> <pre name="code" class="sycode">#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <cstdlib>#include <ctime>#include <set>#include <vector>#include <map>#define lch(x) x> 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 = 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, rson);    up(b, rt);}int query(int b, int L, int R, int l, int r, int rt) {    if(L = 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, rson);    return ret;}int main(){    int op, x, y, z;    scanf("%d", &n);    for(int i = 1; i  <br> <p></p> <p><br> </p> <p> </p> </map></vector></set></ctime></cstdlib></algorithm></cstdio></cstring></iostream>