6 条题解
-
2
yfzcsc LV 8 @ 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); }最简短代码
-
2
题目分析
为了找出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%的数据。-
1216822876 @ 2016-05-01 08:44:02
并不是特别明白，可不可以给出动态转移方程和标程，多谢了
-
-
0
//思路与上位基本相同，先找出所有的情况，再特判一下
#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
hjp_handsome LV 8 @ 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。
剩下的就是加一些特判处理了-
数据貌似水了，一开始没有撞上组合数个数小于k但值大于75000的数，不然就RE了
-
-
0
http://blog.csdn.net/zhhx2001/article/details/51288234
//此题解题报告，代码注释写的很好-
everforever @ 2016-05-01 14:39:40
弱弱的问一下。。。对于有的数据，张卡片数字和可能大于b，那最后一句ans=max(ans,b-last);
会不会有问题。。。
-
-
-3
#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;
}
yfzcsc
LV 8
@ 2016-10-02 20:35:59
- 1