試題 A: 階乘求和

【問題描述】

令 S = 1! + 2! + 3! + ... + 202320232023!，求 S 的末尾 9 位數字。

提示：答案首位不為 0。

【答案提交】

這是一道結果填空的題，你只需要算出結果后提交即可。本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分。

思路:暴力計算量會超過10^12,考慮階乘特點,對于i∈[1,202320232023],當i增大時,i中所含的偶因子{2,5,10...}會越來越多,不妨假設當i超過某個數時i!的末九尾全為0,所以打表看一下Si = 1!+2!+.....+i!,當Si的末九位不變時,就得到了答案.

試題 B: 幸運數字

【問題描述】

哈沙德數是指在某個固定的進位制當中，可以被各位數字之和整除的正整數。例如 126 是十進制下的一個哈沙德數，因為 (126)10 mod (1+2+6) = 0；126也是八進制下的哈沙德數，因為 (126)10 = (176)8，(126)10 mod (1 + 7 + 6) = 0；同時 126 也是 16 進制下的哈沙德數，因為 (126)10 = (7e)16，(126)10 mod (7 +e) = 0。小藍認為，如果一個整數在二進制、八進制、十進制、十六進制下均為哈沙德數，那么這個數字就是幸運數字，第 1 至第 10 個幸運數字的十進制表示為：1 , 2 , 4 , 6 , 8 , 40 , 48 , 72 , 120 , 126 . . . 。現在他想知道第 2023 個幸運數字是多少？你只需要告訴小藍這個整數的十進制表示即可。

【答案提交】

這是一道結果填空的題，你只需要算出結果后提交即可。本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分。

思路:簡單模擬

試題 C: 數組分割

時間限制: 1.0s

內存限制: 512.0MB

【問題描述】

小藍有一個長度為 N 的數組 A = [A0, A1, . . . , AN?1]?，F在小藍想要從 A 對應的數組下標所構成的集合 I = {0, 1, 2, . . . , N ? 1} 中找出一個子集 R1，那么 R1在 I 中的補集為 R2。記 S 1 = ∑ r∈R1 Ar，S 2 = ∑r∈R2 Ar，我們要求S 1 和 S 2 均為偶數，請問在這種情況下共有多少種不同的R1。當R1 或 R2 為空集時我們將S1 或 S2 視為 0。

【輸入格式】

第一行一個整數 T，表示有 T 組數據。接下來輸入 T 組數據，每組數據包含兩行：第一行一個整數 N，表示數組A 的長度；第二行輸入 N 個整數從左至右依次為 A0, A1, . . . , AN?1，相鄰元素之間用空格分隔。

【輸出格式】

對于每組數據，輸出一行，包含一個整數表示答案，答案可能會很大，你需要將答案對 1000000007 進行取模后輸出。

【樣例輸入】

2

2

6 6

2

1 6

【樣例輸出】

4

思路:若A中的元素有奇數個奇數,則無存在的劃分,反之若存在n個(n%2=0&&n!=0),則劃分為組合數Cn0+Cn2+Cn4+...+Cnn = 2^(n-1)+1,若n=0,則劃分為Cn1+Cn2+Cn3+...+Cnn = 2^n。

試題 D: 矩形總面積

時間限制: 1.0s

內存限制: 512.0MB

【問題描述】

平面上有個兩個矩形 R1 和 R2，它們各邊都與坐標軸平行。設 (x1, y1) 和(x2, y2) 依次是 R1 的左下角和右上角坐標，(x3, y3) 和 (x4, y4) 依次是 R2 的左下角和右上角坐標，請你計算 R1 和 R2 的總面積是多少？

注意：如果 R1 和 R2 有重疊區(qū)域，重疊區(qū)域的面積只計算一次。

【輸入格式】

輸入只有一行，包含 8 個整數，依次是：x1，y1，x2，y2，x3，y3，x4 和 y4。

【輸出格式】

一個整數，代表答案。

【樣例輸入】

2 1 7 4 5 3 8 6

【樣例輸出】

22

思路:得出R1四個角的坐標后看看是否存在某個角落在R2的區(qū)域,減去重疊區(qū)域的面積。

時間開銷O(1)

試題 E: 蝸牛

時間限制: 1.0s

內存限制: 512.0MB

【問題描述】

這天，一只蝸牛來到了二維坐標系的原點。在 x 軸上長有 n 根竹竿。它們平行于 y 軸，底部縱坐標為 0，橫坐標分別為 x1, x2, ..., xn。竹竿的高度均為無限高，寬度可忽略。蝸牛想要從原點走到第n 個竹竿的底部也就是坐標 (xn, 0)。它只能在 x 軸上或者竹竿上爬行，在 x 軸上爬行速度為 1 單位每秒；由于受到引力影響，蝸牛在竹竿上向上和向下爬行的速度分別為 0.7 單位每秒和 1.3 單位每秒。為了快速到達目的地，它施展了魔法，在第 i 和 i + 1 根竹竿之間建立了傳送門（0 < i < n），如果蝸牛位于第 i 根竹竿的高度為 ai 的位置 (xi , ai)，就可以瞬間到達第 i + 1 根竹竿的高度為 bi+1 的位置 (xi+1, bi+1)，請計算蝸牛最少需要多少秒才能到達目的地。

【輸入格式】

輸入共 1 + n 行，第一行為一個正整數 n；

第二行為 n 個正整數 x1, x2, . . . , xn；

后面 n ? 1 行，每行兩個正整數 ai , bi+1。

【輸出格式】

輸出共一行，一個浮點數表示答案（四舍五入保留兩位小數）。

【樣例輸入】

3

1 10 11

1 1

2 1

思路:dp,設有dp[i][0],dp[i][1]表示到達第i根桿子底部和第i根桿子的傳送點的最優(yōu)解,則有狀態(tài)轉移方程dp[i][0] = min(dp[i-1][0],dp[i-1][1]+從第i-1根下來到第i根的時間),dp[i][1] = min(dp[i-1][1]+兩個傳送點的時間,dp[i-1][0]+從第i-1根底部到第i根傳送點的時間);當到達最后一根桿子時,ans = min(dp[n-1][0],dp[n-1][1]+從第n-1根上下來的時間).

時間開銷O(n)

試題 G: 買二贈一

時間限制: 1.0s

內存限制: 512.0MB

【問題描述】

某商場有 N 件商品，其中第 i 件的價格是 Ai?，F在該商場正在進行 “買二贈一” 的優(yōu)惠活動，具體規(guī)則是：每購買 2 件商品，假設其中較便宜的價格是 P（如果兩件商品價格一樣，則 P 等于其中一件商品的價格），就可以從剩余商品中任選一件價格不超過 P2的商品，免費獲得這一件商品。可以通過反復購買 2 件商品來獲得多件免費商品，但是每件商品只能被購買或免費獲得一次。小明想知道如果要拿下所有商品（包含購買和免費獲得），至少要花費多少錢？

【輸入格式】

第一行包含一個整數 N。

第二行包含 N 個整數，代表 A1, A2, A3, . . . ，AN。

【輸出格式】

輸出一個整數，代表答案。

【樣例輸入】

7

1 4 2 8 5 7 1

【樣例輸出】

25

思路:貪心,首先sort(A,A+n),每次取兩個最大的出來然后,用其中小的帶來的優(yōu)惠買一件免費的,用book數組記錄被買過的。

時間復雜度O(nlogn);

未來的路上，期待和大家一同進步！感謝大家的支持！掃碼關注 計算機理論干貨分享 ，有更多好物與你分享！快來和我一起學習啦！