自动搬运

查看原文

来自洛谷，原作者为

	IDNo1 hi||OI(2020-2023)|不学信竞了也要加油捏|bioer|chemier

搬运于2025-08-24 22:26:03，当前版本为作者最后更新于2023-08-13 21:07:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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$ 数组用于记录答案，因为每个人都会把自己算进去，所以减一即可。

你学会了吗？