無窮的數(shù)列

找規(guī)律

【問題描述】

有一個無窮序列如下：

110100100010000100000…

請你找出這個無窮序列中指定位置上的數(shù)字。

【輸入】

第一行一個正整數(shù) N，表示詢問次數(shù)；接下來的 N 行每行一個正整數(shù) Ai，Ai 表示在序列中的位置。

【解題過程】

找規(guī)律就好了。對于一個給定的位置 P，可以發(fā)現(xiàn)如果 P 上的數(shù)字是 1，那么必然滿足 P-1 = x*(x+1)/2，那么判斷這個方程是否有整數(shù)解即可（開平方取整再乘）。

1 次 AC。

?

方程

動態(tài)規(guī)劃

【問題描述】

【輸入】

第一行是 n 和 c。

第二行是 n 個數(shù)，分別表示 a1, a2, ..., an。

【輸出】

輸出解的組數(shù)（結(jié)果對 999983 取模）。

【解題過程】

一開始真的沒思路啊，剛好數(shù)學(xué)在上排列組合，有個神奇的「隔板法」，差點誤入歧途。

然后想到了一個很奇葩的方法，用 f[i] 表示用這個式子組成 i 這個值有幾組解，則

f[i] = sum{ f[i-a[j]], 1<=j<=n }

看上去有點道理，然后其實是錯的。這種狀態(tài)轉(zhuǎn)移的方式無法判斷重復(fù)的情況，比如 b1 取 1，b2 取 1 是可以由兩種情況（1, 0 和 0, 1）推過來的，加的時候也就多加了。

然后居然想了將近一個小時才想到正解，我也是醉了。

用 f[i][j] 表示用 a1, a2, ..., ai 來組成 j 有多少組解，則

f[i][j] = f[i-1][j] + f[i-1][j-a[i]], 1<=j<=n

然后如果用上滾動數(shù)組的話，最后表現(xiàn)出來的代碼與上面那種錯誤方法幾乎完全一樣，只是外循環(huán)和內(nèi)循環(huán)調(diào)換了一下。

然后聽到 lzw 大神說無限背包。然后就沒有然后了。

1 次 AC。

?

交錯匹配

動態(tài)規(guī)劃

【問題描述】

有兩排非負(fù)整數(shù) A[1..N]，B[1..M]，如果 A[i]=B[j]=k，那么可以在 A[i]和 B[j]之間連一條線，稱為一條 k 匹配，每個數(shù)至多連一條線。另外，每個 k 匹配都必須恰好跟一個 r 匹配相交，且 k≠r。現(xiàn)在要求一個最大的匹配數(shù)。

例如：以下兩行數(shù)的最大匹配數(shù)為 8.一個數(shù)最多只能和一個數(shù)連線。

【輸入】

輸入文件第一行包含兩個正整數(shù) n 和 m。

第二行 n 個自然數(shù)，表示 a[i]。

第三行 m 個自然數(shù)，表示 b[i]。

【數(shù)據(jù)規(guī)模】

30%的數(shù)據(jù)滿足 n,m≤30。

60%的數(shù)據(jù)滿足 n,m≤200。

100%的數(shù)據(jù)滿足 n,m≤1000，0<所有數(shù)≤32767。

【解題過程】

看到什么最大匹配的還以為是二分圖，嚇了一小跳。

然后從數(shù)據(jù)范圍來看幾乎可以肯定是 O(mn) 的動態(tài)規(guī)劃。

借鑒 LCS 的狀態(tài)表示，用 f(i, j) 表示 a1, ..., ai 與 b1, ..., bj 之間的最大匹配數(shù)，那么我們只要考慮 ai 與 bj 是否需要進行匹配。如果要進行匹配，那么只要在 bj 的左邊找與 ai 匹配的數(shù)、在 ai 的左邊找與 bj 匹配的數(shù)就能保證兩個匹配相交。很明顯，對于 ai 找 bj 左邊距離 bj 最近的那個匹配才可能是最優(yōu)解，對于 bj 也應(yīng)該找 ai 左邊最近的匹配。這個找匹配的過程我們可以事先進行預(yù)處理。用 p(i, j) 表示 ai 在 b1, b2, ..., bj 中離 bj 最近的那個匹配所在的位置，則可以進行遞推：

若 ai=bj，則 p(i, j) = j

否則，p(i, j) = p(i, j-1)

然后可以用 q(j, i) 表示 bj 在 a1, a2, ..., ai 中離 ai 最近的那個匹配的位置，遞推過程類似。

然后就可以寫出狀態(tài)轉(zhuǎn)移方程了，

f(i, j) = max{ f(q(j, i-1)-1, p(i, j-1)-1), f(i-1, j), f(i, j-1), f(i-1, j-1) }

初始得分 90 分。原因是把遞推的嵌套循環(huán)范圍寫錯了（這樣也能拿 90 分？）。

轉(zhuǎn)載于:https://www.cnblogs.com/lsdsjy/p/3982489.html

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。