1樓：橫豎乙個張
問題可以簡化為，求的值
因為每次只能向前或者向後跳個單位，所以我們只能先找到後面可以取到的最大值，即然後通過改變量字前面的正負號使為要求的數值，可以概述為向後求最大然後向前取整，但向前取的時候只能使值為偶數（因為把乙個值由正改為負時相當於減去2倍的這個值），所以減的值只能是偶數
由上可知：依次向後找值為時的最大和，使其與所求值的差為偶數即可：，為題目所給的值，為所求的步數
#include
using
namespace
std;
intmain
()cout
< boolss[ n];for( inti=0 ;i i++)ss [i]= false ;sum-=k ;sum/=2 ;for (inti= n-1; i>=0; i--)else sum-=n; }for (inti= 0;i i++)else }cout < cout <<0< 2樓： bfs可以沒啥說的 但我覺得 dp也可以 跳了i步了，當前位置是j，下次前跳為1，後為0dp[i+1][j+i+1][0] = dp[i][j][1]; dp[i+1][j+i+1][1] = dp[i][j][1]; dp[i+1][j-i-1][0] = dp[i][j][0]; dp[i+1][j-i-1][1] = dp[i][j][0]; 3樓：點點 送分題 1 +/- 2 +/- 3 … 由於區域性最小解(n)是 1-2+3 …=n（每次遞增1）所以全域性最優解小於等於區域性最小解2n 全域性可能最優解(m) 1+2+3...n=m是符合全為+或- 所以全域性最優解大於等於這個m = (n+n^2)/2 n>= x >= m 證出n>3時有一般解 (y1,y2)=（x+1-n+n1）/2 n1為小於n的最大的m y為設為-的數可能是1個也可能是2個取決於右邊的奇偶性O(1)複雜度 偽dp問題 4樓： 只考慮位置的絕對值。 先求始終向正向到達或超過所需步數n。 如果此時離目標距離為偶數，則n為所求。 否則如果n為偶數，則n+1為所求。 否則n+2為所求。 5樓：靈劍 想成是先跳1,2,3,……n步，這樣就到了的地方；然後挑一些步數，把正著跳變成反著跳，每一次減少的數是2k。由於我們把乙個正跳變成反跳，只能減少偶數步，所以最開始的總和必須要跟x的奇偶性相同。這個表示式的奇偶性取決於n對4取模的結果，餘0、餘3的時候是偶數，餘1、餘2的時候是奇數。 分別可以寫成： 我們再來考慮要回退的數的範圍。為了方便，我們記前面的表示式。 如果我們挑了乙個奇數，它： 位於S(4k+1)與S(4k+2)之間，於是相應的n至少應當是4k+2。我們要回退的範圍是0到4k中的偶數。回退乙個數足夠了。 位於S(4k+2)與S(4k+5)之間，相應的n至少應當是4k+5。要回退的範圍是0到12k + 10中的偶數。這時候乙個就不夠了，6k+5不在範圍內……但是，4k+3和2k+2怎麼樣？ 如果更小的話，自然也可以表示成4k+3和相應數的和，或者用單個數。 如果我們挑出了乙個偶數，它： 位於S(4k)與S(4k+3)之間，於是相應的n至少應當是4k+3，要回退的範圍是0到12k+4中的偶數。4k+2，2k，兩個數剛好。更小的數自然也可以表示。 位於S(4k+3）與S(4k+4)之間，於是相應的n至少應當是4k+4，要回退的範圍是0到4k+4中的偶數。乙個數足夠了。 結論：只要選出符合條件的最小的n，就一定可以跳到這一點上。符合條件是指： S(n) >= x，且x為奇數是n = 4k + 1或4k + 2，x為偶數時n = 4k + 3或4k + 4。 求n的方法自然是求根公式： 這裡要小心處理的乙個坑是當1 + 8x是完全平方數的時候，整個表示式算出的結果是個整數，如果捨入誤差處理不好，往上進了1，就貽笑大方了……所以算出結果之後可以帶回到n(n+1) >= 2x的表示式當中，檢驗n0和n0-1各自是否符合條件。算出n0之後，再根據x的奇偶性和n0對4取模的結果調整一下就可以輸出了。 6樓：班傑明 一開始覺得很難，覺得自己很水。。。。後來洗澡的時候想了一下，居然想出來答案了，真是覺得自己萌萌噠。 答案樓上已經說得很清楚了，我簡單地說說： 1.螞蟻最少跳多少步？ 答：螞蟻一直往前跳，直到跳過「輸入資料」位置（跳了p步）。螞蟻的最短步數為p或者p+1。 2. 有沒有比p少的步數？ 答：螞蟻一直往前跳都跳不到「輸入資料」，比p少絕壁不可能。 3. 為什麼第p步一定能剛剛好跳到「輸入資料」？ 答：螞蟻一直往前跳p步，跳到M處。 假設螞蟻第1步往後跳，其他都往前跳，那麼就能跳到M-2*1處。 假設螞蟻第2步往後跳，其他都往前跳，那麼就能跳到M-2*2處。 假設螞蟻第1和2步往後跳，其他都往前跳，那麼就能跳到M-2*（1+2）處。 所以理論上螞蟻能跳到任何乙個「輸入資料」的地方，只要控制好向後步數x，就能得到M-2*x=任何數（與M相差2,4,6,8等等任何偶數的數）。 如果「輸入資料」與M相差是奇數，則再往前跳一次，重複上面的過程。也就是p+1步。 7樓：朱麗啦 和王遠的想法差不多 首先只考慮正數情況，因為負數是一樣的 先去用數列疊加去逼近目標值 比如1+2+3+...+n<=x<1+2+...+（n+1）如果不等式中等號成立，那自然答案就是n。 如果不等，考慮y=1+2+...+(n+1)-x 如果是偶數，那麼翻轉數字y的符號即可，答案表示n+1. 如果y是奇數，那麼肯定1，2,...，n+1是無法表達出x的。現在只能去考慮 1+2+3+...+（n+2）和1+2+...+（n+3）如果前者與x相減還是奇數，則去考慮後者。 其與x相減為偶數的時候，則必然可以反轉數列中的某兩個數字使得整個式子結果為x 8樓： 這是數學題，自然數相加到n的和大於等於x，求n即可。 我來回答是突然想起高中競賽一道題，noip 2005 青蛙過河 變化的地方在於可跳躍步數是乙個範圍，河上面有石頭，意思是落腳點是個離散點集合，求最少步數。dp只能解30%。 9樓： 最簡單粗暴的方法：bfs… 下面是數學方法，可以視為對@王遠答案的補充，因為我覺得他寫的不夠直觀 首先引入一條引理：1,2,3...p中部分數的和與1到p(p+1)/2之間的整數存在雙射關係，且兩者相等。下圖是p=4時的例子 10樓： 宣告：僅考慮正距離。 首先，反過來考慮乙個問題： 使用跳躍x次能走過的哪些距離？ 答案是：對於任意的，只要k與x奇偶性相同，都可以到達。 首先是跳躍x次能夠到達的最遠距離。 那麼對於，僅需要在第一步時回跳即可，即 對於,都是可以找到組合實現回跳的。 (總能找到的子集表示任意小於S的數字。) 基於以上結論，對於所需達到的距離k，我們只需要找到最小的x即可。 1：利用二次方程求解公式求出x0 double x0=Math.ceil((Math.sqrt(1+8*k)-1)/2); 2：奇偶性判斷 如果k和奇偶性不同，則需要修正x0 if(k %2==0 )elseif( x0%4== 2)}else elseif( x0%4=3)} 11樓： 我的直覺和Yah是一樣。隨手寫了個。O(N^2)int func(int n) ; for (int cur = 1; ; curif (iset.find(n)!=iset. end()) return cur-1unordered_set jsetfor (auto i:isetjset.insert(i + curjset. insert(i - curiset = jset;}} 董昊 相當於for i 0,j 0 i 10 j 6 i j document.write k 顯然當i j 5的時候跳出迴圈，故k 10 二尺七大褲衩 這個主要是逗號語句，當有多個條件，之間用逗號隔開的時候，會返回最右側的條件 可以試驗 第乙個 vari,j k for i 0,j 0 i 10,... 木夏 長夜漫漫，又是乙個明早要上課卻無法入睡的夜晚.和劍靈答的相反，我覺得最後應該是趨於所有人都感染才對，A為受感染男性比例，B為受感染女性比例，A B 1 但人數又無窮，根本感染不完呀，這題好像沒法穩定。其實我強行算了乙個解，穩定條件是感染人數的增加比率相同，而不是比率等於期望。結果和初始條件感染... 張文軒 顯然是不可以的，a是number型別，六種基本型別的一種，基本型別是不會有方法的，但是有時候發現基本型別也能呼叫一些方法，是因為在呼叫這些方法之前會建立對應的包裝型別，比如Number包裝型別，然後基本型別就可以使用包裝型別的方法，但是呼叫之後，這個包裝型別就會被銷毀，所以a.b為undef...一道前端JS面試題，求解？
一道關於概率的面試題？
一道網易 JS 面試題，有哪些解題思路？