關(guān)于啥是Project Euler 詳見 https://projecteuler.net/about? ? ???

觀前聲明：? ? ? ? ? ? ? ?

1. 這是個人興趣使然的對自己入坑pe的記錄，僅提供思路和部分代碼； 各個方面肯定都是有著優(yōu)化與提升空間的，甚至在許多大佬看來這應(yīng)該是初學(xué)者的淺薄而未經(jīng)剪枝的丑碼，如果能幫到有興趣的人自是最好，也歡迎能醍醐灌頂?shù)纳疃扔懻摗??

2. 大佬看到了笑笑就行，還請輕噴。

3. 帶著惡意，抬杠者...俺也噴不過您，也不能拿您咋樣...畢竟這只是我個人興趣使然的行為或者說是學(xué)習(xí)記錄分享。?（說是記錄，但因為是早先寫的所以其實是在各種意義上公開處刑和吐槽自己 并嘗試補救優(yōu)化）

4. 語言是c++，用的VS平臺

前排：本期一言難盡.88和90是100內(nèi)難度比最高的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?

積和數(shù)N具有?N =?a1?+?a2?+ ... +?ak?=?a1?×?a2?× ... ×?ak的性質(zhì)

對于一個特定的k，能找到最小的N使之滿足上式

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

2≤k≤12000時，找到每個k對應(yīng)的最小的N（N不能重復(fù)，如k=4,5時N都為8，但8只計入一次），并求出這些N的和。

顯然，這道題只能用搜索+記錄+最優(yōu)替換的思路去做。

稍稍分析一下，對于特定的k，因為2k總能分解為：

1+1+1+...+1+k+2? （(k-2個1)+k+2）? （總共k個數(shù)）

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

所以對于特定的k，N的上界為2k，N的下界顯然為k

對于k，若已經(jīng)找到minimal product-sum numbers N，用數(shù)組n[k]=N表示

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

那么k可以分解為 k=N的大于1的因子個數(shù)(為方便用pro表示)+1的個數(shù)

1的個數(shù)為N-N大于1的因子之和=N-sum_product(為方便用sump表示)

所以k=pro+N-sump

那么i*N這個數(shù)的3項值就可以在N的基礎(chǔ)上直接得到

i*N的因子相當(dāng)于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的基礎(chǔ)上使用這個模式能得到一個新的k值和對應(yīng)的新的N值(i*N)

從N=1開始，遍歷所有的i*N，若i*N小于當(dāng)前的n[k]那么便替換

因為k總能用pro+N-sump的形式來表示，所以逆向遍歷所有情況后就能得到所有k的n[k]

之后再在主函數(shù)中跑一遍標(biāo)記已經(jīng)找到的N值避免重復(fù)

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

第二個鏈接是羅馬字符書寫規(guī)則

在羅馬，像羅馬人一樣思考！

羅馬數(shù)字的書寫規(guī)則允許一個數(shù)字被用多種方式表達（具體見?Roman Numerals）。但是，對于每個數(shù)字都存在一種“最佳”書寫方式。

例如，以下是數(shù)字 16 的所有書寫形式：

IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI

只有XIIIIII和XVI是合法的（滿足3個基本規(guī)則，詳細(xì)見下或Roman?Numerals）。

XVI是最高效的，因為它使用了最少的數(shù)字。

roman.txt中包含一千個羅馬數(shù)字，但不一定是最簡形式；

找出將所有數(shù)字寫成最簡式一共節(jié)省的字符數(shù)。

注意：你可以認(rèn)為文件中所有的每個羅馬數(shù)字中同一單位的字符最多連續(xù)出現(xiàn)4次。

有意思的模擬題，至少能學(xué)學(xué)羅馬人如何計數(shù)的。

3個基本規(guī)則：

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.

數(shù)字必須按大小降序排列；

M C X不能被較小羅馬數(shù)字表示或超過；

D L V最多只能出現(xiàn)一次；

4條附加規(guī)則：

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個基本規(guī)則，但不一定滿足4個附加規(guī)則

使用4個附加規(guī)則可能能夠得到最簡書寫形式

4個附加規(guī)則其實很簡單，I X C能夠通過放在某個數(shù)的首位來表示減數(shù)

比如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種減數(shù)

思路大概就是先把羅馬數(shù)字變成數(shù)字，再變成最簡羅馬數(shù)字

或者直接找出冗余的寫法，實際上只有少數(shù)幾種冗余的寫法如VIIII之類的，全部找出來后變換求節(jié)省字符也很快。

不過我還是用了第一個思路。

將羅馬數(shù)字變?yōu)閿?shù)字很簡單，逐步分類討論即可，因為羅馬數(shù)字是降序字符排列，所以寫的時候也按對應(yīng)的降序來寫條件判斷；

數(shù)字變?yōu)榱_馬數(shù)字，羅馬數(shù)字包含減數(shù)只有13種表示法：

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

分解當(dāng)前數(shù)字即可，比如開始的16，按ac數(shù)組進行降序分解

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 的數(shù)字，另一個立方體也如此。將兩個立方體用不同的方式挨著放置，我們可以得到不同的兩位數(shù)。

如果仔細(xì)選擇每個立方體面上的數(shù)字，我們可以表示出 100 以下所有的平方數(shù)： 01, 04, 09, 16, 25, 36, 49, 64, 和 81。
例如，能夠達到這個目的的一種方式在一個立方體上標(biāo)示 {0, 5, 6, 7, 8, 9}，在另一個上標(biāo)示 {1, 2, 3, 4, 8, 9}。
但是在這個問題中，我們允許 6 和 9 通過顛倒來互相表示。所以 {0, 5, 6, 7, 8, 9} 和 {1, 2, 3, 4, 6, 7} 就可以表示所有 9 個平方數(shù)，否則無法標(biāo)示 09。
在判斷不同的安排時，我們只對每個立方體上的數(shù)字感興趣，而不考慮順序。

{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 個平方數(shù)的話，一共有多少種可行的排列？

用2個數(shù)組表示當(dāng)前的骰子A B狀態(tài)

寫一個函數(shù)判斷當(dāng)前A B是否能表示9個平方數(shù)

暴搜所有情況...

來說一下實現(xiàn)思路，可以直接寫好多個for來暴搜 （沒事 也很快）

但我想實現(xiàn)一個復(fù)雜一點的迭代遞推：

因為不同排列均相同，且一個骰子內(nèi)不會出現(xiàn)重復(fù)數(shù)字

所以不妨令A(yù)初始情況為 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骰子的狀態(tài)的下一個狀態(tài)開始

暴搜所有情況。

迭代函數(shù)的實現(xiàn)分類討論幾下就能完成：

ans：1217

其實90題寫的時候這個寫法略為繁瑣了，直接上for應(yīng)該更輕松點，但模擬過程中還是以中有足樂者。

這次難度比是40% 20% 40%? 不知各位感覺何如，當(dāng)時我還卡了好一會.

那么 后續(xù)也是隨意更新了.