Problem A: 神奇的fans

Time Limit: 1 Sec  

Memory Limit: 128 MB

Submit: 84  

Solved: 30

[ ][ ][ ]

Description

传说fans是一个数学天才。在他五岁那年，从一堆数字卡片中选出了4张 卡片：5，7，6，8。这4个数字有什么神秘之处呢？如果把这4张卡片自左往右的排成：5，6，7，8。你就会发现：原来这4个数字构成了等差数列！当年 fans选出了n组卡片，据说都能够构成等差数列。但是事实真的是这样吗？fans真的有这么神奇吗？ n组数据就是fans选出的n组卡片，请你判断每一组卡片是否能构成等差数列.

Input

第一个数为数据的组数n，表示后面有n行，每行中的第一个数为该组数据的元素个数m（1≤m≤100），其后是m个正整数（不会超出int的表示范围）。

Output

如果能够构成等差数列，输出“yes”，否则输出“no”。

Sample Input

2

4 5 7 6 8

8 1 7 3 2 8 12 78 3

Sample Output

yes

no

题目大意：给你n个数，问是否可以构成等差数列

分析：水题，sort后判断一下是不是等差即可

1 #include 
       
         2 #include
        
          3 #include
         
           4 using namespace std; 5 int n,t; 6 int a[110]; 7 int main() 8 { 9     scanf("%d", &t);10     while(t--)11     {12         scanf("%d", &n);13         for (int i=0; i
         
        
       

Problem B: 

Time Limit: 2 Sec  

Memory Limit: 128 MB

Submit: 18  

Solved: 5

[ ][ ][ ]

Description

      Adam和Eve玩一个游戏，他们先从1900.1.1到2001.11.4这个日期之间随意抽取一个日期出来。然后他们轮流对这个日期进行操作：       1  ：  把日期的天数加1，例如1900.1.1变到1900.1.2       2  ：  把月份加1，例如：1900.1.1变到1900.2.1       其中如果天数超过应有天数则日期变更到下个月的第1天。月份超过12则变到下一年的1月。而且进行操作二的时候，如果有这样的日期：1900.1.31，则变成了1900.2.31，这样的操作是非法的，我们不允许这样做。而且所有的操作均要考虑历法和闰年的规定。       谁先将日期变到2001.11.4谁就赢了。       每次游戏都是Adam先操作，问他有没有必胜策略？

Input

    一个测试点。多组数据。     第一行为数据组数。     接下来一行X  Y  Z表示X年Y月Z日

Output

    输出“YES”or“NO”表示亚当是否有必胜策略。 

Sample Input

3

2001 11 3

2001 11 2

2001 10 3

Sample Output

YES

NO

NO

HINT

    建议先把所有情况都算出来^_^

题目大意：给你一个时间（年月日），你可以将月份+1或将日+1，谁先达到2001.11.4谁赢了，如果你先操作，问你是否必赢。

分析：博弈论，找规律。打表找到的规律是如果（月份+日）为偶数则一定赢，否则输，但有两组特殊数据即11月30与9月30，这两组也为赢。

1 #include 
        
          2 #include 
         
           3 #include 
          
            4 using namespace std; 5 int t,y,m,d; 6 int main () 7 { 8     scanf("%d",&t); 9     while(t--)10     {11         scanf("%d%d%d",&y,&m,&d);12         if (m==9&&d==30)13             printf("YES\n");14         else if(m==11&&d==30)15             printf("YES\n");16         else if((m+d)&1)17             printf("NO\n");18         else19             printf("YES\n");20     }21 }
          
         
        

Problem C:  

Time Limit: 1 Sec  

Memory Limit: 128 MB

Submit: 76  

Solved: 13

[ ][ ][ ]

Description

        一个核电站有N个放核物质的坑，坑排列在一条直线上。如果连续M个坑中放入核物质，则会发生爆炸，于是，在某些坑中可能不放核物质。         现在，请你计算：对于给定的N和M，求不发生爆炸的放置核物质的方案总数。

Input

输入文件只有一行，两个正整数N,M。

Output

输出文件只有一个正整数，表示方案总数。

Sample Input

4 3

Sample Output

13

HINT

全部数据n< =50,m< =5

题目大意：上面说的很清楚了

分析：递推，找规律。令f[i]表示i个电站的方案数，那么f[i]=2*f[i-1]-f[i-m-1]

1 #include 
         
           2 #include 
          
            3 #include 
           
             4 using namespace std; 5 long long  s[60]; 6 int main () 7 { 8     int n,m; 9     while(scanf("%d%d",&n,&m)!=EOF)10     {11         s[4]=s[5]=1;12         for(int i=6; i<=n+6; ++i)13         {14             s[i]=2*s[i-1]-s[i-m-1];15         }16         printf("%lld\n",s[n+5]);17     }18 }
           
          
         

Problem D: Function(Function(F...

Time Limit: 2 Sec  

Memory Limit: 128 MB

Submit: 58  

Solved: 13

[ ][ ][ ]

Description

对于一个递归函数w(a,b,c) 如果a< =0  or  b< =0  or  c< =0就返回值1. 如果a> 20  or  b> 20  or  c> 20就返回w(20,20,20) 如果a< b并且b< c  就返回w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c) 其它别的情况就返回w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1) 这是个简单的递归函数，但实现起来可能会有些问题。当a,b,c均为15时，调用的次数将非常的多。你要想个办法才行.

Input

会有若干行. 并以-1，-1，-1结束.

Output

输出若干行

Sample Input

1 1 1

2 2 2

-1 -1 -1

Sample Output

w(1, 1, 1) = 2

w(2, 2, 2) = 4

题目大意：给了你一个递归式，要求你求答案。

分析：记忆化搜索或递推。

1、如果直接写成递归形式会超时（这是一定的），所以采用数组保存每一次搜索到的数据，下次再搜索到这个位置时就直接返回不在递归下去。

2、直接写成递推形式，两者没什么太大区别。

1 #include 
          
            2 #include 
           
             3 #include 
            
              4 #define maxlen 30 5 using  namespace std; 6 int f[maxlen][maxlen][maxlen]; 7 int main() 8 { 9     int  a,b,c;10     for (int i=0; i<=20; i++)11     {12         for (int j=0; j<=20; j++)13         {14             for (int k=0; k<=20; k++)15             {16                 if ((i==0)||(j==0)||(k==0)) f[i][j][k]=1;17                 else if ((i
             
              
               20)||(b>20)||(c>20))29             printf("w(%d, %d, %d) = %d\n",a,b,c,f[20][20][20]);30         else31             printf("w(%d, %d, %d) = %d\n",a,b,c,f[a][b][c]);32     }33     return (0);34 }
              
             
            
           
          

Problem E: 

Time Limit: 2 Sec  

Memory Limit: 128 MB

Submit: 8  

Solved: 7

[ ][ ][ ]

Description

一个铁路线上有n(2< =n< =10000)个火车站，每个火车站到该线路的首发火车站距离都是已知的。任意两站之间的票价如下表所示： 站之间的距离X 票价 0< X< =L1 C1  L1< X< =L2 C2 L2< X< =L3 C3 其中L1，L2，L3，C1，C2，C3都是已知的正整数，且(1  < =  L1  <   L2  <   L3  < =  10^9,  1  < =  C1  <   C2  <   C3  < =  10^9)。显然若两站之间的距离大于L3，那么从一站到另一站至少要买两张票。注意：每一张票在使用时只能从一站开始到另一站结束。 现在需要你对于给定的线路，求出从该线路上的站A到站B的最少票价。你能做到吗？

Input

输入文件的第一行为6个整数,  L1,  L2,  L3,  C1,  C2,  C3  (1  < =  L1  <   L2  <   L3  < =  10^9,  1  < =  C1  <   C2  <   C3  < =  10^9)  ,这些整数由空格隔开.第二行为火车站的数量N  (2  < =  N  < =  10000).第三行为两个不同的整数A、B,由空格隔开。接下来的  N-1  行包含从第一站到其他站之间的距离.这些距离按照增长的顺序被设置为不同的正整数。相邻两站之间的距离不超过L3.  两个给定火车站之间行程花费的最小值不超过10^9，而且任意两站之间距离不超过  10^9。

Output

输出文件中只有一个数字,表示从A到B要花费的最小值. 

Sample Input

3 6 8 20 30 40

7

2 6

3

7

8

13

15

23

Sample Output

70

HINT

题目大意：给你三种距离对应的票价，然后给你n个站之间的距离，问你从站a->站b最少的费用是多少。

分析:动态规划。令dp[i]表示第a个站到第i个站的最小费用，那么有三种情况，即分别买三种车票（如果可以）。。。

所以状态转移方程为dp[i]=min{dp[j]+c1,dp[k]+c2,dp[l]+c3},j,k,l分别表示买相应车票能够到的最远的车站编号。

这个程序有点小问题，TLE,但是却过了。为什么能过呢？稍后解答

1 #include 
          
            2 #include 
           
             3 #include 
            
              4 #include 
             
               5 #define maxlen 10010 6 #define INF 0x3fffffff 7 using  namespace std; 8 long long   dp[maxlen],dist[maxlen]; 9 int l1,l2,l3,c1,c2,c3;10 int n,a,b;11 int main ()12 {13     while(scanf("%d%d%d%d%d%d",&l1,&l2,&l3,&c1,&c2,&c3)!=EOF)14     {15         scanf("%d",&n);16         scanf("%d%d",&a,&b);17         dist[1]=0;18         for(int i=2;i<=n;++i)19             scanf("%lld",&dist[i]);20         for(int i=0;i<=n;++i)21             dp[i]=INF;22         dp[a]=0;23         for(int i=a;i<=b;++i)24         {25             for(int j=a;j<=b;++j)26             {27                 if(abs(dist[i]-dist[j])<=l1)28                     dp[i]=min(dp[i],dp[j]+c1);29                 else if(abs(dist[i]-dist[j]<=l2))30                     dp[i]=min(dp[i],dp[j]+c2);31                 else  if(abs(dist[i]-dist[j]<=l3))32                     dp[i]=min(dp[i],dp[j]+c3);33             }34         }35         printf("%lld\n",dp[b]);36     }37 }
             
            
           
          

为什么上面错误的代码能过呢？因为测试数据只有一组！！！就只有样例，所以下面的神级代码也可以过。=。=明天加数据rejudge吧。

1 #include 
          
           2 #include 
           
            3 using  namespace std;4 int main ()5 {6     printf("70\n");7 }
           
          

Problem F: 

Time Limit: 2 Sec  

Memory Limit: 128 MB

Submit: 15  

Solved: 8

[ ][ ][ ]

Description

        2001年9月11日，一场突发的灾难将纽约世界贸易中心大厦夷为平地，Mr.  F曾亲眼目睹了这次灾难。为了纪念“9?11”事件，Mr.  F决定自己用水晶来搭建一座双塔。         Mr.  F有N块水晶，每块水晶有一个高度，他想用这N块水晶搭建两座有同样高度的塔，使他们成为一座双塔，Mr.  F可以从这N块水晶中任取M（1≤M≤N）块来搭建。但是他不知道能否使两座塔有同样的高度，也不知道如果能搭建成一座双塔，这座双塔的最大高度是多少。所以他来请你帮忙。         给定水晶的数量N（1≤N≤100）和每块水晶的高度Hi（N块水晶高度的总和不超过2000），你的任务是判断Mr.  F能否用这些水晶搭建成一座双塔（两座塔有同样的高度），如果能，则输出所能搭建的双塔的最大高度，否则输出“Impossible”。

Input

        输入的第一行为一个数N，表示水晶的数量。第二行为N个数，第i个数表示第i个水晶的高度。

Output

        输出仅包含一行，如果能搭成一座双塔，则输出双塔的最大高度，否则输出一个字符串“Impossible”。

Sample Input

5

1 3 4 5 2

Sample Output

7

HINT

题目大意：给你n个数的水晶序列，问你能不能将这些水晶构成两个高度相同的塔，如果可以输出最大的塔高。

分析：动态规划，dp[i][j]表示第一座塔高i，第二座高j能不能达到，（1为可以，0为不可以）

那么就是变形0-1背包了，一个水晶可以加入第一座塔，也可以加入第二座，或者不加。枚举每个水晶，记录每次可能的情况，最后搜索最大的i使dp[i][i]=1就是答案，如果没有则输出Impossible。

注意点：初始化为dp[0][0]=1，其余为0，但最后如果有（0，0）的应该是输出Impossible的。

1 #include 
          
            2 #include 
           
             3 #include 
            
              4 #include 
             
               5 #define maxlen 2100 6 #define INF 0x7fffff 7 using  namespace std; 8 bool dp[maxlen][maxlen]; 9 int num[200];10 int n;11 int main()12 {13     while(scanf("%d",&n)!=EOF)14     {15         memset(dp,0,sizeof(dp));16         for(int i=0; i
              
               =0; --j)22             {23                 for(int k=1010; k>=0; --k)24                 {25                     if(dp[j][k]==true)26                     {27                         if(j+num[i]<=1010)28                             dp[j+num[i]][k]=true;29                         if (k+num[i]<=1010)30                             dp[j][k+num[i]]=true;31                     }32                 }33             }34         }35         int flag=0;36         for(int i=1010; i>0; --i)37         {38             if(dp[i][i]==true)39             {40                 flag=1;41                 printf("%d\n",i);42                 break;43             }44         }45         if(!flag)46             printf("Impossible\n");47     }48 }
              
             
            
           
          

Problem G: 

Time Limit: 1 Sec  

Memory Limit: 128 MB

Submit: 10  

Solved: 2

[ ][ ][ ]

Description

        在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。         题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。         对于30%的数据，L  < =  10000；         对于全部的数据，L  < =  10^9。

Input

        输入的第一行有一个正整数L（1  < =  L  < =  10^9），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1  < =  S  < =  T  < =  10，1  < =  M  < =  100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。

Output

        输出只包括一个整数，表示青蛙过河最少需要踩到的石子数。

Sample Input

10

2 3 5

2 3 5 6 7

Sample Output

2

题目大意：一个青蛙要过河，每次跳的距离为s-t之间，河里有若干个石头，问青蛙要过河最少需要跳的石头数。

分析：动态规划+状态压缩

1、如果桥的距离比较少那么可以直接解，详情见邝斌学长博客：

2、本题的桥长度很大，蛋根据题目可以知道石头是很少的，就是说石头与石头之间（把桥的两端也看成石头）的距离是很小的，而青蛙跳的距离范围很小，那么有很大一部分区域是没有石头的，青蛙跳这些距离跟等价于没有跳这些距离，所以我们要做的就是将桥的距离压缩到与其等价的较小的距离里，当然要保证是一样的。s t最大为10。所以我们可以将石头的距离mod 110(稍微大点，具体值最小值应为lcm(s,t))既可以压缩，那么接下来就是1里面的问题了。

注意：特别的如果s,t相等，那么青蛙只能是间隔s的距离跳，这个时候就不能压缩了，单独判断（也很好判）。

1 #include
           
             2 #include
            
              3 #include 
             
               4 using namespace std; 5 int  l,a[102],s,t,n; 6 int  dp[3300000],d[3300000]; 7 int main() 8 { 9     scanf("%d%d%d%d",&l,&s,&t,&n);10     for(int i=1; i<=n; ++i)11         scanf("%d",&a[i]);12     int num;13     if(s==t)14     {15         num=0;16         for(int i=1; i<=n; i++)17             if(a[i]%s==0) num++;18         printf("%d\n",num);19     }20     else21     {22         int  tmp;23         sort(a+1,a+n+1);24         a[n+1]=l;25         for(int  i=1; i<=n; ++i)26         {27             if(a[i+1]-a[i]>100)28                 a[i+1]=a[i]+(a[i+1]-a[i])%100;29         }30         l=a[n+1];31         for(int  i=1; i<=n; ++i)32             d[a[i]]=1;33         for(int  i=1; i<=l+t; ++i)34             dp[i]=0xFFFFFFF;35         for(int i=s; i<=l+t; ++i)36         {37             for(int  j=s; j<=t; ++j)38             {39                 if(i>=j&&dp[i]>dp[i-j]+d[i])40                     dp[i]=dp[i-j]+d[i];41             }42         }43         num=0xFFFFFFF;44         for(int i=l; i<=l+t; ++i)45             num=min(num,dp[i]);46         printf("%d\n",num);47     }48     return 0;49 }
             
            
           

Problem H: 过河卒

Time Limit: 1 Sec  

Memory Limit: 128 MB

Submit: 42  

Solved: 9

[ ][ ][ ]

Description

如图，A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图 C 点上的马可以控制 9 个点（图中的P1，P2 … P8 和 C）。卒不能通过对方马的控制点。

棋盘用坐标表示，A 点（0，0）、B 点（n,m）(n,m 为不超过 20 的整数，并由键盘输入)，同样马的位置坐标是需要给出的（约定: C<>A，同时C<>B）。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。

Input

键盘输入

B点的坐标（n,m）以及对方马的坐标（X,Y）{不用判错}

Output

屏幕输出

一个整数（路径的条数）。

Sample Input

6 6 3 2

Sample Output

17

HINT

题目大意：给你一个n*m个棋盘。卒只能向下或向右走，有一匹马在(x,y)马边上（9个）的的位置不能走，问从(0,0)到(n,m)有多少种走法。

分析：动态规划。令dp[i][j]表示(0,0)到(i,j)的路径数，那么方程就是dp[i][j]=dp[i-1][j]+dp[i][j-1]。

1 #include 
            
              2 #include 
             
               3 #include 
              
                4 #define maxlen 30 5 #define INF -100000 6 using  namespace std; 7 long long  dp[30][30],visited[30][30]; 8 int n,m,x,y; 9 int xx[]= {-2,-2,-1,-1, 1, 1, 2, 2};10 int yy[]= {-1, 1,-2, 2,-2, 2,-1, 1};11 int xxx[]={
          0,-1};12 int yyy[]={-1,0};13 int main ()14 {15     while(scanf("%d%d%d%d",&n,&m,&x,&y)!=EOF)16     {17         memset(dp,0,sizeof(dp));18         dp[0][0]=1;19         memset(visited,0,sizeof(visited));20         visited[x][y]=visited[0][0]=1;21         for(int i=0; i<8; ++i)22         {23             int nextx=x+xx[i];24             int nexty=y+yy[i];25             visited[nextx][nexty]=1;26         }27         for(int i=0; i<=n; ++i)28         {29             for(int j=0; j<=m; ++j)30             {31                 for(int k=0;k<2;++k)32                 if(!visited[i][j])33                 dp[i][j]+=dp[i+xxx[k]][j+yyy[k]];34             }35         }36         printf("%lld\n",dp[n][m]);37     }38 }