COCI 2012/2013 Round #1

Brief description:

Problem A. Dom

… 刪除一個字元串中的所有的 「CAMBRIDGE」 中的字元。。

import re
print re.sub("[CAMBRIDGE]","",raw_input())
Problem B. F7

。。n 個人參加一個比賽,(沒有並列。。
。。其中第 i 名 獲得 n-i+1 分。。
現在給定 n 個人一個初始分數,問最後有多少人可能獲得總分第一?(並列第一也可以。。

I = lambda: map(int, raw_input().split())

n = input() 
a = [0] * n
for i in range(0, n):
	a[i] = input()

a.sort()

i = n		
best = 0

while i>=0:	
	i -= 1
	if (a[i]+n < best): break	
	if (a[i]+n-i > best): best = a[i]+n-i
print n-i-1	

(貪心。。Python 後三個點超時。。

。。。

Problem C. Koncert

。。。我這個蠢飛了啊。這個簡直就是 bug 啊。
。。。進去會場裡面還能帶票出來給別人。跪跪跪。。。
。模擬。。

Problem D. Ljubomora

。。n 個人 m 堆石子,第 i 堆石子有 ai 個。。現在要把這 m 堆石子分給這 n
個人,要求每個人拿到的石子必須來自同一堆。。。求方案使得拿到石子最多的人拿到的最少。。
二分答案判定。。(假設答案為 x,若滿足  \sum_{i=1}^n \lceil \frac{a_i}{x} \rceil \leq n 則合法。。

Problem E. Snaga

定義 K(x) 為最小的不能整除 x 的數,定義 strength(x) = strength(K(x)) + 1 (  strength(2) = 0  。。
 \sum_{i=A}^B strength(i)

Problem F. Mars

要求構造一個 2^k 階的排列。。
滿足以此排列構造的滿二叉樹的每個結點,(每個結點是一個集合,以 ai 位置的數為葉子,然後每個結點由其左右子樹合併而成。。
。都是一段連續的數字。。已知每對數字之間存在一個斥力。。
最小化排列相鄰數字之間的斥力和。。。

Analysis:

Problem E. Snaga

注意到 K(x) 的值很小(大概不超過 100 。。。
於是暴力即可。。

Problem F. Mars

F[i][j] 表示前 i 個數,最後一個是 j。我們注意到能轉移到這個狀態的狀態,時一個長度為 low_bit(i) 的區間。
注意到我們可以用神位運算直接得到這個區間。。這樣暴力的話複雜度就是 O(n^2logn) 。。。。

const int N = 1029;

int f[N][N], a[N][N];
int n, z;

int main(){

    n = _1(RD()); REP_2(i, j, n, n) RD(a[i][j]);

    FLC(f, 0x3f), RST(f[0]); FOR(i, 1, n) REP(j, n){
        int s = (j - j % low_bit(i)) ^ low_bit(i), e = s + low_bit(i);
        FOR(k, s, e) checkMin(f[i][j], f[i-1][k] + a[j][k]);
    }

    OT(*min_element(f[n-1], f[n-1]+n));
}

。動態規劃,位運算。。

External link:

http://evaluator.hsin.hr/index.php
http://www.codeforces.com/blog/entry/5585