设为首页 加入收藏

TOP

[SDOI2019] 热闹又尴尬的聚会
2019-06-08 18:14:05 】 浏览:19
Tags:SDOI2019 热闹 尴尬 聚会

热闹度\(p\)子图中最小的度数,尴尬度\(q\)独立集大小,之间的约束
\[ \begin{aligned} \lfloor n/(p+1)\rfloor\le q &\rightarrow \lceil(n-p-1+1)/(p+1)\rceil\le q\\ &\rightarrow \lceil(n-p)/(p+1)\rceil\le q\\ &\rightarrow (n-p)/(p+1)\le q\\ &\rightarrow n-p\le pq+q\\ &\rightarrow n<(p+1)(q+1) \end{aligned} \]

显然\(\lfloor n/(q+1)\rfloor\le p\)也能推出一样的不等式。

我们每次从图上选出度数最小的点,记录它的度数\(d_i\)并删除相邻的\(d_i\)个点,如此反复至无点可选,设进行了\(q\)次,显然

\[ \sum_{i=1}^q (d_i+1)=n \]

显然存在一个热闹度\(p\)是$\max d_i $的方案1,那么
\[ (\max d_i+1)q\ge \sum_{i=1}^q(d_i+1)=n\rightarrow (\max d_i+1)(q+1)>n \]

是满足约束的。

神题啊神题,代码留坑


  1. 设在点\(x\)取到\(\max d_i\),考虑将删除的与\(x\)相邻的那些点,显然它们的度数\(\ge\max d_i\),故方案就是与 点\(x\)\(x\)相邻的这些点 相邻且未被删除的所有点,热闹度\(p=\max d_i\)?




编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇[HEOI2016/TJOI2016] 求和 下一篇C++类的默认函数

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }