109學年度北二區資訊學科能力競賽

發表於 更新於 Disqus：

前言

這次打得跟去年燒雞比起來好多了><
以下題目可能會有雷

題目

上午場(三小時 5題 每題20分)

分數100/100

pA 20/20

給兩個int範圍內的整數$a, b$，求有多少位元是$a$沒有$b$有的?

基本上就考位元運算，
差不多這樣就能拿滿20。

1
2
3
4
5
6
7
8
signed main() { EmiliaMyWife
	int a, b, c = 0;
	cin >> a >> b;
	for(int i = 0; i < 40; i++)
		if(!(a >> i & 1) && (b >> i & 1))
			c++;
	cout << c << '\n';
}

pB 20/20

給一個數字$N$，
對於一個tuple$(n1, n2, n3, n4, n5)$ $(1 \le n_1 < n_2 < n_3 < n_4 < n_5\le 30)$
定義以下數字:
a1=…
a2=…
a3=…
a4=…
a5=…
…代表運算細節，我忘了，不過只是拿那五個n來加減乘除。
求滿足a1+a2+a3+a4+a5=N的tuple數量的三次方
但如果數量為0，請輸出$N$乘三加上五

巢狀迴圈…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
signed main() { EmiliaMyWife
	int n, c = 0;
	cin >> n;
	for(int n1 = 1; n1 <= 30; n1++) {
		for(int n2 = n1 + 1; n2 <= 30; n2++) {
			for(int n3 = n2 + 1; n3 <= 30; n3++) {
				for(int n4 = n3 + 1; n4 <= 30; n4++) {
					for(int n5 = n4 + 1; n5 <= 30; n5++) {
						int a1 = ...;
						int a2 = ...;
						int a3 = ...;
						int a4 = ...;
						int a5 = ...;
						if(a1 + a2 + a3 + a4 + a5 == n)
							c++;
					}
				}
			}
		}
	}
	if(c)
		cout << c * c * c << '\n';
	else
		cout << n * 3 + 5 << '\n';
}

pC 20/20

給一個凸多邊形上的$n$個頂點(不一定照順序)，再給$a, b$，求$max(ax+by), (x, y)\in \mathbb{Z}, (x,y)$在多邊形內，且還要輸出(x, y)。
$n\le 20, -10^5\le x_i,y_i\le 10^5$

這題我是唬爛過去的，基本就是可以發現最佳解一定在凸包的最外圍(邊上or點上)，所以就直接模擬每個方向爬行(超級唬爛)。
聽到比較好的做法是枚舉x找上下兩點，更新答案。
p.s.直接代入所有頂點可以拿12分www

pD 20/20

原題目好多廢話(? 看不太懂
但總之就是：

給四條長度不超過18的有序且無重複序列，序列中每個數字為1到25的整數。
然後給$n, h$。
問有多少序列滿足長度為$n$且為至少$h$條序列的子序列。

因為數字只有25種，所以直接$2^{25}$爆搜，可以先把序列用位元存起來加快檢查速度。

pE 20/20

給一個只有加和乘的數學算式(字串長度不超過1500，所以數字為int範圍內的正整數)，問答案的後五位數為多少。

我是直接把字串輸入進來再手動切割，用stack存最後的數字來處理乘法，過程不斷%$10^5$，後來才知道可以直接交給cin，輸入好難ww。

不過我一開始打錯字，變成%$10^4$，丟上去拿了16分，後來發現後改成$10^5$，結果變8分，把bug找出來後再丟還是8分，此時我覺得很怪，所以把修正bug後的版本再改成%$10^4$，然後AC…

用提問系統跟他們反映這件事也只得到no comment，出來後的確有很多人被這題給卡爛，雖然後來有rejudge，但損失不輕。我也算運氣真好(X

下午場(2小時 3題 1題20分)

得分36/60，整個大燒雞。

pA 12/20

給一個最高次為100的多項式函數，再給定$x, M(M < 10)$，求$f(x)$的後$M$位(係數，x皆在int範圍)。
不足$M$位的地方要補0，如果函數值為負，那就得輸出負的值，但要把負號拿掉。
比如:答案為302，$M=2$，則輸出02。 答案為-205，$M=2$，則輸出05(不是95!)。

因為我不會判斷正負數，所以只輸出正的然後拿12分。
原本以為要大數，出來後聽到一個做法是從高次往低次做，當前數字太大就可斷言正負，整個orz。

pB 20/20

有$n$個消毒劑，消毒劑剛噴灑時會有係數$x$，且過了$t$時間後係數會變為$x-t$，給：

每個消毒劑的噴灑時間和係數。
$y$，代表當前時間為第一次噴灑後過$y$時間。
問當前時間下所有消毒劑的係數總和為多少。

數字範圍都沒給，不過其實直接$\mathcal{O}(n)$照做然後就能過了(?

有個小陷阱就是第一次噴灑的時間不一定是0，所以不能直接拿$y$做，但是範測卻剛好都是0。

pC 4/20

考慮某RSA加密，過程如下：
先選定兩個質數$p, q$，令$N=pq$。

再找出兩個整數$e, d$，滿足$ed\equiv 1\mod (p-1)(q-1)$

之後會有公開金鑰$N, e$，私密金鑰$N, d$。

如果要加密的訊息為$m$，加密後為$c$，則有以下關係式
$$c=m^e\mod N$$
$$m=c^d\mod N$$
解密時，如果我們留著$p,q$，且定義$m_p=c^d\mod p, m_q=c^d\mod q$，那就可以利用中國剩餘定理解出$m$。

而今天我們的$mp, mq$其中一個是錯誤的，想當然算出來的$m’$也會是錯誤的，給定$N, m’, e, c$，請還原出$p, q$。

$N$為64位元範圍內的正整數。

沒想法，我直接用根號對$N$做質因數分解拿4分，後來去問AC的人，她居然是用Pollard’s rho對$N$做質因數分解ww。
結果還是討論不出要怎麼正常使用另外三個數字，甚至不知道題目說的中國剩餘定理要怎麼做。

正文

最後是以136/160，rank 5收尾。
雖然我覺得一整個就是運氣ww(我沒被pE的錯誤測資卡到，且pC的唬爛作法直接過)。
題目部分是真的很糟糕，根本沒考什麼演算法或資結，就只是數學和爆搜，然後下午的第一三題變成決勝點= =; 怪題。
雖然去年燒雞燒超慘，但那題目寫起來才好玩QQ
但至少高中的競賽之旅應該…算踏上正軌了吧(?