NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

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

顯示文章

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

文章 - sagit

頁: [1] 2 3 ... 12
1
NPSC2018高中組決賽 / A.分裂的樹堆
« 於: 五月 14, 2020, 10:46:38 am »
每破壞一條邊,就會多一個樹堆出來,
因為只要計算這條路徑有幾條邊,
加一之後則是分散出來的樹堆有幾個。

先以起點 S 做一次 BFS 或DFS 計算出 S 到每個點的距離 Di
再將 i 值從 L 做到 R 計算 Di+1的值即可。

2
NPSC2018高中組初賽 / E.三角形
« 於: 五月 14, 2020, 09:18:40 am »
將所有的邊長相加之後為 S,
答案就是 S*6/(n*(n-1))

3
NPSC2018高中組初賽 / D.分裂吧,樹堆
« 於: 五月 14, 2020, 09:15:23 am »
先處理特殊情況 N=1:
S0<K 輸出-1
S0=K 輸出0
S0>K 輸出P0

N>=2的情況:
先依照 S 值由大排到小,S 值相同的則依照 P 值由大排到小
如果前兩個的 S 相加之後小於 K,則輸出 -1,
接下來把這些數字切成兩段,
前面的是 Si > K,後面的則是 Si < K,
如果有找到 Si = K,則輸出 0。
前面 Si > K 的部分只要把該樹堆分裂即可,
因此找 Pi 最小的一個為 P1,
前面 Si < K 的部分則是需要兩個樹堆合併,
S 值相加之後大於 K 時才會有解,將 P 值較小的樹堆分裂,
這邊的最小值為 P2,
而若有一組 S 值相加之後等於 K,則 P2=0,
最後輸出 P1、P2 中較小的那個即可。

4
NPSC2018高中組決賽 / H.輸贏吧,在二次元征戰之中
« 於: 五月 14, 2020, 09:03:47 am »
基本上應該沒什麼困難的,
每一行的數字加起來,
就是那個選手可以贏幾場,
用一次的迴圈找出最大值是多少,
再用一次的迴圈找出和最大值相同的有幾個,
最後再用一次的迴圈,印出這些人的名字。

5
NPSC2018高中組決賽 / B.貓咪與拉不拉多
« 於: 五月 14, 2020, 09:01:12 am »
原始的玩法是輪到你時剩 K+1 個的整數倍就輸了,
因為最多可以一次吃兩次,所以變成剩下 2*K+1 時就輸了,
但是再上去還是跟 K+1 有關。
最後一規則是:
N=0 狗贏
N<K*2+1 貓贏
N=K*2+1 狗贏
N>K*2+1的情況下:
(N-(K*2+1))可被(K+1)整除 狗贏
其他情況 貓贏

6
NPSC2019高中組初賽 / Re: D.分裁判問題
« 於: 十一月 23, 2019, 11:49:31 am »
請問
#define endl '\n'
這一列是不是可以省略?
直接寫
cout<<'\n';
是可以的嗎?

可以

7
NPSC2019高中組初賽 / Re: D.分裁判問題
« 於: 十一月 17, 2019, 10:40:01 pm »
這個網站是不是都沒人了阿

站長還活著,但沒什麼人會來了
曾經有一度這網站被NPSC官方網站列入參考資料的網站,
後來一次改版之後就被拿掉了,
然後人就越來越少了。

8
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, 可在程式一開始先算出它們的值。

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

10
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。

11
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是否成立即可。

12
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 ],
即可求出答案。

13
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;

14
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)),得解。

15
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 的值,
這樣就不會超過時間。

16
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的數則是有解,
其他情況則無解。

17
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。

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

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

19
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組。

20
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;
這樣問題應該就解決了。

頁: [1] 2 3 ... 12