9.9 京东笔试编程题

思路: 结果就是补图的联通快都是团
但是数据有点水, 我用这种遍历方法也给过了

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>
// #include <unistd.h>
#include <unordered_map>

using namespace std;

#define LL long long
#define pb push_back
#define mk make_pair
#define pill pair<int, int>
#define fi first
#define se second
#define mst(a, b) memset(a, b, sizeof a)
#define lson (rt << 1)
#define rson ((rt << 1) | 1)

const int qq = 1e3 + 10;
const int INF = 1e9 + 10;
const int MOD = 1e9 + 7;
int n, m;
int mar[qq][qq];
int main() {
    #ifdef ONLINE_JUDGE
    #else
        freopen("in.txt", "r", stdin);
    #endif
    int t;  scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        for (int i = 1, a, b; i <= m; ++i) {
            scanf("%d%d", &a, &b);
            mar[a][b] = mar[b][a] = 1;
        }
        bool f = true;
        for (int i = 1; i <= n && f; ++i) {
            vector<int> node;
            for (int j = 1; j <= n; ++j) {
                if (i == j || mar[i][j])    continue;
                node.pb(j);
            }
            for (int j = 1; j <= n && f; ++j) {
                if (i == j || !mar[i][j])   continue;
                for (int k = 0; k < node.size() && f; ++k) {
                    if (!mar[j][node[k]])   f = false;
                }
            }
        }
        if (f)  puts("Yes");
        else    puts("No");
        mst(mar, 0);
    }
    return 0;
}

思路: 类似三维偏序, 不过这里没这么复杂, 对a排序… 然后离散化b, 线段树维护c

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>
// #include <unistd.h>
#include <unordered_map>

using namespace std;

#define LL long long
#define pb push_back
#define mk make_pair
#define pill pair<int, int>
#define fi first
#define se second
#define mst(a, b) memset(a, b, sizeof a)
#define lson (rt << 1)
#define rson ((rt << 1) | 1)

const int qq = 5e5 + 10;
const int INF = 1e9 + 10;
const int MOD = 1e9 + 7;
struct Node {
    int a, b, c;
    bool operator < (const Node &d) const {
        return a > d.a;
    }
}p[qq];
int n;
int maxn[qq << 2];
int num[qq << 2];
int tmp[qq];

void updateMaxn(int l, int r, int rt, int x, int y, int val) {
    if (l == r) {
        maxn[rt] = max(maxn[rt], val);
        return;
    }
    if (x <= l && r <= y) {
        maxn[rt] = max(maxn[rt], val);
        return ;
    }
    int mid =  (l + r) >> 1;
    if (mid >= x)   updateMaxn(l, mid, lson, x, y, val);
    if (mid < y)    updateMaxn(mid + 1, r, rson, x, y, val);
    maxn[rt] = max(maxn[lson], maxn[rson]);
}
int getMaxn(int l, int r, int rt, int x, int y) {
    if (l == r) {
        return maxn[rt];
    }
    if (x <= l && r <= y) {
        return maxn[rt];
    }
    int ans = 0;
    int mid = (l + r) >> 1;
    if (mid >= x)   ans = max(ans, getMaxn(l, mid, lson, x, y));
    if (mid < y)    ans = max(ans, getMaxn(mid + 1, r, rson, x, y));
    return ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d%d", &p[i].a, &p[i].b, &p[i].c);
    }
    sort(p, p + n);
    for (int i = 0; i < n; ++i) {
        tmp[i] = p[i].b;
    }
    sort(tmp, tmp + n);
    int k = unique(tmp, tmp + n) - tmp;
    int id = lower_bound(tmp, tmp + k, p[0].b) - tmp;
    id++;
    updateMaxn(1, k, 1, id, id, p[0].c);
    int ans = 0;
    for (int i = 1; i < n; ++i) {
        id = lower_bound(tmp, tmp + k, p[i].b) - tmp;
        id++;
        int x = 0;
        if (id != k)
            x = getMaxn(1, k, 1, id + 1, k);
        if (x > p[i].c) {
            ans++;
        }
        updateMaxn(1, k, 1, id, id, p[i].c);
    }
    printf("%d\n", ans);
    return 0; 
}