P1416 攻击火星【洛谷算法习题】

P1416 攻击火星网页链接P1416 攻击火星题目描述一群外星人将要攻击火星。火星的地图是一个n nn个点的无向图。这伙外星人将按照如下方法入侵先攻击度为0 00的点相当于从图中删除掉它然后是度为1 11的点依此类推直到度为n − 1 n-1n−1的点。所有的点度统计是动态统计的。一个点删掉后与之相连的点的点度都会− 1 -1−1。外星人攻击度为某个数的点时是同时攻击的。你需要设计这个图的边的方案来使得未被攻击的点最多。注意你设计的图不允许自环及重边。输入格式输入文件包含一行一个整数n nn。输出格式一行一个整数表示最多的最后未被攻击的点。输入输出样例 #1输入 #13输出 #11说明/提示【样例解释】一种可能的方案是1 ↔ 2 ↔ 3 1\leftrightarrow 2\leftrightarrow 31↔2↔3这样首先删掉度为1 11的点1 11和点3 33此时点2 22度数为0 00不会被删去。【数据范围】对于20 % 20\%20%的数据1 ≤ n ≤ 10 1\le n\le 101≤n≤10对于100 % 100\%100%的数据1 ≤ n ≤ 5 × 10 4 1\le n\le 5\times 10^41≤n≤5×104。【题目来源】tinylic改编解题思路本题是图论构造结论题通过分析分层删除规则的性质可以推导出最优解的闭式结论无需复杂图算法。删除规则与幸存条件外星人按轮次从小到大删除节点第i ii轮同时删除所有当前度数恰好等于i ii的节点删除后邻接节点度数减1。一个节点能幸存的充要条件是在每一轮i ii开始时它的当前度数都不等于i ii。由此可推出一个关键性质当所有外围节点都被删除后若剩余核心节点的固定度数t tt小于当前轮次编号则后续轮次编号会持续增大永远不会等于t tt核心节点将全部永久幸存。最优构造方案选取n − 2 n-2n−2个节点作为核心构成完全子图剩余 2 个节点作为外围点每个外围点与所有核心点相连。外围点的度数等于核心点总数s n − 2 s n-2sn−2会在第s ss轮被统一删除。核心点初始度数为核心内部度数( s − 1 ) (s-1)(s−1)加上 2 条外围连接即s 1 s1s1。第s ss轮开始时度数为s 1 ≠ s s1 \neq ss1s不会被删除。删除外围点后核心点度数变为s − 1 s-1s−1此时进入第s 1 s1s1轮满足s − 1 s 1 s-1 s1s−1s1。后续轮次编号始终大于核心点度数所有核心点永久幸存。上界证明无法构造出幸存n − 1 n-1n−1个节点的图。若仅保留 1 个外围点则要么外围点与核心点度数相同、在同一轮被全部删除要么核心点会在对应轮次触发删除条件无法让n − 1 n-1n−1个节点全部幸存。因此n − 2 n-2n−2是理论上界。最终结论最大幸存点数为max ⁡ ( 0 , n − 2 ) \max(0, n-2)max(0,n−2)n 1 n1n1时无幸存节点。总结核心逻辑通过构造“完全核心子图 两个全连外围点”的方案达到n − 2 n-2n−2的幸存数同时证明该值为理论上界直接输出结论即可。关键操作结论推导、边界值处理n 1 n1n1输出 0。效率保障纯O ( 1 ) O(1)O(1)时间复杂度无需遍历或图运算。代码简要说明读入整数n nn。计算并输出max ⁡ ( 0 , n − 2 ) \max(0, n-2)max(0,n−2)保证n 1 n1n1时结果非负。关闭流同步加速输入输出适配常规数据规模。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;cinn;coutmax(0LL,n-2)endl;return0;}