关于啥是Project Euler 详见 https://projecteuler.net/about       

观前声明：               

1. 这是个人兴趣使然的对自己入坑pe的记录，仅提供思路和部分代码； 各个方面肯定都是有着优化与提升空间的，甚至在许多大佬看来这应该是初学者的浅薄而未经剪枝的丑码，如果能帮到有兴趣的人自是最好，也欢迎能醍醐灌顶的深度讨论。  

2. 大佬看到了笑笑就行，还请轻喷。

3. 带着恶意，抬杠者...俺也喷不过您，也不能拿您咋样...毕竟这只是我个人兴趣使然的行为或者说是学习记录分享。 （说是记录，但因为是早先写的所以其实是在各种意义上公开处刑和吐槽自己 并尝试补救优化）

4. 语言是c++，用的VS平台

前排：本期一言难尽.88和90是100内难度比最高的2道，都是40%（其实也还行，分析理解后就会觉得简单）

Product-sum numbers

Problem 88

A natural number, N, that can be written as the sum and product of a given set of at least two natural numbers, {a1, a2, ... , ak} is called a product-sum number: N = a1 + a2 + ... + ak = a1 × a2 × ... × ak.

For example, 6 = 1 + 2 + 3 = 1 × 2 × 3.

For a given set of size, k, we shall call the smallest N with this property a minimal product-sum number. The minimal product-sum numbers for sets of size, k = 2, 3, 4, 5, and 6 are as follows.

k=2: 4 = 2 × 2 = 2 + 2
k=3: 6 = 1 × 2 × 3 = 1 + 2 + 3
k=4: 8 = 1 × 1 × 2 × 4 = 1 + 1 + 2 + 4
k=5: 8 = 1 × 1 × 2 × 2 × 2 = 1 + 1 + 2 + 2 + 2
k=6: 12 = 1 × 1 × 1 × 1 × 2 × 6 = 1 + 1 + 1 + 1 + 2 + 6

Hence for 2≤k≤6, the sum of all the minimal product-sum numbers is 4+6+8+12 = 30; note that 8 is only counted once in the sum.

In fact, as the complete set of minimal product-sum numbers for 2≤k≤12 is {4, 6, 8, 12, 15, 16}, the sum is 61.

What is the sum of all the minimal product-sum numbers for 2≤k≤12000?

积和数N具有 N = a1 + a2 + ... + ak = a1 × a2 × ... × ak的性质

对于一个特定的k，能找到最小的N使之满足上式

比如k=2: 4 = 2 × 2 = 2 + 2;k=3: 6 = 1 × 2 × 3 = 1 + 2 + 3

2≤k≤12000时，找到每个k对应的最小的N（N不能重复，如k=4,5时N都为8，但8只计入一次），并求出这些N的和。

显然，这道题只能用搜索+记录+最优替换的思路去做。

稍稍分析一下，对于特定的k，因为2k总能分解为：

1+1+1+...+1+k+2  （(k-2个1)+k+2）  （总共k个数）

2k=1*1*1*...*1*2*k  

所以对于特定的k，N的上界为2k，N的下界显然为k

对于k，若已经找到minimal product-sum numbers N，用数组n[k]=N表示

在N的该种表示法下（N = a1 + a2 + ... + ak = a1 × a2 × ... × ak，ai=1或N的大于1的因子）

那么k可以分解为 k=N的大于1的因子个数(为方便用pro表示)+1的个数

1的个数为N-N大于1的因子之和=N-sum_product(为方便用sump表示)

所以k=pro+N-sump

那么i*N这个数的3项值就可以在N的基础上直接得到

i*N的因子相当于N的因子多了个i

所以pro(i*N)=pro(N)+1

所以sump(i*N)=sump(N)+i

所以k(i*N)=i*N-sump(N)-i+pro(N)+1

所以在原有的k的基础上使用这个模式能得到一个新的k值和对应的新的N值(i*N)

从N=1开始，遍历所有的i*N，若i*N小于当前的n[k]那么便替换

因为k总能用pro+N-sump的形式来表示，所以逆向遍历所有情况后就能得到所有k的n[k]

之后再在主函数中跑一遍标记已经找到的N值避免重复

ans：7587457

Roman numerals

Problem 89

For a number written in Roman numerals to be considered valid there are basic rules which must be followed. Even though the rules allow some numbers to be expressed in more than one way there is always a "best" way of writing a particular number.

For example, it would appear that there are at least six ways of writing the number sixteen:

IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI

However, according to the rules only XIIIIII and XVI are valid, and the last example is considered to be the most efficient, as it uses the least number of numerals.

The 11K text file, roman.txt , contains one thousand numbers written in valid, but not necessarily minimal, Roman numerals; see About... Roman Numerals for the definitive rules for this problem.

Find the number of characters saved by writing each of these in their minimal form.

Note: You can assume that all the Roman numerals in the file contain no more than four consecutive identical units.

roman.txt：https://projecteuler.net/project/resources/p089_roman.txt

About... Roman Numerals：https://projecteuler.net/about=roman_numerals

第二个链接是罗马字符书写规则

在罗马，像罗马人一样思考！

罗马数字的书写规则允许一个数字被用多种方式表达（具体见 Roman Numerals）。但是，对于每个数字都存在一种“最佳”书写方式。

例如，以下是数字 16 的所有书写形式：

IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI

只有XIIIIII和XVI是合法的（满足3个基本规则，详细见下或Roman Numerals）。

XVI是最高效的，因为它使用了最少的数字。

roman.txt中包含一千个罗马数字，但不一定是最简形式；

找出将所有数字写成最简式一共节省的字符数。

注意：你可以认为文件中所有的每个罗马数字中同一单位的字符最多连续出现4次。

有意思的模拟题，至少能学学罗马人如何计数的。

3个基本规则：

Numerals must be arranged in descending order of size.
M, C, and X cannot be equalled or exceeded by smaller denominations.
D, L, and V can each only appear once.

数字必须按大小降序排列；

M C X不能被较小罗马数字表示或超过；

D L V最多只能出现一次；

4条附加规则：

1. Only one I, X, and C can be used as the leading numeral in part of a subtractive pair.

2. I can only be placed before V and X.

3. X can only be placed before L and C.

4. C can only be placed before D and M.

文本里的文件满足3个基本规则，但不一定满足4个附加规则

使用4个附加规则可能能够得到最简书写形式

4个附加规则其实很简单，I X C能够通过放在某个数的首位来表示减数

比如I=1，V=5，X=10，L=50，C=100，D=500，M=1000

IV=4,IX=9

XL=40,XC=90

CD=400,CM=900

且仅有这6种减数

思路大概就是先把罗马数字变成数字，再变成最简罗马数字

或者直接找出冗余的写法，实际上只有少数几种冗余的写法如VIIII之类的，全部找出来后变换求节省字符也很快。

不过我还是用了第一个思路。

将罗马数字变为数字很简单，逐步分类讨论即可，因为罗马数字是降序字符排列，所以写的时候也按对应的降序来写条件判断；

数字变为罗马数字，罗马数字包含减数只有13种表示法：

int ac[13] = { 1000,900,500,400,100,90,50,40,10,9,5,4,1 };

分解当前数字即可，比如开始的16，按ac数组进行降序分解

16=10+5+1  即XVI

文件中第3个为MMMDLXVIIII，表示3000+500+50+10+5+4=3569

3569=3*1000+500+50+10+9=MMMDLXIV

ans：743

Cube digit pairs

Problem 90

Each of the six faces on a cube has a different digit (0 to 9) written on it; the same is done to a second cube. By placing the two cubes side-by-side in different positions we can form a variety of 2-digit numbers.

For example, the square number 64 could be formed:

In fact, by carefully choosing the digits on both cubes it is possible to display all of the square numbers below one-hundred: 01, 04, 09, 16, 25, 36, 49, 64, and 81.

For example, one way this can be achieved is by placing {0, 5, 6, 7, 8, 9} on one cube and {1, 2, 3, 4, 8, 9} on the other cube.

However, for this problem we shall allow the 6 or 9 to be turned upside-down so that an arrangement like {0, 5, 6, 7, 8, 9} and {1, 2, 3, 4, 6, 7} allows for all nine square numbers to be displayed; otherwise it would be impossible to obtain 09.

In determining a distinct arrangement we are interested in the digits on each cube, not the order.

{1, 2, 3, 4, 5, 6} is equivalent to {3, 6, 4, 1, 2, 5}
{1, 2, 3, 4, 5, 6} is distinct from {1, 2, 3, 4, 5, 9}

But because we are allowing 6 and 9 to be reversed, the two distinct sets in the last example both represent the extended set {1, 2, 3, 4, 5, 6, 9} for the purpose of forming 2-digit numbers.

How many distinct arrangements of the two cubes allow for all of the square numbers to be displayed?

一个立方体的六个面上每个面都有一个 0-9 的数字，另一个立方体也如此。将两个立方体用不同的方式挨着放置，我们可以得到不同的两位数。

如果仔细选择每个立方体面上的数字，我们可以表示出 100 以下所有的平方数： 01, 04, 09, 16, 25, 36, 49, 64, 和 81。
例如，能够达到这个目的的一种方式在一个立方体上标示 {0, 5, 6, 7, 8, 9}，在另一个上标示 {1, 2, 3, 4, 8, 9}。
但是在这个问题中，我们允许 6 和 9 通过颠倒来互相表示。所以 {0, 5, 6, 7, 8, 9} 和 {1, 2, 3, 4, 6, 7} 就可以表示所有 9 个平方数，否则无法标示 09。
在判断不同的安排时，我们只对每个立方体上的数字感兴趣，而不考虑顺序。

{1, 2, 3, 4, 5, 6} 等价于 {3, 6, 4, 1, 2, 5}
{1, 2, 3, 4, 5, 6} 和  {1, 2, 3, 4, 5, 9} 则是不同的排列

但是由于我们允许 6 和 9 互相颠倒，所以上面的第二个例子的两个排列都可以表示 {1, 2, 3, 4, 5, 6, 9}。
要表示所有 9 个平方数的话，一共有多少种可行的排列？

用2个数组表示当前的骰子A B状态

写一个函数判断当前A B是否能表示9个平方数

暴搜所有情况...

来说一下实现思路，可以直接写好多个for来暴搜 （没事 也很快）

但我想实现一个复杂一点的迭代递推：

因为不同排列均相同，且一个骰子内不会出现重复数字

所以不妨令A初始情况为 int A[6] = { 0,1,2,3,4,5 };

在之后的迭代中A[i+1]>A[i]始终成立

{0,1,2,3,4,5}->{0,1,2,3,4,6}->{0,1,2,3,4,7}->...->{0,1,2,3,4,9}

{0,1,2,3,4,9}->{0,1,2,3,5,6}->{0,1,2,3,5,7}->...->{0,1,2,3,5,9}

{0,1,2,3,6,7}->...

以此类推

最后一种情况为{4,5,6,7,8,9}  让B骰子每次从A骰子的状态的下一个状态开始

暴搜所有情况。

迭代函数的实现分类讨论几下就能完成：

ans：1217

其实90题写的时候这个写法略为繁琐了，直接上for应该更轻松点，但模拟过程中还是以中有足乐者。

这次难度比是40% 20% 40%  不知各位感觉何如，当时我还卡了好一会.

那么 后续也是随意更新了.