信息學(xué)-集訓(xùn)隊(duì)作業(yè)

中國(guó)國(guó)家集訓(xùn)隊(duì)第一輪訓(xùn)編號(hào)程度a[i,j]=∑fk(si[x..y]=sky>=j)fk可重復(fù)計(jì)算sk在不同sib[i,j]表sij的目標(biāo)串的后綴時(shí)的最大價(jià)值，..sk[len(sk)+l-j..len(sk)]即si的前綴匹配sk的后綴）}O(N2★★挺有意思的動(dòng)態(tài)規(guī)來(lái)好像有AC了，我卻又在Test16RuntimeError某賽區(qū)有一題和這題差ZOJ過(guò)Circle2K個(gè)人站成一圈，為1..2K，輪流報(bào)數(shù)，每數(shù)到這題真沒(méi)什么思路，K這么小，枚舉可能可以（，CONST 分析：BFS或Dijkstra ofdistancesN使f*xx)2yy)2 AC但是這個(gè)算法在第13WA了。★★的題經(jīng)典的計(jì)展到空間似乎就不N-1條直線(xiàn)分割成了N2個(gè)角形，這些角形為1..N2，如果AB則它們之間標(biāo)記為“>”，否則★沒(méi)什么意ABBA相等就將A，又是計(jì)算 XORviaAND misterCBush醒來(lái)打算謀殺Sadam。Sadam有一些碉堡，Sadam移動(dòng)到一個(gè)相鄰的碉堡，Bush每個(gè)小時(shí)只能一個(gè)碉堡。問(wèn)是否存在一個(gè)方案使Sadam必死無(wú)疑。據(jù)hwdAC的算法：有兩種情況可以ESC：第一古怪的題我考慮得BestS是空間中點(diǎn)的集合，把S分成若干個(gè)不相交子集S1,S2,...,SK,|Si|≥2，使D最小。D是這樣計(jì)算的：★★ D2 2Xx2 XxSi D好像就是每個(gè)子集的方差之和吧。可以肯定的是要我覺(jué)得這是NP-完全的，不過(guò)題目中說(shuō)不需要求最優(yōu)D小于臨界值DkAC。所以可以考慮一下一些近似算法，比如隨機(jī)化貪if(++t>f[s])s++;時(shí)空均低于不知道有沒(méi)有更好分析：化搜索或遞推，狀態(tài)數(shù)為642★很一般的 S1，S2，求一個(gè)能匹配兩個(gè)正則分析：明顯的動(dòng)態(tài)規(guī)劃。f[i,j]S1i位S2j位的最短的字符串的長(zhǎng)度。狀態(tài)轉(zhuǎn)移方程 (S1[i]S2[j]f[i,j]max{f[i1,j]1,f[i,j1]}(S[i]'*',S[j]max{f[i,j1]1,f[i1,j]}(S1i] 1Mine一個(gè)人在ABN個(gè)，此人希望線(xiàn)，曲線(xiàn)上的任一點(diǎn)到任意的距離都不小于R。Rmax/2★這題應(yīng)該是023的煩的計(jì)算幾何……不過(guò)挺有終于有一題搜索Hacker's已知a1=(b*cXORab1=(a*cXORb,c1=(a*b)XORc。輸入a1,b1,c1，求a,b,c★太有意思沒(méi)做過(guò)這！Nim算法：把每堆石頭的數(shù)目進(jìn)行異或操作，若結(jié)果為經(jīng)典的博StoneStoneGameO(1) GiveAway4a,b,c,d個(gè)石頭，兩人輪流從算法：(aXORbXORcXORdXORord(aORbORcORd<=1))=0則后拿的必勝，否則先拿的必勝。這是hwd告訴，我也不太明白為這樣。我覺(jué)得前面aXORbXORcXORd100的判斷方