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搞一下就好咯。。。。果然是水题。。。。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年11月19日 星期六 18时56分06秒
4File Name :code/wfly/#1/A.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=3E3+15;
34int n,k;
35char maze[4][N];
36struct node
37{
38 int x,y;
39 void out()
40 {
41 printf("x:%d y : %d\n",x,y);
42 }
43}s;
44int a[3][N];
45bool vis[3][N];
46bool ok;
47void bfs()
48{
49 ms(vis,false);
50 queue<node>q;
51 while (!q.empty()) q.pop();
52 q.push(s);
53 vis[s.x][s.y] = true;
54 while (!q.empty())
55 {
56 node pre = q.front();
57// pre.out();
58 q.pop();
59 if (pre.y>=3*n-2)
60 {
61 ok = true;
62 return;
63 }
64 if (a[pre.x][pre.y+1]) continue; //走一步死。
65 for ( int i = 0 ; i < 3 ; i++)
66 {
67 if (abs(i-pre.x)>=2) continue ; //一次只能移动一步。
68 if (a[i][pre.y+1]) continue; //必须有空完成上下移动。
69 if (a[i][pre.y+2]) continue;
70 if (a[i][pre.y+3]) continue;
71 if (vis[i][pre.y+3]) continue;
72 vis[i][pre.y+3] = true;
73 node tmp;
74 tmp.x = i;
75 tmp.y = pre.y+3;
76 q.push(tmp);
77 }
78 }
79}
80int main()
81{
82 #ifndef ONLINE_JUDGE
83 freopen("code/in.txt","r",stdin);
84 #endif
85 int T;
86 cin>>T;
87 while (T--)
88 {
89 scanf("%d%d",&n,&k);
90 for ( int i = 0 ; i < 3 ; i++) scanf("%s",maze[i]);
91 for ( int i = 0 ; i < 3 ; i++)
92 {
93 if (maze[i][0]=='s')
94 {
95 s.x = i ;
96 s.y = 0 ;
97 }
98 }
99 ms(a,0); // !!!
100 for ( int i = 0 ; i < 3 ; i++)
101 {
102 for ( int j = 0 ; j < n ; j++)
103 {
104 if (maze[i][j]=='.'||maze[i][j]=='s') a[i][j] = 0;
105 else a[i][j] = 1 ;
106 }
107 }
108 /* for ( int i = 0 ; i < 3 ; i++)
109 {
110 for ( int j = 0 ; j < n ; j++) printf("%d",a[i][j]);
111 printf("\n");
112 } */
113 ok = false;
114 bfs();
115 if (ok)
116 {
117 puts("YES");
118 }
119 else
120 {
121 puts("NO");
122 }
123 }
124
125 #ifndef ONLINE_JUDGE
126 fclose(stdin);
127 #endif
128 return 0;
129}
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，结论很容易发现。。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年11月19日 星期六 20时47分53秒
4File Name :code/wfly/#1/D.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33int n;
34int main()
35{
36 #ifndef ONLINE_JUDGE
37 freopen("code/in.txt","r",stdin);
38 #endif
39 cin>>n;
40 if (n%2==1)
41 {
42 puts("black");
43 }
44 else
45 {
46 puts("white");
47 puts("1 2");
48 }
49
50 #ifndef ONLINE_JUDGE
51 fclose(stdin);
52 #endif
53 return 0;
54}
F：题意：猜数游戏。。四种猜法。。大于，大于等于，小于，小于等于。。。并且给出每次猜得对还是错。。。问最后这个数是否存在。。
思路：维护一个L,R。。。最后看L<=R是否成立即可。。。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年11月19日 星期六 20时21分42秒
4File Name :code/wfly/#1/F.cpp
5 ************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33int n;
34char opt[3];
35int x;
36char cmd[3];
37int main()
38{
39#ifndef ONLINE_JUDGE
40 freopen("code/in.txt","r",stdin);
41#endif
42 scanf("%d",&n);
43 int L,R;
44 L = -2E9;
45 R = 2E9;
46 for ( int i = 1; i <= n ; i++)
47 {
48 scanf("%s %d %s",opt,&x,cmd);
49 if (opt[0]=='>')
50 {
51 if (opt[1]=='=')
52 {
53 if (cmd[0]=='Y')
54 {
55 L = max(L,x);
56 }
57 else
58 {
59 R = min(R,x-1);
60 }
61 }
62 else
63 {
64 if (cmd[0]=='Y')
65 {
66 L = max(L,x+1);
67 }
68 else
69 {
70 R = min(R,x);
71 }
72 }
73 }else
74 {
75 if (opt[1]=='=')
76 {
77 if (cmd[0]=='Y')
78 {
79 R = min(R,x);
80 }
81 else
82 {
83 L = max(L,x+1);
84 }
85 }
86 else
87 {
88 if (cmd[0]=='Y')
89 {
90 R = min(R,x-1);
91 }
92 else
93 {
94 L =max(L,x);
95 }
96 }
97 }
98 }
99 if (L<=R)
100 {
101 printf("%d\n",L);
102 }
103 else
104 {
105 puts("Impossible");
106 }
107
108
109#ifndef ONLINE_JUDGE
110 fclose(stdin);
111#endif
112 return 0;
113}