4.26 腾讯笔试-数据分析与技术研究

#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define MAXN 100005
struct node{
    int id;
    vector<int> a;
    bool operator < (const node p) const{
        for(int i = 0 ; i < a.size() ; i++){
            if(a[i] != p.a[i])
                return a[i] < p.a[i];
        }
        return id < p.id;
    }
}a[MAXN];
int n,m;
ll ans;
bool equ(int p, int q){
    for(int i = 0 ; i < m ; i++){
        if(a[p].a[i] != a[q].a[i])
            return false;
    }
    return true;
}
int ok(int p, int q){
    for(int i = 0 ; i < m ; i++){
        if(a[p].a[i] + a[q].a[i] < 0)
            return -1;
        if(a[p].a[i] + a[q].a[i] > 0)
            return 1;
    }
    return 0;
}
int main()
{
    scanf("%d %d",&n, &m);
    for(int i = 0 ; i < n ; i++){
        int p, q;
        scanf("%d", &p);
        a[i].id = i;
        a[i].a.clear();
        a[i].a.push_back(0);
        for(int j = 1 ; j < m ; j++){
            scanf("%d", &q);
            a[i].a.push_back(q - p);
        }
    }
    sort(a, a+n);
    int l = 0, r = n-1;
    ans = 0;
    while(l < r){
        int l_num = 1;
        int r_num = 1;
        while(l+l_num < r && equ(l, l+l_num)){
            l_num++;
        }
        while(r-r_num > l && equ(r, r-r_num)){
            r_num++;
        }
        int t = ok(l,r);
        if(t == 0){
            if(equ(l, r)){ //多个0 0 0
                ans += 1LL * (r - l + 1) * (r - l) / 2;
            }
            else ans += 1LL * l_num * r_num;
            l += l_num;
            r -= r_num;
        }
        else if(t < 0){
            l += l_num;
        }
        else if(t > 0){
            r -= r_num;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define MAXN 100005
struct node{
    int x,y;
    node(){}
    node(int xx,int yy):x(xx),y(yy){}
    bool operator < (const node a) const{
        if(x == a.x) return y < a.y;
        return x < a.x;
    }
};
vector<int> a[MAXN * 2];
int b[MAXN][2];
int c[MAXN * 2];
char s[MAXN];
bool vis[MAXN * 2];
int n,m;
int ans;
int main()
{
    int tt,ca = 1;
    int p,q;
    scanf("%d",&tt);
    while(tt--){
        scanf("%d", &n);
        memset(vis, 0, sizeof(vis));
        for(int i = 0 ; i < n ; i++){
            scanf("%d %d", &b[i][0], &b[i][1]);
            c[i*2] = b[i][0];
            c[i*2+1] = b[i][1];
        }
        sort(c,c+2*n);
        int nn = unique(c,c+2*n)-c;
        for(int i = 0 ; i < nn ; i++)
            a[i].clear();
        for(int i = 0 ; i < n ; i++){
            p = b[i][0];
            q = b[i][1];
            int pp = lower_bound(c,c+nn,p)-c;
            int qq = lower_bound(c,c+nn,q)-c;
            a[pp].push_back(qq);
            a[qq].push_back(pp);
        }
        ans = 0;
        for(int i = 0 ; i < nn; i++){
            if(vis[i])
                continue;
            vis[i] = true;
            queue<int> que;
            que.push(i);
            int sum = 1;
            while(!que.empty()){
                int t = que.front();
                que.pop();
                for(int i = 0 ; i < a[t].size() ; i++){
                    int q = a[t][i];
                    if(vis[q])
                        continue;
                    vis[q] = true;
                    sum++;
                    que.push(q);
                }
            }
            ans = max(ans, sum);
        }
        printf("%d\n",ans);
    }
    return 0;
}