2014
Problem A. 奇偶求和
题目描述：
给定N个数，分别求出这N个数中奇数的和以及偶数的和。
输入格式
第一行为测试数据的组数T（1<=T<=50）。请注意，任意两组测试数据之间是相互独立的。
每组数据包含两行：
第一行为一个整数N（1<=N<=10C）。
第二行为N个正整数，整数之间用一个空格隔开，且每个整数的绝对值均大不于10^5。
输出格式：
每组数据输出两个数，即N个数中奇数之和和偶数之和，中间用空格隔开。
输入样例
2
5
1 2 3 4 5
5
1 1 1 1 1
输出样例
9 6
5 0
#include
<iostream>
using namespace std;
/* run this program
using the console pauser or add your own getch, system("pause") or
input loop */
int main(int argc,
char *argv[]) {
int T,N,*a=NULL;
cin>>T;
while(T--){
cin>>N;
if(N>0){
a=new int[N];
}else{
return -1;
}
int i=0;
while(i<N){
cin>>a[i++];
}
int odd=0,even=0;
for(i=0;i<N;i++){
if(a[i]%2!=0){
odd+=a[i];
}else{
even+=a[i];
}
}
cout<<odd<<"
"<<even<<endl;
}
return 0;
}
Problem B. 最长连续等差子数列
题目描述
给定一个长度为N的整数数列，你需要在其中找到最长的连续子数列的长度，并满足这个子序列是等差的。
注意公差小于或等于0的情况也是允许的。
输入格式
第一行为数据组数T（1<=T<=100），表示测试数据的组数。
对于每行测试数据：
第一行是一个正整数N（1<=N<=100），表示给定数列的长度。
第二行是N个整数，其中第i个整数valuei(1<=valuei<=10^5)表示下标为i的数字。
输出格式
对于每组测试数据，输出最长的连续等差子数列的长度。
输入样例
2
2
1 3
5
1 6 4 2 4
5 -2 -2 2
输出样例
2
3
样例解释
两组样例的最长连续等差子数列分别是{1,3}和{6,4,2}
#include
<iostream>
using namespace std;
/* run this program
using the console pauser or add your own getch, system("pause") or
input loop */
int main(int argc,
char *argv[]) {
int T,N,*a=NULL;
cin>>T;
while(T--){
cin>>N;
if(N>0){
a=new int[N];
}else{
return -1;
}
int i=0;
while(i<N){
cin>>a[i++];
}
if(N<=2){
cout<<N<<endl;
continue;
}
int *d=new int[N-1];
for(i=0;i<N-1;i++){
d[i]=a[i+1]-a[i];
// cout<<d[i]<<"
";
}
//cout<<endl;
int max=0,tmp=0;
for(i=0;i<N-2;i++){
if(d[i+1]==d[i]){
tmp++;
}else{
tmp=0;
}
max=max<tmp?tmp:max;
// cout<<max<<"
";
}
//cout<<endl;
cout<<max+2<<endl;
}
return 0;
}
Problem C. 最近公共祖先
题目描述
给出一棵有N个节点的有根树TREE（根的编号为1），对于每组查询，请输出树上节点u和v的最近公共祖先。
最近公共祖先：对于有向树TREE的两个结点u,v。最近公共祖先LCA（TREE u,v）表示一个节点x，满足x是u、v的祖先且x的深度尽可能大。
输入格式
输入数据第一行是一个整数T（1<=T<=100），表示测试数据的组数。
对于每组测试数据：
第一行是一个正整数N（1<=N<=100），表示树上有N个节点。
接下来N-1行，每行两个整数u,v(1<=u,v<=N)，表示节点u是v的父节点。
接下来一行是一个整数M（1<=M<=1000），表示查询的数量。
接下来M行，每行两个整数u,v(11<=u,v<=N)，表示查询节点u和节点v的最近公共祖先。
输出格式
对于每个查询，输出一个整数，表示最近公共祖先的编号，
输入样例
2
3
1 2
1 3
1
2 3
4
1 2
1 3
3 4
2
2 3
3 4
1
1
3
#include
<iostream>
using namespace std;
/* run this program
using the console pauser or add your own getch, system("pause") or
input loop */
int getCommParent(int
*a,int n,int u,int v){
if(u==v){
return u;
}else if(u<v){
while(u<v){
v=a[v];
}
if(u==v){
return u;
}else{
return a[u];
}
}else{
return getCommParent(a,n,v,u);
}
}
int main(int argc,
char *argv[]) {
int T,N,M,*a=NULL;
cin>>T;
while(T--){
cin>>N;
if(N>1){
a=new int[N+1];
}else{
return -1;
}
a[0]=-1;
a[1]=0;
int i=1,p,c;
while(i++<N){
cin>>p>>c;
a[c]=p;
}
for(i=1;i<=N;i++){
cout<<a[i]<<"
";
}
cout<<endl;
cin>>M;
int u,v;
while(M--){
cin>>p>>c;
cout<<getCommParent(a,N,p,c)<<endl;
}
}
return 0;
}
Problem D. 数据库检索
题目描述
在数据库的操作过程中，我们进场会遇到检索操作。这个题目的任务是完成一些特定格式的检索，并输出符合条件的数据库中的所有结果。
我们现在有一个数据库，维护了学生的姓名（Name），性别（Sex）以及出生日期（Birthday）。其中，Name项是长度不超过30的字符串，只可能包含大小写字母，没有空格；Sex项进可能为‘Male’或者‘Female’（不含引号）；Birthday项以yyy/mm/dd的格式存储，如：1990/01/01，
1991/12/31，等等。
每个查询所可能包含的条件如下：
Name=‘REQUIRED_NAME’，查询姓名为REQUIRED_NAME的学生，其中REQUIRED_NAME为长度在1到30之间的字符串；
Sex=‘Male’或Sex=‘Female’，查询性别为男/女的学生；
Birthday=‘yyy/mm/dd’，查询出生年/月/日为特定值的学生。如果其中某项为’*’，则说明该项不受限制。例如，‘1990/06/*’表示1990年6月出生，‘*/03/*’表示出生月份为3月。
给定数据库的所有表项以及若干条查询，你需要对每条查询输出它返回的结果。
输入格式
输入包含多组测试数据。输入的第一行为测试数据的组数T（1<=T<=50）。
对于每组测试数据，第一行是两个整数N和M（N,M<=500），分别表示数据的数量以及查询的数量。
接下来N行，每行以Name Sex Birthday的形式给出每个学生的信息。
没下来M行，每行给出若干条限制条件，以空格隔开。条件以Name Sex
Birthday的顺序给出（如果存在），且每种限制条件最多只出现一次。
输出格式
对于每条查询，按照输入的顺序输出符合条件的学生姓名，每个一行。如果没有符合查询的信息，则输出一行NULL。
样例输入
1
5 6
Michael Male 1990/02/28
Amy Female 1992/04/03
Tom Male 1991/12/15
Lynn Female 1991/04/09
Zheng Male 1990/04/20
Name='Amy'
Name='Betty'
Sex='Female' Birthday='*/04/09’
Sex=’Female’ Birthday=’*/*/*’
Name=’Michael’ Sex=’Female’
Name=’Michael’ Sex=’Male’ Birthday=’1990/02/*’
样例输出
Amy
NULL
Lynn
Amy
Lynn
NULL
Michael
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Vector;
/**
* Created by yueli on 2019/1/7.
*/
public class sqlHandler {
Scanner scanner;
ArrayList<String>name;
ArrayList<String>gender;
ArrayList<String>date;
String str;
int T,N,M;
sqlHandler(){
scanner=new Scanner(System.in);
name=new ArrayList<>();
gender=new ArrayList<>();
date=new ArrayList<>();
}
public void BeginFromName(String
term,boolean sex,boolean date){
boolean flag=true;
if(!sex&&!date){
String n=term.split("=")[1];
n=n.substring(1,n.length()-1);
for(int i=0;i<N;i++){
if(name.get(i).equals(n)){
System.out.println(name.get(i));
flag=false;
}
}
if(flag) System.out.println("NULL");
}else {
String tmp[] = term.split(" ");
String n = tmp[0].split("=")[1];
n=n.substring(1,n.length()-1);
LinkedList<Integer>
mark = new LinkedList<>();
for (int i = 0; i < N; i++)
{
if (name.get(i).equals(n)) {
mark.add(i);
}
}
if(mark.isEmpty()){
System.out.println("NULL");
return;
}
if(sex)
{
if (!date) {
BeginFromSex(tmp[1],
false, mark);
} else {
BeginFromSex(tmp[1]
+ " " + tmp[2], true,
mark);
}
}else {
BeginFromDate(tmp[1],mark);
}
}
}
public void BeginFromSex(String
term,boolean date,LinkedList<Integer> mark){
if(date){
String tmp[]=term.split(" ");
String s=tmp[0].split("=")[1];
s=s.substring(1,s.length()-1);
LinkedList<Integer>_mark=new LinkedList<>();
for(int i=mark.getFirst();;mark.removeFirst(),i=mark.getFirst()){
if(gender.get(i).equals(s)){
_mark.add(i);
}
if (mark.size()<2)break;
}
if (_mark.isEmpty()){
System.out.println("NULL");
return;
}
BeginFromDate(tmp[1],_mark);
}else{
String s=term.split("=")[1];
s=s.substring(1,s.length()-1);
boolean flag=true;
for(int i=mark.getFirst();;mark.removeFirst(),i=mark.getFirst()){
if(gender.get(i).equals(s)){
System.out.println(name.get(i));
flag=false;
}
if (mark.size()<2)break;
}
if(flag)System.out.println("NULL");
}
}
public void BeginFromDate(String
term,LinkedList<Integer>mark){
String tmp=term.split("=")[1];
tmp=tmp.substring(1,tmp.length()-1);
String d[]=tmp.split("/");
boolean flag=true;
for(int i=mark.getFirst();;mark.removeFirst(),i=mark.getFirst()){
String dd[]=date.get(i).split("/");
flag=true;
for(int k=0;k<3;k++){
if(d[k].equals("*")){
continue;
}else{
if(d[k].equals(dd[k])){
continue;
}else{
flag=false;
continue;
}
}
}
if(flag)
System.out.println(name.get(i));
if (mark.size()<2)break;
}
if(!flag)
System.out.println("NULL");
}
public void runMethod(){
T=scanner.nextInt();
int i;
while(T-->=0) {
name.clear();gender.clear();date.clear();
i=0;
N=scanner.nextInt();
M=scanner.nextInt();
LinkedList<Integer>mark=new LinkedList<>();
scanner.nextLine();
while(i++<N){
str=scanner.nextLine();
String[] tmp=str.split("
");
name.add(tmp[0]);
gender.add(tmp[1]);
date.add(tmp[2]);
}
while (M-->=0){
str=scanner.nextLine();
String[] tmp=str.split("
");
String begin=tmp[0].split("=")[0];
switch (begin){
case "Name":
if(tmp.length==3){
BeginFromName(str,true,true);
}else if(tmp.length==2){
if(str.indexOf("Sex")!=-1){
BeginFromName(str,true,false);
}else {
BeginFromName(str,false,true);
}
}else {
BeginFromName(str,false,false);
}
break;
case"Sex":
mark.clear();
for(int k=0;k<N;k++){
mark.add(k);
}
if(tmp.length==2){
BeginFromSex(str,true,mark);
}else{
BeginFromSex(str,false,mark);
}
break;
case"Birthday":
mark.clear();
for(int k=0;k<N;k++){
mark.add(k);
}
BeginFromDate(str,mark);
}
}
}
}
public static void main(String[] args) {
sqlHandler handler=new sqlHandler();
handler.runMethod();
}
}
北邮软院机试2018
1.二进制数字调转
题目描述：一个2^32的数字n，将其转换成二进制数，再倒转，求倒转的二进制数对应的十进制数。
例如：
123
0000 0000 0000 0000 0000 0000 0111 1011
1101 1110 0000 0000 0000 0000 0000 0000
3724541952
举例：
输入：123
输出：3724541952
#include <iostream>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
void getBinary(long p,char *a){
int r,i=0;
long q;
while(p>1){
q=p/2;
r=p%2;
a[i++]=r+48;
p=q;
}
a[i]=p+48;
for(i=i+1;i<32;i++){
a[i]=48;
}
}
long long getDec(char a[32]){
long long n=0,mult=1;
for(int i=31;i>=0;i--){
if(a[i]-48){
n+=mult;
}
mult*=2;
}
return n;
}
int main(int argc, char *argv[]) {
char a[33];
long long n;cin>>n;
getBinary(n,a);
cout<<a<<endl;
cout<<getDec(a)<<endl;
return 0;
}
2.输出数字
题目描述：不同数字的输出形状如下：
黑色部分是1，白色部分是0。
输入：长度为1-20的字符串
输出：0和1组合的数字形状，
举例：
输入：01
输出：
111001
101001
101001
101001
111001
#include <iostream>
#include <string.h>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
void perNo(bool b[5][3],int n){
int i,j;
switch(n){
case 0:{
for(i=0;i<5;i++){
for(j=0;j<3;j++){
b[i][j]=1;
}
}
b[1][1]=0;b[2][1]=0;b[3][1]=0;
break;
}
case 1:{
for(i=0;i<5;i++){
for(j=0;j<3;j++){
b[i][j]=0;
}
}
for(int i=0;i<5;i++){
b[i][2]=1;
}
break;
}
case 2:{
for(i=0;i<5;i++){
for(j=0;j<3;j++){
b[i][j]=1;
}
}
b[1][0]=0;b[1][1]=0;
b[3][1]=0;b[3][2]=0;
break;
}
case 3:{
for(i=0;i<5;i++){
for(j=0;j<3;j++){
b[i][j]=1;
}
}
b[1][0]=0;b[1][1]=0;
b[3][0]=0;b[3][1]=0;
break;
}
case 4:{
for(i=0;i<5;i++){
for(j=0;j<3;j++){
b[i][j]=1;
}
}
b[0][1]=0;b[1][1]=0;
b[3][0]=0;b[3][1]=0;
b[4][0]=0;b[4][1]=0;
break;
}
case 5:{
for(i=0;i<5;i++){
for(j=0;j<3;j++){
b[i][j]=1;
}
}
b[1][1]=0;b[1][2]=0;
b[3][0]=0;b[3][1]=0;
break;
}
case 6:{
for(i=0;i<5;i++){
for(j=0;j<3;j++){
b[i][j]=1;
}
}
b[1][1]=0;b[1][2]=0;
b[3][1]=0;
break;
}
case 7:{
for(i=0;i<5;i++){
for(j=0;j<3;j++){
b[i][j]=0;
}
}
for(int i=0;i<5;i++){
b[i][2]=1;
}
b[0][0]=1;b[0][1]=1;
break;
}
case 8:{
for(i=0;i<5;i++){
for(j=0;j<3;j++){
b[i][j]=1;
}
}
b[1][1]=0;
b[3][1]=0;
break;
}
case 9:{
for(i=0;i<5;i++){
for(j=0;j<3;j++){
b[i][j]=1;
}
}
b[1][1]=0;
b[3][0]=0;b[3][1]=0;
break;
}
}
}
int main(int argc, char *argv[]) {
char ch[21];cin>>ch;
int i,j;
bool b[5][60];
bool tmp[5][3];
for(i=0;i<strlen(ch);i++){
perNo(tmp,ch[i]-48);
for(int k=0;k<5;k++){
for(int j=0;j<3;j++){
b[k][j+i*3]=tmp[k][j];
}
}
}
for(i=0;i<5;i++){
for(j=0;j<3*strlen(ch);j++){
cout<<b[i][j];
}
cout<<endl;
}
return 0;
}
3.发财数
题目描述：一个数字如果是由8个及8个以上的质因数乘积而成的数为发财数
输入：数字n
输出：10000以内的第几个发财数
举例：输入：1 输出：256
10000/128=78.125
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73
#include <iostream>
#include <string.h>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
bool check(int *fac,int n){
int cnt=0;bool flag=true;
while(cnt<8&&n>=2&&flag){
flag=false;
for(int i=0;i<21;i++){
if(n%fac[i]==0){
flag=true;
cout<<++cnt<<" "<<fac[i]<<endl;
n/=fac[i];
}
}
}
if(cnt>=8){
return true;
}
return false;
}
int main(int argc, char *argv[]) {
int fac[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73};
int n,i;cin>>n;
while(n){
for(i=256;i<=10000;i++){
if(check(fac,i)){
n--;
}
if(!n){
break;
}
}
}
cout<<i<<endl;
return 0;
}
4.最长平衡子串
题目描述：只包含0和1的数字串中，如果0和1的个数一样，称为平衡字符串。求一个字符串的最长平衡子串
举例：输入：01011 输出：4
#include <iostream>
#include <string.h>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int MaxSub(char *ch){
int sum0=0,sum1=0,max=0;;
for(int i=0;i<strlen(ch);i++){
if(ch[i]=='0'){
sum0++;
}else if(ch[i]=='1'){
sum1++;
}
if(sum0==sum1&&max<sum0+sum1){
max=sum0+sum1;
}
}
return max;
}
int main(int argc, char *argv[]) {
char ch[200];cin>>ch;
int i,max=0;
for(i=0;i<strlen(ch);i++){
if(max<MaxSub(&ch[i])){
max=MaxSub(&ch[i]);
}
}
cout<<max<<endl;
return 0;
}