# 震惊！出题人的一张机票可以用无限次

## T1https://www.luogu.org/problem/show?pid=T16500

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
using namespace std;
const LL mod=7;
{
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);
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;
}```

## T2https://www.luogu.org/problem/show?pid=T16501

```#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;
}```

## T3https://www.luogu.org/problem/show?pid=T16502

mmp这是我最想吐槽的一个题目！！

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int MAXN=1e6+10;
const int INF=0x7fffff;
{
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 num=1;
inline void add_edge(int x,int y,int z)
{
edge[num].u=x;
edge[num].v=y;
edge[num].w=z;
}
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();
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;
{
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);
memset(dis,0x7f,sizeof(dis));
for(int i=1;i<=m;i++)
{
}
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;
{
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 num;
inline void add_edge(int x,int y,int z)
{
edge[num].u=x;
edge[num].v=y;
edge[num].w=z;
}
}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);
{
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)
{
{
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()
{
for(int i=1;i<=m;i++)
{
}
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])
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;
}```

T3我就不多说啥了。。

1811 篇文章126 人订阅

0 条评论