Gym - 101142C CodeCoder vs TopForces（搜索）

题意：给定n个人在两个网站上的得分，一个人若能在任意一个网站里战胜另一个人，则认为这个人能战胜那个人。问每个人都能战胜多少人。

分析：

1、战胜具有传递性。

例如：

4 5

2 7

3 3

因为第三个人能战胜第二个人，第二个人能战胜第一个人，所以虽然第三个人两个分数都比第一个人低，但第三个人能战胜第一个人。

2、按照某个网站的分数排好序，从分数最小的人dfs，经过的人全都标记下来，则若分数较大的人能战胜的人一定大于等于分数较小的人。

原因：假设是按y网站排好序的，（分数由低到高分别id为3， 1， 2， 4）现在研究在y网站中分数最低的人（id为3），若此人在x网站中的分数较高，打败了id为2的人，则由于id为2的人在y网站一定能打败id为1和id为3的人，所以，3,1,2都被标记下来，而且打败的人数是相同的，因为标记过不会再遍历，所以不用担心将自身计入战胜的人中。

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

#define lowbit(x) (x & (-x))

const double eps = 1e-8;

inline int dcmp(double a, double b){

    if(fabs(a - b) < eps) return 0;

    return a > b ? 1 : -1;

}

typedef long long LL;

typedef unsigned long long ULL;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const LL LL_INF = 0x3f3f3f3f3f3f3f3f;

const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};

const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};

const int MOD = 1e9 + 7;

const double pi = acos(-1.0);

const int MAXN = 100000 + 10;

const int MAXT = 10000 + 10;

using namespace std;

struct Node{

    int x, y, id;

    void read(){

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

    }

}num[MAXN];

vector<int> v[MAXN];

bool cmp1(const Node& a, const Node& b){

    return a.x < b.x;

}

bool cmp2(const Node& a, const Node& b){

    return a.y < b.y;

}

int cnt;

int ans[MAXN], vis[MAXN];

void dfs(int cur){

    vis[cur] = 1;

    ++cnt;

    for(int i = 0; i < v[cur].size(); ++i){

        int t = v[cur][i];

        if(vis[t]) continue;

        dfs(t);

    }

}

int main(){

    freopen("codecoder.in", "r", stdin);

    freopen("codecoder.out", "w", stdout);

    int N;

    scanf("%d", &N);

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

        num[i].read();

        num[i].id = i;

    }

    sort(num + 1, num + 1 + N, cmp1);

    for(int i = 2; i <= N; ++i){

        v[num[i].id].push_back(num[i - 1].id);

    }

    sort(num + 1, num + 1 + N, cmp2);

    for(int i = 2; i <= N; ++i){

        v[num[i].id].push_back(num[i - 1].id);

    }

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

        int t = num[i].id;

        if(!vis[t]) dfs(t);

        ans[t] = cnt - 1;

    }

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

        printf("%d\n", ans[i]);

    }

    return 0;

}

巴特西

Gym - 101142C CodeCoder vs TopForces（搜索）

最新文章

热门文章