07 2012 檔案
hdu 3683 極大極小過程 + 搜索
摘要: 在一個(gè)15*15的棋盤上下五子棋。3步之內(nèi)誰能贏。
閱讀全文
hdu 4126 最小生成樹 + 樹形DP + 優(yōu)先級(jí)隊(duì)列
摘要: 求N<3,000個(gè)點(diǎn)的稠密圖的最小生成樹的每條邊的最佳替換邊。
閱讀全文
hdu 4305 計(jì)算幾何 + 高斯消元求行列式 + 逆元
摘要: 平面上有N<300個(gè)點(diǎn)。每個(gè)兩個(gè)點(diǎn)如果距離小于R且之間沒有共線的另一個(gè)點(diǎn)，則這兩點(diǎn)之間有一條邊。求這個(gè)圖的生成樹的個(gè)數(shù)mod 10007。
閱讀全文
codeforces 212C 遞推
摘要: 有一個(gè)長(zhǎng)度為100的只含A和B的環(huán)行串。如果這個(gè)串含有AB，那么就變?yōu)锽A。 給一個(gè)串，問有多少種串可以變?yōu)檫@個(gè)串。
閱讀全文
hdu 3721 樹形DP
摘要: 一顆有N個(gè)節(jié)點(diǎn)(N<2,500)的帶權(quán)樹。現(xiàn)在割去一條邊，加到其他節(jié)點(diǎn)上，并保證也是一棵樹。問最小的直徑是多少？
閱讀全文
codeforces 204E 后綴數(shù)組+線段樹
摘要: 給N個(gè)串(N<100,000)，總長(zhǎng)不超過100,000。對(duì)于每個(gè)串，求至少在其他k個(gè)串中作為子串出現(xiàn)過的子串個(gè)數(shù)。
閱讀全文
codeforces #130 div2
摘要: codeforces #130 div2
閱讀全文
hdu 4117 AC自動(dòng)機(jī) + DP
摘要: 有N(N<20,000)個(gè)只含有小寫字母的字符串，總長(zhǎng)不超過300,000，每個(gè)字符串Si有權(quán)值Vi。現(xiàn)在讓你刪除一些字符串，滿足對(duì)于相鄰的串，前一個(gè)串是后一個(gè)串的子串。求最大權(quán)值和。
閱讀全文
codeforces 212B 狀態(tài)壓縮+離散化
摘要: 給一個(gè)僅含有小寫英文字母的字符串s，(strlen(s)<1,000,000)。詢問k次(k<10,000)。每次給出一個(gè)字母集合S，問含有且僅含有S集合中的字母的極大子串有多少個(gè)？
閱讀全文
codeforces 212E 樹形DP + 背包
摘要: 題目描述：
一棵N(N<5,000)個(gè)節(jié)點(diǎn)的樹，染兩種顏色，不同顏色不能相鄰且要給盡可能多的節(jié)點(diǎn)染色。求顏色A和顏色B可能的染色節(jié)點(diǎn)個(gè)數(shù)。
閱讀全文
codeforces 204D 動(dòng)態(tài)規(guī)劃
摘要: 有一個(gè)長(zhǎng)度為n(n<1,000,000)的字符串A。有三種字符，'B','W','X'。現(xiàn)在讓你將所有的X要么變成B，要么變成W，構(gòu)造字符串，使得其存在a<=b
閱讀全文
codeforces 200A 并查集
摘要: 給一個(gè)大小為n*m(n,m < 2000)的棋盤，有k(K<100,000)次操作。每次在位置（x,y）加入一個(gè)點(diǎn)，如果x,y已經(jīng)有點(diǎn)了，那么加入的點(diǎn)需要滿足：
1. 與x,y的曼哈頓距離最近。
2. 如果滿足條件1的點(diǎn)有多個(gè)，那么要求x最小。
3. 如果滿足條件2的點(diǎn)有多個(gè)，那么要求y最小。
閱讀全文
hdu 4008 樹形DP + LCA
摘要: 題目描述：
給一顆結(jié)點(diǎn)數(shù)為(100,000)的樹，最多詢問100,000次。每次詢問對(duì)兩個(gè)結(jié)點(diǎn)X,Y，以X為根，Y的最小標(biāo)號(hào)的孩子，Y的最小標(biāo)號(hào)的后代。
閱讀全文
codeforces #129 div1
摘要: codeforces #129 div1
閱讀全文
hdu 4125 線段樹 + KMP
摘要: 給一個(gè)長(zhǎng)度為N(N<600,000)的序列，讓你按順序插入靜態(tài)二叉樹。然后DFS出一個(gè)序列，問某個(gè)模式串在這個(gè)序列中出現(xiàn)了幾次？
閱讀全文