void (*signal(int, void (*fp)(int)))(int);
Question:
What is 'signal' ?
#include <cstdio>
using namespace std;
void f(int);
void (*pf)(int), (*qf)(int);
void (*hf(int, void(*)(int)))(int);
typedef void (*sighandler_t)(int);
sighandler_t signal(int, sighandler_t);
void f(int a)
{
printf("void f(int %d)\n", a);
}
void (*hf(int _i, void(*_pf)(int)))(int)
{
printf("_i = %d\n", _i);
_pf(_i);
return _pf;
}
sighandler_t signal(int signum, sighandler_t sighandler)
{
printf("signal num = %d\n", signum);
sighandler(signum);
return sighandler;
}
int main()
{
pf = &f;
qf = hf(12, pf);
qf(23);
signal(54, f);
return 0;
}
void (*signal(int, void (*)(int)))(int);
Answer:signal is a function, passing {
an int and
a pointer [to a function passing an int returning nothing (void)]},
returning {
a pointer [to a function passing an int returning nothing (void)]}.
08合肥網(wǎng)賽某題。
http://poj.org/problem?id=3697題意是問在N個(gè)點(diǎn)的完全圖(N<=10,000)中刪掉M(M<=1,000,000)條邊后, 還有多少個(gè)點(diǎn)與頂點(diǎn)1連通(頂點(diǎn)編號(hào)從1開始).
暴力BFS+HASH+各種WS優(yōu)化的方法很多, 但是出題人原意應(yīng)該是O(M)的做法吧... 下面是我YY出來的O(M)的做法.
只考慮這M條待刪邊, 能得到什么信息呢? 可以先從點(diǎn)1入手. 掃一遍與1鄰接的點(diǎn), 那么剩下沒被掃到的點(diǎn)肯定與1是連通的. 而被掃到的點(diǎn)是"有可能"與1不連通. 所以就把那些肯定與1連通的點(diǎn)做標(biāo)記. 從這些確定連通的點(diǎn)中任選一個(gè)u, 再掃描它的所有鄰接點(diǎn). 這之后, 如果一個(gè)點(diǎn)一共被掃了2次, 那么它才"有可能"與1不連通, 其它少于2次的點(diǎn)肯定與1連通, 因?yàn)樗蛘吲c1連通, 或者與u連通, 而u是已知與1連通的. 這樣再拿出一個(gè)已經(jīng)確定連通的點(diǎn), 掃描它的鄰接點(diǎn), 把被掃過次數(shù)<3的又標(biāo)記為已連通......
經(jīng)過上面的YY, 算法基本上就出來了:
把已知肯定與1連通的點(diǎn)集稱為S, 剩下不確定的為T. 一開始, S中只有1這一個(gè)點(diǎn), 其它點(diǎn)都在T中. 每個(gè)點(diǎn)有個(gè)計(jì)數(shù)器, 記錄自己被掃了多少次.
1) 從S中取出一個(gè)沒處理過的點(diǎn), 把它標(biāo)記為已處理, 并遍歷它的所有鄰接點(diǎn), 被遍歷到的點(diǎn)的計(jì)數(shù)器都+1.
2) T中所有"計(jì)數(shù)<S中已處理點(diǎn)個(gè)數(shù)"的, 都可以確定是連通的, 把它們從T中刪除, 加入S中.
3) 重復(fù)1), 直到S中所有點(diǎn)都處理完.
這時(shí), S中的點(diǎn)就是與1連通的, T中剩下的就是不連通的.
復(fù)雜度分析:
讀入邊和掃描邊都是O(M)的.
S集可以用隊(duì)列維護(hù), 總共O(N).
T集的維護(hù): 每一輪都要掃一遍當(dāng)前的T, 把所有計(jì)數(shù)小的刪掉, 放進(jìn)S中. 這樣, 這一步的總復(fù)雜度就是O(sigma(T)), 會(huì)不會(huì)到達(dá)O(N^2)呢? 實(shí)際上是不會(huì)的. 因?yàn)橐粭l邊最多只會(huì)使一個(gè)頂點(diǎn)的計(jì)數(shù)+1, 因此每一輪還剩在T中的點(diǎn)數(shù)不會(huì)超過這一輪遍歷過的邊數(shù). 這樣, 所有回合的sigma(T)就肯定不會(huì)超過總邊數(shù). 因此這里總共也是O(M)的. 嚴(yán)格來說算上第1輪有N-1個(gè)點(diǎn), 也是O(M+N).
這樣總的復(fù)雜度就是O(M)了.
不過這個(gè)算法讀入用scanf時(shí), g++跑了1000+ms, 改成getchar才到200+ms的. 不知道排前面的神們是不是有更NB的算法.
代碼:
1 #include
2 #include
3 #include
4 #include
5 #include
6 using namespace std;
7
8 const int MAXN = 10010;
9 const int MAXM = 1000010;
10
11 struct Edge {
12 int v, next;
13 }edg[MAXM*2];
14 int ecnt, gg[MAXN];
15 bool yes[MAXN];
16 int que[MAXN], pq, sq, cnt[MAXN], vt[MAXN], nt;
17 int N, M;
18
19 inline int getnextint()
20 {
21 int r = 0;
22 char c;
23 while(!isdigit(c=getchar()));
24 do{
25 r = r*10 + c-'0';
26 } while(isdigit(c=getchar()));
27 return r;
28 }
29
30 inline void addedge(int u , int v)
31 {
32 edg[ecnt].v = v; edg[ecnt].next = gg[u], gg[u] = ecnt++;
33 edg[ecnt].v = u; edg[ecnt].next = gg[v], gg[v] = ecnt++;
34 }
35
36 int main()
37 {
38 int cas = 0;
39 while(~scanf("%d%d", &N, &M) && !(N==0 && M==0)){
40
41 ecnt = 0;
42 for(int i = 0; i < N; i++){
43 gg[i] = -1;
44 yes[i] = i==0 ? true : false;
45 cnt[i] = 0;
46 vt[i] = i+1;
47 }
48 nt = N-1;
49
50 for(int i = 0; i < M; i++){
51 int u = getnextint();
52 int v = getnextint();
53 addedge(--u, --v);
54 }
55
56 pq = sq = 0;
57 que[sq++] = 0;
58 yes[0] = true;
59
60 while(pq != sq) {
61 int u = que[pq++];
62 for(int e = gg[u]; e >= 0; e = edg[e].next) {
63 if(!yes[edg[e].v])
64 cnt[edg[e].v]++;
65 }
66 for(int i = 0; i < nt; i++) {
67 while(i < nt && cnt[vt[i]] < pq) {
68 yes[vt[i]] = true;
69 que[sq++] = vt[i];
70 if(i < --nt)
71 vt[i] = vt[nt];
72 }
73 }
74 }
75 printf("Case %d: %d\n", ++cas, sq-1);
76
77 }
78 return 0;
79 }
250pt MagicalGirlLevelOneDivOne某神在(0,0)處, 需要走到(x,y)處(0<x,y<=10^9), 他只能按類似馬跳的方式走, 即, 給出一個(gè)n, 他可以從(a,b)走到(a-1,b-n) (a+1,b-n) (a-1,b+n) (a+1,b+n) (a-n,b-1) (a+n,b-1) (a-n,b+1) (a+n, b+1) 中的一個(gè).現(xiàn)在給出50個(gè)不同的n[1..50], 他可以以任意的n[i]方式走, 每種方式的使用次數(shù)不限. 問能否走到目的地(x,y).
很明顯, 此神可以沿任意方向2步2步的走, 即先走個(gè)(+1,-n), 再走個(gè)(+1,+n). 所以能否到終點(diǎn), 只與奇偶性有關(guān).
經(jīng)過一陣分類討論可知:
1) 如果x+y=0(mod 2), 則YES.
2) 如果x+y=1(mod 2), 且n[i]中有偶數(shù), 則YES.
3) 否則NO.
[雜]
600pt MagicalGirlLevelTwoDivOne
給一個(gè)H*W(1<=H,W<=50)的矩陣A, 每一位上已經(jīng)有一個(gè)1~9的數(shù)字, 或者是個(gè)'.', 在'.'處可以填上任意1~9的數(shù)字. 再給出n和m(1<=n<=min{10,H}, 1<=m<=min{10,W}). 問一共有多少種填'?'的方法, 使得整個(gè)矩陣滿足:
對(duì)任意的r和c, 以(r,c)開始的水平方向上連續(xù)m個(gè)數(shù)之和是奇數(shù);
對(duì)任意的r和c, 以(r,c)開始的垂直方向上連續(xù)n個(gè)數(shù)之和是奇數(shù).
首先要注意到一個(gè)性質(zhì): 對(duì)任意r和c有 A[r,c]與A[r+n,c]的奇偶性相同. 很顯然, 因?yàn)橐獫M足A[r,c]+A[r+1,c]+...+A[r+n-1,c]與A[r+1,c]+...+A[r+n-1,c]+A[r+n,c]的奇偶性相同, 都是奇數(shù). 列上同樣有A[r,c]與A[r,c+m]奇偶性相同.
因此在一行上, 只用記錄n位的奇偶狀態(tài), 列上同理.
這樣,所有的(r+pn,c+qm)都能合并成同一個(gè)點(diǎn), 且只有兩種狀態(tài): 奇和偶. 合并后該點(diǎn)為奇(或偶)的方法數(shù), 等于組成它的所有點(diǎn)方法數(shù)之積. 最后整個(gè)矩陣合并壓縮成一個(gè)n*m的矩陣, 就可以用狀態(tài)DP來搞, 求每行每列之和都為奇的方法數(shù). dp[n][1<<m], 前n行, 每一列和的奇偶性對(duì)應(yīng)bit為0或1. O(1<<m)的轉(zhuǎn)移復(fù)雜度, 轉(zhuǎn)移時(shí)要注意該行狀態(tài)1有奇數(shù)個(gè).
覺得是道很好的題, 狀態(tài)設(shè)計(jì)很巧妙...
[狀態(tài)DP 狀態(tài)壓縮設(shè)計(jì)]
900pt MagicalGirlLevelThreeDivOne
某神給出K(K<=50)個(gè)01串, 每個(gè)串的長度不超過50. 用這些串組成新的串放到數(shù)組A[]里. 如果i<K, 則A[i]為給出的第i個(gè)串. 否則A[i] = A[i-1] + A[i-K-1] + A[i-2*K-1] + ... + A[i-p*K-1], 其中p是使i-p*K-1>=0的最大整數(shù). 現(xiàn)在此神給出n, lo, hi, 要你求A[n]的子串A[n][lo...hi]中有多少個(gè)連續(xù)的1. 0<=n<=10^15, 0<=hi<= min{A[n]的長度, 10^15}, 0<=lo<=hi. 所有計(jì)數(shù)以0開始.
首先隨便打個(gè)表或者手推一下化簡A[i]的遞推式, 可以發(fā)現(xiàn)當(dāng)i>=2*K時(shí), A[i] = A[i-1] + (A[i-K-1] + ... A[i-p*K-1]) =
A[i-1] + A[i-K], 而K<=50. 所以A[i]的長度關(guān)于i是指數(shù)增長的, 50log(10^15)可能夠用(嚴(yán)格證明不太會(huì), 求指導(dǎo)#.#).
因此其實(shí)n<=10^15范圍是坑爹的, hi不會(huì)超過A[10^4]的長度. 而這些串的前綴都是一樣的, 所以A[n][lo..hi]其實(shí)與A[10^4][lo..hi]相同.
這樣便可直接利用A[i] = A[i-1] + A[i-K]的關(guān)系分治.
和用線段樹求最長連續(xù)1串的思想差不多: 每個(gè)結(jié)點(diǎn)的狀態(tài)變量是(id,lo,hi), 存放A[id][lo..hi]的最優(yōu)解. 除了存放當(dāng)前段的最大長度max外, 為了能合并子區(qū)間, 還要記錄當(dāng)前區(qū)間從左端開始連續(xù)1的個(gè)數(shù)sl, 和從右端開始連續(xù)1的個(gè)數(shù)sr. 剩下的工作與線段樹無異, 假設(shè)要求(id, lo, hi)的(max, sl, sr):
對(duì)于A[id], 它的左兒子就是A[id-1], 右兒子是A[id-K].
1)如果id<2*K, 直接暴力.
2)如果lo>=len[id-1](類似于線段樹中的查詢區(qū)間完全落在右兒子), 則遞歸查詢(id-K, lo-len[id-1], hi-len[id-1]).
3)如果hi<len[id-1], 則遞歸查詢(id-1, lo, hi).
4)否則兩個(gè)兒子都要查詢, 并根據(jù)返回的結(jié)果求當(dāng)前區(qū)間的結(jié)果.
分治思想很強(qiáng)大, 用map寫的"線段樹"很YD, 偶依然蒻爆了.
[分治 復(fù)雜度分析]
500pt Perfect Memory
題意: 某神在M*N(1<=M, N<=50, M*N為偶數(shù))的格子上玩對(duì)對(duì)碰: 每個(gè)格子都有個(gè)隱藏的圖形. 此神一次行動(dòng)翻開2個(gè), 如果相同, 就成功消去這2個(gè)格子. 如果不相同, 那這2個(gè)格子又恢復(fù)隱藏狀態(tài). 但是此神記憶力很NB, 能記住所有翻開過的格子是什么圖形. 還有重要的一點(diǎn), 他一次行動(dòng)時(shí), 是先翻開1個(gè)格子, 知道它的圖形之后, 再?zèng)Q定怎么翻第2個(gè)格子, 而不是兩個(gè)格子同時(shí)翻開. 問此神把所有格子都消去, 需要消耗的行動(dòng)次數(shù)的期望.
容易想到期望與翻格子的位置無關(guān). 有關(guān)的量是: 當(dāng)前還有多少對(duì)圖形沒被消去. 其中有多少對(duì)圖形已經(jīng)知道其中一個(gè)的位置了. so, dp[i][j], i為前者, j為后者. 一次行動(dòng)中, 第1個(gè)格子肯定翻之前沒翻過的(一共有2i-j個(gè), 記為s), 除非已經(jīng)知道某1對(duì)的位置, 直接把2個(gè)都翻出來消掉. 所以轉(zhuǎn)移有幾種情況:
1) 從s中翻出1個(gè)新圖形. 從剩下s-1中翻出了相同圖形, 消除. 這樣的概率是2(i-j)/s * 1/(s-1), 轉(zhuǎn)移到dp[i-1][j].
2) 從s中翻出1個(gè)新圖形. 從剩下s-1中又翻出新圖形, 這樣就多了2種已知圖形. 概率是2(i-j)/s * 2(i-j-1)/(s-1), 轉(zhuǎn)移到dp[i][j+2].
3) 從s中翻出1個(gè)新圖形. 從剩下s-1中翻出了之前j個(gè)已知圖形中的一個(gè). 這樣, 下一次就可以消耗一次行動(dòng)把那對(duì)已知圖形消去, 轉(zhuǎn)移到dp[i-1][j], 概率是2(i-j)/s * j/(s-1).
4) 從s中翻出1個(gè)已知圖形. 直接翻出與它配對(duì)的消去. 轉(zhuǎn)移到dp[i-1][j-1], 概率是j/s * 1.
所以 dp[i][j] = p1*(dp[i-1][j]+1) + p2*(dp[i][j+2]+1) + p3*(dp[i-1][j]+2) + p4*(dp[i-1][j-1]+1).
其中2)的條件是i>=j+2, 4)的條件j>=1. 邊界dp[i][i] = i. 最后dp[M*N][0]即為所求.
[概率 期望 DP]
1000pt Reflections題意: 某神在三維空間中玩一個(gè)游戲, 空間中有N個(gè)(N<=20)平面, 每個(gè)平面都垂直于某個(gè)坐標(biāo)軸, 并且與該坐標(biāo)軸交于整點(diǎn). 此神從(0,0,0)處出發(fā), 想去(X,Y,Z)處. 現(xiàn)在他每行動(dòng)一次可以做如下移動(dòng):
1) 走到與他相鄰的1個(gè)整點(diǎn)上, 即(x+1, y, z) (x-1, y, z) (x, y+1, z) (x, y-1, z) (x, y, z+1) (x, y, z-1)中的一個(gè).
2) 神一次行動(dòng)可以利用一個(gè)平面, 移動(dòng)到關(guān)于這個(gè)平面對(duì)稱的點(diǎn)處. 每個(gè)平面在整個(gè)游戲過程中至多只能利用一次.
問此神到達(dá)終點(diǎn)花費(fèi)的最少行動(dòng)次數(shù).
易知三個(gè)方向是不相關(guān)的. 所以只用先考慮一維的情形.
首先要想到, 走路和反射交替, 是等效于先反射完了再一口氣走到終點(diǎn)的. 因?yàn)樵诜瓷渲暗淖邉?dòng), 不會(huì)被反射動(dòng)作放大. 反射前移動(dòng)多少步, 經(jīng)過若干次反射后所到達(dá)的位置, 與不移動(dòng)直接反射到達(dá)的位置, 相差正好是移動(dòng)的步數(shù).
所以可以轉(zhuǎn)化為先反射若干次, 再行走到終點(diǎn). 現(xiàn)在就要推出反射到達(dá)的位置公式.
假設(shè)每個(gè)反射軸的坐標(biāo)依次是x[1], x[2], ..., x[n], 神經(jīng)過第k次反射后的位置是p[k].
容易推出, p[1] = 2x[1], p[2] = p[1] + 2(x[2]-x[1]) = 2x[2] - 2x[1], ... p[k] = 2x[k]-2x[k-1]+2x[k-2]-...+2*(-1)^(k-1)x[1].
這是很規(guī)則的正負(fù)交替求和, 正項(xiàng)數(shù)等于負(fù)項(xiàng)數(shù), 或者比負(fù)項(xiàng)數(shù)多1.
到此問題轉(zhuǎn)化得很清晰了: 在20個(gè)數(shù)中選出k個(gè)數(shù)作為正項(xiàng), k(或k-1)個(gè)數(shù)作為負(fù)項(xiàng), 每個(gè)數(shù)至多被選1次. 該方案的總行動(dòng)次數(shù)是選出的個(gè)數(shù)(即做反射的總次數(shù)), 加上這些項(xiàng)之和到終點(diǎn)的距離(即最后一路走過去).
選數(shù)要降低復(fù)雜度, 可以把20個(gè)數(shù)分成兩個(gè)集合, 每邊10個(gè)數(shù), 先各自生成2^10個(gè)和. 兩邊分別排序后, 從小到大枚舉左邊的, 記一個(gè)指針從大到小掃右邊的.
[數(shù)學(xué) 分治]
本文純屬YY……
今天多校聯(lián)合訓(xùn)練三的C題，
http://acm.hdu.edu.cn/showproblem.php?pid=3861，題意歸結(jié)起來是在一個(gè)有向圖中求最小路徑覆蓋，也就是用盡量少的鏈去覆蓋整個(gè)圖，每個(gè)頂點(diǎn)必須屬于且只能屬于一條鏈。但是題意并未說明原圖無環(huán)。標(biāo)程解法是強(qiáng)連通分量縮點(diǎn)，再求有向無環(huán)圖的最小路徑覆蓋。反例是：1->2,2->3,4->5,5->6,2->5,5->2。正解是2，123一組，456一組。
因?yàn)槭且舐窂綌?shù)最小，所以YY了一個(gè)上下界最小流的做法。構(gòu)圖是將原來的點(diǎn)A0拆成兩個(gè)，A和A'。從A到A'連一條邊，下界和上界都為1。所有原來A0的出邊，都從A'出去，下界0，上界1.所有原來A0的入邊，都指向A。新建一個(gè)源點(diǎn)S，一個(gè)匯點(diǎn)T。從S到每個(gè)點(diǎn)A連一條邊，下界0，上界1。從每個(gè)A'到T連一條邊，下界0，上界1。
對(duì)這個(gè)新圖求最小流，即為原題所求。
YY的證明：
A->A'，限制了這個(gè)點(diǎn)必須經(jīng)過一次。這條邊上的流量有兩個(gè)來源：其它的點(diǎn)B'，或者源點(diǎn)S，前者說明A和B在同一條鏈中，B是A的前驅(qū)，后者說明A是鏈的起點(diǎn)。同樣，這個(gè)流量有兩個(gè)去處：其它的點(diǎn)C'，或者匯點(diǎn)T，前者說明A和C在同一條鏈中，C是A的后繼，后者說明A是鏈的終點(diǎn)。
到達(dá)匯的每1單位流量，意味著一條鏈的終結(jié)。所以最小流就能讓鏈數(shù)最少。
YY完畢，歡迎開炮……
ps. 理論上說，以上方法肯定是錯(cuò)的。要不然求Hamiltion通路就不是NP了＠。＠
500pt FiveHundredEleven
給出N(N<=50)個(gè)不小于0且不大于511的整數(shù). 開始時(shí)寄存器為0, 兩人輪流選取一個(gè)數(shù), 與寄存器的值OR, 把結(jié)果覆蓋寫入寄存器. 數(shù)不能重復(fù)使用. 如果某人操作之后寄存器的值為511, 或者輪到某人時(shí)數(shù)都取完了, 那么這個(gè)人就算負(fù). 問先手是否有必勝策略.
容易想到2^9這一維, 記錄當(dāng)前每一位的0/1狀態(tài). 實(shí)際上, 不需要記錄當(dāng)前已經(jīng)選過哪些數(shù), 而只用記錄已經(jīng)選了幾個(gè)數(shù), 再由當(dāng)前的0/1態(tài), 就能推算出哪些數(shù)沒選過. 有些數(shù)x滿足x|now != x, 這些數(shù)肯定沒選過. 而對(duì)那些x|now == x的數(shù), 不必知道它具體的值, 因?yàn)樗鼘?duì)后續(xù)操作的影響都一樣, 就是延緩一步, 把局面原封不動(dòng)地丟給對(duì)方. 所以只需知道當(dāng)前還有多少個(gè)這樣的x沒被使用過, 這個(gè)值也能由上面的信息得到.
這樣就是一個(gè)類似極大極小的必勝必?cái)B(tài)記憶化搜索.
狀態(tài)為dp[1<<9][N], 轉(zhuǎn)移為N.
[狀態(tài)DP]
1000pt GameOfLifeDivOne一個(gè)長為N(N<=50)的串(環(huán)狀, 首尾相連, 即x[N-1]與x[0]相連), 由'0', '1' 和'?'組成, 其中'?' 處可以填上'0'或'1'. 從T=0開始, 每過1單位時(shí)間, 整個(gè)串會(huì)更新一次: 某一位, 如果上一時(shí)刻, 它, 以及與它相鄰的兩位, 一共有至少2個(gè)'1', 那么這一時(shí)刻它變成'1', 否則它變成'0'. 問共有多少種填'?'的方法, 使得在經(jīng)過T(T<=1000)時(shí)間后, 還有不少于K(K<=N)個(gè)'1'. 比如'101010'->'010101'->'101010'->...; '11010'->'11101'->'11111'->...
首先容易觀察到, 兩個(gè)或兩個(gè)以上連續(xù)相同的位是永遠(yuǎn)不會(huì)變的. 只有01交替的子串才會(huì)發(fā)生變化. 所以任意一個(gè)串都可以看成是若干個(gè)形如 xpy的子串首尾連接而成, 而且兩串的首尾要相同才能連起來, 就像[xp1y][yp2x][xp3x][xp4y].... 其中pk是01交替序列, x和y都是一位, 可能是'0'或'1'. 特別的,連續(xù)3個(gè)相同字符可以看成是xx和xx粘起來(有1位重疊). 對(duì)于一個(gè)首尾字符固定不變的01交替串, 它在T時(shí)間后有多少個(gè)'1'是很容易算的. 兩頭都是0的話, 如0101010->0010100->0001000, 每時(shí)間減少一個(gè)1; 兩頭都是1的話類似, 每時(shí)間增加一個(gè)1. 一頭是0一頭1, 則0和1的個(gè)數(shù)都不變, 如010101->001011->000111.
這樣就有個(gè)算法的雛形, 類似背包: dp[pos][bit][one]表示: 從0到pos-1的子段, 以bit結(jié)尾, 且T時(shí)間后包含one個(gè)1的方法數(shù). 如果從pos到某一位pos2-1, 能構(gòu)造出以bit起始, 以bit2結(jié)束的交替串, 那么從狀態(tài)dp[pos][bit][one]就能擴(kuò)展到dp[pos2][bit2][one+one2], 則把前者加到后者上去, 其中one2是pos到pos2-1這個(gè)子串T時(shí)間后1的個(gè)數(shù). 把原始串復(fù)制兩遍, 就能比較方便地處理環(huán).
枚舉在原串中首次出現(xiàn)連續(xù)2個(gè)相同字符的位置startpos, 對(duì)每個(gè)startpos做一次上述DP. 把所有one>=K的方法數(shù)加起來即可. 此外要先預(yù)處理出任意edg[i][b1][j][b2], 即從i到j(luò)-1能否構(gòu)造出以b1開始, b2結(jié)尾的交替串, 如果能, T時(shí)間后有多少個(gè)'1'.
其實(shí)整個(gè)題就是一道背包DP, 求用若干個(gè)短棍子, 拼出一個(gè)權(quán)值>=K的長棍子的方法數(shù). 只是模型隱藏得很巧妙. orz...
[背包DP]
250p CubeStickers
給出若干個(gè)方形木板，每個(gè)木板有一種顏色。現(xiàn)在要選出其中6個(gè)，圍出一個(gè)立方體。問是否可能使轉(zhuǎn)出的立方體，任意兩個(gè)相鄰的面顏色不同。
直接按木板的總數(shù)分情況討論就可以，但是我漏想了一種情況@.@
其實(shí)顯然，同一種顏色最多能用兩次，所以統(tǒng)計(jì)每種木板能用的個(gè)數(shù)之和,sigma(min(count[i],2))，和不小于6則可行。
500p CubePacking給出Ns個(gè)邊長為1的立方體和Nb個(gè)邊長為L(2<=L<=10）的立方體。要找一個(gè)體積最小的長方體，使得可以把所有立方體堆進(jìn)去。保證結(jié)果不超int32。
正是因?yàn)椴怀琲nt32，所以可以直接枚舉兩條棱x,y，算第3條z的最小值。枚舉時(shí)循環(huán)條件 x*x*x <= INF, x*y*y <= INF。計(jì)算z的最小值時(shí)要注意除法要向上取整，而且判斷能否把邊長為L的立方體都放進(jìn)去的條件是(x/L)*(y/L)*(z/L) >= Nb，如果z小了，要加到足夠大為止。
[枚舉]
900p CubeBuilding大小相同的紅、綠、藍(lán)色的立方體，分別給R、G、B個(gè)(R,G,B<=25)。把這些立方體全部搭積木一樣的堆到N*N(N<=25)的格子棋盤中。可以在任意格子中堆任意高的立方體。規(guī)定一種方案是合法的，如果從北向南看的側(cè)視圖中只有一種顏色。問一共有多少種堆砌的方案。
可以先考慮N*1的棋盤，也就是側(cè)視圖中棋盤寬度是1。先考慮沒有顏色的方塊怎么放，再去染色。這樣不管怎么堆，
看到的方塊數(shù)總是等于所有格子堆的最大高度，則需要固定顏色的方塊數(shù)就為這個(gè)高度，剩下的方塊可以任意染色。同理N*N的棋盤，需要固定顏色的方塊數(shù)等于所有列中需要固定的數(shù)量之和。要求的答案就是，先枚舉固定方塊的數(shù)目，把它們?nèi)灸骋环N顏色，剩下的方塊可以用組合數(shù)直接算出有多少種染色方案，乘起來，最后求和。
關(guān)鍵就是要求出每一種固定方塊數(shù)目的前提下，不考慮顏色，有多少種堆放方法。
由前面的討論知道，可以先在N*1的棋盤上按行擴(kuò)展，需要記錄的狀態(tài)是當(dāng)前已使用的方塊數(shù)，當(dāng)前的最大高度。
然后利用這個(gè)結(jié)果按列擴(kuò)展，記錄的狀態(tài)是當(dāng)前已使用的方塊數(shù)，當(dāng)前已固定的方塊數(shù)。
ps.染色之前的方案數(shù)只用求一次，之后分別把固定的方塊染成3種不同顏色，只要用組合數(shù)分別算3次，加起來就行了。
O(9*N^5)的算法，時(shí)限有點(diǎn)緊。
[DP]
500pt
50個(gè)點(diǎn)的地圖，從0開始按照順序訪問一系列點(diǎn)（不超過50個(gè)），訪問順序給出，一個(gè)點(diǎn)可能訪問多次。某些點(diǎn)停著若干輛汽車。可以走路，也可以開車。開車的速度比走路快。但是限定一輛汽車只能使用一次，也就是下車后這輛車就作廢。問按要求訪問完所有點(diǎn)的最短總耗時(shí)。
先floyd求每對(duì)點(diǎn)之間走路時(shí)間和開車時(shí)間。對(duì)于訪問順序中的每一步，使用每輛車都有個(gè)節(jié)省的時(shí)間。這就相當(dāng)于建個(gè)二分圖，左邊x是訪問順序中的每一步，右邊y是每一輛車。xi與yj的邊權(quán)就是第i步使用第j輛車能節(jié)省的時(shí)間。
最后結(jié)果就是總的走路時(shí)間減去最大權(quán)匹配。
[floyd最短路 二分圖最大權(quán)匹配]
250p TheMoviesLevelOneDivOne
電影院有n行m列的座位, 有一些已經(jīng)被預(yù)訂了. 求在剩下的座位中, 選出同行且相鄰的兩個(gè)座位的方案數(shù).
可以按行列將已預(yù)訂的座位排序, 然后順便掃一遍, 算出相鄰兩個(gè)被預(yù)訂座位之間的方案數(shù). 最后累加.
也可以用個(gè)set記錄不能使用的方案, 再用沒有預(yù)訂座位的情況下的總方案數(shù)減去之.
500p TheMoviesLevelTwoDivOne若干部電影, 每部電影有一個(gè)加血的時(shí)間點(diǎn). 人看電影, 每看一分鐘掉一點(diǎn)血. 血掉到0就結(jié)束. 問怎樣按排順序使看的電影部數(shù)最多. 如果總部數(shù)相同, 取字典序最小的解輸出.
只有20部電影, 狀態(tài)DP即可.
為保證字典序, 可以從后往前DP, 這樣每次轉(zhuǎn)移時(shí)新加入的電影都是當(dāng)前最先看的, 保證它先擇的是最小的, 即能保證字典序最小.
[DP]
1000p TheMoviesLevelThreeDivOne若干部電影, A和B兩人看每部電影的時(shí)間分別是A[i], B[i]. 初始安排, 要依次把第1,2,..,n部電影放入A或B的待看隊(duì)列的隊(duì)尾. A和B各自開始看自己隊(duì)列中的電影, 看完一部后, 如果這是另一個(gè)人沒看過的, 就加入它的隊(duì)列中. 如果期間某人列隊(duì)空了, 那么他就結(jié)束, 再也不看新電影了. 問有多少種初始安排方法, 能使A和B都能看完所有電影.
首先肯定不會(huì)出現(xiàn)一種安排使得A和B都卡. 因?yàn)锳卡肯定發(fā)生在A看完他所有的電影之后, 且此時(shí)B沒看完自己的, 所以B肯定不會(huì)卡.
這樣就可以用總方案數(shù)2^N分別減去A卡的和B卡的方案數(shù). 考慮A卡的情況. 假設(shè)A那一整坨東西的時(shí)長是sumA, B的第一個(gè)東西是tb1, 則A卡的條件是 sumA-tb1<0. 否則B看完tb1后把ta1加在sumA后面, 這時(shí)卡的條件是(sumA+ta1)-(tb1+tb2)<0. 依此, 如果在這過程中任意一次卡的條件符合, 那么后續(xù)怎么安排都是卡的. 于是用一維狀態(tài)記錄目前為止出現(xiàn)過的最小的X-Y, min, 還要一維記錄當(dāng)前的X-Y, cur, 以轉(zhuǎn)移用. 轉(zhuǎn)移時(shí), 如果把當(dāng)前電影放進(jìn)A, 那么min和cur都增加A[i], 因?yàn)閟umA增加了. 如果放進(jìn)B, 那么用cur和B[i]來計(jì)算新的cur和min.
hint. cur=當(dāng)前所有電影的A[i]的和-B中電影的B[i]的和, 新的min=除了新放的電影外所有放過的電影的A[i]的和-包括新電影在內(nèi)的B中電影的B[i]的和.
ps. 1000的DP都很YD啊...
[DP]