題意：從p=1開始，兩個人輪流乘2~9之間的數，看誰最先乘到比給定的數大。

分析：題目y規律，但也可以根據之前所學的知識用SG求，雖然我不會。

先是規律分析：

p從1開始，每次乘2~9，所以2~9是先手必勝的。然后9~18，是先手必敗。19~18*9是先手必勝，同樣，18*9+1~18*2*9是先手必敗。

容易看出，是以18為規律的，除18，最后看在那個區間。

?

#include <iostream> #include<algorithm> using namespace std; int main() {double n;while(cin>>n){while(n>18){n=n/18; }if(n<=9){cout<<"Stan wins."<<endl;}else{cout<<"Ollie wins."<<endl;}}return 0; }

下面就是正常的推算代碼，摘自https://blog.csdn.net/riba2534/article/details/53895389

先把所有可能的乘積從小到大，一一列舉出來。之后找出乘積小于給定那個數的范圍。最后一個人可以直接*9，所以，從原來最大數除9向下找。解釋放在代碼中，這種方法值得學習！

#include<iostream> using namespace std; int main() {__int64 a[7000] = { 1 }, min, n;int p[10], sg[7000], i, j, k;for (i = 2; i < 10; p[i] = 0, i++);for (i = 1; i < 7000; i++){for (j = 2, min = -1; j < 10; j++)if (min == -1 || a[p[j]] * j < a[p[min]] * min)min = j;a[i] = a[p[min]] * min;min = a[p[min]] * min;if (a[i] >= 5000000000)break;for (j = 2; j < 10; j++)if (a[p[j]] * j == min)p[j]++;}//從小到大求出所有乘積while (scanf("%I64d", &n) != EOF){for (i = 0; i < 7000; i++){sg[i] = 0;if (a[i] >= n)break;}for (j = i - 1; a[j] * 9 >= n && j >= 0; j--)sg[j] = 1;while (j >= 0){for (k = j + 1; k < i&&a[j] * 9 >= a[k]; k++)if (a[k] % a[j] == 0 && sg[k] == 0)//到最后一個點需要兩步，不等于0那就是偶數步，肯定是先手必輸，等于0就是奇數步，先手必贏//第一個判斷是因為要一個一個往下除，所以必須要整除，這里有點搜索的味道了，在x~x*9的范圍里搜索除整除數，//并且是否為奇數步，有一個為奇數步那就是先手必勝，沒有奇數步，全是偶數步那就是先手必輸//所以先手是奇數步可以轉換成偶數步，因為偶數步是0，所以它后面如果能整除那么全都是1，這就回到了PN問題。偶數步只能轉換為奇數步，//而奇數步能找到一個轉換為偶數步的。{sg[j] = 1;break;}j--;}puts(sg[0] ? "Stan wins." : "Ollie wins.");}return 0; }

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的HDOJ1517的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。