2013年中南大学计算机研究生复试机试题解
高温假闲置下来感到有些无聊，在vijos平台上完成了一道CSU的编程题。这可能是由于这些题目出自较早时期。相对来说这道题的难度并不算大。为了方便以后查阅和学习稍微整理了一下这些解题思路和代码逻辑
1264: 惠民工程
在本题中涉及的独特数据结构问题是一道最小生成树（MST）相关的题目；这道题目是关于最小生成树（MST）的经典模板设计；解决该类问题的主要方法包括Prim算法和Kruskal算法
本题要求设计一个程序来确定在给定条件下的最低成本方案。具体来说，在全市n个居民点之间架设煤气管道（并非所有居民点之间都需要直接连接一条管道；只要它们可以通过其他管道间接连接即可）。显然，在这种情况下最多需要架设n(n-1)/2条管道；但实际上只需要n-1条管道就足以使所有居民点连通了。请编写一个程序来计算该经济民生工程所需的最低建设成本。
测试输入包含若干个测试用例。
每个测试用例的第一行提供居民区数量M（不超过100）以及管道评估数量N。
接下来的N行分别记录了各对居民点之间的管道成本数据。
每行为两个正整数：这两个数字分别表示两个居民点编号及其连接管道的成本值。
为了简化问题描述，并将所有居民点依次被标记为从1到M号。
对于每一个测试用例，在一行中输出全市管道全部畅通所需最低的成本。如果统计数据不足以确保这一目标的实现，则输出‘?’。
Sample Input
3 3
1 2 1
1 3 2
2 3 4
3 1
2 3 2
Sample Output
3
?
Prim代码：
#include <stdio.h>
#define INF 0x7ffff
#define MAXVER 128
typedef struct graph
{
int adjMatrix[MAXVER][MAXVER];
int weight[MAXVER];
int vis[MAXVER];
} graph;
graph Graph;
int m,n;
void init()
{
for(int i=0; i<MAXVER; i++)
{
Graph.vis[i] = 0;
for(int j=0; j<MAXVER; j++)
if(i==j)
Graph.adjMatrix[i][j] = 0;
else
Graph.adjMatrix[i][j] = INF;
}
}
int prim()
{
int ans = 0;
for(int i=1; i<=m; i++)
Graph.weight[i] = Graph.adjMatrix[1][i];
Graph.vis[1] = 1;
for(int i=2; i<=m; i++)
{
int minCost = INF,idx;
for(int j=1; j<=m; j++)
if(!Graph.vis[j]&&minCost>Graph.weight[j])
{
minCost = Graph.weight[j];
idx = j;
}
if(minCost==INF)
return -1;
Graph.vis[idx] = 1;
ans+=Graph.weight[idx];
for(int j=1; j<=m; j++)
if(!Graph.vis[j]&&Graph.weight[j]>Graph.adjMatrix[idx][j])
Graph.weight[j] = Graph.adjMatrix[idx][j];
}
return ans;
}
int main()
{
while(~scanf("%d%d",&m,&n))
{
init();
for(int i=0; i<n; i++)
{
int src,dest,weight;
scanf("%d%d%d",&src,&dest,&weight);
Graph.adjMatrix[src][dest] = Graph.adjMatrix[dest][src] = weight;
}
int ans = prim();
(ans==-1)?printf("?\n"):printf("%d\n",ans);
}
return 0;
}Kruskal代码:
#include <stdio.h>
#include <algorithm>
#define MAXVER 4096
int uSet[MAXVER];
int sum,ans;
struct edge
{
int src,dest,weight;
};
edge graph[MAXVER];
int cmp(edge a,edge b)
{
return a.weight<b.weight;
}
void MakeSet(int m)
{
for(int i=1; i<=m; i++)
uSet[i] = i;
}
int Find(int key)
{
if(key!=uSet[key])
key = Find(uSet[key]);
return key;
}
void Union(edge e)
{
if(Find(e.src)!=Find(e.dest))
{
uSet[Find(e.src)] = Find(e.dest);
sum++;
ans+=e.weight;
}
}
void Kruskal(int n)
{
sort(graph+1,graph+n+1,cmp);
for(int i=1; i<=n; i++)
Union(graph[i]);
}
int main()
{
int m,n;
while(~scanf("%d%d",&m,&n))
{
ans = sum = 0;
MakeSet(m);
for(int i=1; i<=n; i++)
scanf("%d%d%d",&graph[i].src,&graph[i].dest,&graph[i].weight);
Kruskal(n);
sum==m-1?printf("%d\n",ans):printf("?\n");
}
return 0;
}1263: 最少钱币数
暴力枚举
Description
A公司的工作人员对每月8日都有特殊的意义，在这一天他不仅能够拿到期待已久的工资收入来维持家用开支, 对于公司财务部门而言, 这一天同样也是一个忙碌的工作日. 最近, 财务室的小王就遇到了一个实际问题: 如果每位员工的具体薪资金额都知道, 我们最少需要准备多少张不同面值的人民币, 才能在发放每位员工薪资时都不必找零. 在这个问题中假设每位员工的薪资都是正整数单位元, 现有的人民币面额有100元钞票、50元纸币以及10元钞票、5元纸币等.
输入数据包括多个测试案例，在每一个案例中的一行表示老师的人数（n<100），代表老师数量；接着是对应数量老师的工资（工资<5000）。
每个测试用例均需输出一行。具体要求如下：即目标金额为M时，请计算并输出所需最少硬币数量。若无法凑出该金额，则输出"Impossible"。假设每种待选硬币的数量均为无限供应。
Sample Input
3
1 2 3
2
1 2
Sample Output
4
2
代码：
#include <stdio.h>
int main()
{
int money[6]= {100,50,10,5,2,1},n;
while(~scanf("%d",&n))
{
int ans = 0,salary = 0;
while(n--)
{
scanf("%d",&salary);
for(int i=0; i<6; i++)
if(salary/money[i])
ans+=salary/money[i],salary%=money[i];
}
printf("%d\n",ans);
}
return 0;
}1262: 安全密码
按题目要求模拟就完事了~
Description
网络上各类交易活动越来越普及，为了能够安安心心地上网，经常需要设置一个安全的密码。一般来说一个比较安全的密码至少应该满足下面两个条件：
(1)密码长度大于等于8。
(2)密码中的字符应该来自下面“字符类别”中四组中的至少三组。
这四个字符类别分别为：
(1)大写字母：A,B,C…Z;
(2)小写字母：a,b,c…z;
(3)数字：0,1,2…9;
(4)特殊符号：~,!,@,#,$,%,^;
给你一个密码，你的任务就是判断它是不是一个安全的密码。
输入数据包含若干组；
每一组占据一行；
每个密码单独一行；
字符串最长不超过50个字符；
且仅包含上述四种类型的字符。
在每一个测试案例中，请评估该密码是否为一个安全有效的密码？如果符合条件，则输出YES；否则，请输出NO。
Sample Input
a1b2c3d4
Linle@ACM
~@^@!%
Sample Output
NO
YES
NO
代码：
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int main()
{
char psw[99];
while(~scanf("%s",psw))
{
int len = strlen(psw);
if(len<8)
{
printf("NO\n");
continue;
}
int k1,k2,k3,k4;
k1 = k2 = k3 = k4 = 0;
for(int i=0; i<len; i++)
{
if(psw[i]>='A'&&psw[i]<='Z')
k1 = 1;
else if(psw[i]>='a'&&psw[i]<='z')
k2 = 1;
else if(psw[i]>='0'&&psw[i]<='9')
k3 = 1;
else
k4 = 1;
}
if(k1+k2+k3+k4>=3)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}1261: 水仙花数
在初中时期觉得这道题十分棘手(￣▽￣)。
实际上只要不把它想得太复杂就能迎刃而解。
多数情况下是没有把问题想得太复杂导致难以入手。
通过去年的AC代码作为反例说明，
告诉各位不要过于复杂化问题。
Description
春季里百花盛开的时节,水仙花常被视为这些美丽花朵中最引人注目的品种,在数学领域中存在一种特殊的数字类型称为水仙花数,它被定义为:一个三位整数,其各位数字分别取立方后相加之和等于该数值本身.例如:153等于其各位数字各自立方后的总和(即1³ + 5³ + 3³).当前的任务是找出并列出所有介于m与n之间的水仙花数.
Input
输入数据有多组，每组占一行，包括两个整数m和n（100<=m<=n<=999）。
针对每一个测试实例，
必须找出并列出所有满足条件范围内的水仙花数，
即满足数值区间[m, n]的要求。
为了实现这一目标，
需要将找到的所有符合条件的水仙花数按照从小到大的顺序排列并在同一行内显示，
但需要注意的是，
每组结果的最后一项之后不应添加额外空格。
如果没有任何符合条件的水仙花数，
则应输出no；
每个测试实例的结果应当独立成行。
Sample Input
100 120
300 380
Sample Output
no
370 371
去年代码（自己给自己加难度作死）：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n,m,x,y,z,sum;
vector<int> ans;
while(cin>>m>>n)
{
sum=0;
ans.clear();
for(int i=m; i<=n; i++)
{
x=i/100;
y=(i/10)%10;
z=i%10;
if((x*x*x)+(y*y*y)+(z*z*z)==i)
{
sum++;
ans.push_back(i);
}
}
if(sum==0)
cout<<"no";
for(vector<int>::iterator it=ans.begin(); it!=ans.end(); it++)
{
if(it!=ans.end())
cout<<*it<<" ";
else
cout<<*it;
}
cout<<endl;
}
return 0;
}今年代码：
#include <stdio.h>
int main()
{
int i,j,k,m,n;
while(~scanf("%d%d",&m,&n))
{
int ans[99];
for(i=m,j=0; i<=n; i++)
{
int a,b,c;
a = i/100;
b = (i/10)%10;
c = i%10;
if(a*a*a+b*b*b+c*c*c==i)
ans[j++] = i;
}
if(j!=0)
{
for(int k=0; k<j-1; k++)
printf("%d ",ans[k]);
printf("%d\n",ans[j-1]);
}
else
printf("no\n");
}
return 0;
}1260: 回文串问题
基本的字符串操作
暴力即可
Description
回文串是一种正读反读均相同的字符串。它仅由数字与小写字母构成，并可举例说明如"level"或"abcdcba"等即是典型的回文串。请编写一个程序以判断输入的字符串是否为'回文'类型。
Input
输入包含多个测试实例，每一行对应一个字符串，串长最多100字母。
对于每一个字符串，请标记为它的索引值，并判断是否为回文串：如果是，则标记为 yes；否则标记为 no。
Sample Input
level
abcde
noon
haha
Sample Output
case1: yes
case2: no
case3: yes
case4: no
代码：
#include <stdio.h>
#include <string.h>
int main()
{
char str[128],cnt = 0;
while(~scanf("%s",str))
{
int len = strlen(str),flag = 1;
for(int i=0; i<len/2; i++)
if(str[i]!=str[len-i-1])
flag = 0;
printf("case%d: %s\n",++cnt,flag?"yes":"no");
}
return 0;
}总结
仅此一道题目涉及数据结构相关内容，其余均为较高难度的C语言程序设计题。对编码能力的要求较高。这道题耗时较久才能通过AC，在考试环境下可能会带来较大的心理压力(T_T)。这道题本质上是一个标准模板问题应当轻松获得AC。未来仍需持续加强练习以巩固掌握。