标签：dots cnt frac EveryWhereIsSparserThanWhole leq Construction equiv

[ARC161D] Everywhere is Sparser than Whole (Construction)

构造题，重在思路，代码不难。

考虑有一个性质，既然部分比整体更稀疏，那么需要每个点的入度都 \(>d\)，因为这样删去之后 \(\div(n-1)\) 才会减小。形式化的说，需要满足

\[记 cnt=\min(度_i(1\le i\le n))\\ d>\dfrac{nd-cnt}{n-1} \]

解得 \(cnt>d\)。

然后构造方案方案如下：

一个有 \(N\) 个顶点的简单无向图最多只能有 \(\frac{N(N-1)}{2}\) 条边，因此当 \(D > \frac{N-1}{2}\) 时，答案为 No。反之，当 \(D \leq \frac{N-1}{2}\) 时，答案为 Yes。例如，对于每个 \(i=1,2,\dots,N\) 和每个 \(k=1,2,\dots,D\)，可以连接顶点 \(i\) 和顶点 \((i+k)\)（如果 \(i+k>N\)，则连接顶点 \((i+k-N)\)），这样就可以得到一个满足条件的简单无向图。

简单证明没有矛盾。

假设存在自环或平行边，则存在 \(i_1, i_2 \in \{1,2,\dots,N\}\) 和 \(k_1, k_2 \in \{1,2,\dots,D\}\)，使得

\[i_1+k_1 \equiv i_2, \quad i_2+k_2 \equiv i_1 \pmod{N} \]

（自环的情况下 \(i_1=i_2\)，平行边的情况下 \(i_1 \neq i_2\)）
将两式相加并整理得

\[k_1+k_2 \equiv 0 \pmod{N} \]

但这与

\[2=1+1 \leq k_1+k_2 \leq D+D \leq N-1 \]

矛盾。

代码

标签：dots,cnt,frac,EveryWhereIsSparserThanWhole,leq,Construction,equiv
From： https://www.cnblogs.com/wscqwq/p/17517570.html