【算法课OJ】作业四
生命不息，希望不止。
链接：http://192.168.173.163/JudgeOnline/contest.php?cid=1115
密码：123654
问题 A: 元素整除问题
题目描述
输入20个整数，输出其中能被数组中其它元素整除的那些数组元素。
输入
输入20个整数
输出
按输入顺序输出符合要求的数字，每行输出一个整数。
样例输入
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
样例输出
4
6
8
9
10
12
14
15
16
18
20
21
题意
如题目描述所示。
思路
两层for循环，是的话直接输出并break。
代码
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
int a[20];
for(int i = 0; i < 20; i++)
{
scanf("%d",&a[i]);
}
for(int i = 0; i < 20; i++)
{
for(int j = 0; j < 20; j++)
{
if(i != j && a[i]%a[j] == 0 )
{
printf("%d\n",a[i]);
break;
}
}
}
return 0;
}
问题 B: 渊子赛马
题目描述
赛马是一古老的游戏，早在公元前四世纪的中国，处在诸侯割据的状态，历史上称为“战国时期”。在魏国作官的孙膑，因为受到同僚庞涓的迫害，被齐国使臣救出后，到达齐国国都。 赛马是当时最受齐国贵族欢迎的娱乐项目。上至国王，下到大臣，常常以赛马取乐，并以重金赌输赢。田忌多次与国王及其他大臣赌输赢，屡赌屡输。一天他赛马又输了，回家后闷闷不乐。孙膑安慰他说：“下次有机会带我到马场看看，也许我能帮你。” 孙膑仔细观察后发现，田忌的马和其他人的马相差并不远，只是策略运用不当，以致失败。 比赛前田忌按照孙膑的主意，用上等马鞍将下等马装饰起来，冒充上等马，与齐王的上等马比赛。第二场比赛，还是按照孙膑的安排，田忌用自己的上等马与国王的中等马比赛，在一片喝彩中，只见田忌的马竟然冲到齐王的马前面，赢了第二场。关键的第三场，田忌的中等马和国王的下等马比赛，田忌的马又一次冲到国王的马前面，结果二比一，田忌赢了国王。 就是这么简单，现在渊子也来赛一赛马。假设每匹马都有恒定的速度，所以速度大的马一定比速度小的马先到终点（没有意外！！）。不允许出现平局。最后谁赢的场数多于一半(不包括一半)，谁就是赢家(可能没有赢家)。渊子有 N(1<=n<=1000)匹马参加比赛。对手的马的数量与渊子马的数量一样，并且知道所有的马的速度。聪明的你来预测一下这场世纪之战的结果，看看渊子能否赢得比赛。
输入
输入有多组测试数据。 每组测试数据包括 3 行： 第一行输入 N。表示马的数量。 第二行有 N 个整型数字，即渊子的 N 匹马的速度。 第三行有 N 个整型数字，即对手的 N 匹马的速度。 当 N 为 0 时退出。
输出
若通过聪明的你精心安排，如果渊子能赢得比赛，那么输出YES。 否则输出NO。
样例输入
5
2 3 3 4 5
1 2 3 4 5
4
2 2 1 2
2 2 3 1
0
样例输出
YES
NO
题意
赛马。
思路
都先从小到大排序。
设两个变量cnt1、cnt2分别存储两人赢的场次。
代码
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn = 1e3+5;
int main()
{
int n,a[maxn],b[maxn],cnt1,cnt2;
while(~scanf("%d",&n) && n)
{
cnt1 = cnt2 = 0;
for(int i = 0; i < n; i++) scanf("%d",&a[i]);
for(int i = 0; i < n; i++) scanf("%d",&b[i]);
sort(a,a+n);
sort(b,b+n);
int j = 0;
for(int i = 0; i < n; i++)
{
if(a[i] > b[j])
{
cnt1++;
j++;
}
else cnt2++;
}
if(cnt1 > cnt2) puts("YES");
else puts("NO");
}
return 0;
}
问题 C: 八皇后问题
题目描述
努比亚和苏丹没有子女，所以他要从一些有集成资格的继承者中挑选一个出来继承王位。他希望这个继承者足够聪明，所以他准备了一个西洋棋盘，上面的每个格子中均有一个 1-99 的数字。他又准备了 8 个皇后棋子。
8 皇后的规则就是不能有任何棋子同行或者同列或者同斜线，在满足这个规则的同时，王位继承者还需要让 8 个皇后所在的位置的数字的和是最大的。
输入
输入一个数字 k(k≤20)，代表棋盘的数量。
接下来有 k 个棋盘，每个棋盘有 64 个数字，分成 8 行 8 列输入，具体可见样例，每一个数字均小于 100。
输出
每一个棋盘对应输出最大的数值， 一共输出 k行
样例输入
1
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
样例输出
260
题意
n皇后问题变种，固定n == 8，棋盘上每个位置都有相应权值，求总权值最大的可行解。
思路
dfs。
用一个变量记录最大值，每次找到可行解若大于最大值则更新最大值。
代码
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
int map[8][8],x[8],ans,sum;
bool check(int xx,int yy)
{
for(int i = 0; i < xx; i++)
{
if(yy == x[i]) return false;
if(abs(xx - i) == abs(yy - x[i])) return false;
}
return true;
}
void queen(int n)
{
if(n == 8){ans = max(ans,sum);return;}
for(int i = 0; i < 8; i++)
{
if(check(n,i))
{
x[n] = i;
sum += map[n][i];
queen(n+1);
x[n] = -1;
sum -= map[n][i];
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
ans = 0;
sum = 0;
for(int i = 0; i < 8; i++)
for(int j = 0; j < 8; j++)
scanf("%d",&map[i][j]);
memset(x,-1,sizeof(x));
queen(0);
printf("%d\n",ans);
}
return 0;
}
问题 D: 组合运算式
题目描述
请考虑一个被空格分隔的，由1到N的整数组成的递增数列：1 2 3 …N。现在请在数列中插入表示加的“+”，或者表示减“-”，亦或者表示空白的“ ”(例如1-2 3就等于1-23)，来将每一对数字组合成一个表达式（第一个数字前无空格）。计算该表达式的结果并判断其值是否为0。请你写一个程序找出所有产生和为零的长度为N的数列。
输入
输入为一行，包含一个整数N，3≤N≤9。
输出
输出为所有在每对数字间插入“+”, “-”, 或 “ ”后能得到和为零的数列，并按照字典（ASCII码）序排列。
样例输入
7
样例输出
1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7
题意
三种填充方式，ASCII从小到大分别为' '（空格）、+、'-'。
按字典序输出可行解（使最终答案为0），其中空格代表拼接。
思路
dfs，用一个参数int pre存储本次增量（遇到空格的时候有用）。
遇到空格的时候往回推。
代码
#include<iostream>
#include<stdio.h>
using namespace std;
int n;
int OP[15] = {1,1};
void dfs(int d,int sum,int pre)
{
sum += pre;
if(d == n)
{
if(!sum)
{
printf("1");
for(int i = 2; i <= n; i++)
{
if(!OP[i]) printf(" %d",i);
else if(OP[i] == 1) printf("+%d",i);
else printf("-%d",i);
}
printf("\n");
}
return;
}
OP[d+1] = 0;
if(pre >= 0) dfs(d+1,sum-pre,pre*10+d+1);
else dfs(d+1,sum-pre,pre*10-d-1);
OP[d+1] = 1;
dfs(d+1,sum,d+1);
OP[d+1] = 2;
dfs(d+1,sum,-d-1);
}
int main()
{
scanf("%d",&n);
dfs(1,0,1);
return 0;
}
问题 E: 无脑博士的试管们
题目描述
无脑博士有三个容量分别是 A,B,C 升的试管，A,B,C分别是三个从 1到 20的整数，最初，A 和 B 试管都是空的，而 C 试管是装满硫酸铜溶液的。有时，无脑博士把硫酸铜溶液从一个试管倒到另一个试管中，直到被灌试管装满或原试管空了。当然每一次灌注都是完全的。由于无脑博士天天这么折腾，早已熟练，溶液在倒的过程中不会有丢失。
写一个程序去帮助无脑博士找出当 A 试管是空的时候，C 试管中硫酸铜溶液所剩量的所有可能性。
输入
多组测试用例，对于每组测试用例，输入包括一行，为空格分隔开的三个数，分别为整数 A,B,C。
输出
输出包括一行，升序地列出当 A 试管是空的时候，C 试管溶液所剩量的所有可能性。
样例输入
2 5 10
样例输出
5 6 7 8 9 10
题意
如题目描述所示，给定三个试管的最大容量。
一开始试管a、b都为空，c满。
求a空时c的可能取值，按从小到大排序。
思路
采用数据结构set<int>存储答案（去重+排序）。
因为有3个试管，所以倒水的方法有6种，暴力写出每种可能，dfs。
三位数组visited的意义：走过的点就不需要再走了，没有的话没法停止。
代码
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<set>
using namespace std;
set<int> s;
int na,nb,nc;
bool visited[25][25][25];
void dfs(int a,int b,int c)
{
if(visited[a][b][c]) return;
visited[a][b][c] = true;
if(!a) s.insert(c);
if(a <= nb-b) dfs(0,a+b,c);
else dfs(a-nb+b,nb,c);
if(b <= na-a) dfs(a+b,0,c);
else dfs(na,a-na+b,c);
if(a <= nc-c) dfs(0,b,a+c);
else dfs(a-nc+c,b,nc);
if(c <= na-a) dfs(a+c,b,0);
else dfs(na,b,c-na+a);
if(b <= nc-c) dfs(a,0,b+c);
else dfs(a,b-nc+c,nc);
if(c <= nb-b) dfs(a,b+c,0);
else dfs(a,nb,c-nb+b);
}
int main()
{
while(~scanf("%d %d %d",&na,&nb,&nc))
{
s.clear();
memset(visited,0,sizeof(visited));
dfs(0,0,nc);
set<int>::iterator it = s.begin();
printf("%d",*it);
it++;
for(; it != s.end(); it++)
{
printf(" %d",*it);
}
printf("\n");
}
return 0;
}
本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明来自 ComyDream 。
本文链接：http://comydream.github.io/2018/10/21/algorithm-homework-4/