跳至内容
CVBB ACM Team
用户工具
注册
登录
站点工具
搜索
工具
显示页面
修订记录
Copy this page
导出 PDF
反向链接
最近更改
媒体管理器
网站地图
注册
登录
>
最近更改
媒体管理器
网站地图
您在这里:
front_page
»
2020-2021
»
teams
»
wangzai_milk
»
20200520比赛记录
2020-2021:teams:wangzai_milk:20200520比赛记录
本页面只读。您可以查看源文件,但不能更改它。如果您觉得这是系统错误,请联系管理员。
====== 2016 Multi-University Training Contest 3 ====== ===== 比赛情况 ===== ^题号 ^A ^B ^C ^D ^E ^F ^G ^H ^I ^J ^K | ^状态 |O |O |O |O |- |- |- |- |- |O |O | //O 在比赛中通过 Ø 赛后通过 ! 尝试了但是失败了 - 没有尝试// **比赛时间** 2020-05-20 13:00-18:00 **提交记录** ''D: Accepted 2020-05-20 17:39:39'' ''D: Runtime Error(ACCESS_VIOLATION) 2020-05-20 17:19:16'' ''D: Time Limit Exceeded 2020-05-20 17:05:43'' ''J: Accepted 2020-05-20 16:48:33'' ''C: Accepted 2020-05-20 16:41:33'' ''C: Wrong Answer 2020-05-20 16:35:54'' ''C: Wrong Answer 2020-05-20 16:30:29'' ''J: Wrong Answer 2020-05-20 16:26:31'' ''J: Wrong Answer 2020-05-20 16:22:36'' ''K: Accepted 2020-05-20 13:57:23'' ''B: Accepted 2020-05-20 13:36:47'' ''A: Accepted 2020-05-20 13:14:42'' ===== 题解 ===== ==== 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 ==== solved by Zars19 给出元素为$\{0,1,2\}$的$N\times M$的矩阵,对某个格子进行操作时对该位置的值加$2$,四周分别加$1$,结果都是模$3$意义下的。给出的矩阵最终必能在$2NM$次操作内化为全$0$,输出一种操作。 题解:模$3$意义下的高斯消元,对于每一个位置$a_{i,j}+2\times opt_{i,j}+\sum opt_{i+dx,j+dy}\equiv 0 \pmod 3$。格子至多$30\times 30$个,看起来$O(N^3M^3)$好像不太行,但事实上每一个方程所关联到的变量不多,矩阵较为稀疏,注意''if(!a[mxline][i])continue;''即可。 code: <hidden> <code cpp> #include<iostream> #include<cstdio> #include<cstring> #include<cassert> #include<cstdlib> #include<cmath> #include<vector> #include<algorithm> #define LL long long using namespace std; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,m,chess[33][33],a[1001][1001],f[1001],res; int num(int x,int y){return (x-1)*m+y;} int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1}; bool in(int x,int y){return x>=1&&x<=n*m&&y>=1&&y<=m;} void exgcd(LL a,LL b,LL &d,LL &x,LL &y) { if(!b)d=a,x=1,y=0; else exgcd(b,a%b,d,y,x),y-=x*(a/b); } LL inv(LL a,LL p) { LL d,x,y;exgcd(a,p,d,x,y); return (x+p)%p==0?p:(x+p)%p; } void Gauss() { for(int i=1;i<=n*m;i++) { int mxline=i; for(int j=i;j<=n*m;j++) if(a[j][i]>a[mxline][i])mxline=j; if(!a[mxline][i])continue; if(mxline!=i) for(int j=i;j<=n*m+1;j++)swap(a[mxline][j],a[i][j]); for(int j=i+1;j<=n*m;j++) { if(!a[j][i])continue; int t=a[j][i]*inv(a[i][i],3)%3; for(int k=i;k<=n*m+1;k++) a[j][k]=(a[j][k]-(t*a[i][k]%3)+3)%3; } } for(int i=n*m;i;i--) { for(int j=n*m;j>i;j--) a[i][n*m+1]=((a[i][n*m+1]-f[j]*a[i][j]%3)+3)%3; f[i]=a[i][n*m+1]*inv(a[i][i],3)%3; if(f[i])res+=f[i]; } } int main() { int T=read(); while(T--) { memset(a,0,sizeof(a)); n=read(),m=read(),res=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) chess[i][j]=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { a[num(i,j)][n*m+1]=(3-chess[i][j])%3; a[num(i,j)][num(i,j)]=2; for(int k=0;k<4;k++) { int tx=i+dx[k],ty=j+dy[k]; if(!in(tx,ty))continue; a[num(tx,ty)][num(i,j)]=1; } } Gauss(); printf("%d\n",res); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=1;k<=f[num(i,j)];k++) printf("%d %d\n",i,j); } return 0; } </code> </hidden> \\ ==== J-Rower Bo ==== === 题目大意 === 有一条在坐标轴上的河,一条船目前在$(0,a)$,水流速度$v_2$延x轴,船的速度$v_1$始终指向原点,问船需要多久到达原点。 === 数据范围 === $0\leq a,v_1,v_2 \leq 100$ === 解题思路 === 如图 {{:2020-2021:teams:wangzai_milk:2016-multi3-j.jpg?600|}} === 代码 === <hidden> <code cpp> #include <stdio.h> #include <math.h> int main() { int a,v1,v2; while (scanf("%d%d%d",&a,&v1,&v2)!=EOF) { if (a == 0) {printf("0\n");} else if (v1 <= v2) {printf("Infinity\n");} else { printf ("%lf\n",(double)a*v1/(v1*v1 - v2*v2)); } } return 0; } </code> </hidden> \\ ==== K-Teacher Bo ==== === 题目大意 === 给出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> <code c++> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #include <algorithm> using namespace std; const int N = 1e5+5; bool vis[N<<1]; int x[N],y[N]; int main() { int cas; scanf("%d",&cas); while (cas--) { int n,m; scanf("%d%d",&n,&m); for (int i = 0;i <= 2*m;i++) vis[i] = false; for (int i = 1;i <= n;i++) { scanf("%d%d",&x[i],&y[i]); } bool flag = false; for (int i = 1;i <= n && !flag;i++) { for (int j = i+1;j <= n && !flag;j++) { int dis = abs(x[i]-x[j])+abs(y[i]-y[j]); if (vis[dis]) flag = true; } for (int j = i+1;j <= n && !flag;j++) { int dis = abs(x[i]-x[j])+abs(y[i]-y[j]); vis[dis] = true; } } if (!flag) printf("NO\n"); else printf("YES\n"); } return 0; } </code> </hidden> \\ ===== replay ===== ==== 13:00-13:30 ==== _wzx27开到A发现可打表找范围做,提交,正确。 Zars19发现J是可做物理题,和_wzx27讨论,好像要积分,然后不会。 发现很多人过B,读题,infinity37提出概率大概是固定的。 ==== 13:30-14:00 ==== infinity37找到1/3和1/2概率规律,提交B,正确。 三人讨论K题,过得人太多了,感到迷惑。 infinity37提出曼哈顿距离种数依赖于坐标范围,种数不多,鸽巢原理暴力即可,Zars19附和。 infinity37提交K题,正确。 ==== 14:00-14:30 ==== _wzx27开到D题发现可做,提出爆搜DP说。 Zars19加入D题资源开发,提出贪心说(后证实为假)。 ==== 14:30-15:00 ==== infinity37阐述了C题概况,手玩得到king解和castle猜想 _wzx27和Zars19加入进行一些讨论 ==== 15:00-15:30 ==== 讨论了knight平局问题,king解打表得到证实,castle猜想可以直接归纳证明。 进行了很多对queue的讨论,Zars19打了一些表(虽然最后不太有用) ==== 15:30-16:00 ==== _wzx27提出C题皇后的O(NM)做法。去写C ==== 16:00-16:30 ==== _wzx27提交C题,wa两次后正确。 infinity37去积分了,得到J题柿子,Zars19和_wzx27以为然。 infinity37提交J题,wa了2次,其间更正了下无解条件。 ==== 16:30-17:00 ==== infinity37使用G++提交J题,正确,之前疑似是选用C++编译器导致的精度问题。 Zars19提出D题高斯消元说,开始写。 ==== 17:00-17:30 ==== Zars19提交D题,由于没有continue掉多解消元时主对角线上元素为0的情况TLE一次。然后出现了令人疑惑的RE ==== 17:30-18:00 ==== 种种推理下没有道理RE,扩大数组范围再交,数据范围可能假了,D正确。 ===== 总结 ===== ==== Zars19 ==== 大家这次状态比上次好<del>,不过可能是因为题比上次的可做,区分度没有把我们区分出去</del>,不过我不太行好几个题反应很迟钝orz。rank1是8题,比我们题多的一般会做出来相对更可做的G(我错了这好像是我的树DP)和不太可做我们没开到的E(好像是主席树)或者I(字符串DP)。罚时有点多,6题里面我们很靠后了,对一些套路更熟悉的话有些题应该可以更快想到,另外交题的时候可以冷静一点。 ==== infinity37 ==== 这次比赛签到题过的比较快,但是中部用了很多时间解题,说明我们的解题速度还有待加强,同时认识到了我们在博弈论上有一些缺陷,那么就这么愉快的决定了,这周就学博弈论() ==== _wzx27 ==== 这次做得比上次好一点,可能是因为简单一点(不过为什么会有物理题啊)。不过感觉自己手速和思维都好慢啊,有待提高。以及知识点不够全,有些题不怎么有思路,还是得拓宽知识面才行。
2020-2021/teams/wangzai_milk/20200520比赛记录.txt
· 最后更改: 2020/05/26 00:26 由
wzx27
页面工具
显示页面
修订记录
反向链接
Copy this page
导出 PDF
回到顶部