程序设计算法竞赛高级——练习1解题报告
程序设计算法竞赛高级——练习1解题报告
1001 寒冰王座
Problem Description
不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前.
死亡骑士:“我要买道具!”
地精商人:“我们这里有三种道具,血瓶150块一个,魔法药200块一个,无敌药水350块一个.”
死亡骑士:“好的,给我一个血瓶.”
说完他掏出那张N元的大钞递给地精商人.
地精商人:“我忘了提醒你了,我们这里没有找客人钱的习惯的,多的钱我们都当小费收了的,嘿嘿.”
死亡骑士:"…"
死亡骑士想,与其把钱当小费送个他还不如自己多买一点道具,反正以后都要买的,早点买了放在家里也好,但是要尽量少让他赚小费.
现在死亡骑士希望你能帮他计算一下,最少他要给地精商人多少小费.
Input
输入数据的第一行是一个整数T(1<=T<=100),代表测试数据的数量.然后是T行测试数据,每个测试数据只包含一个正整数N(1<=N<=10000),N代表死亡骑士手中钞票的面值.
注意:地精商店只有题中描述的三种道具.
Output
对于每组测试数据,请你输出死亡骑士最少要浪费多少钱给地精商人作为小费.
Sample Input
2
900
250
Sample Output
0
50
Author
Ignatius.L
解题思路
虽然地精有三种商品，但其实我们只需考虑血瓶和魔法药，因为无敌药水=血瓶+魔法药。
先买尽量多的血瓶，若有剩余则用血瓶+50换购魔法药。
代码实现
#include<iostream>
using namespace std;
//血瓶150，魔法药200，无敌350
const int xueping = 150, mofa = 200, wudi = 350;
int main() {
int t;
cin >> t;
while(t--) {
int n, ex;
int a1, a2, a3;
cin >> n;
//所有钱最大买al个血瓶，还剩ex元
ex = n % xueping;
a1 = n / xueping;
//若ex>=50且买的血瓶有余，则置换为魔法药
while(ex >= 50 && a1 > 0) {
ex -= 50;
a1--;
}
cout << ex << endl;
}
return 0;
}
1002 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活
Problem Description
急！灾区的食物依然短缺！
为了挽救灾区同胞的生命，心系灾区同胞的你准备自己采购一些粮食支援灾区，现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装产品，其价格不等，并且只能整袋购买。
请问：你用有限的资金最多能采购多少公斤粮食呢？
后记：
人生是一个充满了变数的生命过程，天灾、人祸、病痛是我们生命历程中不可预知的威胁。
月有阴晴圆缺，人有旦夕祸福，未来对于我们而言是一个未知数。那么，我们要做的就应该是珍惜现在，感恩生活——
感谢父母，他们给予我们生命，抚养我们成人；
感谢老师，他们授给我们知识，教我们做人
感谢朋友，他们让我们感受到世界的温暖；
感谢对手，他们令我们不断进取、努力。
同样，我们也要感谢痛苦与艰辛带给我们的财富～
Input
输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类，然后是m行数据，每行包含3个数p，h和c(1<=p<=20,1<=h<=200,1<=c<=20)，分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。
Output
对于每组测试数据，请输出能够购买大米的最多重量，你可以假设经费买不光所有的大米，并且经费你可以不用完。每个实例的输出占一行。
Sample Input
1
8 2
2 100 4
4 100 2
Sample Output
400
Author
Icy
Source
2008-06-18《 ACM程序设计》期末考试——四川加油！中国加油！
解题思路
多重背包问题
代码实现
#include<cstdio>
#include<cstring>
using namespace std;
//p大米价格，h大米质量，c大米袋数
struct INF {
int p;
int h;
int c;
};
INF rice[105];
long long ma[105];
long long max(const long long a, const long long b) {
if(a > b) return a;
else return b;
}
long long output(const int n, const int m) {
memset(ma, 0, sizeof(ma));
for(int i = 0; i < m; i++) {
for(int j = n; j > 0; j--) {
for(int k = rice[i].c; k >= 1; k--) {
//若资金j足以支持购买k带大米i，则比较购买k带大米是否为资金j的最优方案
if(k * rice[i].p <= j) {
//选择资金为j时的最优方案
ma[j] = max(ma[j], ma[j - k * rice[i].p] + k * rice[i].h);
}
}
}
}
return ma[n];
}
int main() {
int c;
scanf("%d", &c);
while(c--) {
int n, m;
scanf("%d %d", &n, &m);
for(int i = 0; i < m; i++) scanf("%d %d %d", &rice[i].p, &rice[i].h, &rice[i].c);
long long maxsum = output(n, m);
printf("%lld\n", maxsum);
}
return 0;
}
1003 湫湫系列故事——减肥记I
Problem Description
对于吃货来说，过年最幸福的事就是吃了，没有之一！
但是对于女生来说，卡路里（热量）是天敌啊！
资深美女湫湫深谙“胖来如山倒，胖去如抽丝”的道理，所以她希望你能帮忙制定一个食谱，能使她吃得开心的同时，不会制造太多的天敌。
当然，为了方便你制作食谱，湫湫给了你每日食物清单，上面描述了当天她想吃的每种食物能带给她的幸福程度，以及会增加的卡路里量。
Input
输入包含多组测试用例。
每组数据以一个整数n开始，表示每天的食物清单有n种食物。
接下来n行，每行两个整数a和b，其中a表示这种食物可以带给湫湫的幸福值（数值越大，越幸福），b表示湫湫吃这种食物会吸收的卡路里量。
最后是一个整数m，表示湫湫一天吸收的卡路里不能超过m。
[Technical Specification]
1. 1 <= n <= 100
2. 0 <= a,b <= 100000
3. 1 <= m <= 100000
Output
对每份清单，输出一个整数，即满足卡路里吸收量的同时，湫湫可获得的最大幸福值。
Sample Input
3
3 3
7 7
9 9
10
5
1 1
5 3
10 3
6 8
7 5
6
Sample Output
10
20
Source
2013腾讯编程马拉松初赛第一场（3月21日）
解题思路
完全背包问题，将其转换为01背包问题即可
代码实现
#include<cstdio>
#include<cstring>
#define max(a,b) a>b?a:b
//a[i]表示i食物带来的幸福值，b[i]表示i食物带来的卡路里，happy[i]表示每日摄入i卡路里时获得最大幸福
const int maxn = 1e5 + 5;
int a[105];
int b[105];
int happy[maxn];
int main() {
int n;
while(scanf("%d", &n) != EOF) {
for(int i = 0; i < n; i++) {
scanf("%d %d", &a[i], &b[i]);
}
int m;
scanf("%d", &m);
memset(happy, 0, sizeof(happy));
for(int i = 0; i < n; i++) {
//每日卡路里摄入从低到高遍历，将完全背包转化为01背包
for(int j = b[i]; j <= m; j++) {
happy[j] = max(happy[j], happy[j - b[i]] + a[i]);
}
}
printf("%d\n", happy[m]);
}
return 0;
}
1004 畅通工程
Problem Description
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省*“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
Input
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时，输入结束，该用例不被处理。
Output
对每个测试用例，在1行里输出最少还需要建设的道路数目。
Sample Input
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0
Sample Output
1
0
2
998
Source
浙大计算机研究生复试上机考试-2005年
解题思路
并查集问题
代码实现
#include<cstdio>
const int maxn = 1005;
int city[maxn];
//寻找n指向的最终值
int getfather(int n) {
if(city[n] == n) return n;
else return getfather(city[n]);
}
int main() {
int n, m;
while(scanf("%d", &n) != EOF && n != 0) {
scanf("%d", &m);
for(int i = 1; i <= n; i++) {
city[i] = i;
}
while(m--) {
int a, b;
scanf("%d %d", &a, &b);
//找出a，b两个的最终索引值并比较，若不相等则令其相等
int af = getfather(a);
int bf = getfather(b);
if(af != bf) city[bf] = city[af];
}
//判断公路将各个村庄连接为ex部分
int ex = 0;
for(int i = 1; i <= n; i++) {
if(city[i] == i) {
ex++;
}
}
//村庄分为ex部分，则至少还需修ex-1条道路
printf("%d\n", ex-1);
}
return 0;
}
1005 还是畅通工程
Problem Description
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省*“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。
Output
对每个测试用例，在1行里输出最小的公路总长度。
Sample Input
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
Sample Output
3
5
Source
浙大计算机研究生复试上机考试-2006年
解题思路
和普通并查集问题不同，需要运用贪心算法
代码实现
#include<cstdio>
#include<algorithm>
//村庄a—>村庄b 需要建设meter长的道路
struct INF {
int a;
int b;
int meter;
//INF升序 <=> meter升序
bool operator < (const INF city)const {
return meter < city.meter;
}
};
const int maxn = 1005;
const int maxns = 1e6 + 5;
int city[maxn];
INF road[maxns];
int getfather(int n) {
if(city[n] == n) return n;
else return getfather(city[n]);
}
int main() {
int n;
while(scanf("%d", &n) != EOF && n != 0) {
int m = n * (n - 1) / 2;
for(int i = 1; i <= n; i++) {
city[i] = i;
}
for(int i = 0; i < m; i++) {
scanf("%d %d %d", &road[i].a, &road[i].b, &road[i].meter);
}
//将所有道路按长度从小到大排序
std::sort(road, road + m);
long long sum = 0;
for(int i = 0; i < m; i++){
//判断修第i条道路前村庄a和村庄b是否连通，若未联通则修建此道路
int af = getfather(road[i].a);
int bf = getfather(road[i].b);
if(af != bf){
city[bf] = city[af];
sum += road[i].meter;
}
}
printf("%lld\n", sum);
}
return 0;
}
1006 继续畅通工程
Problem Description
省*“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。
当N为0时输入结束。
Output
每个测试用例的输出占一行，输出全省畅通需要的最低成本。
Sample Input
3
1 2 1 0
1 3 2 0
2 3 4 0
3
1 2 1 0
1 3 2 0
2 3 4 1
3
1 2 1 0
1 3 2 1
2 3 4 1
0
Sample Output
3
1
0
Author
ZJU
Source
浙大计算机研究生复试上机考试-2008年
解题思路
与还是畅通工程相似，只需判断路是否已修建，若已修建则需要费用为0
代码实现
#include<cstdio>
#include<algorithm>
struct INF {
int a;
int b;
int money;
//INF升序 <=> money升序
bool operator < (const INF city)const {
return money < city.money;
}
};
const int maxn = 105;
const int maxns = 1e4 + 5;
int city[maxn];
INF road[maxns];
int getfather(int n) {
if(city[n] == n) return n;
else return getfather(city[n]);
}
int main() {
int n;
while(scanf("%d", &n) != EOF && n != 0) {
int m = n * (n - 1) / 2;
for(int i = 1; i <= n; i++) {
city[i] = i;
}
for(int i = 0; i < m; i++) {
int temp;
scanf("%d %d %d %d", &road[i].a, &road[i].b, &road[i].money, &temp);
//如果道路已经修建则money为0
if(temp == 1) road[i].money = 0;
}
std::sort(road, road + m);
long long sum = 0;
for(int i = 0; i < m; i++){
int af = getfather(road[i].a);
int bf = getfather(road[i].b);
if(af != bf){
city[bf] = city[af];
sum += road[i].money;
}
}
printf("%lld\n", sum);
}
return 0;
}
1007 畅通工程续
Problem Description
某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。
Input
本题目包含多组数据，请处理到文件结束。
每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000)，分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0～N-1编号。
接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。
再接下一行有两个整数S,T(0<=S,T<N)，分别代表起点和终点。
Output
对于每组数据，请在一行里输出最短需要行走的距离。如果不存在从S到T的路线，就输出-1.
Sample Input
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
Sample Output
2
-1
Author
linle
Source
2008浙大研究生复试热身赛（2）——全真模拟
解题思路
利用结构体存储读入的道路数据，然后从村庄come(出发点)开始搜索去各个村庄的最优道路
代码实现
#include<cstdio>
#include<vector>
using namespace std;
const int maxn = 0x7FFFFFFF;
struct INF {
vector<int> go;
vector<int> xi;
int min = maxn;
};
INF city[205];
//city[i]中存放从村庄i出发到村庄go[j]所需路程xi，以及从村庄come到该村庄所需最小路程min
//去往村庄mum已经走过x的路程
void minxi(const int mum, const int x) {
//如果走法为最优走法，则前往下一个村庄
if(x < city[mum].min) {
city[mum].min = x;
for(int i = 0; i < city[mum].go.size(); i++) {
//路程增加
int minx = x + city[mum].xi[i];
minxi(city[mum].go[i], minx);
}
}
}
int main(){
int n, m;
while(scanf("%d %d", &n, &m) == 2){
for(int i = 0; i < 205; i++){
city[i].go.clear();
city[i].xi.clear();
city[i].min = maxn;
}
while(m--){
int a, b, x;
scanf("%d %d %d", &a, &b, &x);
//双向道路
city[a].go.push_back(b);
city[a].xi.push_back(x);
city[b].go.push_back(a);
city[b].xi.push_back(x);
}
int come, go;
scanf("%d %d", &come, &go);
//调用循环计算去往各个村庄最优路程
minxi(come, 0);
if(city[go].min != maxn)printf("%d\n", city[go].min);
else printf("-1\n");
}
return 0;
}
1008 一个人的旅行
Problem Description
虽然草儿是个路痴（就是在杭电待了一年多，居然还会在校园里迷路的人，汗~),但是草儿仍然很喜欢旅行，因为在旅途中 会遇见很多人（白马王子，0），很多事，还能丰富自己的阅历，还可以看美丽的风景……草儿想去很多地方，她想要去东京铁塔看夜景，去威尼斯看电影，去阳明山上看海芋，去纽约纯粹看雪景，去巴黎喝咖啡写信，去北京探望孟姜女……眼看寒假就快到了，这么一大段时间，可不能浪费啊，一定要给自己好好的放个假，可是也不能荒废了训练啊，所以草儿决定在要在最短的时间去一个自己想去的地方！因为草儿的家在一个小镇上，没有火车经过，所以她只能去邻近的城市坐火车（好可怜啊~）。
Input
输入数据有多组，每组的第一行是三个整数T，S和D，表示有T条路，和草儿家相邻的城市的有S个，草儿想去的地方有D个；
接着有T行，每行有三个整数a，b，time,表示a,b城市之间的车程是time小时；(1=<(a,b)<=1000;a,b 之间可能有多条路)
接着的第T+1行有S个数，表示和草儿家相连的城市；
接着的第T+2行有D个数，表示草儿想去地方。
Output
输出草儿能去某个喜欢的城市的最短时间。
Sample Input
6 2 3
1 3 5
1 4 7
2 8 12
3 8 4
4 9 12
9 10 2
1 2
8 9 10
Sample Output
9
Author
Grass
Source
RPG专场练习赛
解题思路
与畅通工程续相似，只是此处出发点和终点为多个而已
代码实现
#include<cstdio>
#include<vector>
using namespace std;
const int maxn = 0x7FFFFFFF;
struct INF {
vector<int> go;
vector<int> ti;
int min = maxn;
};
INF city[1005];
int by[1005], want[1005];
//前往城市mum时已经用了tim时间
void mintime(const int mum, const int tim) {
//如tim为已知最优，则前往下一个城市
if(tim < city[mum].min) {
city[mum].min = tim;
for(int i = 0; i < city[mum].go.size(); i++) {
int time = tim + city[mum].ti[i];
mintime(city[mum].go[i], time);
}
}
}
int main() {
int t, s, d;
while(scanf("%d %d %d", &t, &s, &d) == 3) {
for(int i = 0; i < 1005; i++){
city[i].go.clear();
city[i].ti.clear();
city[i].min = maxn;
}
while(t--) {
int a, b, time;
scanf("%d %d %d", &a, &b, &time);
//双向道路
city[a].go.push_back(b);
city[a].ti.push_back(time);
city[b].go.push_back(a);
city[b].ti.push_back(time);
}
for(int i = 0; i < s; i++) scanf("%d", &by[i]);
for(int i = 0; i < d; i++) scanf("%d", &want[i]);
//多个出发点
for(int i = 0; i < s; i++) mintime(by[i], 0);
//多个终点中用时需求最小的即为所求mint
int mint = maxn;
for(int i = 0; i < d; i++) if(mint > city[want[i]].min) mint = city[want[i]].min;
printf("%d\n", mint);
}
return 0;
}