当前位置：Gxlcms > html代码 > CodeforcesRound#149(Div.2)_html/css_WEB-ITnose

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

时间：2021-07-01 10:21:17 帮助过：2人阅读

这个round真的太简单了。。
A，B就不说了

C 题目说了合法的点不会超过10^5个
那么直接离散化，完了跑bfs就行了

离散化用map就行

#include #include #include #include #include #include #include #include #include #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 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 #include #include #include #include #include #include #include #include #define MAXN 111#define MAXM 55555#define INF 1000000007using namespace std;vectorg[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 #include #include #include #include #include #include #include #include #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<

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

人气教程排行