C/C++教程

【题解】CF830E Perpetual Motion Machine

本文主要是介绍【题解】CF830E Perpetual Motion Machine,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录
  • 题解
    • 菊花图
    • 特殊情况
  • 注意事项

有翻译的传送门,可以点到原题

orz _ztyqwq, SIGSEGV.

给定 \(n\) 个点,\(m\) 条边的无向图,要求你给每个节点赋正权值 \(a_i\),使得至少有一个节点有非零权值,且:

\[\sum_{i=1}^n a_i^2 \le \sum_{i=1}^m a_{u_i}a_{v_i} \]

其中 \((u_i,v_i)\) 是图中的一条边。

题解

虽然题目中没有给定图的连通性,但如果有至少一个连通块构造满足条件,则其余节点赋 \(0\) 就一定合法。所以下面的讨论假定图连通。

首先,注意到给所有节点赋 \(1\) 时,条件等价于 \(n\le m\),即对于所有非树图,都存在一种构造。

考虑树的情况时,发现难以直接构造,考虑几种极端情况,比如:链和菊花图。

经过尝试,发现链的情况总是无解。证明:

设存在构造,链上每个点的权值为 \(a_i\),则原式变形为:

\[\begin{aligned} \sum_{i=1}^n a_i^2&\le \sum_{i=2}^n a_{i-1}a_i\\ \sum_{i=1}^n a_i^2-\sum_{i=2}^n a_{i-1}a_i&\le 0\\ 2\sum_{i=1}^n a_i^2-2\sum_{i=2}^n a_{i-1}a_i&\le 0\\ \left(a_1^2+\sum_{i=2}^n a_i^2\right)+\left(a_n^2+\sum_{i=2}^n a_{i-1}^2\right)-\sum_{i=2}^n 2a_{i-1}a_i&\le 0\\ a_1^2+a_n^2+\sum_{i=2}^n (a_i^2-2a_ia_{i-1}+a_{i-1}^2)&\le 0\\ a_1^2+a_n^2+\sum_{i=2}^n (a_i-a_{i-1})^2&\le 0\\ \end{aligned} \]

注意到左边一定为非负数,则不等式成立,即等号取到当且仅当 \(a_1=a_2=\cdots=a_n=0\),与题目条件矛盾,所以一定无解。

菊花图

考虑有解的边界。

显然,将中间的点权赋较大值,周围的点权取小更优。更极端地,所有叶子节点的点权都应为 \(1\)。设 \(f_n(x)\) 为 \(n\) 个点,中间点点权取 \(x\) 时,条件中 \(\text{右边}-\text{左边}\) 的值。则易得表达式为 \(f_n(x)=\left(x^2+n-1\right)-\left((n-1)x\right)=x^2-(n-1)x+n-1\)。

以 \(x\) 为主元,则 \(f_n(x)\) 为关于 \(x\) 的二次方程。即,\(\exist x\, f(x)\ge 0 \Leftrightarrow (n-1)^2-4(n-1)\ge 0\),舍去不合法根解得 \(n\ge 5\),即至少有 \(4\) 个叶子节点时一定有解。

构造也十分简单:中间节点赋 \(2\),其余点赋 \(1\)。易证这样一定是合法的。


如何将菊花图的构造拓展到一般的树呢?考虑如下构造:

  • 如果该节点的度 \(> 1\),即非叶子节点,赋 \(2\);
  • 否则,即为叶子节点,赋 \(1\)。

正确性:设有 \(k\) 个叶子节点,可得:

\[\begin{aligned} \text{左边}&=4(n-k)+k\\ &=4n-3k\\ \end{aligned}\\ \begin{aligned} \text{右边}&=4(n-k-1)+2k\\ &=4n-4k-4+2k\\ &=4n-2k-4 \end{aligned}\\ \begin{aligned} \text{左边}-\text{右边}&=(4n-3k)-(4n-2k-4)\\ &=4-k\le 0 \end{aligned} \]

即 \(k\ge 4\),这与菊花图的限制是相同的。

特殊情况

上面的分类讨论包括了:

  • 叶子数为 \(2\),这样的树一定是链;
  • 叶子数 \(\ge 4\)。

接下来我们将讨论最困难的一种情况:有 \(3\) 个叶子的树。

手玩片刻后,可能以为 \(3\) 个叶子是无解的。但考虑如下构造:

节点 \(1\) 的点权为 \(3\),\(2,4,6\) 为 \(2\),其余为 \(1\)。注意到此时满足条件。

依旧考虑有解的边界。首先注意到对于所有三个叶子节点的树,一定存在恰好一个度为 \(3\) 的节点(下文称为「根」),而删去这个节点后,这棵树就分成了三条链。

注意到三条链是互相独立的,所以考虑每条链对答案的贡献。注意这里,包括下文,对答案的定义为题目中式子的 \(\text{右边}-\text{左边}\)。显然,我们希望答案越大越好。


令 \(f(x,l)\) 为根的权值为 \(x\) 时,节点数为 \(l\) 的链的最大贡献。套用链那段公式,即:

\[f(x,l)=-{1\over 2}\min\left(x^2+a_n^2+\sum_{i=2}^l (a_i-a_{i-1})^2\right) \]

构造 \(a\) 的差分数组 \(b\),即 \(b_i=a_i-a_{i+1}\)(为了方便,令 \(a_{l+1} = 1\))。则

\[f(x,l)=-{x^2\over 2}-{1\over 2}\min\left(\sum_{i=1}^l b_i^2\right) \]

由于 \(\sum b_i=x\),则均分一定最小,即:

\[\min \sum b_i^2=l\times \left(\dfrac{x}{l}\right)^2=\dfrac{x^2}{l} \]

所以 \(f(x,l)=-\dfrac{x^2}{2}-\dfrac{x^2}{2l}\),则答案为:

\[\begin{aligned} f(x,l_1)+f(x,l_2)+f(x,l_3)+2x^2&=2x^2-\sum_{k=l_1,l_2,l_3}\left(\dfrac{x^2}{2}+\dfrac{x^2}{2k}\right)\\ &=\dfrac{x^2}{2}-\sum_{k=l_1,l_2,l_3}\dfrac{x^2}{2k}\ge 0 \end{aligned} \]

等价于:

\[\begin{aligned} 1-\sum_{k=l_1,l_2,l_3}\dfrac{1}{k}&\ge 0\\ {1\over l_1}+{1\over l_2}+{1\over l_3}&\le 1 \end{aligned} \]

这就是最终的条件。考虑给出构造。注意到我们只需要给出 \({1\over l_1}+{1\over l_2}+{1\over l_3}= 1\) 的构造即可(可证如果有构造,则答案一定恰好为 \(0\)),其余的情况中,一定存在删去某些链的末端得到上述情况的方法。此时只需要将该删去的节点赋成上一个(距离根更近的)的值,易证这样对答案无影响。

通过枚举,发现只有 \((3,3,3)\),\((2,4,4)\),\((2,3,6)\) 满足条件。同时,要使答案恰好为 \(0\),则上述所有不等式均须取到等号,即要满足 \(b_i\) 全部相等。考虑如下构造:

  • 根节点权值为 \(l_1l_2l_3\);
  • 以第一条链为例,如果距离根节点距离为 \(x\),则权值为 \((l_1-x)l_2l_3\)。

容易证明这样的构造是满足条件的。


最后,总结一下整体的步骤:

  1. 提取连通块;
  2. 检查是否为树;
  3. 检查叶子节点个数;
  4. 检查链长。

精细实现可以达到 \(\mathcal{O}(n\alpha(n))\) 的复杂度。(不太理解 \(\mathcal{O}(n)\) 是什么科技)

注意事项

注意查链时的判重。

My Code

这篇关于【题解】CF830E Perpetual Motion Machine的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!