首页 > 代码库 > 中国(北方)大学生程序设计训练赛(第一周)

中国(北方)大学生程序设计训练赛(第一周)

比赛链接

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);
    }
}
D

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;
//      }
    }
}
E

 

中国(北方)大学生程序设计训练赛(第一周)