问题:
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.cppblog.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.cppblog.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.cppblog.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 }