题解 CF23B 【Party】

双倍经验：P1416 攻击火星（用户名叫 Mars 的我有被冒犯额）。因此，本题显然恶评了。 ## 题目大意 现在聚会上有 $n$ 个人参加，然后依次按照规律离开，第一次是有 $0$ 个朋友的人离开，第二次是有 $1$ 个朋友的人离开，第三次是有 $2$ 个朋友的人离开，之后依次是有 $3,4,5,6\cdots n-1$ 个朋友的一次离开，求最后聚会最多将会剩下多少人。 可以抽象为：一个 $n$ 个点的无向图, 先攻击度为 $0$ 的点（相当于从图中删除掉它），然后是度为 $1$ 的点，依此类推直到度为 $n-1$ 的点。 所有的点度统计是动态统计的。（一个点删掉后，与之相连的点的点度都会 $-1$）。攻击度为某个数的点时是同时攻击的。 你需要设计这个图的边的方案来使得未被攻击的点最多。 ## 大体思路 首先观察到 P1416 数据范围 $n\le 50000$，无法直接用邻接表，意味着这可能是一道结论题。 那么我们来找规律 + 构造。 - 当 $n=1,2$ 时，显然所有点均会被删去，$ans=0$。 - 当 $n=3,4$ 时，可以保留一个点。P1416 的样例使用的是类似链的构造 ①-②-③。 - 当 $n=5$ 时，按链构造会出现问题：即删去两端结点后，中间结点度为 $2$，仍会被删去。因此，构造法变为：选出两个末端节点，把两个末端节点与所有非末端节点相连，再把非末端节点与所有非末端节点相连。  因此，特判 $n=1$ 时 $ans=0$，否则 $ans=n-2$。 ## 完整代码 ```cpp #include<bits/stdc++.h>//cpp using namespace std; int main(){ int t; cin>>t; while(t--){ long long n; cin>>n; if(n==1) cout<<0;//特判 else cout<<n-2; puts(""); } return 0; } ``` 相比之下，python 就短了很多： ```python t=int(input())//python while t>0: a=int(input()) if a == 1: print(0)//特判 else print(a-2) t -= 1 ``` ## 后记 1. python 中 `input()` 函数默认输入字符串，因此需要强制类型转换 `int(input())`； 2. python 缩进相当于大括号； 3. t-=1 不能写成 t--。 更多技巧详见 LucasXu80 [博客](https://www.luogu.com.cn/blog/HuayuLucas/python-kuai-su-shang-shou)。