洛谷题解 CF23B 【Party】

解题思路:

首先这一看就是数学题【应该让雾之湖的Cirno来做(这题明显就很⑨$^*$)】。

*:⑨就是baka的意思。

其次,题目要求你在这$n$个人中找到一种关系图使得剩下的人最多,输出剩下的人数。

题目所说的朋友个数是指在场的,走了的就要减去。

关系是相互的。

(题目翻译有点误导人,没说明白)

当然要先画图模拟找规律啦!

规律:

一个人:

一个人就不画图了,明摆着当扫到0个朋友的人离开时他就要走。

两个人:

同上,图可以脑补,因为只存在两种关系(要么两个人是朋友,要么不是)。

同样,没有人可以剩下。

三个人:

咯,你们要的图:

如图所设的关系:

当0个朋友的人要走时,没有人要走;

当1个朋友的人要走时,23要走;

当2个朋友的人要走时,没有人要走;(此时1的朋友个数为0,巧妙地绕过了扫描)

这样我们就剩下了1个人。

四个人:

如图所设的关系:

当0个朋友的人要走时,没有人要走;

当1个朋友的人要走时,没有人要走;

当2个朋友的人要走时,13要走;

当3个朋友的人要走时,没有人要走;(此时24的朋友个数为1,巧妙地绕过了扫描)

这样我们就剩下了2个人。

n个人:

(4人以后的情况就不画了,占的版面太多)

根据上述方法继续推,不难发现剩下的人数总是$n-2$。

所以我们就有以下关系(设答案为$ans$):

$$ ans= \begin{cases} 0, & 0 \leq n < 2 \\ n-2, & n \geq 2 \end{cases} $$

所以我们就有如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<cstdio>
using namespace std;

int T,n;

int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
(n<2)?printf("0\n"):printf("%d\n",n-2);//这里就不用解释了吧
}
return 0;
}

题目详见:https://www.luogu.com.cn/problem/CF23B