hacker cup 2015 资格赛
分类:
IT文章
•
2023-11-02 23:02:11
A：交换一个数的两位，问能得到最大和最小的数是多少。
水题：
![]()
1 // File Name: a.cpp
2 // Author: darkdream
3 // Created Time: 2015年01月10日 星期六 17时16分44秒
4
5 #include<vector>
6 #include<list>
7 #include<map>
8 #include<set>
9 #include<deque>
10 #include<stack>
11 #include<bitset>
12 #include<algorithm>
13 #include<functional>
14 #include<numeric>
15 #include<utility>
16 #include<sstream>
17 #include<iostream>
18 #include<iomanip>
19 #include<cstdio>
20 #include<cmath>
21 #include<cstdlib>
22 #include<cstring>
23 #include<ctime>
24 #define LL long long
25
26 using namespace std;
27 LL a[20];
28 int T;
29 LL SP(LL i , LL j, LL tmp)
30 {
31 int x =(tmp)/a[i] % 10 ;
32 int y =(tmp)/a[j] % 10 ;
33 if(x == 0 && j == T)
34 return tmp;
35 return tmp - x * a[i] - y*a[j] + y *a[i] + x*a[j];
36 }
37 int count(LL tmp)
38 {
39 int num = 0 ;
40 while(tmp)
41 {
42 num ++;
43 tmp/= 10;
44 }
45 return num ;
46 }
47 int main(){
48 int t ;
49 scanf("%d",&t);
50 a[1] = 1;
51 for(int i = 2;i <= 13 ;i++)
52 {
53 a[i] = a[i-1]*10;
54 }
55 for(int ca = 1 ; ca <= t ;ca ++)
56 {
57 LL tmp;
58 scanf("%lld",&tmp);
59 LL mx = tmp;
60 LL mi = tmp;
61 T = count(tmp);
62 for(int i = 1;i <= T;i ++)
63 for(int j = i + 1;j <= T ;j ++)
64 {
65 LL now = SP(i,j,tmp);
66 if(now > mx)
67 mx = now;
68 if(now < mi)
69 mi = now;
70 }
71 printf("Case #%d: %lld %lld
",ca,mi,mx);
72 }
73
74 return 0;
75 }
View Code
B：给你n件物品，每个物品都有三种属性值，问从中选取任意件，能不能使得最后得到确定值
解题思路：二进制枚举
解题代码：
![]()
1 // File Name: b.cpp
2 // Author: darkdream
3 // Created Time: 2015年01月10日 星期六 17时55分37秒
4
5 #include<vector>
6 #include<list>
7 #include<map>
8 #include<set>
9 #include<deque>
10 #include<stack>
11 #include<bitset>
12 #include<algorithm>
13 #include<functional>
14 #include<numeric>
15 #include<utility>
16 #include<sstream>
17 #include<iostream>
18 #include<iomanip>
19 #include<cstdio>
20 #include<cmath>
21 #include<cstdlib>
22 #include<cstring>
23 #include<ctime>
24 #define LL long long
25
26 using namespace std;
27 int Ga,Gb,Gc;
28 int a[30],b[30],c[30];
29 bool solve(int k)
30 {
31 int t= 0 ;
32 int ta,tb,tc;
33 ta = tb = tc = 0 ;
34 while(k)
35 {
36 if(k % 2)
37 {
38 ta += a[t];
39 tb += b[t];
40 tc += c[t];
41 }
42 k /= 2;
43 t ++ ;
44 }
45 //<F5> printf("%d %d %d
",ta,tb,tc);
46 if(ta == Ga && tb == Gb&& tc == Gc)
47 {
48 return 1;
49 }
50 return 0 ;
51 }
52 int main(){
53 int T;
54 scanf("%d",&T);
55 for(int ca = 1;ca <= T; ca ++)
56 {
57 scanf("%d %d %d",&Ga,&Gb,&Gc);
58 int n;
59 scanf("%d",&n);
60 for(int i= 0;i < n;i++)
61 {
62 scanf("%d %d %d",&a[i],&b[i],&c[i]);
63 }
64 int total = (1 << n)-1;
65 int ok = 0 ;
66 for(int i =0 ;i <= total;i ++)
67 {
68 if(solve(i))
69 {
70 ok = 1;
71 break;
72 }
73 }
74 if(ok)
75 printf("Case #%d: yes
",ca);
76 else printf("Case #%d: no
",ca);
77 }
78 return 0;
79 }
View Code
![]()
1 // File Name: c.cpp
2 // Author: darkdream
3 // Created Time: 2015年01月10日 星期六 20时10分04秒
4
5 #include<vector>
6 #include<list>
7 #include<map>
8 #include<set>
9 #include<deque>
10 #include<stack>
11 #include<bitset>
12 #include<algorithm>
13 #include<functional>
14 #include<numeric>
15 #include<utility>
16 #include<sstream>
17 #include<iostream>
18 #include<iomanip>
19 #include<cstdio>
20 #include<cmath>
21 #include<cstdlib>
22 #include<cstring>
23 #include<ctime>
24 #define LL long long
25
26 using namespace std;
27 int mp[5][105][105];
28 int bex , bey ;
29 int enx, eny ;
30 int n , m;
31 int vis[105][105][105];
32 void fillmap(int k )
33 {
34 for(int i = 1;i <= n;i ++)
35 {
36 for(int j = 1;j <= m ;j ++)
37 {
38 if(mp[k][i][j] == 2)
39 {
40 int x = i + 1;
41 while(mp[k][x][j] == 1 || mp[k][x][j] == -1)
42 {
43 mp[k][x][j] = -1;
44 x ++ ;
45 }
46 } else if(mp[k][i][j] == 3)
47 {
48 int x = i - 1;
49 while(mp[k][x][j] == 1 || mp[k][x][j] == -1)
50 {
51 mp[k][x][j] = -1;
52 x -- ;
53 }
54 } else if(mp[k][i][j] == 4)
55 {
56 int x = j + 1;
57 while(mp[k][i][x] == 1 || mp[k][i][x] == -1)
58 {
59 mp[k][i][x] = -1;
60 x ++;
61 }
62 }else if(mp[k][i][j] == 5)
63 {
64 int x = j -1;
65 while(mp[k][i][x] == 1 || mp[k][i][x] == -1)
66 {
67 mp[k][i][x] = -1;
68 x --;
69 }
70 }
71 }
72 }
73 }
74 void print(int k )
75 {
76 for(int i = 1;i <= n;i ++)
77 {
78 for(int j = 1;j <= m ;j ++)
79 {
80 printf("%d ",mp[k][i][j]);
81 }
82 printf("
");
83 }
84 printf("
");
85 }
86 void changeto(int k )
87 {
88 for(int i = 1;i <= n;i ++)
89 {
90 for(int j = 1;j <= m;j ++)
91 {
92 if(mp[k-1][i][j] == 0)
93 mp[k][i][j] == 0;
94 else if(mp[k-1][i][j] == 1)
95 mp[k][i][j] = 1;
96 else if(mp[k-1][i][j] == 2)
97 mp[k][i][j] = 5;
98 else if(mp[k-1][i][j] == 3)
99 mp[k][i][j] = 4;
100 else if(mp[k-1][i][j] == 4)
101 mp[k][i][j] = 2;
102 else if(mp[k-1][i][j] == 5)
103 mp[k][i][j] = 3;
104 else if(mp[k-1][i][j] == -1)
105 mp[k][i][j] = 1;
106 }
107 }
108 fillmap(k);
109 //print(k);
110 }
111 struct node{
112 int x,y,step,flag;
113 node(){
114
115 }
116 node(int _x ,int _y ,int _step ,int _flag)
117 {
118 x = _x;
119 y = _y;
120 step = _step;
121 flag = _flag;
122 }
123 }qu[101000];
124 int xadd[] = {1,-1,0,0};
125 int yadd[] = {0,0,-1,1};
126 int bfs()
127 {
128 memset(vis,0,sizeof(vis));
129 qu[1] = node(bex,bey,0,0);
130 vis[0][bex][bey] = 1;
131 int l = 1;
132 int r = 1;
133 while(l <= r)
134 {
135 // printf("%d %d
",qu[l].x,qu[l].y);
136 if(qu[l].x == enx && qu[l].y == eny)
137 {
138 return qu[l].step;
139 }
140 int k = (qu[l].flag + 1)%4;
141 for(int i = 0;i <= 3; i ++)
142 {
143 int tx = qu[l].x + xadd[i];
144 int ty = qu[l].y + yadd[i];
145 if(mp[k][tx][ty] == 1 && vis[k][tx][ty] != 1)
146 {
147 vis[k][tx][ty] = 1;
148 r ++ ;
149 qu[r] = node(tx,ty,qu[l].step + 1, k);
150 }
151 }
152 l ++ ;
153 }
154 return 0 ;
155 }
156 int main(){
157 freopen("in.txt","r",stdin);
158 freopen("out","w",stdout);
159 int T;
160 scanf("%d",&T);
161 for(int ca = 1; ca <= T; ca ++)
162 {
163 scanf("%d %d",&n,&m);
164 char str[1000];
165 memset(mp,0,sizeof(mp));
166 for(int i = 1;i <= n;i ++)
167 {
168 scanf("%s",&str[1]);
169 for(int j = 1;j <= m;j ++)
170 {
171 if(str[j] == 'S')
172 {
173 bex = i ;
174 bey = j ;
175 mp[0][i][j] = 1;
176 }else if(str[j] == 'G')
177 {
178 mp[0][i][j] = 1;
179 enx = i ;
180 eny = j;
181 }else if(str[j] == '#')
182 {
183 mp[0][i][j] = 0 ;
184 }else if(str[j] == '.')
185 mp[0][i][j] = 1 ;
186 else if(str[j] == 'v')
187 mp[0][i][j] = 2;
188 else if(str[j] == '^')
189 mp[0][i][j] =3;
190 else if(str[j] == '>')
191 mp[0][i][j] =4 ;
192 else if(str[j] == '<')
193 mp[0][i][j] =5;
194 }
195 }
196
197 fillmap(0);
198 changeto(1);
199 changeto(2);
200 changeto(3);
201 //for(int i = 0 ;i <= 3;i ++ )
202 // print(i);
203 int ok = bfs();
204 printf("Case #%d: ",ca);
205 if(ok == 0 )
206 printf("impossible
");
207 else printf("%d
",ok);
208 }
209 return 0;
210 }
