预
100 + 100 + 60
实
30 + 0 + 40
T16500 2017.11.7数学老师的报复
题目描述
11 班数学大佬 YXN 又在上数学课的时候把班主任 MP6 的错误当众挑出来了,MP6 再一
次感到很难堪,于是决定报复 YXN
MP6 对 YXN 说:给你一个函数 f(x),定义如下:
f ( 1 ) = 1
f ( 2 ) = 1
f ( n ) = ( A * f ( n - 1 ) + B * f ( n - 2 ) ) mod 7。
YXN 说这还不简单,可以秒杀! MP6 微微笑了笑说:n 等于 100 你算得出来,那 n 等于 2147483648 呢?
YXN 哑口无言,决定向信息组的你求助。由于这是你唯一一次可以在数学题上秒杀 YXN，
你决定好好把握这一次机会。
输入输出格式
输入格式：
仅一行包含 3 个整数 A,B 和 n。
输出格式：
一个整数,即 f ( n ) 的值。
暂无测试点
说明
20%的数据, n≤1,000
50%的数据, n≤100,000,000
100%的数据,n≤2147,483,648
矩阵快速幂裸题，用初始矩阵开始乘，因为是初始矩阵，最后少计算了一次
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
#define LL long long
const int M = 7;
struct Matrix {
LL a[2][2];
Matrix() {
memset(a,0,sizeof(a));
}
Matrix operator * (const Matrix &y)const {
Matrix aa;
for(int i=0;i<=1;i++)
for(int j=0;j<=1;j++)
for(int k=0;k<=1;k++)
aa.a[i][j]=(aa.a[i][j]+a[i][k]*y.a[k][j])%M;
return aa;
}
};
LL a,b;
int q_pow(LL x) {
Matrix ans,trs;
ans.a[0][0]=ans.a[0][1]=1;
trs.a[0][0]=a,trs.a[1][0]=b,trs.a[0][1]=1;
while(x) {
if(x&1)
ans=ans*trs;
trs=trs*trs;
x>>=1;
}
return ans.a[0][0];
}
int main() {
// freopen("attack.in","r",stdin);
// freopen("attack.out","w",stdout);
LL n;
scanf("%lld%lld%lld",&a,&b,&n);
cout<<q_pow(n-2)<<endl;
return 0;
}
T16501 2017.11.7 T2.物理和生物老师的战争
题目描述
物。万物也。牛为大物。牛为物之大者。故物从牛。与半同意。天地之数起於牵
牛。戴先生原象曰。牵牛为纪首。命曰星纪。自周而上。日月之行不起於；牵牛也。按许说
物从牛之故。又广其义如此。故从牛。勿声。文弗切。十五部。
总之，物理老师和生物老师因为“物”而吵了起来，物理老师认为，物理是万物之
源， 而生物老师认为生物才是万物之源。 所以物理学科带头人和生物学科带头人号召了所有
物理、生物老师，进行战斗。
战斗开始前他们需要排队，有 n 个物理老师和 m 个生物老师站在一起排成一列，
过安检进入打斗场。物理老师是一个神奇的物种，他们十分严谨，在开始之前就分析过：如
果在任意某一个人往前数（包括这个人） ，生物老师的数量超过了物理老师，根据牛顿三大
定律以及开普勒三大定律，这样风水是不太好的。这时候，物理老师就会引爆核弹。为了构
建社会主义和谐社会，你决定避免这一场核战的发生。所以，请你计算不会引发核弹爆炸的
排队方案的概率。 （排队方案不同定义为当且仅当某一位老师不一样，注意不是老师所教的
科目不一样。eg：物 A 物 B，物 B 物 A，是不同的方案）
输入输出格式
输入格式：
第一行，Test , 表示测试数据的组数。
每个数据 有两个数 N,M
输出格式：
对于每组数据,输出一个实数（保留到小数点后 6 位,）
输入输出样例
暂无测试点
说明
30%的数据：(Test<=10),(0<=N,M<=1000).
100%的数据：(Test<=9008 )，( 0<=N,M<=20000 ).
打表找规律，暴力对拍。
判断n<m情况时，把0打成5，
然后没分，因为多组数据
#include<cstdio>
#include<iostream>
#include<algorithm>
inline int read() {
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9') {
if(c=='-')f=-1;
c=getchar();
}
while(c<='9'&&c>='0') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int n,m;
int main() {
int T=read();
while(T--) {
n=read();m=read();
if(n==0){
puts("0.000000");continue;
}
int tmp=(n-m);
if(tmp<0){ puts("0.000000");
continue;
}
double ans=double(n-m+1)/double(n+1);
printf("%.6lf
",ans);
}
return 0;
}
T16502 2017.11.7T3.化学竞赛的大奖
题目描述
XYX 在 CChO(全国化学奥林匹克竞赛)比赛中获得了大奖，奖品是一张特殊的机票。
使用这张机票，可以在任意一个国家内的任意城市之间的免费飞行，只有跨国飞行时才
会有额外的费用。XYX 获得了一张地图，地图上有城市之间的飞机航班和费用。已知从
每个城市出发能到达所有城市，两个城市之间可能有不止一个航班。一个国家内的每两
个城市之间一定有不止一条飞行路线， 而两个国家的城市之间只 有一条飞行路线。 XYX
想知道， 从每个城市出发到额外费用最大的城市， 以便估算出出行的费用， 请你帮助他。
当然，你不能通过乘坐多次一个航班增加额外费用， 也就是必须沿费用最少的路线飞
行。
输入输出格式
输入格式：
第一行，两个整数 N,M，表示地图上有 N 个城市，M 条航线。
接下来 M 行，每行三个整数 a,b,c，表示城市 a,b 之间有一条费用为 c 的航线。
输出格式：
共 N 行，第 i 行为从城市 i 出发到达每个城市额外费用的最大值。
输入输出样例
暂无测试点
说明
对于 40%的数据 1<=N<=1000,1<=M<=1000
对于 100%的数据 1<=N<=20000,1<=M<=200000
写了个树形dp，炸了
tarjan缩点后形成一棵树，树上每个点距离到其直径两端距离取最大值
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n,m,topp;
#define N 300007
#define NN 20007
struct sta{
int sz[30007];
int top(){return sz[topp];}
void push(int x){sz[++topp]=x;}
void pop(){if(topp>0)topp--;}
}stack;
inline int read()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
struct node{
int v,next,w;
}edge1[N*5],edge[N*5];int head[NN],num;
int dfn[NN],low[NN],color[NN];bool vis[NN];
inline void add_edge(int x,int y,int w) {
edge[++num].v=y;edge[num].next=head[x];edge[num].w=w;head[x]=num;
}int num1=0,head1[N];
inline void add_edge1(int x,int y,int w) {
edge1[++num1].v=y;edge1[num1].next=head1[x];edge1[num1].w=w;head1[x]=num1;
}
int cnt;
void tarjan(int x,int f) {
dfn[x]=low[x]=++num;
stack.push(x);
vis[x]=1;
for(int i=head[x];i;i=edge[i].next) {
int v=edge[i].v;
// if(v==f)continue;
if(!dfn[v]) {
tarjan(v,x);
low[x]=min(low[x],low[v]);
}
else if(vis[v]&&v!=f)low[x]=min(low[x],dfn[v]);
}
if(dfn[x]==low[x]) {
++cnt;
int r;
do {
r=stack.top();
color[r]=cnt;
vis[r]=0;
stack.pop();
}while(r!=x);
}
return ;
}
int mx,root,dis1[NN],dis[NN];
void dfs1(int x,int f) {
for(int i=head1[x];i;i=edge1[i].next) {
int v=edge1[i].v;
if(v==f)continue;
dis[v]=dis[x]+edge1[i].w;
if(dis[v]>mx)mx=dis[v],root=v;
dfs1(v,x);
}
}
void dfs2(int u,int f) {
for(int i=head1[u];i;i=edge1[i].next) {
int v=edge1[i].v;
if(v==f)continue;
dis1[v]=dis1[u]+edge1[i].w;
dfs2(v,u);
}
}
void floyd() {
dfs1(1,0);
mx=0;memset(dis,0,sizeof dis);
dfs1(root,0);
dfs2(root,0);
for(int i=1;i<=n;++i)
printf("%d
",std::max(dis[color[i]],dis1[color[i]]));
}
int main() {
//freopen("prize.in","r",stdin);
//freopen("prize.out","w",stdout);
n=read(),m=read();
int a,b,w;
//cnt=n;
for(int i=1;i<=m;i++) {
a=read(),b=read(),w=read();
//scanf("%d%d%d",&a,&b,&w);
add_edge(a,b,w);
add_edge(b,a,w);
}
num=0;
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i,0);
// memset(vis,0,sizeof vis);
// memset(map,0x3f,sizeof map);
for(int i=1;i<=n;i++) {
for(int j=head[i];j;j=edge[j].next) {
int v=edge[j].v;
if(color[i]!=color[v]){
add_edge1(color[i],color[v],edge[j].w);
//add_edge1(color[v],color[i],edge[j].w);
}
}
}
floyd();
return 0;
}