A
六邊形網(wǎng)格組成一個(gè)六邊形,邊長為a,b,c,a,b,c.(a,b,c<100)
問一共有多少個(gè)六邊形
算法分析:
不斷的消去最外圍的六邊形, 直到有一個(gè)邊是1為止. 復(fù)雜度O(n).
代碼:
http://codeforces.com/contest/216/submission/2007011
B
給一個(gè)點(diǎn)數(shù)為100的無向圖,每個(gè)點(diǎn)度數(shù)最多是2. 問最少消去多少個(gè)點(diǎn),可以使這個(gè)圖2-染色.
算法分析:
每個(gè)聯(lián)通塊不是鏈就是環(huán), 如果是偶數(shù)的話可能可以2染色,如果是奇環(huán)一定要去掉一個(gè)才能2染色,如果是奇鏈的話... 統(tǒng)計(jì)一下奇鏈的個(gè)數(shù).
代碼:
http://codeforces.com/contest/216/submission/2008126
C
題目描述太奇葩...
算法分析:
貪心求解, 由于點(diǎn)數(shù)比較小,覆蓋的時(shí)候直接暴力就好了.
我還是很腦慘的寫了個(gè)線段樹優(yōu)化到nlogn了,可惜由于末尾判斷錯(cuò)誤寫掛了...
代碼:
http://codeforces.com/contest/216/submission/2013405D
題目描述過于奇葩...
算法分析:
把所有的bridge用vector存起來然后二分查找就可以了.
太奇葩了,C和D唯一的難點(diǎn)就在理解題意???
代碼:
http://codeforces.com/contest/216/submission/2015729E
給一個(gè)長度為n的k進(jìn)制數(shù)(n<100,000, k<1,000,000,000),問這個(gè)序列有多少子串的數(shù)字根等于 m.
算法分析:
k進(jìn)制數(shù)x的數(shù)字根等于x mod (k-1) .
預(yù)處理出前綴和mod(k-1)的值,統(tǒng)計(jì)有多少對(duì)值做差等于m就可以了.
統(tǒng)計(jì)的過程很簡單, 可以用map, 可以離散化之后直接統(tǒng)計(jì)...
注意m = 0和m = k-1的情況, 還要注意最后減去所有的0...
代碼:
http://codeforces.com/contest/216/submission/2013341
posted on 2012-08-15 16:25
西月弦 閱讀(269)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
解題報(bào)告