～技术宅真可怕～#1 - 2020-2-15 18:51
CureDovahkinn🤔 (プリキュアなりたい)
给定一个整数n，输出一个由循环的“114514”组成的四则运算(+-*/)算式，可包含括号。
*必须为完整的114514组成
*挑战：使用尽可能少的114514
例：
*必须为完整的114514组成
*挑战：使用尽可能少的114514
例：
输入：142857
输出：“114514+1*14514+1*14514-114-514-(1-1*4*5)*(1-4)”
1、二分法枚举最少的次数N N属于[1, n] 因为最多n个114514就够了
二分的合理性在于：如果N1个能够达成目的，那么对于任意一个N2 > N1肯定能完成，因为可以往后加上(N2 - N1)个((1-1) * 4514) = 0
2、对于每个枚举的N，使用动态规划，从初始为0正推或者结果为n倒推
dp[N] = n
dp[0] = 0
dp[N] 由 dp[N-1] 与一个 114514 通过某种方法得到，关键就是这里，要枚举的可能性很多
因为这个算法的可行性的证明，等价于用 114514 构造 1 的可行性
所以我本来以为大家卡住的技术细节是因为，
对 GCD 的性质及推导 GCD 时构造的群不熟悉
而这个不熟悉，蕴含初等数论/群论两门基础数学课的不扎实
但是自己动笔后发现技术上不涉及 GCD 相关，也有很多种用 114514 做出 1 的办法（比如肥肥君在 #3 给的结构就很简洁漂亮）是我震惊体了
我只是对数学上算法存在性的做了确认，算法的效率优化/效果优化在我熟悉的领域之外所以抱歉没法深入讨论
突然想到的无关吐槽：
数学的学术共同体的范式中，从无限到有限被视为意义重大的工作，而从有限到更小的有限的优化则被排除在“有价值的问题”之外。学界对张益唐和陶哲轩在孪生素数上的工作的不同态度就是实例
打着审美的旗号来逃避繁琐的工作，把问题遗留给工业界
是我的操作业余了
既视感：
大年初一的时候，一个读 CS 的朋友微信我 “嘿给你看个脑筋急转弯”
也是发了张图过去，对面回我
“你这个方法改成用 2 进制不是能简洁不少吗?"
经历两次同样的尴尬
（这根本不是算法题