2016 Multi-University Training Contest 3
A - Sqrt Bo
题意：给一个数 n，问n要多少次平方后化为1，如果超过5次输出"TAT"。
tags：SB题，5次内平方的，即小于2*2*4*16*256*65536 。然后0、1特判。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,b,a) for (int i=b;i>=a;i--) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f typedef long long ll; const int N = 200005;int main() {string s;while(cin>>s) {if(s.length()>10) { puts("TAT"); continue; }ll x=0, s1=1;per(i, s.length()-1, 0) x+=(s1*(s[i]-'0')), s1*=10;if(x>=4294967296) { puts("TAT"); continue; }if(x==0) { puts("TAT"); continue; }if(x==1) { cout<<1<<endl; continue; }int cnt=0;while(x!=1) x=(ll)sqrt(x), ++cnt;cout<<cnt<<endl;}return 0; } //4294967296
B - Permutation Bo
题意：给出数组c[]，另有一个数组h[]是1~n的序列。f()=c[i]*(h[i]>h[i-1] && h[i]>h[i+1])，(i=1~n) 。
tags：根据期望的线性性，我们可以分开考虑每个位置对答案的贡献。或者打个表看每个位置计算了多少次，也能看出规律。注意要特判1的情况。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,b,a) for (int i=b;i>=a;i--) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f typedef long long ll; const int N = 200005;int main() {int n;while(scanf("%d", &n)!=EOF){int ai;if(n==1) { scanf("%d", &ai); printf("%.6f\n", ai*1.0); continue; }double x=0;rep(i,1,n) {scanf("%d", &ai);if(i==1 || i==n) x+= ai*1.0/2;else x+= ai*1.0/3;}printf("%.6f\n", x);}return 0; }
C - Life Winner Bo
题意：N*M的国际象棋棋盘，有 王、皇后、车、马四种棋子。一个棋子最初在(1,1)，指定棋子类型，两人轮流移动(要按棋子规则，且只能往右下方移动)，问先手胜负。
tags： 分成4种博弈分别处理。
王：可以向右、向下或斜向移动一格，看作n-1和m-1的两堆石子，每次可以选一堆取一个或者两堆都取一个，即巴什博弈。
皇后：看作两堆石子，每次可以选一堆取任意个或者两堆取同样多个，即威佐夫博弈。
车：看作两堆石子，每次可以选一堆取任意个，即尼姆博弈。
马：NP态搜一下，(n,m)位置是必败态，bfs往前面推，可以到必败态的即为必胜，只能到必胜态的即为必败。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,b,a) for (int i=b;i>=a;i--) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define PII pair<int , int > #define fi first #define se second #define MP make_pair typedef long long ll; const int N = 1005;int ty, n, m, vis[N][N]; bool check(int x, int y) {if(x>=1 && y>=1) return true;return false; } int bfs() {mes(vis, 0); vis[n][m]=-2;queue<PII> q; q.push(MP(n,m));while(!q.empty()){int x=q.front().fi, y=q.front().se;q.pop();if(vis[x][y]==-2) {if(check(x-2, y-1)) vis[x-2][y-1]=1, q.push(MP(x-2, y-1));if(check(x-1, y-2)) vis[x-1][y-2]=1, q.push(MP(x-1, y-2));}else if(vis[x][y]==1) {if(check(x-2, y-1)) --vis[x-2][y-1];if(vis[x-2][y-1]==-2) q.push(MP(x-2, y-1));if(check(x-1, y-2)) --vis[x-1][y-2];if(vis[x-1][y-2]==-2) q.push(MP(x-1, y-2));}}return vis[1][1]; } int main() {int T; scanf("%d", &T);while(T--){scanf("%d %d %d", &ty, &n, &m);if(ty==1) {if((n-1)%2==1 || (m-1)%2==1) puts("B");else puts("G");}if(ty==2) {if((n-1)^(m-1)) puts("B");else puts("G");}if(ty==4) {double ci=1.0*(1+sqrt(5))/2*abs(n-1-(m-1));if(((int)ci)==min(n-1, m-1)) puts("G");else puts("B");}if(ty==3) {int ci=bfs();if(ci==0 || ci==-1) puts("D");else if(ci==1) puts("B");else puts("G");}}return 0; }
J - Rower Bo
题意：船在点(0,a)，要到(0,0)。有速度v2的水流沿x轴方向，船速v1方向始终指向(0,0)，问最少要多少时间到(0,0) 。
tags：积分的知识都忘的差不多了。。
代码：
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,b,a) for (int i=b;i>=a;i--) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f typedef long long ll; const int N = 200005;int main() {int a, v1, v2;while(scanf("%d %d %d", &a, &v1, &v2)!=EOF){if(a==0) puts("0");else if(v1<=v2) puts("Infinity");else {printf("%.6f\n", 1.0*a*v1/(v1*v1-v2*v2));}}return 0; }
K - Teacher Bo
题意：给出 n个点，问是否有点A、B和点C、D的曼哈顿距离相等。
tags：题目特意说了点的坐标域为[0,M]，则曼哈顿距离的域则为[0,2*M]。由抽屉原理，只要暴力跑出2*M+1个距离就一定可以找出答案。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,b,a) for (int i=b;i>=a;i--) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define PII pair<int , int > #define fi first #define se second typedef long long ll; const int N = 100005;int n, m; PII co[N]; map<int , int > mp; int main() {int T; scanf("%d", &T);while(T--){mp.clear();scanf("%d %d", &n, &m);rep(i,1,n) scanf("%d %d", &co[i].fi, &co[i].se);bool flag=0; int cnt=0;rep(i,1,n) {if(flag==1 || cnt==2*m+1) break;rep(j,i+1,n) {int s= abs(co[i].fi-co[j].fi) + abs(co[i].se-co[j].se);if(mp.find(s)!=mp.end()) { flag=1; break; }else mp[s]=1;++cnt; if(cnt==2*m+1) break;}}if(flag==1) puts("YES");else puts("NO");}return 0; }
