2019牛客多校 Round3

Solved:3

Rank:105

治哥出题了我感动哭了

A Graph Game (分块)

题意:1e5个点 2e5条边 s(x)表示与x点直接相邻的点集合

　　有两种操作 1种将按输入顺序的边第l条到第r条边翻转连接->切断切断->链接

　　还有一种询问 s(x)与s(y)是否相等

题解:题解说可以给每个点随机一个值然后s(x)可以用与x直接相邻的点xor起来 (还有这种操作???

　　然后我们把边分块翻转操作就是xor操作每个点之间边的状态是一样的所以可以共用

　　而且对一条边的修改影响的只有两个点的信息所以对块两边的边暴力修改他所影响的点

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5;

int n, m, blo;

int bl[MAXN << 1];

int sum[MAXN][505];

int now[MAXN];

int val[MAXN];

int u[MAXN << 1];

int v[MAXN << 1];

int vis[505];

void update(int l, int r) {

    for(int i = l; i <= min(r, bl[l] * blo); i++) {

        now[u[i]] ^= val[v[i]];

        now[v[i]] ^= val[u[i]];

    }

    if(bl[l] != bl[r]) {

        for(int i = (bl[r] - 1) * blo + 1; i <= r; i++) {

            now[u[i]] ^= val[v[i]];

            now[v[i]] ^= val[u[i]];

        }

    }

    for(int i = bl[l] + 1; i < bl[r]; i++) vis[i] ^= 1;

}

int main() {

    srand(time(NULL));

    for(int i = 1; i <= 100000; i++) val[i] = rand() + 1;

    int T;

    scanf("%d", &T);

    while(T--) {

        scanf("%d%d", &n, &m);

        blo = sqrt(m);

        for(int i = 1; i <= m; i++) bl[i] = (i - 1) / blo + 1;

        for(int i = 1; i <= n; i++) now[i] = 0;

        for(int i = 1; i <= n; i++)

        for(int j = 1; j <= bl[m]; j++) sum[i][j] = 0;

        for(int i = 1; i <= bl[m]; i++) vis[i] = 1;

        for(int i = 1; i <= m; i++) {

            scanf("%d%d", &u[i], &v[i]);

            sum[u[i]][bl[i]] ^= val[v[i]];

            sum[v[i]][bl[i]] ^= val[u[i]];

        }

        int qu; scanf("%d", &qu);

        while(qu--) {

            int opt, x, y;

            scanf("%d%d%d", &opt, &x, &y);

            if(opt == 1) update(x, y);

            else if(opt == 2) {

                int ans1 = now[x], ans2 = now[y];

                for(int i = 1; i <= bl[m]; i++) {

                    if(vis[i]) {

                        ans1 ^= sum[x][i];

                        ans2 ^= sum[y][i];

                    }

                }

                if(ans1 == ans2) printf("1");

                else printf("0");

            }

        }

        puts("");

    }

    return 0;

}

A Graph Game

F Planting Trees

题意:500x500的矩阵求一个最大的子矩阵使得区间最大减最小<=M

题解:枚举纵坐标的区间对于每一个区间从第一行开始单调尺取搞一搞

#include <bits/stdc++.h>

using namespace std;

int a[505][505];

int zd[505];

int zx[505];

int qd[505];

int qx[505];

int main() {

    int T;

    scanf("%d", &T);

    while(T--) {

        int n, m;

        scanf("%d%d", &n, &m);

        for(int i = 1; i <= n; i++) {

            for(int j = 1; j <= n; j++)

                scanf("%d", &a[i][j]);

        }

        int ans = 1;

        for(int j = 1; j <= n; j++) {

            for(int k = 1; k <= n; k++) {

                zx[k] = 1e5 + 5;

                zd[k] = 0;

            }

            for(int k = j; k <= n; k++) {

                for(int i = 1; i <= n; i++) {

                    zd[i] = max(zd[i], a[i][k]);

                    zx[i] = min(zx[i], a[i][k]);

                }

                int lx = 1, rx = 0;

                int ld = 1, rd = 0;

                int nowl = 1;

                for(int i = 1; i <= n; i++) {

                    while(lx <= rx && zx[qx[rx]] >= zx[i]) rx--;

                    qx[++rx] = i;

                    while(ld <= rd && zd[qd[rd]] <= zd[i]) rd--;

                    qd[++rd] = i;

                    while(nowl <= i && zd[qd[ld]] - zx[qx[lx]] > m) {

                        nowl++;

                        while(lx <= rx && qx[lx] < nowl) lx++;

                        while(ld <= rd && qd[ld] < nowl) ld++;

                    }

                    if(nowl <= i && zd[qd[ld]] - zx[qx[lx]] <= m) {

                        ans = max(ans, (k - j + 1) * (i - nowl + 1));

                    }

                }

            }

        }

        printf("%d\n", ans);

    }

    return 0;

}

F Planting Trees

G Removing Stones

题意:n堆石子每次可以选择两堆不同的各拿走一个如果能拿完就表示获胜

　　如果石子的和为奇数则将最少的一堆石子数-1

　　问有多少对区间能获胜

题解:显然题目等于计算区间max * 2 <= 区间和的个数

　　考虑反问题计算max * 2 > 区间和

　　然后直接暴力枚举每个点作为最大值往前搞搞往后搞搞

　　巧妙的是这样的时间复杂度其实并不高要让这样暴力枚举的时间复杂度退化到n方的数据显然是ai >= ai+1 * 2
　　举个例子长度为5的数组 16 8 4 2 1 能让暴力枚举的复杂度退化到n方但是ai < 1e9

　　均摊一下每个数的平均枚举到log

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a[300005];

ll pre[300005];

int main() {

    int T;

    scanf("%d", &T);

    while(T--) {

        ll n;

        scanf("%lld", &n);

        for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);

        ll ans = 0;

        for(int i = 1; i <= n; i++) {

            int cnt = 0;

            pre[0] = 0;

            for(int j = i + 1; j <= n; j++) {

                pre[++cnt] = a[j];

                pre[cnt] += pre[cnt - 1];

                if(pre[cnt] >= a[i]) {

                    cnt--;

                    break;

                }

            }

            ans += cnt;

            ll sum = 0;

            for(int j = i - 1; j >= 1; j--) {

                sum += a[j];

                if(sum >= a[i]) break;

                ans++;

                int l = 0, r = cnt;

                int mid = l + r >> 1;

                while(l + 1 < r) {

                    mid = l + r >> 1;

                    if(sum + pre[mid] < a[i]) l = mid;

                    else r = mid;

                }

                if(sum + pre[r] < a[i]) ans += r;

                else ans += l;

            }

        }

        ans = n * (n - 1) / 2 - ans;

        printf("%lld\n", ans);

    }

    return 0;

}

G Removing Stones

巴特西

2019牛客多校 Round3

最新文章

热门文章