欧阳:诶,存的套题太多怎么办
要不我们明天考试吧?
大佬与我:不!!!
欧阳:那就愉快的决定了(核爱的微笑.jpg)
隔着屏幕都能感觉到对数学与物理,生物的满满恶意
虽然作为一名化学课代表
数学老师的报复
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,
你决定好好把握这一次机会。
一眼题 斐波那契的变形
#include <bits/stdc++.h> using namespace std; #define mod 7 long long A,B,n; struct Matrix { long long a[5][5]; Matrix() {memset(a,0,sizeof(a));} Matrix operator * (const Matrix &b) const { Matrix res; for(int i=1;i<=2;++i) { for(int j=1;j<=2;++j) { for(int k=1;k<=2;++k) { res.a[i][j]=(res.a[i][j]+a[i][k]*b.a[k][j])%mod; } } } return res; } } ans,base; void readda_() { scanf("%lld%lld%lld",&A,&B,&n); if(n<=2) {printf("1");return;} n-=2; ans.a[1][1]=ans.a[1][2]=1; base.a[1][1]=A;base.a[1][2]=1; base.a[2][1]=B;base.a[2][2]=0; while(n) { if(n&1) ans=ans*base; base=base*base; n>>=1; } printf("%lld",ans.a[1][1]); } int main() { //freopen("a.txt","r",stdin); readda_(); return 0; }
物理老师和生物老师的战争
物。万物也。牛为大物。牛为物之大者。故物从牛。与半同意。天地之数起於牵
牛。戴先生原象曰。牵牛为纪首。命曰星纪。自周而上。日月之行不起於;牵牛也。按许说
物从牛之故。又广其义如此。故从牛。勿声。文弗切。十五部。
总之,物理老师和生物老师因为“物”而吵了起来,物理老师认为,物理是万物之
源,而生物老师认为生物才是万物之源。所以物理学科带头人和生物学科带头人号召了所有
物理、生物老师,进行战斗。
战斗开始前他们需要排队,有 n 个物理老师和 m 个生物老师站在一起排成一列,
过安检进入打斗场。物理老师是一个神奇的物种,他们十分严谨,在开始之前就分析过:如
果在任意某一个人往前数(包括这个人),生物老师的数量超过了物理老师,根据牛顿三大
定律以及开普勒三大定律,这样风水是不太好的。这时候,物理老师就会引爆核弹。为了构
建社会主义和谐社会,你决定避免这一场核战的发生。所以,请你计算不会引发核弹爆炸的
排队方案的概率。(排队方案不同定义为当且仅当某一位老师不一样,注意不是老师所教的
科目不一样。eg:物 A 物 B,物 B 物 A,是不同的方案)
虽然这个标题让我想起上一任同桌的最新随笔:儿子们的战争
反正我成功的打表,然后没有找出规律
打表答案是实数时,最好弄成分数形式
结果是卡特兰数,模板题爆0,莫名心酸,
#include<bits/stdc++.h> #define re return #define ll long long #define inc(i,l,r) for(int i=l;i<=r;++i) using namespace std; template<typename T>inline void rd(T&x) { char c;bool f=0; while((c=getchar())<'0'||c>'9')if(c=='-')f=1; x=c^48; while((c=getchar())>='0'&&c<='9')x=x*10+(c^48); if(f)x=-x; } double n,m; int main() { int T; rd(T); while(T--) { rd(n),rd(m); if(n<m)printf("0.000000\n"); else printf("%.6lf\n",(n+1-m)/(n+1)); } re 0; }
化学竞赛的的大奖
【问题描述】
XYX 在 CChO(全国化学奥林匹克竞赛)比赛中获得了大奖,奖品是一张特殊的机票。
使用这张机票,可以在任意一个国家内的任意城市之间的免费飞行,只有跨国飞行时才
会有额外的费用。XYX 获得了一张地图,地图上有城市之间的飞机航班和费用。已知从
每个城市出发能到达所有城市,两个城市之间可能有不止一个航班。一个国家内的每两
个城市之间一定有不止一条飞行路线,而两个国家的城市之间只 有一条飞行路线。XYX
想知道,从每个城市出发到额外费用最大的城市,以便估算出出行的费用,请你帮助他。
当然,你不能通过乘坐多次一个航班增加额外费用, 也就是必须沿费用最少的路线飞
行。
【输入】
第一行,两个整数 N,M,表示地图上有 N 个城市,M 条航线。
接下来 M 行,每行三个整数 a,b,c,表示城市 a,b 之间有一条费用为 c 的航线。
【输出】
共 N 行,第 i 行为从城市 i 出发到达每个城市额外费用的最大值。
由于在最近在写树的题,感觉非常良好?
手玩一把样例,所谓国内=》就是tarjan缩一波点
额外费用,就是该点到树上最远点的距离
这怕不是n^2的换根
算了,二次扫描dp一下
#include<bits/stdc++.h> #define re return #define ll long long #define inc(i,l,r) for(register int i=l;i<=r;++i) using namespace std; template<typename T>inline void rd(T&x) { char c;bool f=0; while((c=getchar())<'0'||c>'9')if(c=='-')f=1; x=c^48; while((c=getchar())>='0'&&c<='9')x=x*10+(c^48); if(f)x=-x; } const int maxn=20005,maxm=200005; int n,k=1,m,hd[maxn]; struct node{ int to,nt,val; }e[maxm<<1],e1[maxn<<1]; inline void add(int x,int y,int z) { e[++k].to=y;e[k].nt=hd[x];hd[x]=k;e[k].val=z; e[++k].to=x;e[k].nt=hd[y];hd[y]=k;e[k].val=z; } inline void add1(int x,int y,int z) { e1[++k].to=y;e1[k].nt=hd[x];hd[x]=k;e1[k].val=z; e1[++k].to=x;e1[k].nt=hd[y];hd[y]=k;e1[k].val=z; } int tot,col,dfn[maxn],low[maxn],belong[maxn]; stack<int>s; inline void tarjan(int x,int fa) { s.push(x); dfn[x]=low[x]=++tot; for(int i=hd[x];i;i=e[i].nt) { int v=e[i].to; if(v==fa)continue; if(!dfn[v]) { tarjan(v,x); low[x]=min(low[x],low[v]); } else if(!belong[v])low[x]=min(low[x],dfn[v]); } if(dfn[x]==low[x]) { ++col; int v=-1; while(v!=x) { v=s.top(); belong[v]=col; s.pop(); } } } //------------------------------------------------------------------------------------------------------------------------------- struct lll { int val,id; }dis1[maxn],dis2[maxn]; /* e1e1e1e1e1 */ inline void dfs(int x,int fa) { for(int i=hd[x];i;i=e1[i].nt) { int v=e1[i].to; if(v==fa)continue; dfs(v,x); if(dis1[v].val+e1[i].val>=dis1[x].val) { dis2[x]=dis1[x]; dis1[x].val=dis1[v].val+e1[i].val; dis1[x].id=v; } else if(dis1[v].val+e1[i].val>dis2[x].val) { dis2[x].val=dis1[v].val+e1[i].val; dis2[x].id=v; } } } int ans[maxn],fa[maxn]; inline void dfs1(int x,int fa,int maxx) { ans[x]=max(dis1[x].val,maxx); for(int i=hd[x];i;i=e1[i].nt) { int v=e1[i].to; if(v==fa)continue; if(v!=dis1[x].id)dfs1(v,x,max(dis1[x].val,maxx)+e1[i].val); else dfs1(v,x,max(dis2[x].val,maxx)+e1[i].val); } } inline int find(int x) { re x==fa[x]?x:fa[x]=find(fa[x]); } int main() { int x,y,z; rd(n),rd(m); inc(i,1,m) { rd(x),rd(y),rd(z); add(x,y,z); } inc(i,1,n) { if(!dfn[i])tarjan(i,0); fa[i]=i; } int m=k; inc(i,1,col)hd[i]=0; k=1; inc(i,2,m) { int x=belong[e[i].to],y=belong[e[i^1].to]; if(x!=y&&find(x)!=find(y)) { add1(x,y,e[i].val); fa[fa[x]]=y; } } dfs(1,1); dfs1(1,1,0); inc(i,1,n) printf("%d\n",ans[belong[i]]); re 0; }