noip2014day1题解-白红宇

noip2014day1题解

阅读量：4511 次

发布时间：2019-06-08

本文共 6149 字，大约阅读时间需要 20 分钟。

描述

石头剪刀布是常见的猜拳游戏：石头胜剪刀，剪刀胜布，布胜石头。如果两个人出拳一样，则不分胜负。在《生活大爆炸》第二季第 8 集中出现了一种石头剪刀布的升级版游戏。升级版游戏在传统的石头剪刀布游戏的基础上，增加了两个新手势：

斯波克：《星际迷航》主角之一。蜥蜴人：《星际迷航》中的反面角色。

这五种手势的胜负关系如表一所示，表中列出的是甲对乙的游戏结果。

现在，小 A 和小 B 尝试玩这种升级版的猜拳游戏。已知他们的出拳都是有周期性规律的，但周期长度不一定相等。例如：如果小 A 以“石头-布-石头-剪刀-蜥蜴人-斯波克”长度为 6 的周期出拳，那么他的出拳序列就是“石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-……”，而如果小 B 以“剪刀-石头-布-斯波克-蜥蜴人”长度为 5 的周期出拳，那么他出拳的序列就是“剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-……”

已知小 A 和小 B 一共进行 N 次猜拳。每一次赢的人得 1 分，输的得 0 分；平局两人都得 0 分。现请你统计 N 次猜拳结束之后两人的得分。

格式

输入格式

第一行包含三个整数：N，NA，NB，分别表示共进行 N 次猜拳、小 A 出拳的周期长度，小 B 出拳的周期长度。数与数之间以一个空格分隔。

第二行包含 NA 个整数，表示小 A 出拳的规律，第三行包含 NB 个整数，表示小 B 出拳的规律。其中，0 表示“剪刀”，1 表示“石头”，2 表示“布”，3 表示“蜥蜴人”， 4 表示 “斯波克”。数与数之间以一个空格分隔。

输出格式

输出一行，包含两个整数，以一个空格分隔，分别表示小 A、小 B 的得分。

样例1

样例输入1

10 5 60 1 2 3 40 3 4 2 1 0

样例输出1

6 2

样例2

样例输入2

9 5 50 1 2 3 41 0 3 2 4

样例输出2

4 4

限制

对于 100%的数据，0 < N ≤ 200，0 < NA ≤ 200， 0 < NB ≤ 200。

模拟...

1 #include
       
         2 #include
        
          3 #include
         
           4 int nowa=-1,nowb=-1; 5 int N,Na,Nb,ansa=0,ansb=0,A[201],B[201]; 6  7 void change_a(int a,int b) 8 { 9     if(a==0&&(b==2||b==3))ansa++;10     else if(a==1&&(b==3||b==0))ansa++;11     else if(a==2&&(b==4||b==1))ansa++;12     else if(a==3&&(b==4||b==2))ansa++;13     else if(a==4&&(b==0||b==1))ansa++;14 }15 16 void change_b(int a,int b)17 {18     if(a==0&&(b==2||b==3))ansb++;19     else if(a==1&&(b==3||b==0))ansb++;20     else if(a==2&&(b==4||b==1))ansb++;21     else if(a==3&&(b==4||b==2))ansb++;22     else if(a==4&&(b==0||b==1))ansb++;23 }24 25 int main()26 {27     std::cin>>N>>Na>>Nb;28     Na--;29     Nb--;30     for(int i=0;i<=Na;i++)std::cin>>A[i];31     for(int i=0;i<=Nb;i++)std::cin>>B[i];32     for(int i=0;i

描述

无向连通图 G 有 n 个点，n-1 条边。点从 1 到 n 依次编号，编号为 i 的点的权值为，每条边的长度均为 1。图上两点(u, v)的距离定义为 u 点到 v 点的最短距离。对于图上的点对(u, v)，若它们的距离为 2，则它们之间会产生×的联合权值。

请问图 G 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？

格式

输入格式

第一行包含 1 个整数 n。

接下来 n-1 行，每行包含 2 个用空格隔开的正整数 u、v，表示编号为 u 和编号为 v 的点之间有边相连。

最后 1 行，包含 n 个正整数，每两个正整数之间用一个空格隔开，其中第 i 个整数表示图 G 上编号为 i 的点的权值为。

输出格式

输出共 1 行，包含 2 个整数，之间用一个空格隔开，依次为图 G 上联合权值的最大值和所有联合权值之和。由于所有联合权值之和可能很大，输出它时要对10007取余。

样例1

样例输入1

51 22 33 44 51 5 2 3 10

样例输出1

20 74

限制

对于 30%的数据，1 < n ≤ 100；

对于 60%的数据，1 < n ≤ 2000；

对于 100%的数据，1 < n ≤ 200,000，0 < ≤ 10,000。

提示

本例输入的图如上所示，距离为 2 的有序点对有(1,3)、(2,4)、(3,1)、(3,5)、(4,2)、(5,3)。其联合权值分别为 2、15、2、20、15、20。其中最大的是 20，总和为 74。

枚举中间的点，算的时候一边加一边乘

1 #include
         
           2 #include
          
            3 #include
           
             4 #include
            
              5 using namespace std; 6 int n,E[400001][2]={
       0},index[200001]={
       0},w[200001]; 7  8 int main() 9 {10     int a,b,sum,max1,max2,maxans=0,sumans=0;11 12     cin>>n;13     for(int i=1;i
             
              max1)max1=b;40             else max2=max2>b?max2:b;41 42             sumans+=(sum%10007)*b*2%10007;43             sumans%=10007;        44             sum+=b;45 46             a=E[a][1];47         }48 49         if(max1*max2>maxans)maxans=max1*max2;50     }51 52     cout<
              
               <<" "<

描述

Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度，让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话，便宣告失败。

为了简化问题，我们对游戏规则进行了简化和改编：

游戏界面是一个长为 n，高为 m 的二维平面，其中有k 个管道（忽略管道的宽度）。

小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发，到达游戏界面最右边时，游戏完成。

小鸟每个单位时间沿横坐标方向右移的距离为 1，竖直移动的距离由玩家控制。如果点击屏幕，小鸟就会上升一定高度 X，每个单位时间可以点击多次，效果叠加；如果不点击屏幕，小鸟就会下降一定高度 Y。小鸟位于横坐标方向不同位置时，上升的高度 X 和下降的高度 Y 可能互不相同。

小鸟高度等于 0 或者小鸟碰到管道时，游戏失败。小鸟高度为 m 时，无法再上升。

现在，请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。

格式

输入格式

第 1 行有 3 个整数 n，m，k，分别表示游戏界面的长度，高度和水管的数量，每两个整数之间用一个空格隔开；

接下来的 n 行，每行 2 个用一个空格隔开的整数 X 和 Y，依次表示在横坐标位置 0~n-1 上玩家点击屏幕后，小鸟在下一位置上升的高度 X，以及在这个位置上玩家不点击屏幕时，小鸟在下一位置下降的高度 Y。

接下来 k 行，每行 3 个整数 P，L，H，每两个整数之间用一个空格隔开。每行表示一个管道，其中 P 表示管道的横坐标，L 表示此管道缝隙的下边沿高度为 L，H 表示管道缝隙上边沿的高度（输入数据保证 P 各不相同，但不保证按照大小顺序给出）。

输出格式

共两行。

第一行，包含一个整数，如果可以成功完成游戏，则输出 1，否则输出 0。第二行，包含一个整数，如果第一行为 1，则输出成功完成游戏需要最少点击屏幕数，否则，输出小鸟最多可以通过多少个管道缝隙。

样例1

样例输入1

10 10 63 99 91 21 31 21 12 12 11 62 21 2 75 1 56 3 57 5 88 7 99 1 3

样例输出1

样例2

样例输入2

10 10 41 23 12 21 81 83 22 12 12 21 21 0 26 7 99 1 43 8 10

样例输出2

限制

对于 30%的数据：5≤n≤10，5≤m≤10，k=0，保证存在一组最优解使得同一单位时间最多点击屏幕 3 次；

对于 50%的数据：5≤n≤20，5≤m≤10，保证存在一组最优解使得同一单位时间最多点击屏幕 3 次；

对于 70%的数据：5≤n≤1000，5≤m≤100；

对于 100%的数据：5≤n≤10000，5≤m≤1000，0≤k<n，0<X<m，0<Y<m，0<P<n，0≤L<H ≤m，L+1<H。

提示

如下图所示，蓝色直线表示小鸟的飞行轨迹，红色直线表示管道。

dp...只是转移有点难写（容易写错

1 #include
           
             2 #include
            
              3 #include
             
               4 #define N 10000 5 #define M 1000 6 using namespace std; 7 int n,m,k; 8 int cube[N+5][2]; 9 int X[N+5],Y[N+5];10 int answer[N+5][M+5];11 12 int main()13 {14     int a,b,c;15     cin>>n>>m>>k;16     for(int i=0;i
              
               >X[i]>>Y[i],cube[i][0]=0,cube[i][1]=m+1;18     cube[n][0]=0;19     cube[n][1]=m+1;20     for(int i=0;i
               
                >a>>b>>c;23             cube[a][0]=b;24             cube[a][1]=c;25     }26     for(int i=1;i<=n+2;i++)27      for(int j=0;j<=m;j++)28       answer[i][j]=999999999;29     for(int i=1;i<=n+2;i++)30     {31             for(int j=1;j<=m;j++)32              if(answer[i-1][j]!=999999999)33               answer[i][min(j+X[i-1],m)]=min(answer[i][min(j+X[i-1],m)],answer[i-1][j]+1);34             for(int j=1;j<=m;j++)35              if(answer[i][j]!=999999999)36               answer[i][min(j+X[i-1],m)]=min(answer[i][min(j+X[i-1],m)],answer[i][j]+1);37             for(int j=Y[i-1]+1;j<=m;j++)38              if(answer[i-1][j]!=999999999)39               answer[i][j-Y[i-1]]=min(answer[i-1][j],answer[i][j-Y[i-1]]);40             for(int j=0;j<=cube[i][0];j++)41               answer[i][j]=999999999;42             for(int j=cube[i][1];j<=m;j++)43               answer[i][j]=999999999;44      }       45      /*for(int i=0;i<=n;i++)46      {47              cout<
                <<":"<
                 
                  =0;i--)63 for(int j=0;j<=m;j++)64 if(answer[i][j]!=999999999)65 {66 ans=0;67 for(int l=0;l<=i;l++)68 if(cube[l][0]!=0||cube[l][1]!=m+1)69 ans++;70 cout<<0<
                  
                   <
                   
                    <