首页 > 代码库 > 2016年浙江财经大学信工学院程序设计竞赛题解
2016年浙江财经大学信工学院程序设计竞赛题解
代码为本人出于爱好 验题时所写，如有错误，敬请指出。
题面$pdf$为本人排版，不到之处，还请海涵。
联系方式$QQ$：$774388357$ 浙江财经大学 $14$软件工程 周甄陶
正赛题面：https://pan.baidu.com/s/1jIQASxo
热身赛题面：https://pan.baidu.com/s/1mi4mjMg
热身赛$pdf$密码：IbcS3jJkkOsxiMCYfF6v
弱校现场赛$Rank$：https://pan.baidu.com/s/1kVBFGMV
热身赛$Problem$ $D$：圆覆盖
首先，如果$x$的跨度大于$400000$，一定无解，因为圆半径最多是$100000$。剩下的情况可以枚举计算，枚举横坐标$x$，统计横坐标为$x$的被所有圆覆盖的整点有几个，每个圆覆盖的整点都是一段区间，也就是计算区间交。
#include<bits/stdc++.h>using namespace std; long long x[110],y[110],r[110];int n;long long xmin,xmax,ans;long long INF=10000000000;double eps=1e-5; int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>x[i]>>y[i]>>r[i]; xmin=x[1]-r[1]; xmax=x[1]+r[1]; for(int i=2;i<=n;i++) { xmin=min(xmin,x[i]-r[i]); xmax=max(xmax,x[i]+r[i]); } if(xmax-xmin>400000) { printf("0\n"); return 0; } for(long long xx=xmin;xx<=xmax;xx++) { bool fail=0; long long L=-INF,R=INF; for(int i=1;i<=n;i++) { if(x[i]-r[i]>xx) fail=1; if(x[i]+r[i]<xx) fail=1; long long p=(long long)sqrt(r[i]*r[i]-(xx-x[i])*(xx-x[i])); long long rr=y[i]+p; long long ll=y[i]-p; if(ll>R) fail=1; if(rr<L) fail=1; if(fail) break; L=max(L,ll); R=min(R,rr); } if(fail) continue; ans=ans+R-L+1; } cout<<ans; return 0;}
$Problem$ $A$：祝大家院赛取得好成绩
这题不算题。
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std; int main(){ printf("AC\n"); return 0;}
$Problem$ $B$：进击的会长
对于每个数，去前面寻找是否出现过，没出现过答案加$1$。
#include<bits/stdc++.h>using namespace std; int f[1010],n; int main(){ int ans=0; cin>>n; for(int i=1;i<=n;i++) { int x; cin>>x; if(f[x]==0) { ans++; f[x]=1; } } cout<<ans; return 0;}
$Problem$ $C$：博弈
从规则来看，每次取卡必然取走一张$A$卡，当$A$卡没有的时候，游戏结束。因此只需判断$A$卡的张数是奇数还是偶数。
#include<bits/stdc++.h>using namespace std; int main(){ int n,m; scanf("%d%d",&n,&m); if(n%2==1) puts("Yes"); else puts("No"); return 0;}
$Problem$ $D$：来自上级的压迫
数据范围较小，可以暴力匹配做，开一个数组记录下哪些位置被屏蔽了。
#include <iostream>#include <cstdio>#include <cstring>using namespace std; char s[1010],t[15];int n,lens,lent,flag[1010]; bool Equ(char a,char b){ if(b==‘_‘) return 0; if(a==b||a+‘a‘-‘A‘==b||a-‘a‘+‘A‘==b) return 1; return 0;} void work(int x){ if(x+lent-1>=lens) return; for(int i=0;i<lent;i++) if(!Equ(t[i],s[i+x])) return; for(int i=0;i<lent;i++) flag[i+x]=1;} int main(){ scanf("%s",s); scanf("%d",&n); memset(flag,0,sizeof flag); lens=strlen(s); for(int p=0;p<n;p++) { scanf("%s",t); lent=strlen(t); for(int i=0;i<lens;i++) work(i); } for(int i=0;i<lens;i++) { if(flag[i]) printf("*"); else printf("%c",s[i]); } printf("\n"); return 0;}
$Problem$ $E$：$zzt$发明了永动机
模拟，按题意说的操作一遍就可以了。
#include<bits/stdc++.h>using namespace std; int n,m,x,y;int a[1010];int p,q,cnt; int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; if(n==0||m<1000) { cout<<0<<" "<<m<<endl; return 0; } cnt=0; int now=1; while(1) { if(m<1000) break; m=m-1000; p=q=0; while(1) { if(now>n) break; if(a[now]==0) cnt++,q++; else cnt++,p++; if(p==12||q==3) { m=m+20*(1+p)*p/2; break; } now++; } if(now>n) break; now++; if(now>n) break; } cout<<cnt<<" "<<m<<endl; return 0;}
$Problem$ $F$：$zzt$的守望
贪心，统计一下每个训练营分别有多少人，排序，从人数多的训练营开始取人。
#include<bits/stdc++.h>using namespace std; int n,m,x;int a[1010];bool cmp(int a,int b) {return a>b;}int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>x, a[x]++; sort(a,a+100,cmp); int ans=0; for(int i=0;i<100;i++) { ans=ans+min(a[i],m)*min(a[i],m); m=m-min(a[i],m); if(m<=0) break; } cout<<ans<<endl; return 0;}
$Problem$ $G$：黑鸡打$BOSS2.0$
模拟题，按照题意说的做。
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std; int n,atk,def,hp,lv=0,eee,ans,f[35];bool fail=0; int main(){ f[0]=1; for(int i=1;i<=30;i++) f[i]=2*f[i-1]; cin>>n; lv++; atk=5*lv; def=5*lv; hp=lv*100; eee=0; for(int i=1;i<=n;i++) { int h,a,d,e; cin>>h>>a>>d>>e; if(i%2==1) { int cnt=0; int res=-1; while(1) { cnt++; if(cnt%3==0) h=h-max(0,2*(atk-d)); else h=h-max(0,atk-d); if(h<=0) {res=1; break;} hp=hp-max(0,a-def); if(hp<=0) {res=0; break;} } if(res==0) {fail=1, ans=i; break; } } else { int res=-1; while(1) { h=h-max(0,6*atk/5-d); if(h<=0) {res=1; break;} hp=hp-max(0,a-def); if(hp<=0) {res=0; break;} } if(res==0) {fail=1, ans=i; break; } } if(fail==1) break; else { eee=eee+e; while(1) { if(eee>=f[lv]) eee-=f[lv],lv++,atk=5*lv, def=5*lv, hp=lv*100; else break;} } } if(fail) printf("%d\n",ans); else printf("oh my hero heiji\n"); return 0;}
$Problem$ $H$：$Quick$ $Pow$
裸的快速幂，题面给出了教学。
#include<bits/stdc++.h>using namespace std; long long a,b;long long mod=2016; long long POW(long long a,long long b){ long long res=1; while(b) { if(b%2==1) res=res*a%mod; b=b/2; a=a*a%mod; } return res;} int main(){ cin>>a>>b; printf("%lld\n",POW(a,b)); return 0;}
$Problem$ $I$：$Easy$ $Search$
广搜，数据范围较小，可以暴力通过，每次扫一遍图往外标记即可。
#include<bits/stdc++.h>using namespace std; int n,m,k;char s[120][120];int sx,sy,flag[120][120];int ans=0; void work(int a,int b,int c){ if(a<0||b<0) return ; if(a>=n||b>=m) return ; if(s[a][b]==‘#‘) return ; flag[a][b]=c; if(s[a][b]==‘+‘) ans=1;} int main(){ memset(flag,-1,sizeof flag); cin>>n>>m>>k; for(int i=0;i<n;i++) cin>>s[i]; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(s[i][j]==‘@‘) sx=i,sy=j; } } flag[sx][sy]=0; for(int p=1;p<=k;p++) { for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(flag[i][j]!=p-1) continue; work(i-1,j,p); work(i+1,j,p); work(i,j-1,p); work(i,j+1,p); if(ans) break; } if(ans) break; } if(ans) break; } if(ans) printf("YES\n"); else printf("NO\n"); return 0;}
$Problem$ $J$：初中平面几何
连接$OA$,$OD$,$OE$，将问题转化为扇形面积减去两个三角形面积。
#include<cstdio>#include<cstring>#include<iostream>#include<cmath>using namespace std; int main(){ int r,a,b; cin>>r>>a>>b; double pi=acos(-1.0); double jiao1=asin(1.0*b/r); double jiao3=asin(1.0*a/r); double jiao2=pi/2-(jiao1+jiao3); double ss=jiao2/2*r*r; double sda=0.5*sin(jiao2)*r*r; double sgong=ss-sda; double q=sqrt(1.0*r*r-1.0*a*a); double p=sqrt(1.0*r*r-1.0*b*b); double sxi=0.5*(p-a)*(q-b); printf("%.2lf\n",sgong+sxi); return 0;}
$Problem$ $K$：天天摸球身体棒
概率。和$p$无关，即无论第几个人，概率都是和第一个人一样的，总的方案数有$sum!$种，第$p$个位置为颜色为$q$的方案数有$(sum-1)!*a[q]$种。化简之后，答案就是$a[q]/sum$。
#include<cstdio>#include<cstring>#include<iostream>using namespace std; int n,p,q,fz,fm; int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b);} int main(){ cin>>n>>p>>q; fz=fm=0; for(int i=1;i<=n;i++) { int x; cin>>x; if(i==q) fz=x; fm=fm+x; } int g=gcd(fz,fm); cout<<fz/g<<"/"<<fm/g<<endl; return 0;}
$Problem$ $L$：GayDong的礼物
$dp$，分别记录到第$i$位$L$、$LO$、$LOV$、$LOVE$的方案数即可递推。
#include<cstdio>#include<cstring>#include<iostream>using namespace std; int n,a,b,c,d;char s[100010];int mod=1e9+7; int main(){ cin>>n>>s; a=b=c=d=0; for(int i=0;s[i];i++) { if(s[i]==‘L‘) a=(a+1)%mod; else if(s[i]==‘O‘) b=(b+a)%mod; else if(s[i]==‘V‘) c=(c+b)%mod; else if(s[i]==‘E‘) d=(d+c)%mod; } cout<<d<<endl; return 0;}
$Problem$ $M$：数字旋转
$dp$，$dp[i][j]$表示前$i$个数，旋转次数小于等于$j$次的情况下获得的最大价值，枚举第$i$个数字旋转了几次即可递推。该问题与背包问题类似，可以学一下背包问题九讲。
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std; int n,m,f[15];long long dp[110][1010];long long v[15]; int main(){ f[0]=1; for(int i=1;i<=10;i++) f[i]=10*f[i-1]; memset(dp,0,sizeof dp); cin>>n>>m; for(int i=1;i<=n;i++) { long long x; cin>>x; long long t=x; int len=0; while(t) len++,t=t/10; v[0]=x; for(int j=1;j<=10;j++) v[j]=(v[j-1]%f[len-1])*10+v[j-1]/f[len-1]; for(int j=0;j<=10;j++) { for(int k=j;k<=m;k++) { dp[i][k]=max(dp[i][k],dp[i-1][k-j]+v[j]); } } } cout<<dp[n][m]; return 0;}
2016年浙江财经大学信工学院程序设计竞赛题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。