/ Vijos / 题库 / 游戏 /

题解

6 条题解

  • 2
    @ 2016-05-01 00:10:27

    题目分析
      为了找出t和m的最大差,我们需要先找出所有可能的m,也就是要算出来有哪些数字可以通过在n个数字中挑选k个来得到。这一个简化版的01背包问题,记F[i][j][x]表示前i个数字中选出j个来,是否可以组成数字x。这样做时间复杂度是O(nkMAXB)的,可以通过85%的数据。
      又可以发现F[i][j][x]全都是boolean型的,考虑把多个F[i][j][x]在最后一维进行压缩,例如我们可以用一个64位整数来表示64个boolean值。01背包的所有转移都可以用位运算来实现。这便可以通过100%的数据。

    • @ 2016-05-01 08:44:02

      并不是特别明白,可不可以给出动态转移方程和标程,多谢了

  • 1
    @ 2016-10-02 20:35:59
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #define maxn 255
    #include<bitset>
    using namespace std;
    int c[maxn],a,b,n,k,t,l,lst,r,p,z,ans=0,sum=0;
    bitset<76000> dp[maxn];
    int main(){
        scanf("%d%d%d%d",&n,&k,&a,&b);
        for(int i=1;i<=n;++i)scanf("%d",&c[i]);
        dp[0][0]=1;
        for(int i=1,sum=c[1];i<=n;++i,sum+=c[i])
            for(int j=k;j>=1;--j)
                dp[j]|=dp[j-1]<<c[i];
        for(l=0;l<a;++l)if(dp[k][l])lst=l;
        for(l=a,r=a;l<=b;++l)if(dp[k][l]){
            if(lst<a){
                ans=min(a-lst,l-a);
                lst=l;
            }
            ans=max(ans,(lst+l)/2-lst),lst=l;
        }
        ans=max(ans,b-lst);
        printf("%d",ans);
    }
    

    最简短代码

  • 0
    @ 2016-10-22 20:28:00

    //思路与上位基本相同,先找出所有的情况,再特判一下
    #include<stdio.h>
    #include<stdlib.h>
    #include<iostream>
    #include<algorithm>
    #define MAXN 10000001
    using namespace std;
    int n,k,a,b,x[MAXN],y[MAXN],p[MAXN],o[MAXN],date[75004];
    bool dp[75004][251];
    int main()
    {
    int i,j,min=9999999,max=-1;
    cin>>n>>k>>a>>b;
    for(i=1;i<=n;i++)
    cin>>date[i];
    int s=0,d=0,l=0;
    x[0]=0;
    y[0]=0;
    for(i=1;i<=n;i++)
    {
    d=s;
    for(j=0;j<=d;j++)
    {
    int q,w;
    q=x[j]+date[i];
    w=y[j]+1;
    if(!dp[q][w])
    dp[q][w]=1;
    else
    continue;
    if(w<k)
    {
    if(q<min)
    {
    s++;
    x[s]=q;
    y[s]=w;
    }
    }
    if(w==k)
    {
    if(q>=a&&q<=b)
    {
    l++;
    p[l]=q;
    }
    else if(q<a)
    {
    if(q>max) max=q;
    }
    else if(q>b)
    {
    if(q<min) min=q;
    }
    }
    }
    }
    if(max!=-1) p[++l]=max;
    if(min!=9999999) p[++l]=min;
    sort(p+1,p+l+1);
    int maxn=0;
    //for(int i=1;i<=l;i++)cout<<p[i]<<" ";
    //cout<<endl;
    if(p[l]<=(a+b)/2) cout<<b-p[l]<<endl;
    else if(p[1]>=(a+b)/2) cout<<p[1]-a<<endl;
    else{
    for(i=2;i<l-1;i++)
    o[i]=p[i+1]-p[i];
    if(p[1]>=a) o[1]=p[2]-p[1];
    if(p[l]<=b) o[l-1]=p[l]-p[l-1];
    for(i=1;i<l;i++)
    if(o[i]>maxn)
    maxn=o[i];
    maxn=maxn/2;
    if(p[1]<a&&a-p[1]>maxn&&p[2]-a>maxn)
    {
    maxn=((a-p[1])<(p[2]-a))?(a-p[1]):(p[2]-a);
    }
    if(p[l]>b&&p[l]-b>maxn&&b-p[l-1]>maxn)
    {
    maxn=((b-p[l-1])<(p[l]-b))?(b-p[l-1]):(p[l]-b);
    }
    cout<<maxn<<endl;
    }
    return 0;
    }

  • 0
    @ 2016-05-26 09:04:10
    #include<algorithm>
    #include<cstdio>
    using namespace std;
    int n,k,a,b,c[10001],x[10000001],y[10000001],p[1000001],o[1000001];
    bool z[75001][251];
    int main()
    {
        int min=9999999,max=-9999999;   
        cin>>n>>k>>a>>b;
        for(int i=1;i<=n;i++)cin>>c[i]; 
        int s,d,l=0;    x[0]=0; y[0]=0; s=0; d=0;    
        for(int i=1;i<=n;i++)
        {
    //      cout<<i<<"  i循环"<<endl;
            d=s;
    //      cout<<"D=  "<<d<<endl;
            for(int j=0;j<=d;j++)
                {        
    //              cout<<j<<"  j循环"<<endl;  
                    int q,w;
                    q=x[j]+c[i];
                    w=y[j]+1;
    //              cout<<"Q W取值    "<<q<<"  "<<w<<endl;            
                    if(!z[q][w])z[q][w]=1;
                    else continue;                                   
    //              cout<<"此处未跳过"<<endl;        
                    if(w<k)
                    {
                        if(q<min)
                        {
                            s++;
                            x[s]=q;
                            y[s]=w;
                            
    //                      cout<<x[s]<<"   "<<y[s]<<endl;                      
                        }                   
                    }
                    if(w==k)
                    {
                        if(q>=a && q<=b)
                        {
                            l++;
                            p[l]=q;                 
                        }
                        if(q<a)
                        {
                            if(q>max)max=q;
                        }
                        if(q>b)
                        {
                            if(q<min)min=q;
                        }               
                    }                                   
                }
        }   
    //  for(int i=1;i<=l;i++)cout<<p[i]<<"   ";cout<<endl;  
        if(min!=9999999)p[++l]=min;
        if(max!=-9999999)p[++l]=max;
        sort(p+1,p+l+1);        
    //  for(int i=1;i<=l;i++)cout<<p[i]<<"   "; 
    //  cout<<endl; 
        int maxn=0;
        if(p[l]<=(a+b)/2)cout<<b-p[l];
        else
           if(p[1]>=(a+b)/2)cout<<p[1]-a;
           else
           {
              for(int i=2;i<l-1;i++)
                o[i]=p[i+1]-p[i];
              if(p[1]>=a)o[1]=p[2]-p[1];
              if(p[l]<=b)o[l-1]=p[l]-p[l-1];
              
    //          for(int i=1;i<=l;i++)cout<<o[i]<<"   "; 
    //          cout<<endl; 
              
              for(int i=1;i<l;i++)
                if(o[i]>maxn)maxn=o[i];
              maxn=maxn/2;
              
              if(p[1]<a)
              {
                 if(a-p[1]>maxn && p[2]-a>maxn)
                 {
                      if(p[2]-a>a-p[1])maxn=a-p[1];
                      else maxn=p[2]-a;
                 }
              }
              if(p[l]>b)
              {
                 if(p[l]-b>maxn && b-p[l-1]>maxn)
                 {
                      if(b-p[l-1]>p[l]-b)maxn=p[l]-b;
                      else maxn=b-p[l-1];
                 }
              }
              cout<<maxn;
           }
        return 0;
    }
    

    通过类似动归的方法构造组合数。
    因为a,b<=75000,最多250种组合情况,设置Z[75001][251]判重,不用担心构造组合数时数组被爆,数组x,y用于记录未满k个组合数个数且值小于min的数的值和组合数个数(min为组合数个数为k,且值大于b的所有数中最小值,min在构造组合数过程中不断更新),max为组合个数为k,且值小于a的所有数中最大值,max在构造组合数过程中不断更新。
    最后得到组合数个数为k,且值位于a,b之间的数列p。以及组合数个数为k,且值小于a的max,以及组合数个数为k,且值大于b的min。
    剩下的就是加一些特判处理了

    • @ 2016-05-26 09:15:47

      数据貌似水了,一开始没有撞上组合数个数小于k但值大于75000的数,不然就RE了

  • 0
    @ 2016-05-01 10:21:22

    http://blog.csdn.net/zhhx2001/article/details/51288234
    //此题解题报告,代码注释写的很好

    • @ 2016-05-01 14:39:40

      弱弱的问一下。。。对于有的数据,张卡片数字和可能大于b,那最后一句ans=max(ans,b-last);
      会不会有问题。。。

  • -4
    @ 2017-01-05 13:05:51

    #include <iostream>  
    #include <windows.h>  
    #include <ctime>  
    using namespace std;  
      
    int const ROW = 4;  
    int const COL = 4;  
    int game[ROW][COL] = {0};  
      
    //上下左右  
    int const UP = 1;  
    int const DOWN = 2;  
    int const LEFT = 3;  
    int const RIGHT = 4;  
      
    //游戏所处的状态  
    int const GAME_OVER = 1;  
    int const GAME_WIN = 2;  
    int const GAME_CONTINUE = 3;  
      
    enum GameNum  
    {  
        Game_2 = 2,  
        Game_4 = 4,  
        Game_8 = 8,  
        Game_16 = 16,  
        Game_32 = 32,  
        Game_64 = 64,  
        Game_128 = 128,  
        Game_256 = 256,  
        Game_512 = 512,  
        Game_1024 = 1024,  
        Game_2048 = 2048,  
    };  
      
    //打印所得的数组  
    void Print()  
    {  
        system("cls");  
        cout << "*****************  2048 控 制 台 版  ******************" << endl;  
        cout << "*****************  By Tanzf (Intern) ******************" << endl << endl;  
        for (int i = 0; i < ROW; ++i)  
        {  
            cout << "---------------------------------"<< endl;  
            for (int j = 0; j < COL; ++j)  
            {  
                if (game[i][j] == 0)  
                {  
                    cout <<"|   \t";  
                }  
                else   
                {  
                    cout <<"|   " << game[i][j] << "\t";  
                }  
            }  
            cout << "|" << endl;  
        }  
        cout << "---------------------------------"<< endl;  
    }  
      
      
    bool CreateNumber()  
    {  
        int x = -1;  
        int y = -1;  
        int times = 0;  
        int maxTimes = ROW * COL;  
        //三分之二的概率生成2,三分之一的概率生成4  
        int whitch = rand() % 3;  
        do   
        {  
            x = rand() % ROW;  
            y = rand() % COL;  
            ++times;  
        } while (game[x][y] != 0 && times <= maxTimes);  
      
        //说明格子已经满了  
        if(times >= maxTimes)  
        {  
            return false;  
        }  
        else  
        {  
            GameNum num;  
            if(whitch == 0)  
            {  
                num = Game_4;  
            }  
            else if(whitch)  
            {  
                num = Game_2;  
            }  
            game[x][y] = num;  
        }  
      
        return true;  
    }  
      
    void Process(int direction)  
    {  
        switch (direction)  
        {  
        case UP:  
            //最上面一行不动  
            for(int row = 1; row < ROW; ++row)  
            {  
                for(int crow = row; crow >= 1; --crow)  
                {  
                    for(int col = 0; col < COL; ++col)  
                    {  
                        //上一个格子为空  
                        if(game[crow-1][col] == 0)  
                        {  
                            game[crow-1][col] = game[crow][col];  
                            game[crow][col] = 0;  
                        }  
                        else   
                        {  
                            //合并  
                            if(game[crow-1][col] == game[crow][col])  
                            {  
                                game[crow - 1][col] *= 2;  
                                game[crow][col] = 0;  
                            }  
      
                        }  
                    }  
                }  
            }  
            break;  
        case DOWN:  
            //最下面一行不动  
            for(int row = ROW - 2; row >= 0; --row)  
            {  
                for(int crow = row; crow < ROW - 1; ++crow)  
                {  
                    for(int col = 0; col < COL; ++col)  
                    {  
                        //上一个格子为空  
                        if(game[crow + 1][col] == 0)  
                        {  
                            game[crow + 1][col] = game[crow][col];  
                            game[crow][col] = 0;  
                        }  
                        else   
                        {  
                            //合并  
                            if(game[crow + 1][col] == game[crow][col])  
                            {  
                                game[crow + 1][col] *= 2;  
                                game[crow][col] = 0;  
                            }  
      
                        }  
                    }  
                }  
            }  
            break;  
        case LEFT:  
            //最左边一列不动  
            for(int  col = 1; col < COL; ++col)  
            {  
                for(int ccol = col; ccol >= 1; --ccol)  
                {  
                    for(int row = 0; row < ROW; ++row)  
                    {  
                        //上一个格子为空  
                        if(game[row][ccol-1] == 0)  
                        {  
                            game[row][ccol - 1] = game[row][ccol];  
                            game[row][ccol] = 0;  
                        }  
                        else   
                        {  
                            //合并  
                            if(game[row][ccol - 1] == game[row][ccol])  
                            {  
                                game[row][ccol - 1] *= 2;  
                                game[row][ccol] = 0;  
                            }  
      
                        }  
                    }  
                }  
            }  
            break;  
        case RIGHT:  
            //最右边一列不动  
            for(int  col = COL - 2; col >= 0; --col)  
            {  
                for(int ccol = col; ccol <= COL - 2; ++ccol)  
                {  
                    for(int row = 0; row < ROW; ++row)  
                    {  
                        //上一个格子为空  
                        if(game[row][ccol + 1] == 0)  
                        {  
                            game[row][ccol + 1] = game[row][ccol];  
                            game[row][ccol] = 0;  
                        }  
                        else   
                        {  
                            //合并  
                            if(game[row][ccol + 1] == game[row][ccol])  
                            {  
                                game[row][ccol + 1] *= 2;  
                                game[row][ccol] = 0;  
                            }  
      
                        }  
                    }  
                }  
            }  
            break;  
        }  
      
    }  
      
    //处理输入输出,返回上下左右  
    int Input()  
    {  
        //读取上下左右四个方向键  
        int upArrow = 0;  
        int downArrow = 0;  
        int leftArrow = 0;  
        int rightArrow = 0;  
        int direction = 0;  
        while (true)  
        {  
            upArrow = GetAsyncKeyState(VK_UP);  
            downArrow = GetAsyncKeyState(VK_DOWN);  
            leftArrow = GetAsyncKeyState(VK_LEFT);  
            rightArrow = GetAsyncKeyState(VK_RIGHT);  
      
            if(upArrow)  
            {  
                direction = UP;  
                break;  
            }  
            else if(downArrow)  
            {  
                direction = DOWN;  
                break;  
            }  
            else if(leftArrow)  
            {  
                direction = LEFT;  
                break;  
            }  
            else if(rightArrow)  
            {  
                direction = RIGHT;  
                break;  
            }  
      
            Sleep(100);  
        }  
      
        return direction;  
    }  
      
    //判断游戏状态  
    int Judge()  
    {  
        //赢得游戏  
        for(int i = 0; i < ROW; ++i)  
        {  
            for(int j = 0; j < COL; ++j)  
            {  
                if(game[i][j] == 2048)  
                {  
                    return GAME_WIN;  
                    break;  
                }  
            }  
        }  
      
        //横向检查  
        for(int i = 0 ; i < ROW; ++i)  
        {  
            for(int j = 0; j < COL - 1; ++j)  
            {  
                if(!game[i][j] || (game[i][j] == game[i][j+1]))  
                {  
                    return GAME_CONTINUE;  
                    break;  
                }  
            }  
        }  
        //纵向检查  
        for(int j = 0; j< COL; ++j)  
        {  
            for(int i = 0; i < ROW -1; ++i)  
            {  
                if(!game[i][j] || (game[i][j] == game[i+1][j]))  
                {  
                    return GAME_CONTINUE;  
                    break;  
                }  
            }  
        }  
      
        //不符合上述两种状况,游戏结束  
        return GAME_OVER;  
      
    }  
      
    int main()  
    {  
        //设置一个随机数种子  
        srand((unsigned int)time(0));  
        CreateNumber();  
        CreateNumber();  
        Print();  
        int direction = 0;  
        int gameState = -1;  
        while(true)  
        {  
            direction = Input();  
      
            gameState = Judge();  
            if(direction && gameState == GAME_CONTINUE)  
            {  
                Process(direction);  
                CreateNumber();  
                Print();  
                Sleep(100);  
            }  
            else if(gameState == GAME_WIN)  
            {  
                Print();  
                cout << "You Win!" << endl;  
                break;  
            }  
            else if(gameState == GAME_OVER)  
            {  
                Print();  
                cout <<"You lose!" << endl;  
                break;  
            }  
        }  
      
        return 0;  
    }  

    • @ 2017-04-14 20:55:26

      这是甚?

    • @ 2017-07-03 09:54:34

      @lshstc: 还是不要放在这里的好…………

  • 1

信息

ID
1987
难度
8
分类
(无)
标签
(无)
递交数
334
已通过
50
通过率
15%
上传者