原题,洛谷广义斐波那契数列
矩阵快速幂水过
不过这题的模数很小,可以找循环节
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
using namespace std;
const LL mod=7;
inline LL read()
{
char c=getchar();LL f=1,x=0;
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*f;
}
struct Ma
{
LL a[3][3];
Ma(){memset(a,0,sizeof(a));}
};
LL A,B,n;
Ma Mul(Ma A,Ma B)
{
Ma c;
for(LL k=1;k<=2;k++)
for(LL i=1;i<=2;i++)
for(LL j=1;j<=2;j++)
c.a[i][j]+=(A.a[i][k]%mod*B.a[k][j]%mod)%mod;
return c;
}
inline void Ma_Pow(Ma bg,LL p)
{
Ma base;base.a[1][1]=1;base.a[2][2]=1;
while(p)
{
if(p&1) base=Mul(base,bg);
p>>=1;
bg=Mul(bg,bg);
}
printf("%lld",(base.a[1][1] % mod + base.a[2][1] % mod)% mod);
}
int main()
{
// freopen("attack.in","r",stdin);
// freopen("attack.out","w",stdout);
A=read();B=read();n=read();
if(n<=2)
{
printf("1");
return 0;
}
Ma bg;
bg.a[1][1]=A%mod;bg.a[1][2]=1;
bg.a[2][1]=B%mod;bg.a[2][2]=0;
Ma_Pow(bg,n-2);
return 0;
}
不会
正解:
其实这样一想,这个玩意儿就是卡特兰数。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
using namespace std;
const int mod=7;
int main()
{
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
double n,m;
cin>>n>>m;
if(n<m) printf("0.000000\n");
else printf("%.6lf\n",1.0-(double)(m/(n+1)));
}
return 0;
}
mmp这是我最想吐槽的一个题目!!
然后就可以随便飞
这个下划线加的有什么特殊含义么?
前面都有任意了。。。。
搞不懂出题人在搞什么。。。
然后读错了题目的我就瞎搞,居然还过样例了。。
后来稍微一改就是40分
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int MAXN=1e6+10;
const int INF=0x7fffff;
inline int read()
{
char c=getchar();int f=1,x=0;
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*f;
}
struct node
{
int u,v,w,nxt;
bool flag;//是否是割边
bool can;//是否能经过
}edge[MAXN];
int head[MAXN];
int num=1;
inline void add_edge(int x,int y,int z)
{
edge[num].u=x;
edge[num].v=y;
edge[num].w=z;
edge[num].nxt=head[x];
head[x]=num++;
}
int n,m;
int dis[1001][1001];
int nowdis[1001];
int vis[MAXN];
inline void BFS(int now)
{
queue<int>q;q.push(now);
while(q.size()!=0)
{
int p=q.front();
q.pop();
for(int i=head[p];i!=-1;i=edge[i].nxt)
if(vis[edge[i].v]==0&&edge[i].can==0)
vis[edge[i].v]=1,q.push(edge[i].v);
}
}
inline void SPFA(int now)
{
queue<int>q;q.push(now);
memset(vis,0,sizeof(vis));vis[now]=1;
memset(nowdis,0x7f,sizeof(nowdis));
nowdis[now]=0;
while(q.size()!=0)
{
int p=q.front();q.pop();vis[p]=0;
for(int i=head[p];i!=-1;i=edge[i].nxt)
{
if(nowdis[edge[i].v]>nowdis[edge[i].u]+edge[i].w)
{
nowdis[edge[i].v]=nowdis[edge[i].u]+edge[i].w;
if(vis[edge[i].v]==0)
q.push(edge[i].v);
}
}
}
for(int i=1;i<=n;i++)
dis[now][i]=min(dis[now][i],nowdis[i]);
}
int main()
{
// freopen("prize.in","r",stdin);
// freopen("prize.out","w",stdout);
n=read();m=read();
memset(head,-1,sizeof(head));
memset(dis,0x7f,sizeof(dis));
for(int i=1;i<=m;i++)
{
int x=read(),y=read(),z=read();
add_edge(x,y,z);
add_edge(y,x,z);
}
for(int i=1;i<=num-1;i++)
{
memset(vis,0,sizeof(vis));
edge[i].can=1;
BFS(edge[i].u);
if(vis[edge[i].v]==0)
edge[i].flag=1;
edge[i].can=0;
}
for(int i=1;i<=num-1;i++)
if(edge[i].flag!=1)
edge[i].w=0;
for(int i=1;i<=n;i++)//枚举每一个点
{
for(int j=1;j<=n;j++) nowdis[j]=INF;
nowdis[i]=0;
SPFA(i);
int ans=0;
for(int j=1;j<=n;j++)
if(dis[i][j]<INF)
ans=max(ans,dis[i][j]);
printf("%d\n",ans);
}
return 0;
}
/*
6 6
1 4 2
1 2 6
2 5 3
2 3 7
6 3 4
3 1 8
//
4
4
4
6
7
7
*/
正解:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<ctime>
#include<cstdlib>
#include<stack>
using namespace std;
const int MAXN=1e6+10;
inline int read()
{
char c=getchar();int f=1,x=0;
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*f;
}
struct EDGE
{
struct node
{
int u,v,w,nxt;
}edge[MAXN];
int head[MAXN];
int num;
EDGE() { num=1; memset(head,-1,sizeof(head)); }
inline void add_edge(int x,int y,int z)
{
edge[num].u=x;
edge[num].v=y;
edge[num].w=z;
edge[num].nxt=head[x];
head[x]=num++;
}
}e1,e2;
int dfn[MAXN],low[MAXN],vis[MAXN],color[MAXN],colornum,tot=0;
stack<int>s;
int Tarjan(int now,int fa)
{
dfn[now]=low[now]=++tot;
vis[now]=1;
s.push(now);
for(int i=e1.head[now];i!=-1;i=e1.edge[i].nxt)
{
if(dfn[e1.edge[i].v]==0) Tarjan(e1.edge[i].v,now),low[now]=min(low[now],low[e1.edge[i].v]);
else if(vis[e1.edge[i].v]&&e1.edge[i].v!=fa) low[now]=min(low[now],dfn[e1.edge[i].v]);
}
if(dfn[now]==low[now])
{
int top;
++colornum;
do
{
top=s.top(); color[top]=colornum;
vis[top]=0; s.pop();
}while(top!=now);
}
}
struct D
{
int dis[MAXN];
D(){memset(dis,0,sizeof(dis));}
struct M{int pos,val;M(){pos=val=0;}}MX;
void clear(){MX.val=0;memset(dis,0,sizeof(dis));}
int dfs(int now,int fa)
{
for(int i=e2.head[now];i!=-1;i=e2.edge[i].nxt)
{
if(e2.edge[i].v==fa) continue;
dis[e2.edge[i].v]=dis[e2.edge[i].u]+e2.edge[i].w;
if(dis[e2.edge[i].v]>MX.val) MX.val=dis[e2.edge[i].v],MX.pos=e2.edge[i].v;
dfs(e2.edge[i].v,e2.edge[i].u);
}
}
}d1,d2;
int main()
{
int n=read(),m=read();
for(int i=1;i<=m;i++)
{
int x=read(),y=read(),z=read();
e1.add_edge(x,y,z);
e1.add_edge(y,x,z);
}
for(int i=1;i<=n;i++)
{
if(dfn[i]==0)
Tarjan(i,0);
}
for(int i=1;i<=e1.num-1;i++)
if(color[e1.edge[i].u]!=color[e1.edge[i].v])
e2.add_edge(color[e1.edge[i].u],color[e1.edge[i].v],e1.edge[i].w);
d1.dfs(1,-1);
d1.clear();
d1.dfs(d1.MX.pos,-1);
d2.dfs(d1.MX.pos,-1);
for(int i=1;i<=n;i++)
printf("%d\n",max(d1.dis[color[i]],d2.dis[color[i]]));
return 0;
}
考的还可以吧,T2做不出来纯属能力问题
T3我就不多说啥了。。