NOI2015程序自动分析

[NOI2015]程序自动分析 实际上就是个并查集，先处理全部输入的i=j组，再枚举i!=j组判断是否矛盾即可 然而本题数据范围略大，需要使用特殊手段才可以解决

4000ms解法

由题可知，虽然i,j<=1e9，但是组数n<=1e5 根据离散化的思想，我们可以将这些i j映射到一个小数组中，解决本问题 具体操作方法： 对于输入的i与j排序，去重后添加入一个数组a中，即可用a[k]表示原来的第k个数。在使用时只需二分查找即可 在这里我偷懒直接用了stl::map，操作简单，但是有点慢，不开O2的情况下在Luogu上有一个点TLE了…4000ms，开启O2后2000ms

#include <bits/stdc++.h>
#define rint register int
using namespace std;

inline int read() {
    int a = 0; char c;
    do { c = getchar(); } while (c>'9'  c<'0');
    do { a = a * 10 + c - '0'; c = getchar(); } while (c >= '0'&&c <= '9');
    return a;
}

struct INPUT {
    int i, j, e;
};
const int MAXN = 1e5 + 10;
INPUT input[MAXN];
map<int, int> mp;

int ufs[MAXN * 2];

void init() {
    for (rint i = 0; i<MAXN * 2; ++i) {
        ufs[i] = i;
    }
}

int find(int x) {
    return ufs[x] = x == ufs[x] ? x : find(ufs[x]);
}

bool same(int x, int y) {
    int xx = find(x), yy = find(y);
    return xx == yy ? true : false;
}

void unite(int x, int y) {
    int xx = find(x), yy = find(y);
    ufs[xx] = yy;
}

bool comp(const INPUT &x, const INPUT &y) {
    return x.e>y.e;
}

int main() {
    int T = read();
    while (T--) {
        int n = read(), tot = 0;
        init();
        mp.clear();
        for (rint i = 0; i<n; ++i) {
            input[i].i = read();
            input[i].j = read();
            input[i].e = read();
            if (mp.find(input[i].i) == mp.end()) {
                mp[input[i].i] = tot++;
            }
            if (mp.find(input[i].j) == mp.end()) {
                mp[input[i].j] = tot++;
            }
        }
        sort(input, input + n, comp);
        bool ok = true;
        for (rint i = 0; i<n; ++i) {
            int x = mp[input[i].i], y = mp[input[i].j];
            if (input[i].e == 1) {
                unite(x, y);
            }
            else {
                if (same(x, y)) {
                    ok = false;
                    break;
                }
            }
        }
        if (ok) {
            puts("YES");
        }
        else {
            puts("NO");
        }
    }
    return 0;
}

300ms做法

然而作为一名喜欢骗分追求效率的的OIer，我使用了更加快速的玄学解法： 将输入的i与j直接%一个数字MOD，加入数组中 MOD的选择的确是个玄学，看到有人在提交时使用520817通过了此题，我就直接抄来了…… 其它的一些优化：输入时就判断e的值，分为多个数组储存避免每次的判断；使用memcpy代替循环为并查集附初值 开O2后达到了200ms，甚至冲上了最优解的第一页

#include <bits/stdc++.h>
#define rint register int
using namespace std;

inline int read() {
    int a = 0; char c;
    do { c = getchar(); } while (c>'9'  c<'0');
    do { a = a * 10 + c - '0'; c = getchar(); } while (c >= '0'&&c <= '9');
    return a;
}

const int MAXN = 1e5 + 10;
int ii1[MAXN], ii2[MAXN], jj1[MAXN], jj2[MAXN];

const int MOD = 520817;

int ufs[MOD + 100];
int down_ufs[MOD + 100];

int find(int x) {
    return ufs[x] = x == ufs[x] ? x : find(ufs[x]);
}

bool same(int x, int y) {
    int xx = find(x), yy = find(y);
    return xx == yy ? true : false;
}

void unite(int x, int y) {
    int xx = find(x), yy = find(y);
    ufs[xx] = yy;
}

int main() {
    int T = read();
    for (rint i = 0; i<MOD + 100; ++i) {
        down_ufs[i] = i;
    }
    while (T--) {
        memcpy(ufs, down_ufs, sizeof(ufs));
        int n = read(), tot1 = -1, tot2 = -1, tmpi, tmpj, tmpe;
        for (rint i = 0; i<n; ++i) {
            tmpi = read() % MOD;
            tmpj = read() % MOD;
            tmpe = read();
            if (tmpe) {
                ii1[++tot1] = tmpi;
                jj1[tot1] = tmpj;
            }
            else {
                ii2[++tot2] = tmpi;
                jj2[tot2] = tmpj;
            }
        }
        for (rint i = 0; i <= tot1; ++i) {
            unite(ii1[i], jj1[i]);
        }
        bool ok = true;
        for (rint i = 0; i <= tot2; ++i) {
            if (same(ii2[i], jj2[i])) {
                ok = false;
                break;
            }
        }
        puts(ok == true ? "YES" : "NO");
    }
    return 0;
}