2020-2021:teams:wangzai_milk:20200520比赛记录
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:20200520比赛记录 [2020/05/21 14:15] infinity37 [J-Rower Bo] |
2020-2021:teams:wangzai_milk:20200520比赛记录 [2020/05/26 00:26] (当前版本) wzx27 |
||
|---|---|---|---|
| 行 2: | 行 2: | ||
| ===== 比赛情况 ===== | ===== 比赛情况 ===== | ||
| + | |||
| + | ^题号 ^A ^B ^C ^D ^E ^F ^G ^H ^I ^J ^K | | ||
| + | ^状态 |O |O |O |O |- |- |- |- |- |O |O | | ||
| + | |||
| + | //O 在比赛中通过 Ø 赛后通过 ! 尝试了但是失败了 - 没有尝试// | ||
| **比赛时间** | **比赛时间** | ||
| 行 34: | 行 39: | ||
| ===== 题解 ===== | ===== 题解 ===== | ||
| + | |||
| + | ==== A-Sqrt Bo ==== | ||
| + | 有一个函数$f(x)=\left \lfloor \sqrt(n) \right \rfloor$，问对于给定的$n$，$f^k(n)=1$的最小$k$，如果$k\gt5$输出"TAT" | ||
| + | |||
| + | $n$的取值到$10^{100}$，很容易想到在一定范围外$k$就大于$5$了，试一下发现$1^18$就大于$5$，所以判断一下长度小于$18$的时候就暴力看多少次，否则就输出"TAT" | ||
| + | |||
| + | <hidden code> | ||
| + | <code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | #define ll long long | ||
| + | #define pii_ pair<int,int> | ||
| + | #define mp_ make_pair | ||
| + | #define pb push_back | ||
| + | #define fi first | ||
| + | #define se second | ||
| + | #define rep(i,a,b) for(int i=(a);i<=(b);i++) | ||
| + | #define show1(a) cout<<#a<<" = "<<a<<endl | ||
| + | #define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl | ||
| + | using namespace std; | ||
| + | const ll INF = 1LL<<60; | ||
| + | const int inf = 1<<30; | ||
| + | const int maxn = 2e5+5; | ||
| + | inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);} | ||
| + | int main() | ||
| + | { | ||
| + | fastio(); | ||
| + | string s; | ||
| + | while(cin>>s){ | ||
| + | int len = s.size(); | ||
| + | if(len>=18) cout<<"TAT"<<endl; | ||
| + | else{ | ||
| + | ll t = 0; | ||
| + | rep(i,0,len-1) t=t*10+(s[i]-'0'); | ||
| + | //show1(t); | ||
| + | if(t==1) {cout<<0<<endl;continue;} | ||
| + | int flag = 1; | ||
| + | rep(i,1,5){ | ||
| + | t = sqrt(t); | ||
| + | if(t==1) {cout<<i<<endl;flag=0;break;} | ||
| + | } | ||
| + | if(flag) cout<<"TAT"<<endl; | ||
| + | } | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ==== B-Permutation Bo ==== | ||
| + | |||
| + | === 题目大意 === | ||
| + | 两个长度为n的序列$h,c$，$c$给出，$h$是长度为$n$的任意排列，求公式 | ||
| + | $\sum_{i=1}^{n}c_i*[h_{i-1}\leq h_i\;and\;h_{i+1} \leq h_i]$ | ||
| + | 另$h_0 = 0,h_{n+1}=0$ | ||
| + | === 数据范围 === | ||
| + | $n\leq 10^3,0\leq c_i\leq 10^3$ | ||
| + | === 解题思路 === | ||
| + | 看到h是排列，觉得能造成括号中条件的排列数是固定的，遂打表，发现在位置1,n产生这种情况的概率是$\frac{1}{2}$，其他位置产生这种情况的概率是$\frac{1}{3}$，然后按照这个依次乘c就行。 | ||
| + | === 代码 === | ||
| + | |||
| + | <hidden> | ||
| + | <code c++> | ||
| + | |||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | \\ | ||
| + | |||
| + | ==== C-Life Winner Bo ==== | ||
| + | 给一个$n\times m$的棋盘，问$\text{king,rook,knight,queen}$的先手胜负情况 | ||
| + | |||
| + | 基本上都是靠先SG函数打表再总结规律，但是$\text{queen}$实在总结不出来，最后优化到$O(NM)$的打表就过了（代码写得贼丑 | ||
| + | |||
| + | <hidden code> | ||
| + | <code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | #define ll long long | ||
| + | #define pii_ pair<int,int> | ||
| + | #define mp_ make_pair | ||
| + | #define pb push_back | ||
| + | #define fi first | ||
| + | #define se second | ||
| + | #define rep(i,a,b) for(int i=(a);i<=(b);i++) | ||
| + | #define show1(a) cout<<#a<<" = "<<a<<endl | ||
| + | #define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl | ||
| + | using namespace std; | ||
| + | const ll INF = 1LL<<60; | ||
| + | const int inf = 1<<30; | ||
| + | const int maxn = 2e5+5; | ||
| + | inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);} | ||
| + | int mp[1005][1005],row[1005],col[1005],dia[3005]; | ||
| + | int t,n,m; | ||
| + | void printMap() | ||
| + | { | ||
| + | rep(i,1,n){rep(j,1,m)cout<<mp[i][j]<<" ";cout<<endl;} | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | fastio(); | ||
| + | int _; | ||
| + | n=m=1000; | ||
| + | mp[n][m] = 0; | ||
| + | rep(i,1,n) row[i]=2; | ||
| + | rep(i,1,m) col[i]=2; | ||
| + | rep(i,1,m-1) mp[n][i]=1,dia[i-n+1001]=1; | ||
| + | rep(i,1,n-1) mp[i][m]=1,dia[m-i+1001]=1; | ||
| + | for(int i=1;i;i++){ | ||
| + | if(n-i<0 || m-i<0) break; | ||
| + | mp[n-i][m-i] = 1; | ||
| + | } | ||
| + | for(int i=n-1;i;i--) for(int j=m-1;j;j--){ | ||
| + | if(j-i == m-n) continue; | ||
| + | int flag = 1; | ||
| + | //rep(k,i+1,n) if(!mp[k][j]) flag=0; | ||
| + | if(row[i]<m-j) flag = 0; | ||
| + | //rep(k,j+1,m) if(!mp[i][k]) flag=0; | ||
| + | if(col[j]<n-i) flag = 0; | ||
| + | if(dia[j-i+1001]<min(n-i,m-j)) flag = 0; | ||
| + | //for(int k=1;;k++){ | ||
| + | // if(k+i>n || k+j>m) break; | ||
| + | // if(!mp[k+i][k+j]) flag=0; | ||
| + | //} | ||
| + | if(flag) mp[i][j]=0; | ||
| + | else {mp[i][j] = 1;row[i]++,col[j]++,dia[j-i+1001]++;} | ||
| + | } | ||
| + | //printMap(); | ||
| + | for(cin>>_;_;_--){ | ||
| + | cin>>t>>n>>m; | ||
| + | if(t==1){ | ||
| + | if((n&1) && (m&1)) cout<<"G"<<endl; | ||
| + | else cout<<"B"<<endl; | ||
| + | }else if(t==2){ | ||
| + | if(n==m) cout<<"G"<<endl; | ||
| + | else cout<<"B"<<endl; | ||
| + | }else if(t==3){ | ||
| + | int f = -1; | ||
| + | for(int k=0;k<=1000;k++){ | ||
| + | if(n-3*k==1 && m-3*k==1){f=0;break;} | ||
| + | if((n-3*k+1==1&&m-3*k+2==1)||(n-3*k+2==1&&m-3*k+1==1)) {f=1;break;} | ||
| + | } | ||
| + | if(f==1) cout<<"B"<<endl; | ||
| + | else if(f==0)cout<<"G"<<endl; | ||
| + | else cout<<"D"<<endl; | ||
| + | }else{ | ||
| + | if(mp[1000-n+1][1000-m+1]) cout<<"B"<<endl; | ||
| + | else cout<<"G"<<endl; | ||
| + | } | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| ==== D-Gambler Bo ==== | ==== D-Gambler Bo ==== | ||
| 行 174: | 行 331: | ||
| === 题目大意 === | === 题目大意 === | ||
| + | 给出N个点，问是否存在四元组$(A,B,C,D)$其中$A<B,C<D$,$A!=B or C!=D$，使得$A$和$B$之间的曼哈顿距离等于$C$和$D$之间的曼哈顿距离 | ||
| === 数据范围 === | === 数据范围 === | ||
| + | $T\leq 50$ | ||
| + | $N\leq 10^5$ | ||
| + | |||
| + | $0\leq$坐标范围$\leq 10^5$ | ||
| === 解题思路 === | === 解题思路 === | ||
| + | 发现给定的坐标范围比较小，因而两点间曼哈顿距离的种类最多有2*坐标范围种，根据鸽巢原理，答案必可以在2*坐标范围+1次找到，所以即使看似是$O(n^2)$的遍历求解实际复杂度也是$O($坐标范围$)$的，因而直接暴力即可。 | ||
| === 代码 === | === 代码 === | ||
| <hidden> | <hidden> | ||
| 行 222: | 行 383: | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| + | |||
| + | \\ | ||
| ===== replay ===== | ===== replay ===== | ||
2020-2021/teams/wangzai_milk/20200520比赛记录.1590041755.txt.gz · 最后更改: 2020/05/21 14:15 由 infinity37
