bfs的好题目！
开始想到用优先队列，无情的还是过了， 只不过时间用了2000ms多，差点就挂了~杯具的优先
后来一想，其实可以直接bfs, 有情的是意料之外的没有出现TE，而是AC，彻底无语的是只用了500ms多！！！！
大呼优先之哀哉……
至于bfs的做法如下：
1，开始点进栈
2，开始点能直接到达(不花时间的)的所有的点进栈
3，分两步
3.1 开始点不能直接到达（要时间）的点进栈
3.2 将这个点能直接到达(不花时间的)的所有的点进栈
3.3 跳转到3
4 跳转到1
注：开始点为当前出栈的第一个点
不明白这个过程的可以看代码（虽然代码有点……，还可以进一步简化， 以后不能老想着优先了，谁优先谁杯具，当然不是说我们的广大女同胞……）
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4 struct node
5 {
6 int x, y, time;
7 /*friend bool operator < (node a, node b)
8 {
9 return a.time > b.time;
10 }*/
11 };
12 int n, m;
13 int xi[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
14 int yi[8] = {0, 1, 1, 1, 0, -1, -1, -1};
15 char map[1005][1005];
16 bool vist[1005][1005];
17 bool check(int dx, int dy)
18 {
19 if (dx >= 0 && dy >=0 && dx < n && dy < m) return true;
20 return false;
21 }
22 queue <node> q;
23 int bfs(node now, node end)
24 {
25 while (!q.empty())q.pop();
26 now.time = 0;
27 q.push(now);
28
29 for (int i = 0; i < n; i++)
30 for (int j = 0; j < m; j++)
31 vist[i][j] = false;
32 vist[now.x][now.y] = true;
33 node next, tmp;
34 bool flag = false;
35 while (!q.empty())
36 {
37 now = q.front();
38 tmp = now;
39 if (now.x == end.x && now.y == end.y) return now.time;
40 q.pop();
41 flag = false;
42 while (1)
43 {
44 next.x = tmp.x + xi[map[tmp.x][tmp.y]-'0'];
45 next.y = tmp.y + yi[map[tmp.x][tmp.y]-'0'];
46 if (check(next.x, next.y) && !vist[next.x][next.y])
47 {
48 if (next.x == end.x && next.y == end.y) return tmp.time;
49 next.time = tmp.time;
50 vist[next.x][next.y] = true;
51 q.push(next);
52 tmp = next;
53 }else break;
54 }
55 for (int i = 0; i < 8; i++)
56 {
57 next.x = now.x + xi[i];
58 next.y = now.y + yi[i];
59 if (check(next.x, next.y) && !vist[next.x][next.y])
60 {
61 if (map[now.x][now.y] - '0' == i) next.time = now.time;
62 else next.time = now.time + 1;
63 if (next.x == end.x && next.y == end.y) return next.time;
64 vist[next.x][next.y] = true;
65 q.push(next);
66 tmp = next;
67 while (1)
68 {
69 next.x = tmp.x + xi[map[tmp.x][tmp.y]-'0'];
70 next.y = tmp.y + yi[map[tmp.x][tmp.y]-'0'];
71 if (check(next.x, next.y) && !vist[next.x][next.y])
72 {
73 if (next.x == end.x && next.y == end.y) return tmp.time;
74 next.time = tmp.time;
75 vist[next.x][next.y] = true;
76 q.push(next);
77 tmp = next;
78 }else break;
79 }
80 }
81 }
82 }
83 return 0;
84 }
85 int main()
86 {
87 while (scanf("%d%d", &n, &m) != EOF)
88 {
89 int i, j;
90 for (i = 0; i < n; i++)
91 scanf("%s", map[i]);
92 int T;
93 scanf("%d", &T);
94 node now, end;
95 for (i = 0; i < T; i++)
96 {
97 scanf("%d%d%d%d", &now.x, &now.y, &end.x, &end.y);
98 now.time = 0;
99 now.x --;
100 now.y --;
101 end.x --;
102 end.y --;
103 if (now.x == end.x && now.y == end.y)
104 {
105 printf("0\n");
106 }else printf("%d\n", bfs(now, end));
107 }
108 }
109 return 0;
110 }
111
posted @
2012-04-22 20:23 路修远 阅读(1325) |
评论 (0) |
编辑 收藏
单纯的bfs()，当然你也可以用dfs,只要你不怕超时或者你的剪枝够强大
最好开一个三维的数组，记录每一个格子的每一个方向上的最小值，直到bfs完成
具体看代码，不做过多的解释。
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4 struct node
5 {
6 int x, y;
7 int step, dir;
8 };
9 int n, m;
10 int xi[4] = {0, 1, -1, 0};
11 int yi[4] = {1, 0, 0, -1};
12 int vist[82][82][4];
13 char map[82][82];
14 node start;
15 queue <node> q;
16 bool check(int dx, int dy)
17 {
18 if(dx >= 1 && dx <= n && dy >= 1 && dy <= m) return true;
19 else return false;
20 }
21 bool find(node a)
22 {
23 if ((a.x == 1 || a.x == n || a.y == 1 || a.y == m)) return true;
24 else return false;
25 }
26 int bfs()
27 {
28 while (!q.empty())q.pop();
29 memset(vist, 0, sizeof(vist));
30 start.dir = -1;
31 start.step = 0;
32 q.push(start);
33 node now, next;
34 bool flag = true;
35 int tmp;
36 while (!q.empty())
37 {
38 now = q.front();
39 q.pop();
40 if (find(now)) return now.step;
41
42 flag = false;
43 for (int i = 0 ; i < 4; i++)
44 {
45 if (now.dir == i) continue;
46 if (now.dir >=0 && 3-now.dir == i) continue;
47 next.x = now.x + xi[i];
48 next.y = now.y + yi[i];
49 next.step = now.step + 1;
50 if (check(next.x, next.y) && map[next.x][next.y] == '.' )
51 {
52 if (vist[next.x][next.y][i] == 0)
53 {
54 vist[next.x][next.y][i] = next.step;
55 next.dir = i;
56 q.push(next);
57 }
58 else if (vist[next.x][next.y][i] > next.step)
59 {
60 vist[next.x][next.y][i] = next.step;
61 next.dir = i;
62 q.push(next);
63 }
64 flag = true;
65 }
66 }
67 if (!flag)
68 {
69 int i = now.dir;
70 if (i < 0) return 0;
71 next.x = now.x + xi[i];
72 next.y = now.y + yi[i];
73 next.step = now.step + 1;
74 if (check(next.x, next.y) && map[next.x][next.y] == '.' )
75 {
76 if (vist[next.x][next.y][i] == 0)
77 {
78 vist[next.x][next.y][i] = next.step;
79 next.dir = i;
80 q.push(next);
81 }
82 else if (vist[next.x][next.y][i] > next.step)
83 {
84 vist[next.x][next.y][i] = next.step;
85 next.dir = i;
86 q.push(next);
87 }
88 flag = true;
89 }
90 }
91 }
92 return -1;
93 }
94 int main()
95 {
96 int cas;
97 scanf("%d", &cas);
98 while (cas--)
99 {
100 scanf("%d%d", &n, &m);
101 int i, j;
102 for (i = 1; i <= n; i++)
103 scanf("%s", map[i]+1);
104 for (i = 1; i <= n; i++)
105 for (j = 1; j <= m; j++)
106 {
107 if (map[i][j] == '@')
108 {
109 start.x = i;
110 start.y = j;
111 map[i][j] = '.';
112 }
113 }
114 int ans = bfs();
115 printf("%d\n", ans);
116 }
117 return 0;
118 }
119
posted @
2012-04-13 18:34 路修远 阅读(1304) |
评论 (0) |
编辑 收藏
题目大意：
去掉给定的边，看每一个点是否能从别的点到达！
如果能够到达，则求出对于每一个点到其他所有的点最短距离之和，将这些和相加就是最后的结果
解题思路：
对每一个点求一次单源最短路，然后求和，相加的到最后的结果……
但，算一下时间复杂度： 复杂度是O(M*N*M)。由于M*N*M=3000*100*3000=9*10
8，不可能AC
所以，需要我们另辟他径。网上有说建什么最短路径树，这个我不懂……
我的思路是：引用前面的思路，对每一个点求一次最短路，并将其求和，保存在一个数组里头，定为sum[i]，i表示着一个点到所有其他点最短路之和。并将这些和相加 ans = sum[1] + …… + sum[n];
然后，删除一条边，其顶点暂定为u,v，对这条边的一个顶点u在一次求最短路，如果这个点，不能到达这条边的另一个点v，则 直接输出INF
如果，能够到达，则对v也求一次最短路，对于u，v两点来说，求得u到每一个点的最短路之和sum_u，求得v到每一个点的最短路之和sum_v，
最后结果为： ans = ans + sum_u + sum_v - sum[u] - sum[v];
ans为最后答案（千万记住是每一组的，因为有m条边）
具体看代码：
http://acm.hdu.edu.cn/showproblem.php?pid=2433时间是 953ms
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4 const int SIZE = 102;
5 const int INF = 1 << 30;
6 struct node
7 {
8 int v, w, next;
9 }map[SIZE * SIZE];
10
11 int head[SIZE], use;
12 int num[SIZE * 30];
13 int sum[SIZE];
14
15 void add(int u, int v, int w)
16 {
17 map[use].v = v;
18 map[use].w = w;
19 map[use].next = head[u];
20 head[u] = use ++;
21 }
22 void init()
23 {
24 use = 0;
25 memset(head, -1, sizeof(head));
26 memset(sum, 0, sizeof(sum));
27 }
28
29 queue <int> q;
30 bool vist[SIZE];
31 int dis[SIZE];
32
33 int spfa(int s)
34 {
35 while (!q.empty()) q.pop();
36
37 for (int i = 0; i < SIZE ; i ++) dis[i] = INF;
38
39 memset(vist, false, sizeof(vist));
40 dis[s] = 0;
41 vist[s] = true;
42 q.push(s);
43 int ans = 0;
44 while (!q.empty())
45 {
46 int u = q.front();
47 q.pop();
48 vist[u] = false;
49 ans += dis[u];
50 for (int i = head[u]; i != -1; i = map[i].next)
51 {
52 int v = map[i].v;
53 if (dis[v] > dis[u] + map[i].w)
54 {
55 dis[v] = dis[u] + map[i].w;
56 if (!vist[v])
57 {
58 vist[v] = true;
59 q.push(v);
60 }
61 }
62 }
63 }
64 return ans;
65 }
66 int main()
67 {
68 int n, m;
69 while (scanf("%d%d", &n, &m) != EOF)
70 {
71 int i, j, k;
72 int u, v;
73 init();
74 memset(num, 0, sizeof(num));
75 for (i = 1; i <= m; i++)
76 {
77 scanf("%d%d", &u, &v);
78 num[i] = use;
79 add(u, v, 1);
80 add(v, u, 1);
81 }
82 int ans = 0;
83 for (i = 1; i <= n; i++)
84 {
85 sum[i] = spfa(i);
86 ans += sum[i];
87 }
88 int tmp = ans;
89 for (i = 1; i <= m; i++)
90 {
91 map[num[i]].w = INF;
92 map[num[i]^1].w = INF;
93
94 ans = tmp;
95 ans += spfa(map[num[i]].v);
96
97 if (dis[map[num[i]^1].v] == INF)
98 {
99 printf("INF\n");
100 }
101 else
102 {
103 ans += spfa(map[num[i]^1].v);
104 ans = ans - sum[map[num[i]].v] - sum[map[num[i]^1].v];
105 printf("%d\n", ans);
106 }
107 map[num[i]].w = 1;
108 map[num[i]^1].w = 1;
109 }
110 }
111 return 0;
112 }
113
posted @
2012-03-09 15:35 路修远 阅读(1849) |
评论 (8) |
编辑 收藏
Going Home
Description
On a grid map there are n little men and n houses. In each unit time, every little man can move one unit step, either horizontally, or vertically, to an adjacent point. For each little man, you need to pay a $1 travel fee for every step he moves, until he enters a house. The task is complicated with the restriction that each house can accommodate only one little man.
Your task is to compute the minimum amount of money you need to pay in order to send these n little men into those n different houses. The input is a map of the scenario, a '.' means an empty space, an 'H' represents a house on that point, and am 'm' indicates there is a little man on that point.
You can think of each point on the grid map as a quite large square, so it can hold n little men at the same time; also, it is okay if a little man steps on a grid with a house without entering that house.
Input
There are one or more test cases in the input. Each case starts with a line giving two integers N and M, where N is the number of rows of the map, and M is the number of columns. The rest of the input will be N lines describing the map. You may assume both N and M are between 2 and 100, inclusive. There will be the same number of 'H's and 'm's on the map; and there will be at most 100 houses. Input will terminate with 0 0 for N and M.
Output
For each test case, output one line with the single integer, which is the minimum amount, in dollars, you need to pay.
Sample Input
2 2
.m
H.
5 5
HH..m
.....
.....
.....
mm..H
7 8
...H....
...H....
...H....
mmmHmmmm
...H....
...H....
...H....
0 0
Sample Output
2
10
28
KM算法！
其实这个题求的是最小权匹配，，但有些题目最小不一定好求，于是我们可以换一种思维，将有所的距离变成负的，那么我们要求的就是最大权匹配！（在一位大牛的指点下）
废话不多说，看程序：
1 #include<iostream>
2 using namespace std;
3 #define Inf 10000000;
4 int map[105][105];
5 int slack[105];
6 int lx[105],ly[105];
7 bool x[105],y[105];
8 int link[105];
9 int n,m;
10 char mm[105][105];
11 bool dfs(int v)
12 {
13 x[v]=true;
14 int t;
15 for (int i=0;i<m;i++)
16 {
17 if (!y[i])
18 {
19 t=lx[v]+ly[i]-map[v][i];
20 if (t==0)
21 {
22 y[i]=true;
23 if (link[i]==-1||dfs(link[i]))
24 {
25 link[i]=v;
26 return true;
27 }
28 }
29 else slack[i]=min(slack[i],t);
30 }
31 }
32 return false;
33 }
34 void KM()
35 {
36 int i,j,k;
37 memset(link,-1,sizeof(link));
38 for (i=0;i<=m;i++)
39 {
40 lx[i]=-Inf;
41 ly[i]=0;
42 }
43 for (i=0;i<m;i++)
44 {
45 while (1)
46 {
47 memset(x,0,sizeof(x));
48 memset(y,0,sizeof(y));
49
50 for (j=0;j<m;j++) slack[j]=Inf;
51
52 if (dfs(i))break;
53
54 int d=Inf;
55 for (j=0;j<m;j++)
56 if (!y[j])d=min(slack[j],d);
57
58 for (j=0;j<m;j++)
59 {
60 if (x[j])lx[j]-=d;
61 if (y[j])ly[j]+=d;
62 }
63 for (j=0;j<m;j++)
64 if (!y[j])slack[j]-=d;
65 }
66 }
67 }
68 int main()
69 {
70 int i,j,k,t,l,v;
71 while (cin>>k>>t)
72 {
73 if (k+t==0)break;
74 for (i=1;i<=k;i++)
75 for (j=1;j<=t;j++)
76 scanf(" %c",&mm[i][j]);
77 memset(map,0,sizeof(map));
78 n=0,m=0;
79 for (i=1;i<=k;i++)
80 for (j=1;j<=t;j++)
81 {
82 if (mm[i][j]=='H')
83 {
84 n=0;
85 for (l=1;l<=k;l++)
86 for (v=1;v<=t;v++)
87 {
88 if (mm[l][v]=='m')
89 {
90 map[m][n]=-(abs(i-l)+abs(j-v));
91 n++;
92 }
93 }
94 m++;
95 }
96 }
97 KM();
98 int sum=0;
99 for (i=0;i<m;i++)
100 sum+=map[link[i]][i];
101 cout<<0-sum<<endl;
102 }
103 return 0;
104 }
105
106
posted @
2011-04-19 13:54 路修远 阅读(1426) |
评论 (0) |
编辑 收藏
没什么好说的，直接匈牙利算法
#include<iostream>
using namespace std;
int n,m;//n为x集合，m为y集合
int map[305][305];//map[x][y]表示x,y两点之间有边相连
bool visit[305];//记录m中的i节点是否被访问过
int link[305];//记录当前n中的i节点是否与 j节点相连
bool dfs(int a)
{
int i;
for (i=1;i<=n;i++)
{
if (map[a][i]&&!visit[i])
{
visit[i]=true;
if (link[i]==0||dfs(link[i]))
{
link[i]=a;
return true;
}
}
}
return false;
}
int find()
{
int sum=0;
for (int i=1;i<=n;i++)
{
memset(visit,0,sizeof(visit));
if (dfs(i))sum++;
}
return sum;//最大匹配数
}
int main()
{
int t,i,j,k,x;
while (scanf("%d%d",&n,&m)!=EOF)
{
memset(map,0,sizeof(map));
memset(link,0,sizeof(link));
for (i=1;i<=n;i++)
{
scanf("%d",&j);
for (k=1;k<=j;k++)
{
scanf("%d",&x);
map[i][x]=1;
}
}
cout<<find()<<endl;
}
return 0;
}
posted @
2011-04-04 09:50 路修远 阅读(1253) |
评论 (0) |
编辑 收藏
其实这个题，和我上次讲的那个连连看一样！只不过是字符变成了整型而已！
还是贴一下关键代码吧(⊙o⊙)~~
1 bool search(int x1,int y1,int x2,int y2,int n,int m)
2 {
3 memset(gk,0,sizeof(gk));
4 int t=game[x2][y2];
5 game[x2][y2]=0;
6 gk[x1][y1]=1;
7
8 //对game[x1][y1]四个方向是空格的标为1
9 for (int i=x1-1;i>=1;i--)
10 {
11 if(game[i][y1]==0)gk[i][y1]=1;
12 else break;
13 }
14 for (int j=x1+1;j<=n;j++){
15 if(game[j][y1]==0)gk[j][y1]=1;
16 else break;
17 }
18
19 for (int i=y1-1;i>=1;i--){
20 if(game[x1][i]==0)gk[x1][i]=1;
21 else break;
22 }
23 for (int i=y1+1;i<=m;i++){
24 if(game[x1][i]==0)gk[x1][i]=1;
25 else break;
26 }
27
28 if (gk[x2][y2]>0&&gk[x2][y2]<4)
29 {
30 game[x2][y2]=t;
31 return true;
32 }
33 //对gk[i][j]为1的四个方向是空格的标为2
34 for (int i=1;i<=n;i++)
35 for (int j=1;j<=m;j++)
36 if (gk[i][j]==1)
37 {
38 for (int k=i-1;k>=1;k--)
39 {
40 if (game[k][j]==0){
41 if(gk[k][j]==0)gk[k][j]=2;
42 }
43 else break;
44 }
45 for (int k=i+1;k<=n;k++){
46 if (game[k][j]==0){
47 if(gk[k][j]==0)gk[k][j]=2;
48 }
49 else break;
50 }
51
52 for (int k=j-1;k>=1;k--){
53 if (game[i][k]==0){
54 if(gk[i][k]==0)gk[i][k]=2;
55 }
56 else break;
57 }
58 for (int k=j+1;k<=m;k++){
59 if (game[i][k]==0){
60 if(gk[i][k]==0)gk[i][k]=2;
61 }
62 else break;
63 }
64 }
65
66 if (gk[x2][y2]>0&&gk[x2][y2]<4)
67 {
68 game[x2][y2]=t;
69 return true;
70 }
71 //对gk[i][j]为2的四个方向是空格的标为3
72 for (int i=1;i<=n;i++)
73 for (int j=1;j<=m;j++)
74 if (gk[i][j]==2){
75 for (int k=i-1;k>=1;k--)
76 {
77 if (game[k][j]==0)
78 {
79 if(gk[k][j]==0)gk[k][j]=3;
80 }
81 else break;
82 }
83 for (int k=i+1;k<=n;k++)
84 {
85 if (game[k][j]==0)
86 {
87 if(gk[k][j]==0)gk[k][j]=3;
88 }
89 else break;
90 }
91
92 for (int k=j-1;k>=1;k--)
93 {
94 if (game[i][k]==0){
95 if(gk[i][k]==0)gk[i][k]=3;
96 }
97 else break;
98 }
99 for (int k=j+1;k<=m;k++)
100 {
101 if (game[i][k]==0)
102 {
103 if(gk[i][k]==0)gk[i][k]=3;
104 }
105 else break;
106 }
107 }
108
109 game[x2][y2]=t;
110 if(gk[x2][y2]>0&&gk[x2][y2]<4)return true;
111 if(gk[x2][y2]==0) return false;
112 }
posted @
2010-11-24 16:07 路修远 阅读(1808) |
评论 (0) |
编辑 收藏
其实这个题是一个简单的搜索问题，理解了很好做！注意4代表时间复原就行了！具体的在程序里头，这里就不多说了，深知多说无益，还是要多练的！
1 #include<iostream>
2 using namespace std;
3 int map[12][12],tp[12][12],tt[12][12];
4 int n,m;
5 int Min=0xffffff,sum=0;
6 int x[4]={1,0,0,-1};
7 int y[4]={0,1,-1,0};
8 bool f=true;
9 //数组的交换
10 void fun(int a[12][12],int b[12][12])
11 {
12 for (int i=1;i<=n;i++)
13 for (int j=1;j<=n;j++)
14 a[i][j]=b[i][j];
15
16 }
17 void dfs(int x1,int y1,int sum,int p)
18 {
19 if(map[x1][y1]==3&&p>=0)
20 {
21 // 这里要注意，我是从5开始的，搜到3时，p应该是0以上，
22 //刚开始是没搞清楚，p大于0,wa了几次，就是没找到错误！
23 if(Min>sum)Min=sum;
24 //cout<<sum<<endl;
25 f=false;
26 return;
27 }
28 int dx,dy;
29 for (int i=0;i<4;i++)
30 {
31 dx=x1+x[i]; dy=y1+y[i];
32 if (map[dx][dy]!=0&&tp[dx][dy]==0&&p>=1)
33 {
34 if(map[dx][dy]==4)
35 {
36 map[dx][dy]=0;
37 int temp=p;
38 p=5;
39 // cout<<p<<' '<<dx<<' '<<dy<<endl;
40 //输出路径，偏于查找当前的坐标位置和剩余时间p
41 fun(tt,tp);
42 memset(tp,0,sizeof(tp));
43 //到4是可以往回搜的，所以前面的走过的路径应该移除标记
44 //用数组tt记住前面走过的路径，以便于后面的搜索
45 tp[dx][dy]=1;
46 dfs(dx,dy,sum+1,p);
47 //出来混的，是要还的！这里也一样！
48 map[dx][dy]=4;
49 tp[dx][dy]=0;
50 p=temp;
51 fun(tp,tt);
52 }
53 else
54 {
55 tp[dx][dy]=1;
56 //cout<<"->"<<p<<' '<<dx<<' '<<dy<<endl;
57 //输出路径，偏于查找当前的坐标位置和剩余时间p
58 dfs(dx,dy,sum+1,p-1);
59 tp[dx][dy]=0;
60 }
61 }
62 }
63 }
64 int main()
65 {
66 int t;
67 cin>>t;
68 while (t--)
69 {
70 memset(map,0,sizeof(map));
71 memset(tp,0,sizeof(tp));
72 cin>>n>>m;
73 f=true;
74 int x1,y1,x2,y2;
75 for (int i=1;i<=n;i++)
76 for (int j=1;j<=m;j++)
77 {
78 cin>>map[i][j];
79 if(map[i][j]==2)x1=i,y1=j;
80 //if(map[i][j]==3)x2=i,y2=j;
81 }
82 Min=0xffffff,sum=0;
83 int p=5;
84 map[x1][y1]=0;
85 dfs(x1,y1,sum,5);
86 if(!f)cout<<Min<<endl;
87 else cout<<-1<<endl;
88 }
89 return 0;
90 }
91
posted @
2010-11-09 16:59 路修远 阅读(1489) |
评论 (0) |
编辑 收藏
“九宫填数“也叫“九方数”，古代称为“九宫算”。九宫填数是将九个有效数字填在九个方位格子里，要使每行、每列和每条对角线上的和都相等，即：横的三个数之和、竖的三个数之和与斜的三个数之和，都相等。在解这个题之前，先把九宫的方位问题明确了，以便讲行具体的阐述。
这个方位的确定与看地图的方位是一致的。由于要把1—9这九个数填在适当的格子里，这九个数之和是45，无论是横、竖、斜都是三个数，把45平均分成三行，每行三个数的和都是15（包括横、竖、斜）。每三个数的情况：横有3种，竖有3种，斜有2种，共8种。
只要知道三个数就可以枚举所有的数了；
1 #include<iostream>
2 using namespace std;
3 int b[10],a[10];
4 int main(){
5 int f = 0;
6 for (int i=1;i<10;i++){
7 if(i!=5)b[1]=i;
8 for (int j=1;j<10;j++)
9 {
10 b[5] = 5;
11 if(j!=i&&j!=5&&i!=5){
12 b[2] = j;
13 b[8] = 15 - b[2] - b[5];
14 b[3] = 15 - b[1] - b[2];
15 b[9] = 15 - b[1] - b[5];
16 b[7] = 15 - b[3] - b[5];
17 b[4] = 15 - b[1] - b[7];
18 b[6] = 15 - b[3] - b[9];
19 if(b[4]+b[5]+b[6]==15&&b[7]+b[8]+b[9]==15)
20 {
21 f = 0;
22 memset(a,0,sizeof(a));
23 for (int k=1;k<10;k++) a[b[k]]++;
24 for (int k=1;k<10;k++) if(a[k]<=0||a[k]>1){f = 1;break;}
25 if(f==0){
26 for (int k=1;k<10;k++)
27 {
28 cout<< b[k] <<' ';
29 if(k%3==0)cout << endl;
30 }
31 cout << endl;
32 }
33 }
34 }
35 }
36 }
37 system("pause");
38 return 0;
39 }
40
posted @
2010-06-30 08:14 路修远 阅读(479) |
评论 (0) |
编辑 收藏
Problem Description
RSA is one of the most powerful methods to encrypt data. The RSA algorithm is described as follow:
> choose two large prime integer p, q
> calculate n = p × q, calculate F(n) = (p - 1) × (q - 1)
> choose an integer e(1 < e < F(n)), making gcd(e, F(n)) = 1, e will be the public key
> calculate d, making d × e mod F(n) = 1 mod F(n), and d will be the private key
You can encrypt data with this method :
C = E(m) = me mod n
When you want to decrypt data, use this method :
M = D(c) = cd mod n
Here, c is an integer ASCII value of a letter of cryptograph and m is an integer ASCII value of a letter of plain text.
Now given p, q, e and some cryptograph, your task is to "translate" the cryptograph into plain text.
Input
Each case will begin with four integers p, q, e, l followed by a line of cryptograph. The integers p, q, e, l will be in the range of 32-bit integer. The cryptograph consists of l integers separated by blanks.
Output
For each case, output the plain text in a single line. You may assume that the correct result of plain text are visual ASCII letters, you should output them as visualable letters with no blank between them.
Sample Input
101 103 7 11
7716 7746 7497 126 8486 4708 7746 623 7298 7357 3239
Sample Output
I-LOVE-ACM.
以为要数组，想想，不是那么回事！
挺简单的~~
1 #include<iostream>
2 using namespace std;
3 int main(){
4 int p,q,e,t;
5 while (cin>>p>>q>>e>>t)
6 {
7 int n = p*q,fn = (p-1)*(q-1);
8 int d =1;
9 while ((d*e)%fn!=1)d++;
10 int c;
11 for (int i=0;i<t;i++)
12 {
13 cin>>c;
14 int temp=1;
15 for (int j=1;j<=d;j++)
16 {
17 temp*=c;
18 temp%=n;
19 }
20 cout<<char(temp);
21 }
22 cout<<endl;
23 }
24 return 0;
25 }
posted @
2010-06-26 18:59 路修远 阅读(456) |
评论 (0) |
编辑 收藏