TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3917
  • 题目
  • P3917[CF718C] nodgd的魔法序列 | 内含题解
    限制 : 时间限制 : - MS   空间限制 : 262144 KB
    评测说明 : 5s,256MB
    问题描述

    nodgd对魔法序列 \(a_1,\cdots,a_n\) 进行了 \(m\) 次魔法操作,有以下两种形式:

    1. 1 l r x: 将序列的第 \(l\) 到第 \(r\) 个数每个数都增加 \(x\)
    2. 2 l r: 计算 \(f(a_l)+\cdots+f(a_r)\) ,其中 \(f(x)\) 表示斐波那契数列的第 \(x\) 项。答案可能很大,所以 \(\bmod{10^9+7}\) 后输出。

    本题中的斐波那契数列定义为:

    \[ \begin{align} f(1)&=1\\ f(2)&=1\\ f(x)&=f(x-1)+f(x-2)\qquad x>2\\ \end{align} \]

    你能写个程序战胜nodgd吗?

    点击查看此题原内容“题解 高一欢乐寒假赛1”

    1.通讯靠吼
    考点:Floyd
    题目给出了每个人喊话能传递的距离,若x喊话能直接传递到y,我们当做x到y有一条边长为1的边,表示x到y要经过1人喊话。
    我们以上面的条件来构图:
    若x喊话传递的距离为Far[x], x与y的距离为z,若Far[x]<=z,那么Map[x][y]=1,否则Map[x][y]=inf
    建好图以后,因为n<=200,剩下的事情就是用floyd来跑最短路,最后Map[x][y]就是记录x到y传话要经过的人数。
    时间复杂度O(n^3)
    参考代码:
    #include<iostream>
    #include<cstdio>
    #define inf 999999999
    using namespace std;
    int Map[201][201];
    int Far[201],x,y,z;
    int ans[1001],n,m,q;
    int main()
    {
        int i,j,k;
        scanf("%d%d%d",&n,&m,&q);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&Far[i]);
            for(j=1;j<=n;j++)
             if(i!=j)Map[i][j]=inf;else Map[i][j]=0;
                       
        }
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            if(z<=Far[x])Map[x][y]=1;
            if(z<=Far[y])Map[y][x]=1;
        }
        for(k=1;k<=n;k++)
           for(i=1;i<=n;i++)
              for(j=1;j<=n;j++)
                if(Map[i][j]>Map[i][k]+Map[k][j])Map[i][j]=Map[i][k]+Map[k][j];
        for(i=1;i<=q;i++)
        {
            scanf("%d%d",&x,&y);
            ans[i]=Map[x][y];
        }
        for(i=1;i<=q;i++)
        {
            if(ans[i]>=inf)printf("no way\n");
            else printf("%d\n",ans[i]);
        }
        return 0;
    }

    2.奶牛开会
    考点:SPFA
    显然我们要计算下面两个东西:
    1.每个点到x的最短路长度,Way[i];
    2.x到每个点的最短路长度,Dis[i];
    最终答案就是min{  Way[i]+Dis[i]  }

    具体实现,以每个点为起点做一次SPFA,求出每个点到x的最短路长度。
    然后再以x为起点求出x到每个点的最短路长度。
    总共执行(n+1)次SPFA。
    SPFA的时间复杂度为O(k*m),k约为2
    本题点数n<=1000,边数m<=6000
    总时间复杂度O(n*k*m),约为O(1000*2*6000), 看似执行了很多次SPFA,但计算规模并不大,程序跑得飞快。
    注意1,如果采用朴素dijkstra,执行n次的总时间复杂度为O(n^3)会超时。
    注意2,本题有重边。

    参考标程1,朴素Map[ ][ ]暴力存图版本,用时1356 MS:
    #include<iostream>
    #include<cstdio>
    #include<queue>
    #define inf 1000000000
    using namespace std;
    int n,m,x,Cnt,Ans;
    int Dis[1005],Way[1005],Map[1005][1005];
    bool Mark[1005];
    queue<int>Q;
    void SPFA(int s)
    {
        int i,a,b,k;
        for(i=1;i<=n;i++)Dis[i]=inf;
        Dis[s]=0;   Q.push(s);   Mark[s]=true;
        while(Q.size())
        {
            a=Q.front();   Q.pop();  Mark[a]=false;
            for(b=1;b<=n;b++)
              if(Dis[a]+Map[a][b]<Dis[b])
              {
                  Dis[b]=Dis[a]+Map[a][b];
                  if(Mark[b]==false)
                  {
                      Mark[b]=true;
                      Q.push(b); 
                  }
              }
        }
    }
    int main()
    {
        int i,j,u,v,w;
        scanf("%d%d%d",&n,&m,&x);
        for(i=1;i<=n;i++)
          for(j=1;j<=n;j++)
            if(i!=j)Map[i][j]=inf; else Map[i][j]=0;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            if(w<Map[u][v])Map[u][v]=w;
        }
        for(i=1;i<=n;i++)
        {
           SPFA(i);
           Way[i]=Dis[x];
        }
        SPFA(x);
        for(i=1;i<=n;i++)
            Ans=max(Ans,Dis[i]+Way[i]);
        printf("%d\n",Ans);
    }

    参考标程2,存边方式存图,用时155MS:
    #include<iostream>
    #include<cstdio>
    #include<queue>
    #define inf 1000000000
    using namespace std;
    int n,m,x,Cnt,Ans;
    int Dis[1005],Way[1005],Last[1005],Next[6005],End[6005],Len[6005];
    bool Mark[1005];
    queue<int>Q;
    void AddEdge(int u,int v,int w)
    {
        Cnt++;
        Len[Cnt]=w;
        End[Cnt]=v;
        Next[Cnt]=Last[u];
        Last[u]=Cnt;    
    }
    void SPFA(int s)
    {
        int i,a,b,k;
        for(i=1;i<=n;i++)Dis[i]=inf;
        Dis[s]=0;   Q.push(s);   Mark[s]=true;
        while(Q.size())
        {
            a=Q.front();   Q.pop();  Mark[a]=false;
            k=Last[a];
            while(k)
            {
                b=End[k];
                if(Dis[a]+Len[k]<Dis[b])
                {
                    Dis[b]=Dis[a]+Len[k];
                    if(Mark[b]==false)
                    {
                        Mark[b]=true ;
                        Q.push(b);
                    }
                }
                k=Next[k];
            }
        }
    }
    int main()
    {
        int i,u,v,w;
        scanf("%d%d%d",&n,&m,&x);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
                         AddEdge(u,v,w);
        }
        for(i=1;i<=n;i++)
        {
           SPFA(i);
           Way[i]=Dis[x];
        }
        SPFA(x);
        for(i=1;i<=n;i++)
            Ans=max(Ans,Dis[i]+Way[i]);
        printf("%d\n",Ans);
    }

    3.架电话线
    考点:二分答案 最短路
    此题给出了一个有趣的限制条件:可免费任选k条电线,其余多出来的电线需支付其中最贵的那条的费用。
    我们这样考虑,假设需要架设8条电线,可免费安装其中2条(k==2),8条电线费用分别是1,2,3,4,5,6,7,9
    显然,我们应该免费安装费用为7和9的两条,其余5条付费安装,最后支付的费用为5。

    那么此题到底免费安装哪些合适呢?我们可以二分一个答案Mid,凡是大于Mid的都免费安装。这样最后我们只需支付Mid块钱。
    但答案Mid是否可行呢,我们需要讨论。
    我们重新构图,Map[x][y]存原图的边长,G[x][y]存新构的图的边长。
    若Map[x][y]<=Mid那么G[x][y]=0,否则G[x][y]=1
    我们从起点1出发跑一次最短路,求出到终点n的最短距离Dis[n],若Dis[n]<=k表示可行。
    Dis[n]<=k表示经过的长度大于Mid的边不超过k条,满足题目的要求。经过的其他边的长度都不超过Mid,那么Mid块钱就是可行的。

    时间复杂度O(2*m*log(MaxLen))   MaxLen为所有边中最长的那条的长度。

    参考代码1,暴力Map数组存图,用时995ms:
    #include<iostream>
    #include<cstdio>
    #include<queue>
    #define inf 100000000
    #define maxn 1005
    using namespace std;
    int g[maxn][maxn],m[maxn][maxn],dis[maxn],n,k,p;
    bool mark[maxn];
    queue<int>Q;
    void spfa(int mid)
    {
         int i,x,y;
         for(i=1;i<=n;i++){ dis[i]=inf; mark[i]=false; } 
         Q.push(1);   dis[1]=0;  mark[1]=true; 
         while(Q.size())
         {

             x=Q.front();
             Q.pop();
             mark[x]=false; 
             for(y=1;y<=n;y++)
             {
                 if(m[x][y]<=mid)g[x][y]=0;else g[x][y]=1;
                 if(m[x][y]!=inf && dis[x]+g[x][y]<dis[y])
                 {
                     dis[y]=dis[x]+g[x][y];
                     if(!mark[y])
                     {
                          Q.push(y);
                          mark[y]=true;
                     }
                 }
             }
         } 
    }

    int main()
    {
        int i,x,y,z,lft,rit,ans,mid;
        scanf("%d%d%d",&n,&p,&k);
        for(x=1;x<=n;x++)
          for(y=1;y<=n;y++){m[x][y]=inf;g[x][y]=inf;}
        for(x=1;x<=n;x++)m[x][x]=0;
        for(i=1;i<=p;i++)
        {
              scanf("%d%d%d",&x,&y,&z);
              m[x][y]=m[y][x]=z;
              g[x][y]=g[y][x]=1;    
        }
        ans=-1; 
        lft=0; 
       rit=1000000;
        while(lft<=rit)
        {
                         mid=(lft+rit)/2;            
                         spfa(mid);  
                         if(dis[n]>k)lft=mid+1;             
                         else { ans=mid; rit=mid-1;}                   
        }
        printf("%d",ans);
    }

    参考代码2,邻接链表存图,用时0ms:
    #include<iostream>
    #include<cstdio>
    #include<queue>
    #define inf 100000000
    #define maxn 1001
    using namespace std;
    int g[maxn][maxn],m[maxn][maxn],v[maxn][maxn],dis[maxn],n,k,p;
    bool mark[maxn];
    queue<int>Q;
    void spfa(int mid)
    {
         int i,x,y;
         for(i=1;i<=n;i++){ dis[i]=inf; mark[i]=false; } 
         Q.push(1);   dis[1]=0;  mark[1]=true; 
         while(Q.size())
         {

             x=Q.front();
             Q.pop();
             mark[x]=false; 
             for(i=1;i<=v[x][0];i++)
             {
                 y=v[x][i];
                 if(m[x][y]<=mid)g[x][y]=0;else g[x][y]=1;
                 if(dis[x]+g[x][y]<dis[y])
                 {
                     dis[y]=dis[x]+g[x][y];
                     if(!mark[y])
                     {
                          Q.push(y);
                          mark[y]=true;
                     }
                 }
             }
         } 
    }

    int main()
    {
        int i,x,y,z,lft,rit,ans,mid;
        scanf("%d%d%d",&n,&p,&k);
        for(x=0;x<=n;x++)
          for(y=0;y<=n;y++){v[x][y]=0;g[x][y]=inf;}
        for(i=1;i<=p;i++)
        {
              scanf("%d%d%d",&x,&y,&z);
              v[x][0]++;
              v[x][v[x][0]]=y;
              v[y][0]++;
              v[y][v[y][0]]=x;
              m[x][y]=m[y][x]=z;
              g[x][y]=g[y][x]=1;    
        }
        ans=-1; 
        lft=0; 
        rit=1000000;
        while(lft<=rit)
        {
                         mid=(lft+rit)/2;            
                         spfa(mid);  
                         if(dis[n]>k)lft=mid+1;             
                         else { ans=mid; rit=mid-1;}                   
        }
        printf("%d\n",ans);
    }   
    参考代码3,存边方式存图,应该跑得飞快,懒得写了!

    4.奶牛跨栏
    考点:floyd
    这是一道水题,故意放最后。想必很多同学看都没有机会看它吧。

    题意:奶牛们想找一条路径从站台x到站台y,使路径上最高的栏的高度最小。
    我们设Dis[x][y]表示x到y的路径上最高的栏的高度。
    如果x经过k中转再到达y,那么Dis[x][y]=max{ Dis[x][k],Dis[k][y] }
    我们想要使得Dis[x][y]尽可能小,即Dis[x][y]=min{  max{ Dis[x][k],Dis[k][y] }  }
    1<=x,y,k<=n

    经过上面的分析,再看看n的范围是300以内,我们很容易想到floyd。
    我们需要将floyd稍作变形:
    Dis[i][j]记录i到j路径上最高栏的最小值。
    for(k=1;k<=n;k++)
          for(i=1;i<=n;i++)
               for(j=1;j<=n;j++)
        Dis[i][j]=min( max( Dis[i][k] , Dis[k][j] ) , Dis[i][j] );

    题目描述“两个站台之间可能有多条道路相连。”说明图中有重边,读入时需要特殊处理一下。
    时间复杂度O(n^3)

    详情见下面的标程:
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #define inf 1000000000
    using namespace std;
    int Dis[305][305];
    int main()
    {
        int i,j,k,n,m,t,x,y,z;
        scanf("%d%d%d",&n,&m,&t);
        
        for(i=1;i<=n;i++)
          for(j=1;j<=n;j++)
            if(i!=j)Dis[i][j]=inf;else Dis[i][j]=0;
            
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            Dis[x][y]=min(Dis[x][y],z);         //处理重边,只记录权值最小的一条
        }
        
        for(k=1;k<=n;k++)
           for(i=1;i<=n;i++)
              for(j=1;j<=n;j++)
                 Dis[i][j]=min(max(Dis[i][k],Dis[k][j]),Dis[i][j]);
                 
        for(i=1;i<=t;i++)
        {
            scanf("%d%d",&x,&y);
            if(Dis[x][y]<inf)printf("%d\n",Dis[x][y]);
            else printf("-1\n");
        }
    }

     

    输入格式

    第一行两个整数 \(n(1\leq n\leq 10^5),m(1\leq m\leq 10^5)\) ,表示序列长度和魔法操作的次数。

    第二行 \(n\) 个整数的初始序列 \(a_1,\cdots,a_n(1\leq a_i\leq 10^9)\)

    接下来 \(m\) 行,每行3个整数或者4个整数,表示一个操作 \((1\leq l\leq r\leq n,\ 1\leq x_i\leq 10^9)\)

    输出格式

    每次第2种操作输出一行,答案 \(\bmod{10^9+7}\) 后的值。

    样例输入

    5 4
    1 1 2 1 1
    2 1 5
    1 2 4 2
    2 2 4
    2 1 5

    样例输出

    5
    7
    9

    提示
    • 初始序列 $1,1,2,1,1$ 。
    • 第一次操作,询问的答案是 \(f(1)+f(1)+f(2)+f(1)+f(1)=1+1+1+1+1=5\)
    • 第二次操作,修改后序列变成 $1,3,4,3,1$ 。
    • 第三次操作,询问的答案是 \(f(3)+f(4)+f(3)=2+3+2=7\)
    • 第四次操作,询问的答案是 \(f(1)+f(3)+f(4)+f(3)+f(1)=1+2+3+2+1=9\)

    来源  CF718C nodgd搬运并提供数据