首页 > 代码库 > 中国(北方)大学生程序设计训练赛(第一周)
中国(北方)大学生程序设计训练赛(第一周)
比赛链接
D题是个二分,每次check复杂度为O(n),类似于xdu_1068,只是一个是求积,一个是求商
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef long double LF; const LF eps=1e-8; int a[100005],bb[100005]; LF b[100005]; LL A,B; LL K; LL rankof(LF x) { LL ans = 0,now = B; for(int i = 1; i <= A; i++) { while(now) { if(a[i]*b[now] > x) now--; else break; } ans += now; } return A*B-ans; } void print() { puts("========"); for(int i=1; i<=A; i++) printf("%d ",a[i]); puts("========"); for(int i=1; i<=B; i++) printf("%.2Lf ",b[i]); puts("========"); } int main() { int T; scanf("%d",&T); while(T--) { scanf("%lld%lld%lld",&A,&B,&K); K--; for(int i=1; i<=A; i++) scanf("%d",&a[i]); for(int i=1; i<=B; i++) scanf("%d",&bb[i]),b[i]=(LF)1.0/bb[i]; sort(a+1,a+A+1); sort(b+1,b+B+1); // print(); LF l=a[1]*b[1],r=a[A]*b[B]+1,mid; while(r-l>eps) { mid=(l+r)/2; if(rankof(mid)<=K) r=mid; else l=mid; } printf("%.2Lf\n",l); } }
E题是矩阵快速幂,注意sin函数有周期性
//话说这题模板没准备好,调了半天。。。(-?-;)
#include<iostream> #include<algorithm> #include<cstring> using namespace std; typedef long long LL; ////////////////////////////// LL T,n,f1,f2,ans; /////////////////////////////// const long long N=6; const long long mod=1000000007; struct Mat { long long mat[N][N]; }; Mat Mut(Mat a,Mat b) { long long i,j,k; Mat c; memset(c.mat,0,sizeof(c.mat)); for(k=0; k<N; k++) { for(i=0; i<N; i++) { if(a.mat[i][k]) for(j=0; j<N; j++) { if(b.mat[k][j]) c.mat[i][j]=c.mat[i][j]+a.mat[i][k]*b.mat[k][j]%mod; c.mat[i][j]=c.mat[i][j]%mod; } } } return c; } Mat Pow(Mat a,long long n) { long long i,j; Mat c; for(i = 0; i < N; ++i) for(j = 0; j < N; ++j) c.mat[i][j] = (i == j); for(; n; n>>=1) { if(n&1) c=Mut(c,a); a=Mut(a,a); } return c; } LL f(Mat A,long long n) { Mat A_; A_=Pow(A,n); LL ret=0; ret=(ret+A_.mat[1][0]*f2)%mod; ret=(ret+A_.mat[1][1]*f1)%mod; ret=(ret+A_.mat[1][2]*0)%mod; ret=(ret+A_.mat[1][3]*1)%mod; ret=(ret+A_.mat[1][4]*0)%mod; ret=(ret+A_.mat[1][5]*(-1))%mod; return (ret+mod)%mod; } //============================= Mat A; int main() { memset(A.mat,0,sizeof(A.mat)); A.mat[0][0]=1;A.mat[0][1]=1;A.mat[0][2]=1; A.mat[1][0]=1; A.mat[1][1]=0; A.mat[2][5]=1; A.mat[3][2]=1; A.mat[4][3]=1; A.mat[5][4]=1; while(cin>>f1>>f2>>n) { // for(int n=1; n<15; n++) // { if(n==1) { cout<<f1<<endl; continue; } if(n==2) { cout<<f2<<endl; continue; } ans=f(A,n-1); cout<<ans<<endl; // } } }
中国(北方)大学生程序设计训练赛(第一周)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。