P7033题解

· · 题解

P7033题解

这是一道比较水的绿题。

前言：本人代码中的 re 即 register int，用 #define 宏定义即可实现。

解题思路：由于关系具有传递性，所以不能直接暴力枚举，我们需要建立一张图，再进行扫描，求出答案。

第一步： 定义一个结构体，来存放每一个人的信息。

struct node
{
    int a,b,s;
}x[100001];

设这是第 s 个人，则 a 表示 CC_s，b 表示 TF_s，由于后续阶段需要进行排序，我们再定义一个变量 s 表示这是第 s 个人的信息。

第二步： 我们需要先处理读入数据。由于数据量较大，我们需要用快读和快写降低时间复杂度。

这是快读和快写的模板代码，不理解的人可以用普通的 cin 和 cout 替代。

inline int read()
{
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x;
}
inline void write(int x)
{
    if (x>9) 
    {
        write(x/10);
    }
    putchar(x%10+'0');
}

读入数据则需要如下简单的代码（会循环和数组的人都看得懂）：

n=read();
for(re i=0;i<n;i++)
{
    x[i].a=read();
    x[i].b=read();
    x[i].s=i;
}

第三步：由于强具有传递性，所以我们需要根据 CC_i 和 TF_i 的具体情况分别处理，两个排序函数就可以搞定。代码如下：

bool cmp(node u,node v)
{
    return u.a<v.a;
}
bool cmp2(node u,node v)
{
    return u.b<v.b;
}

调用则可以这样写，本人用向量进行存图：

sort(x,x+n,cmp);
for(re i=1;i<n;i++)
{
    v[x[i].s].push_back(x[i-1].s);
}
sort(x,x+n,cmp2);
for(re i=1;i<n;i++)
{
    v[x[i].s].push_back(x[i-1].s);
}

第四步：计算。这是解这道题目最核心的代码，我们可以 bool 一个 vis 数组，来记录此人的情况是否被计算过，因为强具有传递性，所以用 dfs 搜索就可以得到正确答案。

void dfs(re now)
{
    vis[now]=1;//标记已访问
    sum+=1;//开始的时候令 sum=0，由于强具有传递性，所以用类似前缀和的思路即可解决
    for(re i=0;i<v[now].size();i++)//遍历其可以通以打败的人，解决传递性的问题
    {
        if(!vis[v[now][i]])//此人还没有计算过
        {
            dfs(v[now][i]);//搜索
        }
    }
}

调用则如下：

for(re i=0;i<n;i++)
{
    if(!vis[x[i].s])
    {
        dfs(x[i].s);
    }
    ans[x[i].s]=sum-1;
}

因为是从 0 至 n-1 所以每个数据在计算后都会被更新。

其中 ans 数组用于记录答案，因为每个人都会把自己算进去，所以减一即可。

你学会了吗？