Mutual Training for Wannafly Union #1
题外话：
wannafly union:可能有的学校不能很好得传承……可能某一时间可以进过两三次final ……但是final队过后，这个学校就退出了历史的舞台……
说实话我依然记得我入学那年，也就是14年，看到了华科又一次进final，然后15年仿佛已经开始走下坡路，到了16年，icpc连快银都没有....见证了hust的衰落，我的内心是格外凄凉的。
而又不仅仅是见证...内心是有些愧疚的....总觉得自己没能把某些传统传承下去。。。。
曾经我以为学校的荣誉轮不到我去争取，毕竟我实力很弱，高中noip虽然有全省第二...但是大弱省....其实我当年只有275分...
14级的一队...pyy+zk+tm，三个人都是初一就开始参加比赛了....而且湖南+广东+安徽....
其他人，也至少比我发展均衡....
所以之前想着...弱鸡如我好好提高学校的下限就好了....
但是现在发现并不是那么一回事...
其实每个人...都是和学校相关的....
即使最后轮不到我...但是应该仍然有这个想法才对吧....
好了正题：
这次比赛只做出了三道题，A题之前遇到过，当时不会，忘记补了。目测E题也可以补，不过明天约了妹子自习估计要早睡，所以考完试再说吧。
A：
题意：有一个3*n的maze，一个人初始在最左边的某个格子里（3个中的一个，用s表示），然后有若干由大写字母组成的火车...
每一次运动中：人先向右移动一个格子，然后选择不动，或者向上或者向下（具体取决于现在处在3行中的哪一行），之后每列火车向左移动2个格子。如果某个时刻人和火车位于同一个格子，那么人就狗带了。人的获胜条件是到达最右边。
思路：比赛的时候脑抽。。。竟然觉得是指数模型。。。。然后就觉得想错了orz
这道题可以考虑物理的相对运动，我们可以认为火车是不动的，而人时先向右一个格子，然后换行（或者不换）,然后再向右两个
这样直接bfs搞一下就好咯。。。。果然是水题。。。。
/* ***********************************************
Author :111qqz
Created Time :2016年11月19日 星期六 18时56分06秒
File Name :code/wfly/#1/A.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=3E3+15;
7int n,k;
8char maze[4][N];
9struct node
10{
11 int x,y;
12 void out()
13 {
14 printf("x:%d y : %d\n",x,y);
15 }
16}s;
17int a[3][N];
18bool vis[3][N];
19bool ok;
20void bfs()
21{
22 ms(vis,false);
23 queue<node>q;
24 while (!q.empty()) q.pop();
25 q.push(s);
26 vis[s.x][s.y] = true;
27 while (!q.empty())
28 {
29 node pre = q.front();
30// pre.out();
31 q.pop();
32 if (pre.y>=3*n-2)
33 {
34 ok = true;
35 return;
36 }
37 if (a[pre.x][pre.y+1]) continue; //走一步死。
38 for ( int i = 0 ; i < 3 ; i++)
39 {
40 if (abs(i-pre.x)>=2) continue ; //一次只能移动一步。
41 if (a[i][pre.y+1]) continue; //必须有空完成上下移动。
42 if (a[i][pre.y+2]) continue;
43 if (a[i][pre.y+3]) continue;
44 if (vis[i][pre.y+3]) continue;
45 vis[i][pre.y+3] = true;
46 node tmp;
47 tmp.x = i;
48 tmp.y = pre.y+3;
49 q.push(tmp);
50 }
51 }
52}
53int main()
54{
55 #ifndef ONLINE_JUDGE
56 freopen("code/in.txt","r",stdin);
57 #endif
58 int T;
59 cin>>T;
60 while (T--)
61 {
62 scanf("%d%d",&n,&k);
63 for ( int i = 0 ; i < 3 ; i++) scanf("%s",maze[i]);
64 for ( int i = 0 ; i < 3 ; i++)
65 {
66 if (maze[i][0]=='s')
67 {
68 s.x = i ;
69 s.y = 0 ;
70 }
71 }
72 ms(a,0); // !!!
73 for ( int i = 0 ; i < 3 ; i++)
74 {
75 for ( int j = 0 ; j < n ; j++)
76 {
77 if (maze[i][j]=='.'||maze[i][j]=='s') a[i][j] = 0;
78 else a[i][j] = 1 ;
79 }
80 }
81 /* for ( int i = 0 ; i < 3 ; i++)
82 {
83 for ( int j = 0 ; j < n ; j++) printf("%d",a[i][j]);
84 printf("\n");
85 } */
86 ok = false;
87 bfs();
88 if (ok)
89 {
90 puts("YES");
91 }
92 else
93 {
94 puts("NO");
95 }
96 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}
B: 题意：一个字符串，长度最长为10，由小写字母组成，恰好插入一个字母使其变成回文串的方法...
思路：一开始竟然傻傻得分情况讨论。。。。各种漏。。日。。。后来一看数据范围。。。直接暴力。枚举插入的位置和插入的字母。。然后check。复杂度。。10×101026.。。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年11月19日 星期六 20时03分25秒
4File Name :code/wfly/#1/BB.cpp
5 ************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31vector<char>ans;
32bool check()
33{
34 int siz = ans.size();
35 for ( int i = 0 ; i < siz ; i++)
36 {
37 if (ans[i]!=ans[siz-1-i]) return false;
38 }
39 return true;
40}
41int main()
42{
43#ifndef ONLINE_JUDGE
44 freopen("code/in.txt","r",stdin);
45#endif
46 string st;
47 cin>>st;
48 int len = st.length();
49 for ( int i = 0 ; i < len ; i++)
50 {
51 for ( int j = 0; j< 26 ; j++)
52 {
53 char ch = j +'a';
54 ans.clear();
55 for ( int k = 0 ; k < len ; k++)
56 {
57 if (k==i) ans.push_back(ch);
58 ans.push_back(st[k]);
59 }
60 // for ( int k = 0 ; k < ans.size(); k++) printf("%c ",ans[k]);
61 // printf("\n");
62 if (check())
63 {
64 int siz = ans.size();
65 for ( int ii = 0 ; ii < siz; ii++)
66 {
67 printf("%c",ans[ii]);
68 }
69 return 0;
70 }
71 ans.clear();
72// cout<<"st:"<<st<<" ch:"<<ch<<endl;
73 for ( int k = 0 ; k < len ; k++) ans.push_back(st[k]);
74 ans.push_back(ch);
75 // for ( int k = 0 ; k < ans.size() ; k++) printf("%c ",ans[k]);
76 if (check())
77 {
78 int siz = ans.size();
79 for ( int ii = 0 ; ii < siz; ii++)
80 {
81 printf("%c",ans[ii]);
82 }
83 return 0;
84 }
85 }
86 }
87 puts("NA");
88#ifndef ONLINE_JUDGE
89 fclose(stdin);
90#endif
91 return 0;
92}
D:n*n的格子，初始白皇后在(1,1)，黑皇后在(1,n)，其他点被士兵覆盖（士兵不会动。。。）皇后每次可以横竖或者对角线，走到一个有士兵（或者地方皇后）的位置并吃掉。。。（每次移动必须吃掉士兵或者地方皇后）
白皇后先走，问双方都最优策略。。。谁必赢。。如果白必赢，输出第一步的走的方案。
思路：其实算是构造题。。。？手画一下发现。。。只和奇偶性有关2333，结论很容易发现。。
/* ***********************************************
Author :111qqz
Created Time :2016年11月19日 星期六 20时47分53秒
File Name :code/wfly/#1/D.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6int n;
7int main()
8{
9 #ifndef ONLINE_JUDGE
10 freopen("code/in.txt","r",stdin);
11 #endif
12 cin>>n;
13 if (n%2==1)
14 {
15 puts("black");
16 }
17 else
18 {
19 puts("white");
20 puts("1 2");
21 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}
F：题意：猜数游戏。。四种猜法。。大于，大于等于，小于，小于等于。。。并且给出每次猜得对还是错。。。问最后这个数是否存在。。
思路：维护一个L,R。。。最后看L<=R是否成立即可。。。
/* ***********************************************
Author :111qqz
Created Time :2016年11月19日 星期六 20时21分42秒
File Name :code/wfly/#1/F.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6int n;
7char opt[3];
8int x;
9char cmd[3];
10int main()
11{
12#ifndef ONLINE_JUDGE
13 freopen("code/in.txt","r",stdin);
14#endif
15 scanf("%d",&n);
16 int L,R;
17 L = -2E9;
18 R = 2E9;
19 for ( int i = 1; i <= n ; i++)
20 {
21 scanf("%s %d %s",opt,&x,cmd);
22 if (opt[0]=='>')
23 {
24 if (opt[1]=='=')
25 {
26 if (cmd[0]=='Y')
27 {
28 L = max(L,x);
29 }
30 else
31 {
32 R = min(R,x-1);
33 }
34 }
35 else
36 {
37 if (cmd[0]=='Y')
38 {
39 L = max(L,x+1);
40 }
41 else
42 {
43 R = min(R,x);
44 }
45 }
46 }else
47 {
48 if (opt[1]=='=')
49 {
50 if (cmd[0]=='Y')
51 {
52 R = min(R,x);
53 }
54 else
55 {
56 L = max(L,x+1);
57 }
58 }
59 else
60 {
61 if (cmd[0]=='Y')
62 {
63 R = min(R,x-1);
64 }
65 else
66 {
67 L =max(L,x);
68 }
69 }
70 }
71 }
72 if (L<=R)
73 {
74 printf("%d\n",L);
75 }
76 else
77 {
78 puts("Impossible");
79 }
1#ifndef ONLINE_JUDGE
2 fclose(stdin);
3#endif
4 return 0;
5}