Project Euler 079~083
关于啥是Project Euler 详见 https://projecteuler.net/about
观前声明：
这是个人兴趣使然的对自己入坑pe的记录，仅提供思路和部分代码；
各个方面肯定都是有着优化与提升空间的，甚至在许多大佬看来这应该是初学者的浅薄而未经剪枝的丑码，如果能帮到有兴趣的人自是最好，也欢迎能醍醐灌顶的深度讨论。
大佬看到了笑笑就行，还请轻喷。
带着恶意，抬杠者...俺也喷不过您，也不能拿您咋样...毕竟这只是我个人兴趣使然的行为或者说是学习记录分享。 （说是记录，但因为是早先写的所以其实是在各种意义上公开处刑和吐槽自己 并尝试补救优化）
语言是c++，用的VS平台
前排：79水题，80题用了Frazer Jarvis的关于使用减法来迭代求平方根的方法；81，82，83属于动态规划系列题（？熟悉的组合）
Passcode derivation
Problem 79
A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may ask for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.
The text file, keylog.txt, contains fifty successful login attempts.
Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length.
keylog.txt：https://projecteuler.net/project/resources/p079_keylog.txt
网上银行通用的一种加密方法是向用户询问密码中的三位随机字符。例如，如果密码是 531278，那么银行可以询问第 2,3,5 位字符，预期的回复应该是317。keylog.txt中包含 50 次成功的登录尝试，已知三位字符总是按顺序询问，分析文件并找出可能的最短的密码（长度未知）。
keylog如下：
319 680 180 690 129 620 762 689 762 318 368 710 720 710 629 168 160 689 716 731 736 729 316 729 729 710 769 290 719 680 318 389 162 289 162 718 729 319 790 680 890 362 319 760 316 729 380 319 728 716
实际上就50个字符，这道题我是纯手算过的。
只要时刻注意 1.满足最短的密码；2.总是按顺序询问 即可
可以看到4，5一次都没出现，那么从最少数字的情况来考虑，没有4，5；
那么不妨假设就只有8个数字，从第一个数字串开始，不断根据数字出现顺序改变数字的位置或添加新数字：
（注意每次变更需与之前的判断不矛盾，不然就要继续变更，不能变更时说明要加数字）
比如一开始是319，第二个是680，那么不妨假设数字是319680，然后是180，符合条件，再然后是690，说明6在9前面，那么改成316980；
然后是129，1，9之间有个2，那么变为3162980，620不变，762说明6前有个7，变为31762980，689说明8在9前，改成31762890，318不变，368不变，710说明7在1前面，改成37162890，720不变，710不变，629不变，168不变，160不变，689不变，716不变，731说明7在3前，改为73162890，之后可逐一验证均无需改变。
（这道题还可用拓扑排序将每位数字可能的后位数字列出 相关知识请自行搜索）
ans：73162890
Square root digital expansion
Problem 80
It is well known that if the Square root of a natural number is not an integer, then it is irrational. The decimal expansion of such Square roots is infinite without any repeating pattern at all.
The Square root of two is 1.41421356237309504880..., and the digital sum of the first one hundred decimal digits is 475.
For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational Square roots.
众所周知如果一个整数的平方根不是一个整数，那么这个平方根就是一个无理数，这种平方根的小数表示是无限不循环的。2的平方根是1.41421356237309504880...，它的前一百位数字的和是475。
对于前一百个自然数，找出其中无理平方根的小数部分前一百位的总和。
在《数值分析》中有许多关于方程数值解迭代的方法，比如牛顿迭代，二分，抛物线法，割线法等，但对于本题要求的100位的高精度而言，计算机浮点值难免会有误差，所以本题使用了一种收敛不快但必定精确的方法。
此法出自Frazer Jarvis的论文Square roots by subtraction
详细原理可自行查询原文，我只说说算法本身。
如果要求n的平方根，初始时令(a,b)=(5n,5)
重复以下步骤：
如果a≥b，则(a,b)->(a-b,b+10)
如果a<b，则a->100*a,在b的个位数前加一个0。
b代表n的平方根
比如2的平方根初始时(a,b)=(10,5)
(10,5)->(5,15)->(500,105)->(395,115)->(280,125)->(155,135)->(20,145)->(2000,1405)->(595,1415)->(59500,14105)->(45395,14115)->(31280,14125)->(17155,14135)->(3020,14145)->(302000,141405)->160595,141415)->(19180,141425)->(1918000,1414205)..
可见，b在不断接近没有小数点的根号2。
因为100位，所以c++势必要用到大整数，但这个算法与大整数可谓十分契合，直接模拟即可
（为了与大整数加法，乘法等一致保持A[0]储存位数，其余部分逆序储存数的性质，所以减法的写法略微繁琐，之前好像因为没用到所以都没给出？）
再写一个函数使用2个规则迭代，在主函数中跑100内的非平方数即可。
ans：40886
上两题难度分别为5%，20%.
81，82，83是关于路径的动态规划，虽说83我用的dijkstra...
Path sum: two ways
Problem 81
In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.
Find the minimal path sum from the top left to the bottom right by only moving right and down in matrix.txt, a 31K text file containing an 80 by 80 matrix.
matrix.txt：https://projecteuler.net/project/resources/p081_matrix.txt
在5×5的矩阵中从左上角移动到右下角，每次只能向下或向右移动，路径的最小值是2427，在matrix.txt中有一个80×80的矩阵，找到依此规则移动的路径的最小值。
这其实是简单的动态规划问题，若以op[i][j]表示从当前位置(i,j)移动到右下角的路径最小值：
以上图的5×5矩阵为例，比如op[5][5]=A[5][5]，因为本身已在终点，op[4][5]=A[4][5]+op[5][5],
op[5][4]=A[5][4]+op[5][5];
op[4][4]=A[4][4]+min{op[4][5],op[5][4]}
所以状态转移方程为：op[i][j]=A[i][j]+min(op[i+1][j],op[i][j+1]);注意一下边界条件即可直接在主函数实现（这里我的数组A已经储存了80×80矩阵）：
ans：427337
Path sum: three ways
Problem 82
NOTE: This problem is a more challenging version of Problem 81.
The minimal path sum in the 5 by 5 matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down, and right, is indicated in red and bold; the sum is equal to 994.
Find the minimal path sum from the left column to the right column in matrix.txt , a 31K text file containing an 80 by 80 matrix.
从最左侧（任意位置）移动到最右侧（任意位置），每次只能向上或下或右移动一步，权值最短路径如图所示，最短路径和为：994，在matrix.txt中（与上题相同的文件）的80×80矩阵中求出最短路径和。
显然，这也是个动态规划问题。
对于最后一列，显然op[i][j]=A[i][j]
对于倒数第二列，op[i][j]不一定为A[i][j]+op[i][j+1]，实际上，若该列中能有更小的op[k][j]
使得A[i][j]+op[i][j+1]>A[i][j]+A[i+1][j]+...+A[k-1][j]+op[k][j] 那么对于op[i][j]最短路径显然是先到A[k][j]再继续移动，所以从最后一列开始向前规划的思路由此诞生：
状态转移方程：
op[i][j]=min(op[k][j+1]+A[k][j]+...+A[i][j])
k为某一行，A[k][j]+...+A[i][j]中为k到i的所有A[m][j] i<=m<=k或k<=m<=i
ans：260324
Path sum: four ways
Problem 83
NOTE: This problem is a significantly more challenging version of Problem 81.
In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297.
Find the minimal path sum from the top left to the bottom right by moving left, right, up, and down in matrix.txt a 31K text file containing an 80 by 80 matrix.
上两题的矩阵，上下左右4个方向...
这道题能dp，但我选择dijkstra最短路径.
把点权处理一下模拟成边权即可。
大致说下dijkstra算法思想：
声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：S，初始时，原点 s 的路径权重被赋为 0 （dist[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dist[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合S只有顶点s。
然后，从dist数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中。
然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dist中的值。
然后，又从dist中找出最小值，重复上述动作，直到S中包含了图的所有顶点
还是建议没听过的话先百度下.搞懂后再来看我的改编版吧：
首先设置一个初始的Ds0数组，将初始边权定义为相邻两点的点权之和
然后开始dijkstra
需要注意的是，80×80的矩阵中，(i,j)点的编号为80*i+j
编号为n的点的行为n/80,列为n%80
所以新的一轮的路径较短的点的判断为：
dist[u] + A[j / 80][j % 80] < dist[j]
S[u]=1表示点u加入集合S.
ans：425185
3道题难度分别为10% 20% 25%...
希望这月底前能更到100吧 然后我就可以（）了.
预告一下.84是无聊的模拟题.说下思路就过吧 （绝不是我为了节能）
