1.冬冬走迷宫
time limit:1s
memory limit:128 MB
众所周知，冬冬是一个土豪以及游戏*玩家。最近他趁着暑假，买了许多游戏来消遣。可是当他把所有游戏都通关了以后，感到无敌是多么寂寞，必须靠经典才能满足他。于是他又玩起了走迷宫的小游戏。
走迷宫可以简化为一个矩阵，里面含n*m个格子。有些格子是可以进入并且通过的，有些格子内含障碍物，是不能进入通过它的。我们的任务就是在给定一个起点S和一个终点T后，选择一个不经过障碍物以及走出矩阵边界的方案，把自己控制的角色从S走到T。
然而冬冬身经百战，不知道比其他人高到哪里去了，因此他总会选择最短的路径来走完这个迷宫。可是他不能确定自己的路径是不是最短的，因此他希望你能帮助他，给出每个迷宫的最短路径长度(即从S到T经过（包含S和T）的格子数）。
作为新晋ACMer，你能帮助冬冬完成这个任务吗？
Input
多组数据输入，保证格子总数不超过100w。
第一行是两个正整数n，m，代表矩阵的高度和宽度。其中0≤n,m≤100.
接下来n行m列，给出迷宫每个格子的情况。'S'代表起点，'T'代表终点，'#'代表障碍物，'.'代表可通行区域。
Output
对于每组数据，输出一行从S到T的最短路径的长度。若无从S到T的路径，则输出“Impossible”。
Sample Input
5 6
S.....
#.###.
##.T..
#.###.
#.....
2 9
S.#......
###T####.
Sample Output
10
Impossible
一道很基础的bfs题，除了迷宫的地图数组外，加入标记数组，步数数组，bfs时让每个格子向四周扩展，把没有标记的格子以及他的步数加入队列中并标记他们，还需在步数数组上记录到该点的步数，直至队列中没有元素为止（或者bfs到T点就跳出循环）。最后检查下终点T有无被标记过。没有则是Impossible，有则输出T点的步数。
1 #include<cstdio>View Code
2 #include<iostream>
3 #include<cstring>
4 #include<queue>
5 #define clr_1(x) memset(x,-1,sizeof(x))
6 #define clr(x) memset(x,0,sizeof(x))
7 using namespace std;
8 struct node
9 {
10 int x,y,step;
11 }u,v;
12 queue<node> que;
13 char s[200];
14 int map[200][200];
15 int stepm[200][200];
16 int dirx[4]={0,0,-1,1},diry[4]={1,-1,0,0};
17 int n,m,t,k,sx,sy,tx,ty;
18 void init()
19 {
20 clr(map);
21 for(int i=1;i<=n;i++)
22 {
23 scanf("%s",s);
24 for(int j=0;j<strlen(s);j++)
25 {
26 if(s[j]=='S')
27 {
28 sx=i;
29 sy=j+1;
30 map[i][j+1]=1;
31 }
32 if(s[j]=='T')
33 {
34 tx=i;
35 ty=j+1;
36 map[i][j+1]=1;
37 }
38 if(s[j]=='.')
39 {
40 map[i][j+1]=1;
41 }
42 }
43 }
44 while(!que.empty())
45 que.pop();
46 return ;
47 }
48 void bfs()
49 {
50 while(!que.empty())
51 {
52 u=que.front();
53 que.pop();
54 for(int i=0;i<4;i++)
55 {
56 v=u;
57 v.x+=dirx[i];
58 v.y+=diry[i];
59 v.step++;
60 if(map[v.x][v.y]==1)
61 {
62 map[v.x][v.y]=0;
63 stepm[v.x][v.y]=v.step;
64 que.push(v);
65 }
66 }
67
68 }
69 return ;
70 }
71 int main()
72 {
73 freopen("1.in","r",stdin);
74 freopen("1.out","w",stdout);
75 while(scanf("%d%d",&n,&m)!=EOF)
76 {
77 init();
78 u.x=sx;
79 u.y=sy;
80 u.step=1;
81 map[sx][sy]=0;
82 que.push(u);
83 bfs();
84 if(map[tx][ty]==1)
85 {
86 printf("Impossible\n");
87 }
88 else
89 {
90 printf("%d\n",stepm[tx][ty]);
91 }
92 }
93 return 0;
94 }
2.冬冬沉迷走迷宫
time limit:2s
memory limit:128 MB
众所周知，冬冬是一个土豪以及游戏*玩家。最近他趁着暑假，买了许多游戏来消遣。可是当他把所有游戏都通关了以后，感到无敌是多么寂寞，必须靠经典才能满足他。于是他又玩起了走迷宫的小游戏。
走迷宫可以简化为一个矩阵，里面含n*m个格子。有些格子是可以进入并且通过的，有些格子内含障碍物，是不能进入通过它的。我们的任务就是在给定一个起点S和一个终点T后，选择一个不经过障碍物以及走出矩阵边界的方案，把自己控制的角色从S走到T。
然而冬冬身经百战，不知道比其他人高到哪里去了，因此他总会选择最短的路径来走完这个迷宫。可是他不能确定自己的路径是不是最短的，并且他想知道最完美的方案一共有几种。因此他希望你能帮助他，给出每个迷宫的最短路径长度(即从S到T经过（包含S和T）的格子数）以及该长度下一共有几种不同的走法。
作为新晋ACMer，你能帮助冬冬，完成这个任务吗？
Input
多组数据输入，保证不超过2组数据。
第一行是两个正整数n，m，代表矩阵的高度和宽度。其中2≤n,m≤9。
接下来n行m列，给出迷宫每个格子的情况。'S'代表起点，'T'代表终点，'#'代表障碍物，'.'代表可通行区域，其中S一定在左上角，也就是(0,0)的位置；T一定在右下角，也就是(n-1,m-1)的位置。
Output
对于每组数据，输出一行从S到T的最短路径的长度，以及该长度下的方案数，保证答案在long long范围内。若无从S到T的路径，则输出“Impossible”。
Sample Input
5 6
S.....
#.###.
##....
#.###.
#....T
2 9
S.#......
########T
Sample Output
10 1
Impossible
当初准备写个插头dp来着的，后来发现bfs也能做。把上题的所有数组保留加入方案数数组。起初S的方案数为1，其余不变。当bfs扩展到某个格子时，若该格子未被标记，记录从之前格子扩展到该格子的步数，该格子方案数为扩展到他的格子的方案数+1，加入队列。若已被标记，且记录的步数和现在扩展到该格子时的步数相同，则在原先方案数上加上这次扩展该格子获得的方案数。若记录的步数比现在扩展到该格子时的步数少，则不处理。这样做一遍bfs之后，跟上面的做法相同，检查下终点T有无被标记过。没有则是Impossible，有则输出T点的步数和方案数。
插头dp的话左上角要建立一个独立插头，右下角要截止一个独立插头。其他格子在dp时有且仅存在一个独立插头，转移的时候和独立插头的转移一样，就是不能创建独立插头以及截止独立插头。最后dp结束检查最后一个格子步数最小的状态的方案数，若没有则是Impossible，有即为答案。
标程用插头dp写的：
1 #include<cstdio>View Code
2 #include<iostream>
3 #include<cstring>
4 #define clr(x) memset(x,0,sizeof(x))
5 #define clr_1(x) memset(x,-1,sizeof(x))
6 #define LL long long
7 #define HASH 10007
8 #define STATE 1000010
9 using namespace std;
10 struct hashmap//hash表存状态
11 {
12 int size;
13 int next[STATE],head[HASH];
14 LL state[STATE],len[STATE];
15 LL fas[STATE];
16 void init()//清空
17 {
18 size=0;
19 clr_1(head);
20 }
21 void add(LL st,LL length,LL solu)//状态加入
22 {
23 int k=(st*10000+length)%HASH;
24 for(int i=head[k];i!=-1;i=next[i])
25 if(st==state[i] && length==len[i])
26 {
27 fas[i]+=solu;
28 return;
29 }
30 next[++size]=head[k];
31 fas[size]=solu;
32 state[size]=st;
33 len[size]=length;
34 head[k]=size;
35 return ;
36 }
37 }dp[2];
38 int maped[40][40];
39 int code[40];
40 char s[100];
41 void init(int n,int m)//初始化值，读入maped
42 {
43 clr(maped);
44 for(int i=1;i<=n;i++)
45 {
46 scanf("%s",s);
47 for(int j=0;j<strlen(s);j++)
48 {
49 if(s[j]=='.' || s[j]=='S' || s[j]=='T')
50 {
51 maped[i][j+1]=1;
52 }
53 }
54 }
55 return ;
56 }
57 void decode(LL st,int *code,int m)//解码，括号序列
58 {
59 for(int i=m;i>=0;i--)
60 {
61 code[i]=st&3;
62 st>>=2;
63 }
64 return ;
65 }
66 LL encode(int *code,int m)//编码，括号序列
67 {
68 LL st=0;
69 for(int i=0;i<=m;i++)
70 {
71 st<<=2;
72 st|=code[i];
73 }
74 return st;
75 }
76 void shift(int *code,int m)//左移操作
77 {
78 for(int i=m;i>0;i--)
79 code[i]=code[i-1];
80 code[0]=0;
81 return ;
82 }
83 void dpblank(int i,int j,int cnt,int n,int m)//空格子状态转移
84 {
85 int top,left,up;
86 if(i==1 &&j==1)//i=1 且 j=1时加入只有下独立插头 和 右独立插头的状态
87 {
88 decode(dp[cnt].state[1],code,m);
89 if(maped[i][j+1])
90 {
91 code[j-1]=0;
92 code[j]=3;
93 dp[cnt^1].add(encode(code,m),dp[cnt].len[1]+1,dp[cnt].fas[1]);
94 }
95 if(maped[i+1][j])
96 {
97 code[j-1]=3;
98 code[j]=0;
99 if(j==m) shift(code,m);
100 dp[cnt^1].add(encode(code,m),dp[cnt].len[1]+1,dp[cnt].fas[1]);
101 }
102 return ;
103 }
104 if(i==n &&j==m)//i=n 且 j=m时截止单个独立插头的状态
105 {
106 for(int it=1;it<=dp[cnt].size;it++)
107 {
108 decode(dp[cnt].state[it],code,m);
109 code[j-1]=code[j]=0;
110 if(j==m) shift(code,m);
111 dp[cnt^1].add(encode(code,m),dp[cnt].len[it]+1,dp[cnt].fas[it]);
112 }
113 return ;
114 }
115 for(int it=1;it<=dp[cnt].size;it++)
116 {
117 decode(dp[cnt].state[it],code,m);
118 left=code[j-1];
119 up=code[j];
120 if(left && up)//上插头和左插头都存在
121 {
122 if(left==3 || up==3)//存在一个独立插头
123 {
124 if(up==2|| left==2)//若另一个插头为右括号插头，则找到对应的左括号插头变为独立插头
125 {
126 top=0;
127 for(int k=j-2;k>=0;k--)
128 {
129 if(code[k]==2)
130 top++;
131 if(code[k]==1)
132 if(top>0)
133 top--;
134 else
135 {
136 code[k]=3;
137 break;
138 }
139 }
140 }
141 else if(up==1 ||left==1)//若另一个插头为左括号插头，则找到对应的右括号插头变为独立插头
142 {
143 top=0;
144 for(int k=j+1;k<=m;k++)
145 {
146 if(code[k]==1)
147 top++;
148 if(code[k]==2)
149 if(top>0)
150 top--;
151 else
152 {
153 code[k]=3;
154 break;
155 }
156 }
157 }
158 code[j]=code[j-1]=0;
159 if(j==m) shift(code,m);
160 dp[cnt^1].add(encode(code,m),dp[cnt].len[it]+1,dp[cnt].fas[it]);
161 }
162 else if(left!=up)//两个括号插头
163 {
164 if(left==1)//左右括号插头，不允许形成回路
165 continue;
166 else//右左括号插头直接去掉
167 {
168 code[j]=code[j-1]=0;
169 if(j==m) shift(code,m);
170 dp[cnt^1].add(encode(code,m),dp[cnt].len[it]+1,dp[cnt].fas[it]);
171 }
172 }
173 else
174 {
175 if(left==2)//都是左括号插头，找到对应的第一个右括号插头变为左括号插头
176 {
177 top=0;
178 for(int k=j-2;k>=0;k--)
179 {
180 if(code[k]==2)
181 top++;
182 if(code[k]==1)
183 if(top>0)
184 top--;
185 else
186 {
187 code[k]=2;
188 break;
189 }
190 }
191 }
192 else//都是右括号插头，找到对应的第一个左括号插头变为右括号插头
193 {
194 top=0;
195 for(int k=j+1;k<=m;k++)
196 {
197 if(code[k]==1)
198 top++;
199 if(code[k]==2)
200 if(top>0)
201 top--;
202 else
203 {
204 code[k]=1;
205 break;
206 }
207 }
208 }
209 code[j]=code[j-1]=0;
210 if(j==m) shift(code,m);
211 dp[cnt^1].add(encode(code,m),dp[cnt].len[it]+1,dp[cnt].fas[it]);
212 }
213 }
214 else if(left || up)//仅有一个插头，则延伸插头
215 {
216 if(left) top=left;
217 else top=up;
218 if(maped[i][j+1])//右延伸插头
219 {
220 code[j-1]=0;
221 code[j]=top;
222 dp[cnt^1].add(encode(code,m),dp[cnt].len[it]+1,dp[cnt].fas[it]);
223 }
224 if(maped[i+1][j])//下延伸插头
225 {
226 code[j-1]=top;
227 code[j]=0;
228 if(j==m) shift(code,m);
229 dp[cnt^1].add(encode(code,m),dp[cnt].len[it]+1,dp[cnt].fas[it]);
230 }
231 }
232 else//没有插头
233 {
234 if(maped[i+1][j] && maped[i][j+1])//下插头和左插头
235 {
236 code[j-1]=1;
237 code[j]=2;
238 dp[cnt^1].add(encode(code,m),dp[cnt].len[it]+1,dp[cnt].fas[it]);
239 }
240 //可经过可不经过点则可以保持原样，没有插头
241 code[j-1]=code[j]=0;
242 if(j==m) shift(code,m);
243 dp[cnt^1].add(encode(code,m),dp[cnt].len[it],dp[cnt].fas[it]);
244 }
245 }
246 return ;
247 }void dpblock(int i,int j,int cnt,int n,int m)//障碍格子状态转移
248 {
249 for(int it=1;it<=dp[cnt].size;it++)
250 {
251 decode(dp[cnt].state[it],code,m);
252 if(j==m) shift(code,m);
253 dp[cnt^1].add(encode(code,m),dp[cnt].len[it],dp[cnt].fas[it]);
254 }
255 return ;
256 }
257 void solve(int n,int m)
258 {
259 int cnt=0;
260 LL ans,minfas;
261 dp[cnt].init();
262 dp[cnt].add(0,0,1);
263 for(int i=1;i<=n;i++)
264 {
265 for(int j=1;j<=m;j++)
266 {
267 dp[cnt^1].init();
268 if(maped[i][j]==1)
269 dpblank(i,j,cnt,n,m);
270 else
271 dpblock(i,j,cnt,n,m);
272 cnt^=1;
273 /* for(int it=1;it<=dp[cnt].size;it++)
274 {
275 decode(dp[cnt].state[it],code,m);
276 for(int k=0;k<=m;k++)
277 printf("%d:%d ",k,code[k]);
278 printf("fas:%lld\n",dp[cnt].fas[it]);
279 }
280 printf("\n"); */
281 }
282 }
283 if(dp[cnt].size==0)
284 printf("Impossible\n");
285 else
286 {
287 ans=0x3f3f3f3f;
288 for(int i=1;i<=dp[cnt].size;i++)
289 {
290 if(dp[cnt].len[i]<ans)
291 {
292 ans=dp[cnt].len[i];
293 minfas=dp[cnt].fas[i];
294 }
295 }
296 printf("%lld %lld\n",ans,minfas);
297 }
298 return ;
299 }
300 int main()
301 {
302 int n,m,kase=0;
303 while(scanf("%d%d",&n,&m)!=EOF)
304 {
305 init(n,m);
306 solve(n,m);
307 }
308 return 0;
309 }
3.数论只会GCD
time limit:3s
memory limit:512 MB
林学姐从初中就开始参加OI(信息学竞赛),并且当时花了好久写出来了.可爱的林学姐最喜欢GCD问题了,如果你做出来这道题,一定能得到林学姐的芳心.
定义函数:对于正整数,H(x)表示x的素数因子的种类.
例如:2=2, H(2)=1, 2的素数因子只有一种; 6=2*3, H(6)=2, 6的素数因子有2,3两种; 9=3*3, H(9)=1, 9的素数因子只有一种; 12=2*2*3, H(9)=2, 12的素数因子有两种.
每次查询一个范围[L,R],求MAX(GCD(H(i),H(j))),(L<=i<j<<=R).
GCD(a,b)是指a,b两个数最大公约数
Input
多组数据,第一个数为查询次数T,接下来T行每行有一个L,R.
T<=1000000
1<L,R<=1000000
Output
一行,MAX(GCD(H(i),H(j)))
Sample Input
2
2 3
2 5
Sample Output
1
1
看起来100w挺大的，然而每个数包含的不同的质数因子个数算下最多才7个(2*3*5*7*11*13*17*19=9,699,690)，写一个线性筛O(n)的复杂度算下每个数不同质数因子个数，或者埃氏筛法求解不超过O(7*n)的时间复杂度。题目时间放宽写埃氏筛法也能过。把100w的数的进行预处理，并且统计下含质因子数量不同的数的个数的前缀和。之后后再进行读入，用常数的时间算出MAX(GCD(H(i),H(j))),(L<=i<j<<=R)即可，一堆if判断下就行。
1 // code by xadView Code
2 #include <bits/stdc++.h>
3 using namespace std;
4
5 int F[1000010];
6 bool flag[1000010];
7 int S[7][10000010];
8 void init()
9 {
10 for(int i = 2; i <= 1000000; i++) if(!flag[i]){
11 F[i]++;
12 for(int j = i + i; j <= 1000000; j += i) {
13 flag[j] = true;
14 F[j]++;
15 }
16 }
17 for(int i = 2; i <= 1000000; i++) {
18 for(int j = 0; j < 7; j++) {
19 S[j][i] = S[j][i - 1] + (F[i] == j + 1);
20 }
21 }
22 }
23 int main()
24 {
25 init();
26 int T, l, r;
27 scanf("%d", &T);
28 while(T--){
29 scanf("%d%d", &l, &r);
30 assert(l != r);
31 int cnt[8];
32 memset(cnt, 0, sizeof(cnt));
33 for(int i = 0; i < 7; i++) {
34 cnt[i + 1] = S[i][r] - S[i][l - 1];
35 }
36 int ret = 1;
37 if(cnt[2] + cnt[4] + cnt[6]>=2) ret = 2;
38 if(cnt[3] + cnt[6] >= 2) ret = 3;
39 if(cnt[4] >= 2) ret = 4;
40 if(cnt[5] >= 2) ret = 5;
41 if(cnt[6] >= 2) ret = 6;
42 if(cnt[7] >= 2) ret = 7;
43 printf("%d\n", ret);
44 }
45 return 0;
46 }
4.宣区校内快递点
time limit:1s
memory limit:128MB
每次都从校外取快递对同学们来说是一件很累的事情，因此快递点的老板们决定在校内设立几个快递点，但要遵守一个规则就是：使得每个宿舍楼都可以通过在道路上最多d公里到达一个快递点。宿舍楼的位置在本题里是假设的，与真实情况无关。
假设全校一共有n个宿舍，编号从1到n，初始时有n - 1条道路相连。所有道路长1公里。最初可以从一个宿舍到使用这些道路连接的任何其他宿舍。本校一共要设立k个快递点，每个快递点位置就是在n个宿舍中的一个。特别是宿舍整个网络结构符合上述快递老板们遵守的规则。另请注意，一个宿舍可以有多个快递点。
然而，冬冬同学感觉没必要建立n-1条路，为了尽可能多地关闭道路来尽量减少道路维护成本，各位大佬快来帮助冬冬找到最多可以关闭的道路。但我们始终都要遵守一个规则，就是使得每个宿舍楼都可以通过在道路上最多d公里到达一个快递点。
Input
第一行包含三个整数n，ķ，和d（2≤ n≤3·10^5，1≤ ķ ≤3*10^5，0≤ d ≤ n - 1）分别表示宿舍的数量，设立快递点的数量，上述规则中距离限制在d公里内。
第二行包含ķ个整数，p1， p2，...， pķ（1≤ pi≤ n） 表示快递点位于宿舍的编号。
在我以下的第n - 1行包含两个整数u和v （1≤ u， v ≤ n，u ≠ v）表示宿舍u和v间建立一条道路，分别为道路1到道路n-1。从1开始编号（1，2，3…)
只有通过道路才可以从一个宿舍到任何其他宿舍。另外，从任何一个宿舍都可以到达d公里内的一个快递点。
Output
输出包括一行，打印一个整数，表示可以被关闭道路的最大数量。
注：此题使用多组输入。
Sample Input
6 2 4
1 6
1 2
2 3
3 4
4 5
5 6
6 3 2
1 5 6
1 2
1 3
1 4
1 5
5 6
Sample Output
1
2
这题有点问题。本意是让大家把所有快递点加入到队列中，做一遍bfs。并且对bfs中访问过的点做个标记，然后在bfs中删去边的终点为标记点的边，剩下的就是删去边数最大时的边的数量了。
1 //code by fhsView Code
2 #include <bits/stdc++.h>
3 #include <iostream>
4 #include <vector>
5 #include <algorithm>
6 #include <map>
7 #include <set>
8 #include <queue>
9
10 using namespace std;
11
12 typedef long long int64;
13 const int kMaxN= 3e5+10;
14 const int kInf = (1<<30);
15
16 int n, k, d;
17 bool police[kMaxN];
18 vector<int> T[kMaxN];
19 vector<pair<int,int>> edges;
20 int from[kMaxN];
21
22 void bfs() {
23 queue<int> Q;
24 for (int i = 1; i <= n; ++i) {
25 if (police[i]) {
26 from[i] = i;
27 Q.push(i);
28 }
29 }
30
31 while (!Q.empty()) {
32 int x = Q.front();
33 Q.pop();
34
35 for (int i = 0;i < T[x].size();++ i) {
36 int y = T[x][i];
37 if (from[y] == 0) {
38 from[y] = from[x];
39 Q.push(y);
40 }
41 }
42 }
43 }
44
45 void solve() {
46 memset(police,0,sizeof(police));
47 for(int i = 0;i <= kMaxN;++ i)
48 T[i].clear();
49 edges.clear();
50 memset(from,0,sizeof(from));
51 scanf("%d %d %d", &n, &k, &d);
52 for (int i = 1; i <= k; ++i) {
53 int x;
54 scanf("%d", &x);
55 police[x] = true;
56 }
57
58 for (int i = 1; i < n; ++i) {
59 int x, y;
60 scanf("%d %d", &x, &y);
61 T[x].push_back(y);
62 T[y].push_back(x);
63 edges.push_back({x, y});
64 }
65 bfs();
66 vector<int> sol;
67 for (int i = 0; i < edges.size(); ++i) {
68 auto& edge = edges[i];
69 if (from[edge.first] != from[edge.second]) {
70 sol.push_back(i+1);
71 }
72 }
73 cout << sol.size() << "\n";
74 }
75
76 int main() {
77 int tests = 10;
78
79 for (;tests; --tests) {
80 solve();
81 // reset();
82 }
83 }
5.林喵喵算数
time limit:1s
memory limit:128MB
给你两个八进制数，你需要在八进制计数法的情况下计算a-b。
如果结果为负数，你应该使用负八进制数表示。
Input
输入的第一个数字为T,表式测试的样例的组数(1 <= T <= 1000)。
每组数据包括两个八进制数a,b.
Output
输出计算结果，同样八进制表示。如果结果为负数，你应该使用负八进制数表示。
Sample Input
2
176 7
4 14
Sample Output
167
-10
水题签到题。
1 //code by xadView Code
2 #include<iostream>
3 #include<cstdio>
4 #include<cstring>
5 #include<algorithm>
6 using namespace std;
7 typedef long long ll;
8 ll c[1111];
9 ll work1(ll t)
10 {
11 ll ans=0,temp=1;
12 ll num=t;
13 while(num) {
14 ans+=num%10*temp;
15 temp*=8;
16 num/=10;
17 }
18 return ans;
19 }
20
21 int work2(ll t)
22 {
23 ll num=t;
24 int k=0;
25 while(num) {
26 c[++k]=num%8;
27 num/=8;
28 }
29 return k;
30 }
31
32 int main()
33 {
34 int k,T,i,j,flag;
35 ll a,b,num;
36 cin>>T;
37 while(T--) {
38 cin>>a>>b;
39 if(a>=b) flag=1;
40 else flag=-1;
41 num=work1(a)-work1(b);
42 if(num==0) {
43 cout<<"0"<<endl;
44 continue;
45 }
46 k=work2(num*flag);
47 if(flag==-1) cout<<"-";
48 for(i=k;i>=1;i--) cout<<c[i];
49 cout<<endl;
50 }
51 return 0;
52 }
6.签到题
time limit:1s
memory limit:128MB
在计算机网络考试中, 黑帅男神看到一个将IP网络分类的题, 精通C++的他瞬间写出了几行代码成功解决了这个问题
请解析IP地址和对应的掩码，进行分类识别。要求按照A/B/C/D/E类地址归类.
现在假设将所有的IP地址划分为 A,B,C,D,E五类
A类地址1.0.0.0~126.255.255.255;
B类地址128.0.0.0~191.255.255.255;
C类地址192.0.0.0~223.255.255.255;
D类地址224.0.0.0~239.255.255.255；
E类地址240.0.0.0~255.255.255.255
请对输入的IP地址进行分类
Input
多组,第一行是一个T(T<=100000)
接下来T行,每行一个ip地址(不保证正确)
Output
在上面5类中则输出对应类型
不属于上述类型或IP错误则输出”nope”(不含引号)
Sample Input
2
222.195.8.207
127.0.0.1
Sample Output
C
nope
也是水题签到题。
1 //code by xadView Code
2 #include<cstdio>
3 #include<iostream>
4 using namespace std;
5
6 int main(){
7 int T;
8 scanf("%d",&T);
9 for(int i=0;i<T;i++){
10 int a,b,c,d;
11 scanf("%d.%d.%d.%d",&a,&b,&c,&d);
12 if(a>=1&&a<=126&&b>=0&&b<=255&&c>=0&&c<=255&&d>=0&&d<=255){
13 printf("A\n");
14 }
15 else if(a>=128&&a<=191&&b>=0&&b<=255&&c>=0&&c<=255&&d>=0&&d<=255){
16 printf("B\n");
17 }
18 else if(a>=192&&a<=223&&b>=0&&b<=255&&c>=0&&c<=255&&d>=0&&d<=255){
19 printf("C\n");
20 }
21 else if(a>=224&&a<=239&&b>=0&&b<=255&&c>=0&&c<=255&&d>=0&&d<=255){
22 printf("D\n");
23 }
24 else if(a>=240&&a<=255&&b>=0&&b<=255&&c>=0&&c<=255&&d>=0&&d<=255){
25 printf("E\n");
26 }
27 else{
28 printf("nope\n");
29 }
30
31 }
32
33 return 0;
34 }
7.冬冬不喜欢迷宫
time limit:2s
memory limit:128 MB
众所周知，冬冬是一个土豪以及游戏*玩家。最近他趁着暑假，买了许多游戏来消遣。可是当他把所有游戏都通关了以后，感到无敌是多么寂寞，必须靠经典才能满足他。于是他又玩起了走迷宫的小游戏。
走迷宫可以简化为一个矩阵，里面含n*m个格子。有些格子是可以进入并且通过的，有些格子内含障碍物，是不能进入通过它的。我们的任务就是在给定一个起点S和一个终点T后，选择一个不经过障碍物以及走出矩阵边界的方案，把自己控制的角色从S走到T。
然而冬冬身经百战，不知道比其他人高到哪里去了，因此他总想选择最短的路径来走完这个迷宫。可是冬冬的策略总是不能使他达到最优，帅宝宝也告诉他他的路径是第二短的。冬冬很生气。他一直找不出来他的策略哪里有漏洞。
为了安慰冬冬，你能告诉他第二短的路径有多长，以及有多少条这样的路径吗？
Input
多组数据输入，保证不超过2组数据。
第一行是两个正整数n，m，代表矩阵的高度和宽度。其中2≤n,m≤9。
接下来n行m列，给出迷宫每个格子的情况。'S'代表起点，'T'代表终点，'#'代表障碍物，'.'代表可通行区域，其中S一定在左上角，也就是(0,0)的位置；T一定在右下角，也就是(n-1,m-1)的位置。
Output
对于每组数据，输出一行从S到T的第二短路径的长度，以及该长度下的方案数，保证答案在long long范围内。若无从S到T的长度第二短的路径，则输出“Impossible”。
Sample Input
5 6
S.....
#.###.
##....
#.##..
#....T
2 9
S.#......
########T
Sample Output
12 3
Impossible
防新生ak题，简单粗暴插头dp，跟第二题的插头dp想法一样，然后最后输出的是步数第二大的状态 以及该状态下的方案数。
1 #include<cstdio>View Code
2 #include<iostream>
3 #include<cstring>
4 #define clr(x) memset(x,0,sizeof(x))
5 #define clr_1(x) memset(x,-1,sizeof(x))
6 #define LL long long
7 #define HASH 10007
8 #define STATE 1000010
9 using namespace std;
10 struct hashmap//hash表存状态
11 {
12 int size;
13 int next[STATE],head[HASH];
14 LL state[STATE],len[STATE];
15 LL fas[STATE];
16 void init()//清空
17 {
18 size=0;
19 clr_1(head);
20 }
21 void add(LL st,LL length,LL solu)//状态加入
22 {
23 int k=(st*10000+length)%HASH;
24 for(int i=head[k];i!=-1;i=next[i])
25 if(st==state[i] && length==len[i])
26 {
27 fas[i]+=solu;
28 return;
29 }
30 next[++size]=head[k];
31 fas[size]=solu;
32 state[size]=st;
33 len[size]=length;
34 head[k]=size;
35 return ;
36 }
37 }dp[2];
38 int maped[40][40];
39 int code[40];
40 char s[100];
41 void init(int n,int m)//初始化值，读入maped
42 {
43 clr(maped);
44 for(int i=1;i<=n;i++)
45 {
46 scanf("%s",s);
47 for(int j=0;j<strlen(s);j++)
48 {
49 if(s[j]=='.' || s[j]=='S' || s[j]=='T')
50 {
51 maped[i][j+1]=1;
52 }
53 }
54 }
55 return ;
56 }
57 void decode(LL st,int *code,int m)//解码，括号序列
58 {
59 for(int i=m;i>=0;i--)
60 {
61 code[i]=st&3;
62 st>>=2;
63 }
64 return ;
65 }
66 LL encode(int *code,int m)//编码，括号序列
67 {
68 LL st=0;
69 for(int i=0;i<=m;i++)
70 {
71 st<<=2;
72 st|=code[i];
73 }
74 return st;
75 }
76 void shift(int *code,int m)//左移操作
77 {
78 for(int i=m;i>0;i--)
79 code[i]=code[i-1];
80 code[0]=0;
81 return ;
82 }
83 void dpblank(int i,int j,int cnt,int n,int m)//空格子状态转移
84 {
85 int top,left,up;
86 if(i==1 &&j==1)//i=1 且 j=1时加入只有下独立插头 和 右独立插头的状态
87 {
88 decode(dp[cnt].state[1],code,m);
89 if(maped[i][j+1])
90 {
91 code[j-1]=0;
92 code[j]=3;
93 dp[cnt^1].add(encode(code,m),dp[cnt].len[1]+1,dp[cnt].fas[1]);
94 }
95 if(maped[i+1][j])
96 {
97 code[j-1]=3;
98 code[j]=0;
99 if(j==m) shift(code,m);
100 dp[cnt^1].add(encode(code,m),dp[cnt].len[1]+1,dp[cnt].fas[1]);
101 }
102 return ;
103 }
104 if(i==n &&j==m)//i=n 且 j=m时截止单个独立插头的状态
105 {
106 for(int it=1;it<=dp[cnt].size;it++)
107 {
108 decode(dp[cnt].state[it],code,m);
109 code[j-1]=code[j]=0;
110 if(j==m) shift(code,m);
111 dp[cnt^1].add(encode(code,m),dp[cnt].len[it]+1,dp[cnt].fas[it]);
112 }
113 return ;
114 }
115 for(int it=1;it<=dp[cnt].size;it++)
116 {
117 decode(dp[cnt].state[it],code,m);
118 left=code[j-1];
119 up=code[j];
120 if(left && up)//上插头和左插头都存在
121 {
122 if(left==3 || up==3)//存在一个独立插头
123 {
124 if(up==2|| left==2)//若另一个插头为右括号插头，则找到对应的左括号插头变为独立插头
125 {
126 top=0;
127 for(int k=j-2;k>=0;k--)
128 {
129 if(code[k]==2)
130 top++;
131 if(code[k]==1)
132 if(top>0)
133 top--;
134 else
135 {
136 code[k]=3;
137 break;
138 }
139 }
140 }
141 else if(up==1 ||left==1)//若另一个插头为左括号插头，则找到对应的右括号插头变为独立插头
142 {
143 top=0;
144 for(int k=j+1;k<=m;k++)
145 {
146 if(code[k]==1)
147 top++;
148 if(code[k]==2)
149 if(top>0)
150 top--;
151 else
152 {
153 code[k]=3;
154 break;
155 }
156 }
157 }
158 code[j]=code[j-1]=0;
159 if(j==m) shift(code,m);
160 dp[cnt^1].add(encode(code,m),dp[cnt].len[it]+1,dp[cnt].fas[it]);
161 }
162 else if(left!=up)//两个括号插头
163 {
164 if(left==1)//左右括号插头，不允许形成回路
165 continue;
166 else//右左括号插头直接去掉
167 {
168 code[j]=code[j-1]=0;
169 if(j==m) shift(code,m);
170 dp[cnt^1].add(encode(code,m),dp[cnt].len[it]+1,dp[cnt].fas[it]);
171 }
172 }
173 else
174 {
175 if(left==2)//都是左括号插头，找到对应的第一个右括号插头变为左括号插头
176 {
177 top=0;
178 for(int k=j-2;k>=0;k--)
179 {
180 if(code[k]==2)
181 top++;
182 if(code[k]==1)
183 if(top>0)
184 top--;
185 else
186 {
187 code[k]=2;
188 break;
189 }
190 }
191 }
192 else//都是右括号插头，找到对应的第一个左括号插头变为右括号插头
193 {
194 top=0;
195 for(int k=j+1;k<=m;k++)
196 {
197 if(code[k]==1)
198 top++;
199 if(code[k]==2)
200 if(top>0)
201 top--;
202 else
203 {
204 code[k]=1;
205 break;
206 }
207 }
208 }
209 code[j]=code[j-1]=0;
210 if(j==m) shift(code,m);
211 dp[cnt^1].add(encode(code,m),dp[cnt].len[it]+1,dp[cnt].fas[it]);
212 }
213 }
214 else if(left || up)//仅有一个插头，则延伸插头
215 {
216 if(left) top=left;
217 else top=up;
218 if(maped[i][j+1])//右延伸插头
219 {
220 code[j-1]=0;
221 code[j]=top;
222 dp[cnt^1].add(encode(code,m),dp[cnt].len[it]+1,dp[cnt].fas[it]);
223 }
224 if(maped[i+1][j])//下延伸插头
225 {
226 code[j-1]=top;
227 code[j]=0;
228 if(j==m) shift(code,m);
229 dp[cnt^1].add(encode(code,m),dp[cnt].len[it]+1,dp[cnt].fas[it]);
230 }
231 }
232 else//没有插头
233 {
234 if(maped[i+1][j] && maped[i][j+1])//下插头和左插头
235 {
236 code[j-1]=1;
237 code[j]=2;
238 dp[cnt^1].add(encode(code,m),dp[cnt].len[it]+1,dp[cnt].fas[it]);
239 }
240 //可经过可不经过点则可以保持原样，没有插头
241 code[j-1]=code[j]=0;
242 if(j==m) shift(code,m);
243 dp[cnt^1].add(encode(code,m),dp[cnt].len[it],dp[cnt].fas[it]);
244 }
245 }
246 return ;
247 }void dpblock(int i,int j,int cnt,int n,int m)//障碍格子状态转移
248 {
249 for(int it=1;it<=dp[cnt].size;it++)
250 {
251 decode(dp[cnt].state[it],code,m);
252 if(j==m) shift(code,m);
253 dp[cnt^1].add(encode(code,m),dp[cnt].len[it],dp[cnt].fas[it]);
254 }
255 return ;
256 }
257 void solve(int n,int m)
258 {
259 int cnt=0;
260 LL ans,minfas,secans,secminfas;
261 dp[cnt].init();
262 dp[cnt].add(0,0,1);
263 for(int i=1;i<=n;i++)
264 {
265 for(int j=1;j<=m;j++)
266 {
267 dp[cnt^1].init();
268 if(maped[i][j]==1)
269 dpblank(i,j,cnt,n,m);
270 else
271 dpblock(i,j,cnt,n,m);
272 cnt^=1;
273 /* for(int it=1;it<=dp[cnt].size;it++)
274 {
275 decode(dp[cnt].state[it],code,m);
276 for(int k=0;k<=m;k++)
277 printf("%d:%d ",k,code[k]);
278 printf("fas:%lld\n",dp[cnt].fas[it]);
279 }
280 printf("\n"); */
281 }
282 }
283 if(dp[cnt].size<=1)
284 printf("Impossible\n");
285 else
286 {
287 ans=secans=0x3f3f3f3f;
288 for(int i=1;i<=dp[cnt].size;i++)
289 {
290 if(dp[cnt].len[i]<ans)
291 {
292 ans=dp[cnt].len[i];
293 minfas=dp[cnt].fas[i];
294 }
295 }
296 for(int i=1;i<=dp[cnt].size;i++)
297 {
298 if(dp[cnt].len[i]<secans && dp[cnt].len[i]!=ans)
299 {
300 secans=dp[cnt].len[i];
301 secminfas=dp[cnt].fas[i];
302 }
303 }
304 printf("%lld %lld\n",secans,secminfas);
305 }
306 return ;
307 }
308 int main()
309 {
310 int n,m,kase=0;
311 /* freopen("11.in","r",stdin);
312 freopen("11.out","w",stdout);*/
313 while(scanf("%d%d",&n,&m)!=EOF)
314 {
315 init(n,m);
316 solve(n,m);
317 }
318 return 0;
319 }
8.MCC的考验
time limit:1s
memory limit:128 MB
MCC男神听说新一期的选拔赛要开始了，给各位小伙伴们带来了一道送分题，如果你做不出来，MCC会很伤心的。
给定一个大小为n的非空整数数组,现在定义一种操作，每一步操作会将该数组中的n-1个数同时加1，问最少进行多少步操作后，可以使得数组里的每一个数字都相等。
例如，一个n为3的数组[1,2,3]，最少进行3步操作后，可以变为[4,4,4]
过程如下：[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
Input
第一行为一个整数n，代表数组个数。1<=n<=1,000,000
第二行为每个数组的数字a[i],1<=a[i]<=1000
Output
输出需要的最少操作数。
Sample Input
3
2 3 4
Sample Output
3
让n-1个数组的数字同时+1，相当于让一个数组的数字-1。计算下每个数组数字与数字最小的数组的数字的差，然后把他们求和后即为操作数。
1 //code by mccView Code
2 #include<iostream>
3 #include<cmath>
4 #include<vector>
5 #include<utility>
6 #include<algorithm>
7 #include<string>
8 #include<queue>
9 #include<set>
10 #include<map>
11 #include<stack>
12 using namespace std ;
13 int nums[1000010];
14 int main()
15 {
16 /* freopen("1.in","r",stdin);
17 freopen("1.out","w",stdout); */
18 int len ;
19 cin>>len ;
20 for (int i = 0; i < len;i++ ){
21 cin>>nums[i] ;
22 }
23 if (len <= 1){
24 cout<<0<<endl ;
25 return 0 ;
26 }
27 int Min = nums[0] ;
28 int sum = 0 ;
29 for (int i = 0; i < len;i++ ){
30 sum += nums[i] ;
31 if (nums[i] < Min)
32 Min = nums[i] ;
33 }
34 cout<<sum-Min*len<<endl ;
35 return 0;
36 }