2017.11.7解题报告。2017.11.7解题报告。

展望分数:100+0+40=140

前瞻分数:100+0+40=140

实则分数:100+0+0=100

实在分数:100+0+0=100

惊!出题人的平摆放机票可以据此最为次

 

吃惊!出题人的均等摆机票可以用极端次

 

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

  

 

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

  

 

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

不会

正解:

图片 1

实在这么平等想,这个玩意儿就是卡特兰数。。

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

  

 

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

不会

正解:

图片 2

实质上这么平等想,这个玩意儿就是卡特兰数。。

#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这是自最好惦念吐槽之一个题材!!

图片 3

接下来就足以随便飞

图片 4

此下划线加的生什么出格含义么?

面前都有自由了。。。。

折腾不理解出书人于干什么。。。

 

接下来读错了问题的自我就算瞎jb搞,居然尚了样例了。。

后来略一改便是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
*/

  

正解:

图片 5

 

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

  

 

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

 

mmp这是自己最好思念吐槽之一个题材!!

图片 6

接下来就得随便飞

图片 7

其一下划线加的来啊异常含义么?

前都发擅自了。。。。

施行不明了出写人当将什么。。。

 

接下来读错了问题之自家就是瞎jb搞,居然尚了样例了。。

后来不怎么一改便是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
*/

  

正解:

图片 8

 

#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自我哪怕无多说吗了。。

 

总结

测验的尚好吧,T2做不出去纯属能力问题

T3自家就是不多说吗了。。

 

 

 

 

 

相关文章