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-;
int a[],bb[];
LF b[];
LL A,B;
LL K;
LL rankof(LF x)
{
LL ans = ,now = B;
for(int i = ; 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=; i<=A; i++)
printf("%d ",a[i]);
puts("========");
for(int i=; 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=; i<=A; i++)
scanf("%d",&a[i]);
for(int i=; i<=B; i++)
scanf("%d",&bb[i]),b[i]=(LF)1.0/bb[i];
sort(a+,a+A+);
sort(b+,b+B+);
// print();
LF l=a[]*b[],r=a[A]*b[B]+,mid;
while(r-l>eps)
{
mid=(l+r)/;
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=;
const long long mod=; struct Mat
{
long long mat[N][N];
}; Mat Mut(Mat a,Mat b)
{
long long i,j,k;
Mat c;
memset(c.mat,,sizeof(c.mat));
for(k=; k<N; k++)
{
for(i=; i<N; i++)
{
if(a.mat[i][k])
for(j=; 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 = ; i < N; ++i)
for(j = ; j < N; ++j)
c.mat[i][j] = (i == j);
for(; n; n>>=)
{
if(n&) 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=;
ret=(ret+A_.mat[][]*f2)%mod;
ret=(ret+A_.mat[][]*f1)%mod;
ret=(ret+A_.mat[][]*)%mod;
ret=(ret+A_.mat[][]*)%mod;
ret=(ret+A_.mat[][]*)%mod;
ret=(ret+A_.mat[][]*(-))%mod;
return (ret+mod)%mod;
} //=============================
Mat A; int main()
{
memset(A.mat,,sizeof(A.mat));
A.mat[][]=;A.mat[][]=;A.mat[][]=;
A.mat[][]=;
A.mat[][]=;
A.mat[][]=;
A.mat[][]=;
A.mat[][]=;
A.mat[][]=;
while(cin>>f1>>f2>>n)
{
// for(int n=1; n<15; n++)
// {
if(n==)
{
cout<<f1<<endl;
continue;
}
if(n==)
{
cout<<f2<<endl;
continue;
}
ans=f(A,n-);
cout<<ans<<endl;
// }
}
}
E
//3.6下午5点更新
整理了下模板后的E题代码
//p。s。 刚听队友提到矩阵可以用4*4的，感觉自己6*6蠢了些。。
//p。s。 修改时只需要修改列向量b和矩阵A的初始化即可
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL; LL n,ans;
const int N=;
const LL mod=1e9+;
LL b[]= {,,,,,-}; struct Mat
{
LL mat[N][N];
} A;
Mat Mut(Mat a,Mat b)
{
Mat c;
memset(c.mat,,sizeof(c.mat));
for(int k=; k<N; k++)
for(int i=; i<N; i++)
for(int j=; j<N; 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 Qpow(Mat a,LL n)
{
Mat c;
for(int i=; i<N; ++i)
for(int j=; j<N; ++j)
c.mat[i][j]=(i==j);
for(; n; n>>=)
{
if(n&) c=Mut(c,a);
a=Mut(a,a);
}
return c;
}
LL cal(Mat A,LL n,LL b[])
{
Mat A_=Qpow(A,n-);
LL ret=;
for(int i=; i<N; i++)
{
ret+=A_.mat[][i]*b[i];
ret%=mod;
}
return (ret+mod)%mod;
}
void init_A()
{
memset(A.mat,,sizeof(A.mat));
A.mat[][]=,A.mat[][]=,A.mat[][]=;
A.mat[][]=;
A.mat[][]=;
A.mat[][]=;
A.mat[][]=;
A.mat[][]=;
}
int main()
{
init_A();
while(cin>>b[]>>b[]>>n) //b[1]即f1，b[0]即f2
{
ans=cal(A,n,b);
cout<<ans<<endl;
}
}
E——plus