首页 > 代码库 > 九度OJ&北邮机试题（2010计算机）
九度OJ&北邮机试题（2010计算机）
题目一、九度OJ-1169：比较奇偶数个数
http://ac.jobdu.com/problem.php?pid=1169
- 题目描述：
第一行输入一个数，为n，第二行输入n个数，这n个数中，如果偶数比奇数多，输出NO，否则输出YES。
- 输入：
输入有多组数据。
每组输入n，然后输入n个整数（1<=n<=1000）。
- 输出：
如果偶数比奇数多，输出NO，否则输出YES。
- 样例输入：
5 1 5 2 4 3
- 样例输出：
YES
AC代码：
/**
*@xiaoran
*/
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<cstdlib>
#include<cctype>
#include<cmath>
#define LL long long
using namespace std;
int main()
{
int a,even,odd,n;
while(cin>>n){
even=odd=0;
for(int i=0;i<n;i++){
cin>>a;
if(a%2) even++;
else odd++;
}
if(odd>even) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}
题目二、九度OJ-1170：找最小数
http://ac.jobdu.com/problem.php?pid=1170
- 题目描述：
第一行输入一个数n，1 <= n <= 1000，下面输入n行数据，每一行有两个数，分别是x y。输出一组x y，该组数据是所有数据中x最小，且在x相等的情况下y最小的。
- 输入：
输入有多组数据。
每组输入n，然后输入n个整数对。
- 输出：
输出最小的整数对。
- 样例输入：
5 3 3 2 2 5 5 2 1 3 6
- 样例输出：
2 1
/**
*@xiaoran
*排序或者直接比较，排序O(nlogn),空间O(2n),直接O(n),空间O(1)
*/
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<cstdlib>
#include<cctype>
#include<cmath>
#define LL long long
using namespace std;
int main()
{
int n,x,y,xmin,ymin;
while(cin>>n){
cin>>xmin>>ymin;
for(int i=1;i<n;i++){
cin>>x>>y;
if(x<xmin){
xmin=x; ymin=y;
}
if(x==xmin&&y<ymin){
xmin=x; ymin=y;
}
}
cout<<xmin<<" "<<ymin<<endl;
}
return 0;
}
题目三、九度OJ-1171：C翻转
http://ac.jobdu.com/problem.php?pid=1171
- 题目描述：
首先输入一个5 * 5的数组，然后输入一行，这一行有四个数，前两个代表操作类型，后两个数x y代表需操作数据为以x y为左上角的那几个数据。
操作类型有四种：
1 2 表示：90度，顺时针，翻转4个数
1 3 表示：90度，顺时针，翻转9个数
2 2 表示：90度，逆时针，翻转4个数
2 3 表示：90度，逆时针，翻转9个数
- 输入：
输入有多组数据。
每组输入一个5 * 5的数组，然后输入一行，这一行有四个数，前两个代表操作类型，后两个数x y代表需操作数据为以x y为左上角的那几个数据。
- 输出：
输出翻转后的数组。
- 样例输入：
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 1 3 1 1
- 样例输出：
11 6 1 4 5 12 7 2 9 10 13 8 3 14 15 16 17 18 19 20 21 22 23 24 25
二维数组模拟的问题，仔细想都能搞定。
AC代码：
#include<iostream>
#include<cstring>
using namespace std;
int a[10][10],b[10][10];
//ok表示旋转方式,x,y,表示旋转数组的左上角下标,k表示旋转个数
void XuanZhuan(int ok,int k,int x,int y){
memcpy(b,a,sizeof(a));
if(ok==2){//逆时针旋转
int ky,kx=x;
for(int j=y;j<y+k;j++){
ky=y;
for(int i=x+k-1;i>=0;i--){
a[i][j]=b[kx][ky++];
}
kx++;
}
}
else if(ok==1){//顺时针旋转
int ky,kx=x+k-1;
for(int j=y;j<y+k;j++){
ky=y;
for(int i=x;i<x+k;i++){
a[i][j]=b[kx][ky++];
}
kx--;
}
}
}
int main()
{
int ok,k,x,y;
while(cin>>a[1][1]){
for(int i=1;i<=5;i++){
for(int j=1;j<=5;j++){
if((i+j)!=2) cin>>a[i][j];
}
}
cin>>ok>>k>>x>>y;
XuanZhuan(ok,k,x,y);
for(int i=1;i<=5;i++){
for(int j=1;j<=5;j++){
if(j!=5) cout<<a[i][j]<<" ";
else cout<<a[i][j]<<endl;
}
//cout<<endl;
}
}
return 0;
}
题目四、九度OJ-1172：哈夫曼树
http://ac.jobdu.com/problem.php?pid=1172
- 题目描述：
哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。
- 输入：
输入有多组数据。
每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。
- 输出：
输出权值。
- 样例输入：
5 1 2 2 5 9
- 样例输出：
37
可以建立哈弗曼树，但是题目只让求权值，直接上优先队列就行了，当然也可以排序，因为数据太少，怎么都行。
AC代码：
/**
*@xiaoran
*优先队列
*/
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<cstdlib>
#include<cctype>
#include<cmath>
#define LL long long
using namespace std;
int main()
{
int n;
while(cin>>n){
priority_queue<int, vector<int>,greater<int> > p;
int ans=0,x;
for(int i=0;i<n;i++){
cin>>x;
p.push(x);
}
while(p.size()>1){
int a=p.top();
p.pop();
int b=p.top();
p.pop();
ans+=a+b;
p.push(a+b);
}
cout<<ans<<endl;
}
return 0;
}
九度OJ&北邮机试题（2010计算机）