NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » sagit 的個人資料 » 顯示文章
 文章

顯示文章

這裡允許您檢視這個會員的所有文章。請注意, 您只能看見您有權限閱讀的文章。

文章 - sagit

頁: [1] 2 3 ... 12
1
NPSC2017高中組初賽 / G.A|B Problem
« 於: 十月 17, 2018, 02:39:55 pm »
這題要以二進位來思考,
假設 A=100100010,
則滿足 A+B=A|B 條件的 B,
在 A 中為 1 的位元必定為 0,
也就是 B=0xx0xxx0x,
其中的 x 可為 0 或 1,
因此只要數一下 A 裡面有幾個位元是 0,
算出 2 的次方就可以得到答案。

但是題目又規定 B <=X ,
所以我們要將 X 分段處理,
假設 X=1001000100,
先找出最左邊第一個出現的 1 為 1000000000,
分出第一段數字 xxxxxxxxx,(不含上面的數)
也就是 0 ~ 111111111 (1000000000-1),
再用這一段去找有幾個位元在 A 中是 0。
接下來再找出第二個出現的 1 為 1000000,
而第二段數字為 1000xxxxxx,
也就是 1000000000 ~ 1000111111 (1001000000-1),
數字的最前面固定是 1000,
一樣找出後面的位元有幾個在 A 中是 0。
要注意的是,如果這個位元在 X 和在 A 中同時為 1,
則後面就不會再有答案,必須中斷。

再來,因為這個做法只能處理到 X-1,
所以 X 要另外處理。
最後,因為題目要求要正整數,
但這個做法會包含 0,
所以答案要再減一。

核心程式碼:
代碼: [選擇]
for (bit=(1<<30), ans=0; bit; bit>>=1)
{
    if ((bit&x)==0) continue;
    for (bit2=(bit>>1), c=0; bit2; bit2>>=1)
        if ((bit2&a)==0) c++;
    ans+=A[c];
    if (bit&a) break;
}
if ((a|x)==(a+x)) ans++;
printf("%d\n", ans-1);
PS. A[ i ] 為 2i, 可在程式一開始先算出它們的值。

2
NPSC2014高中組初賽 / G.華麗內餡格狀超好吃巧克力
« 於: 十月 15, 2018, 02:56:08 pm »
這題答案的長方形,如果不是 1x2,就一定是 1x3 的大小,
以這個方式每個都找一找就可以找到答案。

3
NPSC2017高中組初賽 / D.魔法施放距離
« 於: 十月 15, 2018, 02:49:58 pm »
將下限L設為 1,上限U設為 4e18 (即 4*1018),
< 和 <= 時修正U (k比U小的時候才修正),
而 > 和 >= 時修正L (k比L大的時候才修正),
U-L+1即是答案,
要注意如果答案是負的則輸出0,
而答案大於 1e18 則是 INF。

4
NPSC2017高中組初賽 / A.A+B Problem
« 於: 十月 15, 2018, 02:43:36 pm »
假設字串長度為L,
以兩層的for迴圈,
第一層 i=1~L/2,第二層 j=i+1~L*2/3,
則可以分解成三個子字串:0~i-1、i~j-1、j~L-1,
任一子字串的長度為2以上,且第一個字元為0時不合法,
接下來再將三個子字串各自轉成long long int,
再判斷a+b==c是否成立即可。

5
NPSC2017高中組決賽 / Re: G. 最大不連續和問題
« 於: 十月 15, 2018, 02:18:21 pm »
用三個陣列來記錄,A[ i ]記錄輸入的數字是多少,
B[ i ]記錄從第一個數到第i個數取某些數字(至少取一個)的最大值是多少,(第i個不一定要取),
B[1]=A[1],i=2~N-2時,B[ i ]=max(A[ i ], B[ i-1 ], A[ i ]+B[ i-1 ]),
而 C[ i ]記錄以第i個為最後一個的最大不連續和是多少,(第i個一定要取)
C[3]=A[1]+A[3],i=4~N時,C[ i ]=max(C[ i-1 ], B[ i-2 ])+A[ i ],
即可求出答案。

6
NPSC2017高中組決賽 / Re: D. 最大不團問題
« 於: 十月 08, 2018, 04:24:59 pm »
其實只要檢查 m!=n*(n-1)*2 即可,後面的資料完全不需要輸入。
另外,因為 n 最大為 10^5,
n*(n-1) 會超過 int 的範圍,要注意,
而因為 m 最大也是 10^5,
所以可以 反推回去 n 超過 500 的情況一定是 n,
就不用再乘了。
也就是:
代碼: [選擇]
if (n>=500||m!=n*(n-1)*2) cout << n << endl;
else cout << 0 << endl;

7
NPSC2016高中組決賽 / Re: E.艾迪摺紙趣
« 於: 十一月 10, 2017, 01:56:05 pm »
這題可以用動態規劃來做,
我們用 A[ i][ j] 來表示長寬為 i、 j 的長方形最少可以分割成幾個正方形,
則 A[ i][ 1]=1 (i=1~N)、A[ 1][ j]=1 (j=1~M),
然後可以用兩層迴圈 i=2~N、j=2~M 來求解。

當 i=j 時, A[ i][ j]=1,
否則做出所有的分割方式找最小值,
例如 A[ i][ k]+A[ i][ j-k] (k=1~M-1) 以及 A[ k][ j]+A[ i-k][ j] (k=1~N-1),
時間複雜度為 O(N*M*(N+M)),得解。

8
NPSC2016高中組決賽 / Re: C. 是誰的餅乾藏在餅乾盒裡
« 於: 十一月 10, 2017, 01:49:33 pm »
基本上這題可以用暴力法來做,
假設長和寬分別為 a、b (1<=a<=b<=sqrt(v)),
則 v 可以被 a*b 整除且 v/a/b 不小於 b,則找到一組解。

但如果你是從 1 找起,
則可能會超過時間,
因此可以先用一層迴圈找出 v 的所有因數(做到 sqrt(v) 即可),
將因數從小到大排序之後,
再以這些因數為 a 和 b 的值,
這樣就不會超過時間。

9
NPSC2016高中組初賽 / NPSC 2016 高中組初賽 B.騎士出任務
« 於: 十一月 09, 2017, 01:41:55 pm »
對於一個N>=3且M>=3的棋盤,
只要依序3、6、1即可往右移一格,
依序4、1、6即可往下移一格,
所以任一棋盤只要符合N>=3且M>=3則一定有解,
N>M>>>3的情況就走3,反之則走4,
若其中一個為3,另一個很大,
則走3、6可以往下兩格,走4、1可以往右兩格,
走到最後,一定可以變長一個為3,另一個為2或3,
就可以解出來。

至於N=1或M=1則是無解,
而N=2或M=2的情況下,
另一個如果是3、7、11等4K-1的數則是有解,
其他情況則無解。

10
NPSC2016高中組初賽 / NPSC 2016 高中組初賽 D.水晶球傳送問題
« 於: 十一月 08, 2017, 03:50:57 pm »
先找出所有祭壇裡面法力門檻最低的是 K,
再來一一找出哪些水晶球可以形成一個循環,
每組循環可以以該循環中法力門檻最低(假設為 L)的那個祭壇做交換,
假設這個循環有 N 個水晶球,
則只要交換 N-1 次就可以讓這 N 個水晶球回到自己的位置,
總花費是 (N-1)*L,但這不一定是最佳解,
另一種做法則是先把其中一個跟全體法力門檻最低的那個交換,
全部交換完一圈則是有 N+1 次的交換,
總花費則是 (N+1)*K,
我們取比較小的那個。

例如官方第57組測資:
9
5 6 9 13 100 200 15 7 20
2 3 1 5 6 4 8 9 7
可以分成123、456、789這三組循環,
123這組剛好有全體法力門檻最低的祭壇,
所以花費是 (3-1)*5=10,
456這組法力門檻最低的祭壇是13,
所以兩種花費分別是 (3-1)*13=26、(3+1)*5=20,取20這一個,
最後789這組法力門檻最低的祭壇是7,
所以兩種花費分別是 (3-1)*7=14、(3+1)*5=20,取14這一個,
整體最小花費就是10+20+14=44。

11
NPSC2016高中組初賽 / NPSC 2016 高中組初賽 G.普遜與食安問題
« 於: 十一月 07, 2017, 01:58:47 pm »
因為最多只有15個點,所以可以用回溯法來寫,
每個點都只有取與不取兩種情況,
所以題目最多就是 215 種組合,
每個組合再以 M 次的迴圈檢查每條邊的兩個點是否至少有一個點有被選取,
如果符合,則是一組答案。

因為答案是依字母順序,在寫回溯法時可以先做"取"再做"不取"的,
以三個點的情況來說,則是 O--、OO-、OOO、OOX、OX-、OXO、OXX…
O代表該點要取,X代表該點不取,-代表還沒判斷。
而找到的答案先記錄起來,並記錄取了幾個點,
如果尋找的過程中取的點數超過了之前最佳的答案,
後面的部分就不需要再展開,以加快處理。

12
NPSC2016高中組初賽 / NPSC 2016 高中組初賽 F.逆序數對
« 於: 十一月 07, 2017, 01:45:22 pm »
使用到排列組合的數學題,
先分析題目中有多少組連續的>,例如 >>><>>,
可分成前面的 >>> 和後面的 >>,
前面的 >>> 代表有四個遞減的數,
這四個數任選兩個都是符合題目要求的送序數對,
總共有 C(4,2)=4*3/2=6 組,
而後面的 >> 則是 C(3,2)=3*2/2=3 組,
答案則是 6+3=9組。

13
NPSC2016高中組初賽 / NPSC 2016 高中組初賽 E.廢文 mining
« 於: 十一月 07, 2017, 01:38:04 pm »
N=1和N=2的情況直接處理,
N=3以上的情況,可以用
代碼: [選擇]
for (int i=3; i<=n; i++)
{
    s=s2+s1;
    s1=s2;
    s2=s;
}
這樣的寫法來取得第 N 天的文章,
但是如果N超大的情況,這個字串的長度可能會超過電腦的記憶體,
幸好題目有說我們要的第 K 字元的 K 最大只到 106
而當文章長度超過 106 時,
接下來不管多少天,前  106 的內容還是一樣的,
所以可以在前面的 for 裡加上一行:
代碼: [選擇]
if (s.size()>=1000000) break;
這樣問題應該就解決了。

14
NPSC2016高中組決賽 / Re: H.吃吃為吃吃,是吃也
« 於: 十一月 07, 2017, 01:22:27 pm »
感謝你提供這麼多題目的解法,
可以的話,請你以後再多幾行文字的敘述,
描述一下解題的重點,
對其他使用者來說應該是會更有幫助。

15
TOI初選討論區 / Re: TOI練習賽
« 於: 十二月 22, 2016, 02:15:46 pm »

16
綜合討論區 / Re: NPSC 2016 模擬試題 有關pD
« 於: 十一月 18, 2016, 09:32:12 am »
這一題系統採用的是 special judge,
和以往文字比對的方式不同,
是另外用一個程式檢查你的輸出對不對,
假設你輸出的是 a、b 兩數,
只要符合 a+b=x 以及 0<=a,b<=1000 這兩個條件,
送出之後應該都會過。

17
站務區 / 註冊須知
« 於: 十一月 01, 2016, 02:35:16 pm »
1.本站開放註冊時間為每年10月1日至12月31日,其他時間關閉註冊。

2.請使用非免費信箱註冊,本站免費信箱只接受 gmail,使用其他信箱者一律刪除。

3.本站採兩階段認證,第一階段由站長審核 email 是否符合規定之後,再發出確認信,
第二階段收到確認信之後再點選其中的連結,即可啟用帳號。

18
NPSC2015高中組決賽 / NPSC 2015 高中組決賽 F.非對稱之美
« 於: 十月 20, 2016, 02:05:42 pm »
先排除所有字元都相同的情況,
接下來如果字串長度是 N,
則不可能同時找到長度為 N 和 N-1 的回文,
因此,答案只有 0、N-1、N 這三種。

19
NPSC2015高中組決賽 / NPSC 2015 高中組決賽 D.三角尼姆
« 於: 十月 20, 2016, 02:03:16 pm »
先分析,因為每個人只能放一顆或三顆棋子,
第一個人放的是第一或第三顆棋子,
而第二個人則是第二、四、六顆棋子,
再回來第一個人則是第三、五、七、九顆棋子,
發現不管怎麼放,第一個人放的最後一顆一定是奇數,
而第二個人放的最後一顆一定是偶數,
所以只要計算總共有幾顆棋子,
就知道最後一顆是誰放的了。

20
NPSC2015高中組初賽 / NPSC2015 高中組初賽 F.秋刀魚捕撈季
« 於: 十月 19, 2016, 04:04:01 pm »
將魚的重量從大排到小,取前 F 重量在 W 以上的加起來就行,
比較麻煩的是魚的重量會出現 other,
因此先以字串的方式輸入,
如果 s[ 0 ]!='o',再將這個字串轉換成數字,
for (i=0, w=0; i<s.size(); i++) w=w*10+s[ i ]-'0';
上面是轉換寫法的一個例子,
只要對字串轉換沒有恐懼,
這題應該是這次初賽中最簡單的一題。

頁: [1] 2 3 ... 12