[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 $的方案¹，那么
\[
(\max d_i+1)q\ge \sum_{i=1}^q(d_i+1)=n\rightarrow (\max d_i+1)(q+1)>n
\]

是满足约束的。

神题啊神题，代码留坑

设在点$x$取到$\max d_i$，考虑将删除的与$x$相邻的那些点，显然它们的度数$\ge\max d_i$，故方案就是与点$x$和$x$相邻的这些点相邻且未被删除的所有点，热闹度$p=\max d_i$。↩

巴特西

[SDOI2019] 热闹又尴尬的聚会

最新文章

热门文章