問題:
http://poj.org/problem?id=2312思路:
這題糾結了...一上午都沒寫出來，原以為很簡單的(其實，很多人都說是簡單題，艾)
首先想到的是廣搜，因為是求從源點到目的地的最小步數嘛，典型的BFS，結果卻始終不知道如何表示每個狀態以及狀態間的判重
既然廣搜不會，那就深搜吧，恩，很快就寫出代碼，結果TLE...
無奈，只好在網上找解法，發現一種相當不錯的BFS代碼:
隊列的狀態只需要保存當前位置即可，另外用數組best[][]表示目前從源點到達每個點的最小步數
在從當前點擴展的時候，只將有最小步數更新的點加入隊列
這樣當BFS搜索結束時，每個best[i][j]都保存了從源點到點[i][j]的最短步數
原來還有這樣寫BFS的方法，又學習了(*^__^*) 嘻嘻……
上述算法有點類似于求最短路徑呵呵
而，事實上，這題是可以很容易轉化成圖論求單源最短路徑的
代碼:
1 /* 32MS */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_LEN 301
6 #define QUEUE_SIZE 90001
7 #define INF 0x7FFFFFFF
8 #define is_valid(x, y) ((x)>=0 && (x)<M && (y)>=0 && (y)<N)
9 char map[MAX_LEN][MAX_LEN];
10 const int dx[] = {0, 0, -1, 1};
11 const int dy[] = {-1, 1, 0, 0};
12 int M, N;
13 int you_x, you_y, target_x, target_y;
14 int best[MAX_LEN][MAX_LEN]; /* important, best[i][j] stores the current 'best solution' at map[i][j] */
15 struct Node {
16 int x, y;
17 } queue[QUEUE_SIZE];
18
19 int
20 bfs()
21 {
22 int i, next_x, next_y, cur, head, tail;
23 struct Node node;
24 head = -1;
25 tail = 0;
26 queue[tail].x = you_x;
27 queue[tail].y = you_y;
28 best[you_x][you_y] = 0;
29 while(head < tail) {
30 ++head;
31 cur = best[queue[head].x][queue[head].y];
32 for(i=0; i<4; i++) {
33 node.x = queue[head].x + dx[i];
34 node.y = queue[head].y + dy[i];
35 if(is_valid(node.x, node.y)) {
36 /* excellent, only push node which can be updated in 'best' into the queue */
37 if(map[node.x][node.y] == 'E' || map[node.x][node.y] == 'T') {
38 if(best[node.x][node.y] > cur+1) {
39 best[node.x][node.y] = cur+1;
40 ++tail;
41 queue[tail] = node;
42 }
43 } else if(map[node.x][node.y] == 'B') {
44 if(best[node.x][node.y] > cur+2) {
45 best[node.x][node.y] = cur+2;
46 ++tail;
47 queue[tail] = node;
48 }
49 }
50 }
51 }
52 }
53 }
54
55 int
56 main(int argc, char **argv)
57 {
58 int i, j;
59 while(scanf("%d %d", &M, &N)!=EOF && M && N) {
60 for(i=0; i<M; i++) {
61 scanf("%s", map[i]);
62 for(j=0; j<N; j++) {
63 if(map[i][j] == 'Y') {
64 you_x = i;
65 you_y = j;
66 } else if(map[i][j] == 'T') {
67 target_x = i;
68 target_y = j;
69 }
70 best[i][j] = INF;
71 }
72 }
73 bfs();
74 printf("%d\n", best[target_x][target_y]==INF ? -1 : best[target_x][target_y]);
75 }
76 }
問題:
http://poj.org/problem?id=3561思路:
簡單題，結果卻WA了一次
注意題目中給出的定義:
in adjacent cells就是說，這些符號必須是連續的，否則就要算兩個
另一點就是符號'\'需要寫成'\\'，開始編譯錯誤了呵呵
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 101
5 #define is_valid(x, y) ((x)>=0 && (x)<N && (y)>=0 && (y)<M)
6 int N, M;
7 char image[MAX_LEN][MAX_LEN];
8 int visited[MAX_LEN][MAX_LEN];
9 int hor, vert, diag;
10
11 void
12 mark(int i, int j, int dx, int dy, char ch)
13 {
14 while(is_valid(i+dx, j+dy) && image[i+dx][j+dy]==ch) {
15 visited[i+dx][j+dy] = 1;
16 i += dx;
17 j += dy;
18 }
19 }
20
21 void
22 solve()
23 {
24 int i, j;
25 char ch;
26 for(i=0; i<N; i++) {
27 for(j=0; j<M; j++) {
28 ch = image[i][j];
29 if(ch!='.' && !visited[i][j]) {
30 visited[i][j] = 1;
31 switch(ch) {
32 case '-':
33 ++hor;
34 mark(i, j, 0, -1, ch);
35 mark(i, j, 0, 1, ch);
36 break;
37 case '|':
38 ++vert;
39 mark(i, j, -1, 0, ch);
40 mark(i, j, 1, 0, ch);
41 break;
42 case '\\':
43 ++diag;
44 mark(i, j, 1, 1, ch);
45 mark(i, j, -1, -1, ch);
46 break;
47 case '/':
48 ++diag;
49 mark(i, j, 1, -1, ch);
50 mark(i, j, -1, 1, ch);
51 break;
52 }
53 }
54 }
55 }
56 }
57
58 int
59 main(int argc, char **argv)
60 {
61 int i, tests;
62 scanf("%d", &tests);
63 while(tests--) {
64 scanf("%d %d", &N, &M);
65 for(i=0; i<N; i++)
66 scanf("%s", image[i]);
67 memset(visited, 0, sizeof(visited));
68 hor = vert = diag = 0;
69 solve();
70 if(hor+vert+diag == 1)
71 printf("CORRECT\n");
72 else
73 printf("INCORRECT\n");
74 }
75 }
問題:
http://poj.org/problem?id=1010思路:
題目比較難理解，解題的話就是DFS
整整花了我一個晚上，終于AC了，(*^__^*) 嘻嘻……
雖然時間花了挺久，雖然自己的解法時間需要500+MS，雖然存在其他更優的解法，雖然......，但還是相當有成就感，完全是我自己寫出來的
如果這題放在5個月之前，估計完全不知道怎么去寫
在沒AC之前，我一直想著自己還是原來那么菜，現在，至少可以說，比5個月之前的我已經強了
繼續努力，Fighting...
代碼:
1 /* 388K 547MS */
2 #include<stdio.h>
3 #include<string.h>
4 #include<stdlib.h>
5 #define MAX_LEN 65 /* maximum number of different types of stamps */
6 #define UPPER 4 /* maximum number of stamps */
7 int types, stamps[MAX_LEN];
8 int request;
9 int maxdf, minusd, high, tie, exist, mark[MAX_LEN], ans[MAX_LEN];
10
11 int
12 compare(const void *arg1, const void *arg2)
13 {
14 return (*(int *)arg1)-(*(int *)arg2);
15 }
16
17 void
18 output()
19 {
20 int i, j;
21 if(!exist) {
22 printf("%d ---- none\n", request);
23 return;
24 }
25 printf("%d (%d): ", request, maxdf);
26 if(tie)
27 printf("tie\n");
28 else {
29 for(i=0; i<types; i++)
30 for(j=0; j<ans[i]; j++)
31 printf("%d ", stamps[i]);
32 printf("\n");
33 }
34 }
35
36 void
37 dfs(int remain, int index, int curdf, int curusd, int curhigh)
38 {
39 int i, flag = 0;
40 if(remain == 0) {
41 if(curdf < maxdf)
42 return;
43 /* satisfy the conditions: UPDATE */
44 if((curdf>maxdf) || (curdf==maxdf&&curusd<minusd) || (curdf==maxdf&&curusd==minusd&&curhigh>high)) {
45 maxdf = curdf;
46 minusd = curusd;
47 high = curhigh;
48 exist = 1;
49 tie = 0; /* remember reset 'tie' */
50 memcpy(ans, mark, sizeof(int)*MAX_LEN); /* copy the current best to 'ans' */
51 return;
52 }
53 /* TIE occurred */
54 if(curdf==maxdf && curusd==minusd && curhigh==high) {
55 tie = 1;
56 return;
57 }
58 return;
59 }
60 /* still exist several stamps unmarked */
61 for(i=index; i<types; i++) { /* Attention: i starts from 'index', which avoid duplicates such as '1 3' and '3 1' */
62 if(!mark[i] && stamps[i]<=remain && curusd+1<=UPPER) {
63 ++mark[i];
64 flag = 1;
65 dfs(remain-stamps[i], i+1, curdf+1, curusd+1, stamps[i]);
66 --mark[i];
67 }
68 }
69 /* all available stamps have been marked */
70 if(!flag) {
71 for(i=types-1; i>=0; i--) {
72 if(stamps[i]<=remain && curusd+1<=UPPER) {
73 ++mark[i];
74 dfs(remain-stamps[i], 0, curdf, curusd+1, curhigh);
75 --mark[i];
76 }
77 }
78 }
79 }
80
81 int
82 main(int argc, char **argv)
83 {
84 while(1) {
85 types = 0;
86 if(scanf("%d", &stamps[types]) == EOF)
87 break;
88 ++types;
89 while(scanf("%d", &stamps[types]) && stamps[types])
90 ++types;
91 qsort(stamps, types, sizeof(int), compare); /* ascent order */
92
93 while(scanf("%d", &request) && request) { /* each request */
94 maxdf = high = 0;
95 minusd = MAX_LEN+1;
96 exist = tie = 0;
97 memset(mark, 0, sizeof(mark));
98 dfs(request, 0, 0, 0, 0);
99 output();
100 }
101 }
102 return 0;
103 }
問題:
http://poj.org/problem?id=2060思路:
將每一個Taxi訂單作為頂點，根據題意如果訂單i與訂單j可以在規定時間內到達，那么說頂點i與頂點j存在一條邊
最小路徑覆蓋問題可以轉化為最大匹配問題
見:
http://www.shnenglu.com/Joe/archive/2010/10/21/130676.html代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 501
5 #define Abs(a) ((a)>=0 ? (a) : (a)*(-1))
6 int M;
7 int graph[MAX_LEN][MAX_LEN];
8 int state[MAX_LEN], fwd[MAX_LEN], bwd[MAX_LEN];
9 struct Taxi {
10 int hour, minu;
11 int sx, sy, dx, dy;
12 }rides[MAX_LEN];
13
14 int
15 reachable(struct Taxi *fst, struct Taxi *scd)
16 {
17 int h, m;
18 h = fst->hour;
19 m = fst->minu + Abs(fst->dx-fst->sx) + Abs(fst->dy-fst->sy) + Abs(scd->sx-fst->dx) + Abs(scd->sy-fst->dy);
20 h = (h+m/60);
21 m = m%60;
22 if(h >= 24)
23 return 0;
24 if(h == scd->hour)
25 return (m<scd->minu);
26 return (h<scd->hour);
27 }
28
29 void
30 build_graph()
31 {
32 int i, j;
33 memset(graph, 0, sizeof(graph));
34 for(i=0; i<M; i++)
35 for(j=i+1; j<M; j++)
36 if(reachable(rides+i, rides+j))
37 graph[i][j] = 1;
38 }
39
40 int
41 find_path(int u)
42 {
43 int i;
44 for(i=0; i<M; i++) {
45 if(graph[u][i] && !state[i]) {
46 state[i] = 1;
47 if(bwd[i]==-1 || find_path(bwd[i])) {
48 bwd[i] = u;
49 fwd[u] = i;
50 return 1;
51 }
52 }
53 }
54 return 0;
55 }
56
57 int
58 MaxMatch()
59 {
60 int i, ans = 0;
61 memset(fwd, -1, sizeof(fwd));
62 memset(bwd, -1, sizeof(bwd));
63 for(i=0; i<M; i++) {
64 if(fwd[i] == -1) {
65 memset(state, 0, sizeof(state));
66 if(find_path(i))
67 ++ans;
68 }
69 }
70 return ans;
71 }
72
73 int
74 main(int argc, char **argv)
75 {
76 int i, tests;
77 scanf("%d", &tests);
78 while(tests--) {
79 scanf("%d", &M);
80 for(i=0; i<M; i++)
81 scanf("%d:%d %d %d %d %d", &rides[i].hour, &rides[i].minu, &rides[i].sx, &rides[i].sy, &rides[i].dx, &rides[i].dy);
82 build_graph();
83 printf("%d\n", M-MaxMatch());
84 }
85 }
在一個ＰＸＰ的有向圖中，路徑覆蓋就是在圖中找一些路經，使之覆蓋了圖中的所有頂點，且任何一個頂點有且只有一條路徑與之關聯；（如果把這些路徑中的每條路徑從它的起始點走到它的終點，那么恰好可以經過圖中的每個頂點一次且僅一次）；如果不考慮圖中存在回路，那么每每條路徑就是一個弱連通子集．
由上面可以得出：
１.一個單獨的頂點是一條路徑；
２．如果存在一路徑p1,p2,......pk，其中p1 為起點，pk為終點，那么在覆蓋圖中，頂點p1,p2,......pk不再與其它的頂點之間存在有向邊．
最小路徑覆蓋就是找出最小的路徑條數，使之成為Ｐ的一個路徑覆蓋．
路徑覆蓋與二分圖匹配的關系：
最小路徑覆蓋＝｜Ｐ｜－最大匹配數；
其中最大匹配數的求法是把Ｐ中的每個頂點pi分成兩個頂點pi'與pi''，如果在p中存在一條pi到pj的邊，那么在二分圖Ｐ＇中就有一條連接pi'與pj''的無向邊；這里pi' 就是p中pi的出邊，pj''就是p中pj 的一條入邊；
對于公式：最小路徑覆蓋＝｜Ｐ｜－最大匹配數；可以這么來理解；
如果匹配數為零，那么Ｐ中不存在有向邊，于是顯然有：
最小路徑覆蓋＝｜Ｐ｜－最大匹配數＝｜Ｐ｜－０＝｜Ｐ｜；即Ｐ的最小路徑覆蓋數為｜Ｐ｜；
Ｐ＇中不在于匹配邊時，路徑覆蓋數為｜Ｐ｜；
如果在Ｐ＇中增加一條匹配邊pi'－－＞pj''，那么在圖P的路徑覆蓋中就存在一條由pi連接pj的邊，也就是說pi與pj 在一條路徑上，于是路徑覆蓋數就可以減少一個；
如此繼續增加匹配邊，每增加一條，路徑覆蓋數就減少一條；直到匹配邊不能繼續增加時，路徑覆蓋數也不能再減少了，此時就有了前面的公式；但是這里只 是說話了每條匹配邊對應于路徑覆蓋中的一條路徑上的一條連接兩個點之間的有向邊；下面來說明一個路徑覆蓋中的每條連接兩個頂點之間的有向邊對應于一條匹配 邊；
與前面類似，對于路徑覆蓋中的每條連接兩個頂點之間的每條有向邊pi--->pj，我們可以在匹配圖中對應做一條連接pi'與pj''的邊， 顯然這樣做出來圖的是一個匹配圖（這一點用反證法很容易證明，如果得到的圖不是一個匹配圖，那么這個圖中必定存在這樣兩條邊 pi'---pj'' 及 pi' ----pk''，（j!=k），那么在路徑覆蓋圖中就存在了兩條邊pi-->pj, pi--->pk ，那邊從pi出發的路徑就不止一條了，這與路徑覆蓋圖是矛盾的；還有另外一種情況就是存在pi'---pj'',pk'---pj''，這種情況也類似可證）；
至此，就說明了匹配邊與路徑覆蓋圖中連接兩頂點之間邊的一一對應關系，那么也就說明了前面的公式成立！
問題:
http://poj.org/problem?id=2536思路:
典型的最大二分匹配，也是咱的第一道最大二分匹配
根據題意，在規定的時間和速度下，gopher[i]能夠到達hole[j]，那么在i與j之間存在一條邊，這樣就建立了二分圖
學習了匈牙利算法，見
http://www.shnenglu.com/Joe/archive/2010/10/20/130573.html代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #include<math.h>
5 #define MAX_LEN 101
6 int map[MAX_LEN][MAX_LEN];
7 int result[MAX_LEN]; /* previous matching */
8 int state[MAX_LEN];
9 int n, m, s, v;
10 struct Coordinate {
11 float x, y;
12 }gophers[MAX_LEN], holes[MAX_LEN];
13
14 int
15 findpath(int u)
16 {
17 int i;
18 for(i=0; i<m; i++) {
19 if(map[u][i] && state[i]==-1) {
20 state[i] = 1;
21 if(result[i]==-1 || findpath(result[i])) {
22 result[i] = u; /* 取反 */
23 return 1;
24 }
25 }
26 }
27 return 0;
28 }
29
30 int
31 MaxMatch()
32 {
33 int i, ans = 0;
34 for(i=0; i<n; i++) {
35 memset(state, -1, sizeof(state));
36 if(findpath(i))
37 ++ans;
38 }
39 return ans;
40 }
41
42 int
43 main(int argc, char **argv)
44 {
45 int i, j;
46 while(scanf("%d %d %d %d", &n, &m, &s, &v) != EOF) {
47 for(i=0; i<n; i++)
48 scanf("%f %f", &gophers[i].x, &gophers[i].y);
49 for(j=0; j<m; j++)
50 scanf("%f %f", &holes[j].x, &holes[j].y);
51
52 memset(map, 0, sizeof(map));
53 memset(result, -1, sizeof(result));
54 for(i=0; i<n; i++)
55 for(j=0; j<m; j++) {
56 if(sqrt((holes[j].x-gophers[i].x)*(holes[j].x-gophers[i].x) + (holes[j].y-gophers[i].y)*(holes[j].y-gophers[i].y)) <= v*s) /*reachable*/
57 map[i][j] = 1;
58 else
59 map[i][j] = 0;
60 }
61
62 printf("%d\n", n-MaxMatch());
63 }
64 }
二分圖指的是這樣一種圖：其所有的頂點分成兩個集合M和N，其中M或N中任意兩個在同一集合中的點都不相連。二分圖匹配是指求出一組邊，其中的頂點分別在兩個集合中，并且任意兩條邊都沒有相同的頂點，這組邊叫做二分圖的匹配，而所能得到的最大的邊的個數，叫做最大匹配。 匈牙利算法。這個算法說白了就是最大流的算法，但是它跟據二分圖匹配這個問題的特點，把最大流算法做了簡化，提高了效率。匈牙利算法其實很簡單，但是網上搜不到什么說得清楚的文章。所以我決定要寫一下。
最大流算法的核心問題就是找增廣路徑（augment path）。匈牙利算法也不例外，它的基本模式就是：
初始時最大匹配為空
while 找得到增廣路徑
do 把增廣路徑加入到最大匹配中去 |
可見和最大流算法是一樣的。但是這里的增廣路徑就有它一定的特殊性，下面我來分析一下。
（注：匈牙利算法雖然根本上是最大流算法，但是它不需要建網絡模型，所以圖中不再需要源點和匯點，僅僅是一個二分圖。每條邊也不需要有方向。）
 圖1  圖2
圖1是我給出的二分圖中的一個匹配：〔1，5〕和〔2，6〕。圖2就是在這個匹配的基礎上找到的一條增廣路徑：3->6->2->5->1->4。我們借由它來描述一下二分圖中的增廣路徑的性質：
(1)有奇數條邊。
(2)起點在二分圖的左半邊，終點在右半邊。
(3)路徑上的點一定是一個在左半邊，一個在右半邊，交替出現。（其實二分圖的性質就決定了這一點，因為二分圖同一邊的點之間沒有邊相連，不要忘記哦。）
(4)整條路徑上沒有重復的點。
(5)起點和終點都是目前還沒有配對的點，而其它所有點都是已經配好對的。（如圖1、圖2所示，〔1，5〕和〔2，6〕在圖1中是兩對已經配好對的點；而起點3和終點4目前還沒有與其它點配對。）
(6)路徑上的所有第奇數條邊都不在原匹配中，所有第偶數條邊都出現在原匹配中。（如圖1、圖2所示，原有的匹配是〔1，5〕和〔2，6〕，這兩條配匹的邊在圖2給出的增廣路徑中分邊是第2和第4條邊。而增廣路徑的第1、3、5條邊都沒有出現在圖1給出的匹配中。）
(7)最后，也是最重要的一條，把增廣路徑上的所有第奇數條邊加入到原匹配中去，并把增廣路徑中的所有第偶數條邊從原匹配中刪除（這個操作稱為增廣路徑的取反），則新的匹配數就比原匹配數增加了1個。（如圖2所示，新的匹配就是所有藍色的邊，而所有紅色的邊則從原匹配中刪除。則新的匹配數為3。）
不難想通，在最初始時，還沒有任何匹配時，圖1中的兩條灰色的邊本身也是增廣路徑。因此在這張二分圖中尋找最大配匹的過程可能如下：
(1)找到增廣路徑1->5，把它取反，則匹配數增加到1。
(2)找到增廣路徑2->6，把它取反，則匹配數增加到2。
(3)找到增廣路徑3->6->2->5->1->4，把它取反，則匹配數增加到3。
(4)再也找不到增廣路徑，結束。
當然，這只是一種可能的流程。也可能有別的找增廣路徑的順序，或者找到不同的增廣路徑，最終的匹配方案也可能不一樣。但是最大匹配數一定都是相同的。
對于增廣路徑還可以用一個遞歸的方法來描述。這個描述不一定最準確，但是它揭示了尋找增廣路徑的一般方法：
“從點A出發的增廣路徑”一定首先連向一個在原匹配中沒有與點A配對的點B。如果點B在原匹配中沒有與任何點配對，則它就是這條增廣路徑的終點；反之，如果點B已與點C配對，那么這條增廣路徑就是從A到B，再從B到C，再加上“從點C出發的增廣路徑”。并且，這條從C出發的增廣路徑中不能與前半部分的增廣路徑有重復的點。
比如圖2中，我們要尋找一條從3出發的增廣路徑，要做以下3步：
(1)首先從3出發，它能連到的點只有6，而6在圖1中已經與2配對，所以目前的增廣路徑就是3->6->2再加上從2出發的增廣路徑。
(2)從2出發，它能連到的不與前半部分路徑重復的點只有5，而且5確實在原匹配中沒有與2配對。所以從2連到5。但5在圖1中已經與1配對，所以目前的增廣路徑為3->6->2->5->1再加上從1出發的增廣路徑。
(3)從1出發，能連到的不與自已配對并且不與前半部分路徑重復的點只有4。因為4在圖1中沒有與任何點配對，所以它就是終點。所以最終的增廣路徑是3->6->2->5->1->4。
但是嚴格地說，以上過程中從2出發的增廣路徑（2->5->1->4）和從1出發的增廣路徑（1->4）并不是真正的增廣路徑。因為它們不符合前面講過的增廣路徑的第5條性質，它們的起點都是已經配過對的點。我們在這里稱它們為“增廣路徑”只是為了方便說明整個搜尋的過程。而這兩條路徑本身只能算是兩個不為外界所知的子過程的返回結果。
顯然，從上面的例子可以看出，搜尋增廣路徑的方法就是DFS，可以寫成一個遞歸函數。當然，用BFS也完全可以實現。
至此，理論基礎部份講完了。但是要完成匈牙利算法，還需要一個重要的定理：
如果從一個點A出發，沒有找到增廣路徑，那么無論再從別的點出發找到多少增廣路徑來改變現在的匹配，從A出發都永遠找不到增廣路徑。
要用文字來證明這個定理很繁，話很難說，要么我還得多畫一張圖，我在此就省了。其實你自己畫幾個圖，試圖舉兩個反例，這個定理不難想通的。（給個提示。如果你試圖舉個反例來說明在找到了別的增廣路徑并改變了現有的匹配后，從A出發就能找到增廣路徑。那么，在這種情況下，肯定在找到別的增廣路徑之前，就能從A出發找到增廣路徑。這就與假設矛盾了。）
有了這個定理，匈牙利算法就成形了。如下：
初始時最大匹配為空
for 二分圖左半邊的每個點i
do 從點i出發尋找增廣路徑。如果找到，則把它取反（即增加了總了匹配數）。 |
如果二分圖的左半邊一共有n個點，那么最多找n條增廣路徑。如果圖中共有m條邊，那么每找一條增廣路徑（DFS或BFS）時最多把所有邊遍歷一遍，所花時間也就是m。所以總的時間大概就是O（n * m）。 |
問題:
http://poj.org/problem?id=2005思路:
簡單題，但是容易錯
特殊情況: 兩張牌都是Ace，這也是Ace需要被當作是1的唯一情況
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 int player, dealer;
5 int n, count[14];
6 char card[3][2];
7
8 int
9 score(char ch)
10 {
11 if(ch == 'A')
12 return 11;
13 else if(ch == 'T' || ch=='J' || ch=='Q' || ch=='K')
14 return 10;
15 else
16 return ch-'0';
17 }
18
19 int
20 main(int argc, char **argv)
21 {
22 int i, tmp, total;
23 while(scanf("%d", &n)!=EOF && n) {
24 total = player = dealer = 0; memset(count, 0, sizeof(count));
25 for(i=0; i<3; i++) {
26 scanf("%s", card[i]);
27 tmp = score(card[i][0]);
28 ++count[tmp];
29 if(i == 0)
30 dealer += tmp;
31 else
32 player += tmp;
33 }
34 if(player == 22) /* two Ace */
35 player = 12;
36 for(i=2; i<=11; i++) {
37 if((dealer+i==22 ? 12 : dealer+i) < player) {
38 if(i == 10)
39 total += (4*4*n-count[i]);
40 else
41 total += (4*n-count[i]);
42 }
43 }
44 printf("%.3f%%\n\n", ((double)total)/(52*n-3)*100);
45 }
46 }
問題:
http://poj.org/problem?id=3670思路:
1.
將原問題化解為求最長不下降子序列和最長不上升子序列即可
求解LIS/LDS的nlogn算法
參考
http://www.shnenglu.com/Joe/archive/2010/08/14/123461.html2.
參考:
http://www.byvoid.com/blog/usaco-feb08-silver-eating-together/代碼:
1 /* LIS/LDS: nlogn */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_LEN 30001
6 int N, group[MAX_LEN];
7 int aux[MAX_LEN];
8
9 int
10 bin_search1(int *arr, int front, int rear, int target)
11 {
12 int mid;
13 while(front <= rear) {
14 mid = (front+rear)/2;
15 if(aux[mid] <= target)
16 front = mid+1;
17 else
18 rear = mid-1;
19 }
20 return front;
21 }
22
23 int
24 bin_search2(int *arr, int front, int rear, int target)
25 {
26 int mid;
27 while(front <= rear) {
28 mid = (front+rear)/2;
29 if(aux[mid] >= target)
30 front = mid+1;
31 else
32 rear = mid-1;
33 }
34 return front;
35 }
36
37 int
38 LIS() /* LUDS, maybe more accurate, meaning Longest Undecreasing Seq */
39 {
40 int i, len = 1;
41 aux[1] = group[0];
42 for(i=1; i<N; i++) {
43 if(group[i] >= aux[len]) {
44 ++len;
45 aux[len] = group[i];
46 } else {
47 aux[bin_search1(aux, 1, len, group[i])] = group[i];
48 }
49 }
50 return len;
51 }
52
53 int
54 LDS() /* LUIS */
55 {
56 int i, len=1;
57 aux[1] = group[0];
58 for(i=1; i<N; i++) {
59 if(group[i] <= aux[len]) {
60 ++len;
61 aux[len] = group[i];
62 } else {
63 aux[bin_search2(aux, 1, len, group[i])] = group[i];
64 }
65 }
66 return len;
67 }
68
69 int
70 main(int argc, char **argv)
71 {
72 int i, lis_len, lds_len;
73 while(scanf("%d", &N) != EOF) {
74 for(i=0; i<N; i++)
75 scanf("%d", group+i);
76 lis_len = LIS();
77 lds_len = LDS();
78 printf("%d\n", N-(lis_len>lds_len ? lis_len : lds_len));
79 }
80 }
問題:
http://poj.org/problem?id=3090思路:
首先可以觀察得到這樣的點集是對稱的，只需要求一半即可
這里，我采用了模擬的方法，直接去掉擋住的點
結果TLE，然后發現可以打表，隨即AC，打表真是強大啊呵呵...
ps.
據說這題與什么歐拉函數有關系，沒有深究
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 1001
5 int N, points[MAX_LEN][MAX_LEN];
6 int result[MAX_LEN];
7
8 /* Attention: symmetrical */
9 void
10 solve()
11 {
12 int i, j, k, count = 0;
13 memset(points, 0, sizeof(points));
14 for(i=1; i<MAX_LEN; i++) {
15 for(j=0; j<i; j++) {
16 if(!points[i][j])
17 ++count;
18 for(k=1; i*k<MAX_LEN&&j*k<MAX_LEN; k++)
19 points[i*k][j*k] = 1;
20 }
21 result[i] = count;
22 }
23 }
24
25 int
26 main(int argc, char **argv)
27 {
28 int i, tests;
29 solve();
30 scanf("%d", &tests);
31 for(i=1; i<=tests; i++) {
32 scanf("%d", &N);
33 printf("%d %d %d\n", i, N, ((result[N]<<1)+1));
34 }
35 }