正文
JUST第二界算法设计大赛题解
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
1、问题描述：
悠悠假期同叔叔一起去书店，他选中了六本书，每本书的单价（单位：元）分别为：3.1，1.7，2，5.3，
0.9 和7.2。不巧的是，叔叔只带了十几块钱，为了让悠悠高兴，叔叔同意买书，但提出了一个要求，要悠
悠从六本书中选出若干本，使得单价相加所得的和同10 最接近。请编程帮助悠悠解决这个问题。输出格
式：第一行输出1 个整数，表示组合方法数量；第二行开始，一行输出一种价格组合。
#include"cstdio"
#include"cmath"
#include"vector"
using namespace std;
double p[]={3.1,1.7,,5.3,0.9,7.2};
int a[];
vector<double> vec[<<];
double maxn;
int cnt;
void solve()
{
for(a[]=;a[]<=;a[]++)
for(a[]=;a[]<=;a[]++)
for(a[]=;a[]<=;a[]++)
for(a[]=;a[]<=;a[]++)
for(a[]=;a[]<=;a[]++)
for(a[]=;a[]<=;a[]++)
{
double s=;
for(int j=;j<;j++)
{
s+=a[j]*p[j];
}
if(fabs(s-)<maxn)
{
maxn=fabs(s-);
for(int i=;i<cnt;i++)
{
vec[i].clear();//若最小值更新，则将结果清空
}
cnt=;
}
if(fabs(fabs(s-)-maxn)<0.000001)
{
for(int j=;j<;j++)
{
if(a[j]!=) vec[cnt].push_back(p[j]);
}
cnt++;
} }
}
void print()
{
printf("%d\n",cnt);
for(int i=;i<cnt;i++)
{
for(int j=;j<vec[i].size();j++)
{
printf("%lf ",vec[i][j]);
}
printf("\n");
}
}
int main()
{
maxn=;
solve();
print();
return ;
}
2、问题描述：
将1、2、3、4、5 和6 填入下表中，要使得每一列右边的数字比左边的数字大，每一行下面的数字比
上面的数字大。请编程计算共有几种填写方法？输出：第一行输出1 个整数，表示填写方法数量；第二行，
依次输出每种填写方式。
#include"cstdio"
#include"set"
#include"vector"
using namespace std;
int a[]={,,,,,};
set<int> vec;
vector<int> ss[**];
int cnt;
bool check()
{
for(int i=;i<;i++)
{
if(!(a[i+]>a[i]&&a[i++]>a[i+]&&a[i+]>a[i]))
{
return false;
}
}
if(!(a[]>a[]))
{
return false;
}
return true;
}
void solve()
{
for(a[]=;a[]<=;a[]++)
for(a[]=;a[]<=;a[]++)
for(a[]=;a[]<=;a[]++)
for(a[]=;a[]<=;a[]++)
for(a[]=;a[]<=;a[]++)
for(a[]=;a[]<=;a[]++)
{
vec.clear();
for(int j=;j<;j++)
{
vec.insert(a[j]);
}
if(vec.size()==&&check())
{
for(int j=;j<;j++)
{
ss[cnt].push_back(a[j]);
}
cnt++;
}
}
}
void print()
{
printf("%d\n",cnt);
for(int i=;i<cnt;i++)
{
for(int j=;j<;j++)
{
printf("%d ",ss[i][j]);
if(j==) printf("\n");
}
printf("\n\n");
}
}
int main()
{
solve();
print();
return ;
}
3、问题描述：
在一个旅馆中住着六个不同国籍的人，他们分别来自美国（US）、德国（GER）、英国（UK）、法国
（FRA）、俄罗斯（RUS）和意大利（ITA）。他们的名字叫A、B、C、D、E 和F。名字的顺序与上面的
国籍不一定是相互对应的。现在已知：
1)A 和美国人是医生。 2)E 和俄罗斯人是技师。
3)C 和德国人是技师。 4)B 和F 曾经当过兵，而德国人从未参过军。
5)法国人比A 年龄大；意大利人比C 年龄大。
6)B 同美国人下周要去西安旅行，而C 同法国人下周要去杭州度假。
请编程分析出A、B、C、D、E 和F 各是哪国人？（程序必须算法分析过程，不可直接输出结果）
输出格式：第一行输出A 是哪国人，第二行输出B 是哪国人......以此类推。（例如：A is US）
方法一、全排列搜索
#include"algorithm"
#include"vector"
#include"string"
#include"iostream"
using namespace std;
int a[]={,,,,,};
vector<string> ss;
bool check1()
{
if(a[]!=&&a[]!=&&a[]!=&&a[]!=)
{
return true;
}
return false;
}
bool check2()
{
if(a[]==)
{
return true;
}
return false;
}
bool check3()
{
if(a[]!=&&a[]!=&&a[]!=)
{
return true;
}
return false;
}
bool check4()
{
if(a[]!=&&a[]!=&&a[]!=)
{
return true;
}
return false;
}
bool check5()
{
if(a[]!=)
{
return true;
}
return false;
}
void print()
{
for(int i=;i<;i++)
{
string s="";
switch(i)
{
case :{ s+=('A'+a[i]);s+=" is US";break;}
case :{ s+=('A'+a[i]);s+=" is GER";break;}
case :{ s+=('A'+a[i]);s+=" is UK";break;}
case :{ s+=('A'+a[i]);s+=" is FRA";break;}
case :{ s+=('A'+a[i]);s+=" is RUS";break;}
case :{ s+=('A'+a[i]);s+=" is ITA";break;}
}
ss.push_back(s);
}
sort(ss.begin(),ss.end());
for(int i=;i<ss.size();i++)
{
cout<<ss[i]<<endl;
}
}
int main()
{
int ans=;
do{
if(check1()&&check2()&&check3()&&check4()&&check5())
{
break;
}
}while(next_permutation(a,a+));
print();
return ;
}
方法二、消元法
#include"cstdio"
using namespace std;
struct node{
int y,x;
node(int cy,int cx):y(cy),x(cx){}
node(){}
};
int a[][]={
,,,,,,
,,,,,,
,,,,,,
,,,,,,
,,,,,,
,,,,,
};
const char* s[]={"US","GER","UR","FRA","RUS","ITA"};
int ans[];
node unique()
{
for(int i=;i<;i++)
{
int cnt=;
int k;
for(int j=;j<;j++)
{
if(a[j][i]==)
{
cnt++;
k=j;
}
}
if(cnt==)
{
node no(k,i);
return no;
}
}
node no(-,-);
return no;
} void update(int row)
{
for(int i=;i<;i++)
{
a[row][i]=;
}
}
bool solve()
{
for(int i=;i<;i++)
{
node no;
no = unique();
if(no.x==-)
{
printf("error\n");
return false;
}
update(no.y);
ans[no.y]=no.x;
}
return true;
}
void print(bool flag)
{
if(flag)
{
for(int i=;i<;i++)
{
printf("%c is %s\n",'A'+i,s[ans[i]]);
}
}
else
{
printf("error\n");
}
}
int main()
{
print(solve());
return ;
}
4、问题描述：
扬扬喜欢滑雪，可是为了获得速度，滑的区域必须向下倾斜，扬扬想知道在一个区域中最长底滑坡。
区域由一个二维数组表示。数组的每个数字代表点的高度。下面是一个例子：
1 3 5 7
23 25 27 9
21 31 29 11
19 17 15 13
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的
滑坡为31-25-3-1，长度为4。当然31-29-27-...-5-3-1 更长。事实上，这是最长的一条,长度为16。
输入：每组数据的第一行表示区域的行数R 和列数C(1 <= R,C <= 100)。下面是R 行，每行有C 个整数，
代表高度h，0<=h<=10000。
输出：输出最长区域的长度。
#include"cstdio"
#include"algorithm"
using namespace std;
const int MAXN=;
int h[MAXN][MAXN];
int mp[MAXN][MAXN];
int n,m;
int dx[]={,,-,};
int dy[]={,,,-};
int rdfs(int y,int x)
{
if(mp[y][x]) return mp[y][x];
int k=;
for(int i=;i<;i++)
{
int ny=y+dy[i];
int nx=x+dx[i];
if(<=ny&&ny<n&&<=nx&&nx<m&&h[ny][nx]<h[y][x])
{
k=max(rdfs(ny,nx),k);
}
}
return mp[y][x]=k+;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=;i<n;i++){
for(int j=;j<m;j++) scanf("%d",&h[i][j]);} int ans=;
for(int i=;i<n;i++){
for(int j=;j<m;j++) ans=max(rdfs(i,j),ans);} printf("%d\n",ans); return ;
}
