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
中国(北方)大学生程序设计训练赛(第一周) (D E)的更多相关文章
-
中国(北方)大学生程序设计训练赛(第二周) (A B D G)
比赛链接 A题是KMP,先把A拼接到B的后面,然后利用next数组的意义(包括其具体含义,以及失配时的应用),得到ans #include<bits/stdc++.h> using nam ...
-
Contest1585 - 2018-2019赛季多校联合新生训练赛第一场(部分题解)
Contest1585 - 2018-2019赛季多校联合新生训练赛第一场 C 10187 查找特定的合数 D 10188 传话游戏 H 10192 扫雷游戏 C 传送门 题干: 题目描述 自然数中除 ...
-
HDU6578 2019HDU多校训练赛第一场 1001 (dp)
HDU6578 2019HDU多校训练赛第一场 1001 (dp) 传送门:http://acm.hdu.edu.cn/showproblem.php?pid=6578 题意: 你有n个空需要去填,有 ...
-
HDU6579 2019HDU多校训练赛第一场1002 (线性基)
HDU6579 2019HDU多校训练赛第一场1002 (线性基) 传送门:http://acm.hdu.edu.cn/showproblem.php?pid=6579 题意: 两种操作 1.在序列末 ...
-
扎西平措 201571030332《面向对象程序设计 Java 》第一周学习总结
<面向对象程序设计(java)>第一周学习总结 正文开头: 项目 内容 这个作业属于哪个课程 https://www.cnblogs.com/nwnu-daizh/ 这个作业的要求在哪里 ...
-
《JAVA程序设计》_第一周学习总结
20175217吴一凡 <java程序设计> 第一周学习总结 虽然已经做好了心理准备,但第一周的学习任务着实让我忙了整整三天,还是挺充实的吧.寒假已经在自己的电脑上安装好了虚拟机,我就在我 ...
-
201871010124 王生涛《面向对象程序设计JAVA》第一周学习总结
项目 内容 这个作业属于哪个课程 https://www.cnblogs.com/nwnu-daizh/ 这个作业的要求在哪里 https://edu.cnblogs.com/campus/xbsf/ ...
-
201871010132-张潇潇《面向对象程序设计(java)》第一周学习总结
面向对象程序设计(Java) 博文正文开头 项目 内容 这个作业属于哪个课程 https://www.cnblogs.com/nwnu-daizh/ 这个作业的要求在哪里 https://www.cn ...
-
网易云课堂_C语言程序设计进阶_第一周:数据类型:整数类型、浮点类型、枚举类型_1计算分数精确值
1 计算分数精确值(10分) 题目内容: 由于计算机内部表达方式的限制,浮点运算都有精度问题,为了得到高精度的计算结果,就需要自己设计实现方法. (0,1)之间的任何浮点数都可以表达为两个正整数的商, ...
随机推荐
-
【转】创建SVN仓库的步骤
转载地址:http://www.cnblogs.com/ivan0626/p/3783053.html 今天在客户现场联调,两个开发人员之间的代码想用SVN来管理,所以就临时在本地机器上搭建一个S ...
-
6. Adapter Class/Object(适配器)
意图: 将一个类的接口转换成客户希望的另外一个接口.Adapter 模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作. 适用性: 你想使用一个已经存在的类,而它的接口不符合你的需求. 你想 ...
-
Oracle+Jsp分页
分页原理: 从jsp页面传到servlet请求中,可以获得当前点击的页数,第一次进入为首页,通过在servlet中获得的当前页数,并且设计一次性显示的内容数,就是几条信息, 并且从dao层查询到数据库 ...
-
windows server 2008 下安装openmeetings 2.2.0
经过两天的痛苦经历,终于完成了openmeetings的安装部署.其实步骤都很简单,只是网上的资料都是英文的,而且很多教程都是针对openmeeting之前的版本,导致我在部署的时候走了很多弯路.网上 ...
-
Class.forName()数据库驱动
在学习jdbc中,用到Class.forName(驱动);,当时学习的时候知道Class.forName就是加载一个类到虚拟机,在加载一个类的时候,这个类的信息会被放到一个方法区,一个CLass 在J ...
-
DOM对象控制HTML无素——详解2
节点属性 在文档对象模型 (DOM) 中,每个节点都是一个对象.DOM 节点有三个重要的属性 : 1. nodeName : 节点的名称 2. nodeValue :节点的值 3. nodeType ...
-
JS滚动条下拉事件
<script type="text/javascript"> window.onscroll = function(){ var t = document.docum ...
-
CCNP交换实验(7) -- NAT
1.静态NAT2.动态NAT3.复用内部全局地址的NAT(PAT) enableconf tno ip do loenable pass ciscoline con 0logg syncexec-t ...
-
C# 为所有 CheckBox 添加事件
C# 为 form 窗体中的所有相同组件循环添加相同事件,这样减少了代码量. private void Form2_Load(object sender, EventArgs e) { foreach ...
-
jest-babel报错:Requires Babel ";^7.0.0-0";, but was loaded with ";6.26.3";
解决方法: yarn remove jest babel-jest babel-core @babel/core yarn add --dev jest babel-jest babel-core@^ ...