娱乐 每 日 算 法 挑 战 （大嘘）【第0x17期】

[Mr.K 018]

第23期哦！话不多说，看题：

第23期 倒饮料

MrK-018和MrK-019有一天出去吃饭，点菜的时候另点了一扎饮料。这两个人都比较抠，因为是AA制结账，所以两个人都想刚好喝到一半的饮料。桌上有两个形状不同的杯子没有用过，可以拿来倒饮料。两个杯子和装饮料的扎都没有刻度，因此只能把杯子/扎倒空或者倒满。

已知两个杯子和扎的容量（整数，单位为毫升），饮料送上来的时候扎是满的。试问，如何倒饮料，才能做到均分饮料（某一个容器中存放的饮料刚好是送上来的一半）？

输入

一行三个整数a b c，分别表示扎和两个杯子的大小。

输出

若能做到，就输出一个可以均分饮料的倒饮料的序列，如下所示：

a > b
b > c

表示把饮料从扎里倒进杯子1，再从杯子1里倒进杯子2.

若不能做到，输出一行Not possible。

以上是今天的题目。另有一个我现在在考虑的问题，发出来供大家讨论：

给定一张带边权的有向图（保证边权都是正的），给定图上的某个顶点，试求一条经过这个顶点的环路，且途径边的边权的平均值最小。

附加题并不是在出之前已经想好答案或者确定有答案的，因此它可能有多项式时间的解也可能没有，请各位留意。

五月 8, 2020，由Mr.K 018修改

[PhoeniXLL]

先判a %2 == 0 && (a / 2) % gcd(b, c) == 0然后BFS求方案

第二个问题我现在只会非简单环，你有简单环这个限制吗

五月 8, 2020，由PhoeniXLL修改

[ZERC]

注意GCD（a,b) = GCD(a, b - a)

将这个性质套到杯子上，可知每一步GCD是不变量，两个杯子饮料的体积的GCD是不变的。

所以杯子任何可能的饮料的体积必定是GCD的倍数。这样推广一下可以推出楼上的前半结论：“a %2 == 0 && (a / 2) % gcd(b, c) == 0”

PS：(a / 2) % gcd(a, c) 和 (a / 2) % gcd(a, b) 应该也可以，但楼上没列... 让我想想，我这边晚上，好困... 明天再思考吧...

PS2：序列麻烦的地方是没有水龙头.... 加一个水龙头序列就很显然了....

PS3：竞赛数学大法好

 

五月 8, 2020，由ZERC修改

[yhz012]

附加题至少有一些预处理可以做

给定有向图，那首先可以获取给定顶点的强连通部分strongly connected components，任何包含这个顶点的环必然只在这个部分里

 

说起来题目要求简单环么，如果要求的话，甚至可以根据双联通bi-connected再砍一次？

五月 8, 2020，由yhz012修改

[Mr.K 018]

1 小时前, PhoeniXLL 说道:

先判a %2 == 0 && (a / 2) % gcd(b, c) == 0然后BFS求方案

第二个问题我现在只会非简单环，你有简单环这个限制吗

 

30 分钟前, yhz012 说道:

附加题至少有一些预处理可以做

给定有向图，那首先可以获取给定顶点的强连通部分strongly connected components，任何包含这个顶点的环必然只在这个部分里

 

说起来题目要求简单环么，如果要求的话，甚至可以根据双联通bi-connected再砍一次？

 

原则上没有

五月 8, 2020，由Mr.K 018修改

[yhz012]

26 分钟前, Mr.K 018 说道:

原则上没有

那最坏情况是在强连通部分暴搜所有环，然后判断环是否包含该顶点……

[Mr.K 018]

刚刚, yhz012 说道:

那最坏情况是在强连通部分暴搜所有环，然后判断环是否包含该顶点……

确实

其实今天本来想出一个类似的题来着，但是就卡在这里，感觉没什么好方法

[PhoeniXLL]

1 小时前, Mr.K 018 说道:

 

 

原则上没有

不要求简单环就二分下答案，然后把图里每条边减掉答案再找负环

[Mr.K 018]

1 分钟前, PhoeniXLL 说道:

不要求简单环就二分下答案，然后把图里每条边减掉答案再找负环

听上去不错，详细说说？

[PhoeniXLL]

3 分钟前, Mr.K 018 说道:

听上去不错，详细说说？

比如先预期一个答案x, 把图里每条边都减掉x, 这时候如果你能找到一个过这个点的负环就说明还有优化空间, 那就继续降低x, 反之提高x

如果不要求简单环那么其实这个限定过某点的限制就有些无力(因为会找到一个和这个点在同一个强联通分量里权值最小的环疯狂转圈), 所以我才问是不是要求简单环但简单环我又不会

五月 8, 2020，由PhoeniXLL修改

[Mr.K 018]

1 小时前, PhoeniXLL 说道:

其实这个限定过某点的限制就有些无力

的确，因为这个限制并不是我加的，而是客观要求，今天这个附加话题是某个更大话题的一部分

[yhz012]

16 小时前, PhoeniXLL 说道:

比如先预期一个答案x, 把图里每条边都减掉x, 这时候如果你能找到一个过这个点的负环就说明还有优化空间, 那就继续降低x, 反之提高x

如果不要求简单环那么其实这个限定过某点的限制就有些无力(因为会找到一个和这个点在同一个强联通分量里权值最小的环疯狂转圈), 所以我才问是不是要求简单环但简单环我又不会

所以这个算法的推论是，均值最后会趋于强连通分量的最小均值环（无论是否包含该顶点）？

全图-x这个做的是真的漂亮

五月 8, 2020，由yhz012修改

[fghdvbgt]

刚刚回归……这个是什么啊？只有题目吗？OJ在哪？这样写了程序没法跑啊

[NianRuoshui]

4 小时前, fghdvbgt 说道:

刚刚回归……这个是什么啊？只有题目吗？OJ在哪？这样写了程序没法跑啊

给出思路就好……毕竟我们也搭不出OJ

[PhoeniXLL]

7 小时前, fghdvbgt 说道:

刚刚回归……这个是什么啊？只有题目吗？OJ在哪？这样写了程序没法跑啊

人脑判题真·评测姬