2023年华东师范大学计算机机试真题.doc

2023机试 2
计算和的数位 2
大写改小写 3
素数对 4
求最大公约数和最小公倍数 6
排序后求位置处的数 7
*路由器连接 8
*编译原理 10
*分开连接 13
2023机试 17
ECNU的含义 17
空瓶换啤酒 18
记录字符 20
2023机试热身 21
粽子买三送一，买五送二 21
工程流水线问题 22
2023机试 24
hello world 24
Special judge 26
查询成绩 28
2023机试热身 30
贪吃蛇 30
仰望星空 34
*编辑距离 36
2023机试 38
字母排序 38
幸运数 39
十六进制的加法 42
电话号码簿合并排序 42
*五子棋 43
*正则表达式匹配 45
2023机试 46
斐波那契数列的素数个数 46
*将a字符变成b字符最少修改次数 47
2023机试热身 49
去重排序 49
蛇形图案 51
数学手稿 54
2023机试
计算和的数位
Sum of digit
Description
Write a program which computes the digit number of sum of two integers a and b.

Input
The first line of input gives the number of cases, N(1 ≤ N ≤ 100). N test cases follow.
Each test case consists of two integers a and b which are separeted by a space in a line. (0<=a,b<=).

Output
For each test case, print the number of digits of a + b.

Sample Input
3
5 7
1 99
1000 999

Sample Output
2
3
4
#include
int main()
{
int n;
int a,b;
int sum;
while(scanf("%d",&n)!=EOF)
{
while(n--)
{
int an=0;
scanf("%d%d",&a,&b);
sum=a+b;
while(sum)
{
an++;
sum/=10;
}
printf("%d\n",an++);
}
}
return 0;
}
大写改小写
Capitalize
Description
Write a program which replace all the lower-case letters of a given text with the corresponding captital letters.

Input
A text including lower-case letters, periods, and space.

Output
Output The converted text.

Sample Input
welcome to east china normal university.

Sample Output
WELCOME TO EAST CHINA NORMAL UNIVERSITY.

#include
#include
char str[1000];
int main()
{
int l;
while(gets(str))
{
l=strlen(str);
int i;
for(i=0;i='a'&&str[i]<='z')
printf("%c",str[i]-32);
else
printf("%c",str[i]);
}
printf("\n");
}
return 0;
}
素数对
Primes Pair
Description
We arrange the numbers between 1 and N (1 <= N <= 10000) in increasing order and decreasing order like this:

1 2 3 4 5 6 7 8 9 . . . N
N . . . 9 8 7 6 5 4 3 2 1

Two numbers faced each other form a pair. Your task is to compute the number of pairs P such that both numbers in the pairs are prime.

Input
The first line of input gives the number of cases, C (1 ≤ C ≤ 100). C test cases follow.
Each test case consists of an integer N in one line.

Output
For each test case, output P .
Sample Input
4
1
4
7
51

Sample Output
0
2
2
6

#include
#include
bool prime[10005];
void init()
{
int i;
int j;
prime[0]=prime[1]=false;//不是素数
prime[2]=true;//是素数
for(i=3;i<=10005;i+=2)
{
prime[i]=true;//是素数
prime[i+1]=false;//不是素数 除0和2之外的偶数都不是素数
}
for(i=3;i<=10005;i+=2)
{
if(prime[i]==true)//是素数
{
j=i+i;
while(j<=10005)
{
prime[j]=false;//不是素数
j+=i;
}
}
}
}
int main()
{
int c;
int n;
init();//初始化
while(scanf("%d",&c)!=EOF)
{
while(c--)
{
scanf("%d",&n);
int sum=0;
int i;
for(i=2;i<=n/2;i++)
{
if(prime[i]==true&&prime[n+1-i]==true)
sum++;
}
sum*=2;
if(n%2==1)//n为奇数
{
if(prime[n/2+1]==true)
sum+=1;
}
printf("%d\n",sum);
}
}
return 0;
}
求最大公约数和最小公倍数
GCD and LCM
Description
Write a program which computes the greatest common divisor (GCD) and the least common multiple (LCM) of given a and b (0 < a, b ≤ 44000).

Input
The first line of input gives the number of cases, N(1 ≤ N ≤ 100). N test cases follow.
Each test case contains two interger a and b separated by a single space in a line.

Output
For each test case, print GCD and LCM separated by a single space in a line.

Sample Input

2
8 6
5000 3000

Sample Output
2 24
1000 15000

#include
int getgcd(int a,int b)
{
int gcd;
int t1,t2;
t1=a;
t2=b;
gcd=t1%t2;
while(gcd!=0)
{
t1=t2;
t2=gcd;
gcd=t1%t2;
}
return t2;
}
int main()
{
int n;
int a,b;
while(scanf("%d",&n)!=EOF)
{
while(n--)
{
scanf("%d%d",&a,&b);
printf("%d %d\n",getgcd(a,b),a*b/getgcd(a,b)));
}
}
return 0;
}
排序后求位置处的数
Sort it…
Description
There is a database,partychen want you to sort the database’s data in the order from the least up to the greatest element,then do the query: "Which element is i-th by its value?"- with i being a natural number in a range from 1 to N.

It should be able to process quickly queries like this.

Input
The standard input of the problem consists of two parts. At first, a database is written, and then there's a sequence of queries. The format of database is very simple: in the first line there's a number N (1<=N<=100000), in the next N lines there are numbers of the database one in each line in an arbitrary order. A sequence of queries is written simply as well: in the first line of the sequence a number of queries K (1 <= K <= 100) is written, and in the next K lines there are queries one in each line. The query "Which element is i-th by its value?" is coded by the number i.

Output
The output should consist of K lines. In each line there should be an answer to the corresponding query. The answer to the query "i" is an element from the database, which is i-th by its value (in the order from the least up to the greatest element).

Sample Input
5
7
121
123
7
121
3
3
2
5

Sample Output
121
7
123
#include
#include
using namespace std;
int num[100010];
int pos[105];
int main()
{
int n;
int i;
int k;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%d",&num[i]);
scanf("%d",&k);
for(i=1;i<=k;i++)
scanf("%d",&pos[i]);
sort(num+1,num+1+n);
for(i=1;i<=k;i++)
printf("%d\n",num[pos[i]]);
}
return 0;
}
*路由器连接
Hub Connection plan
Description
Partychen is working as system administrator and is planning to establish a new network in his company. There will be N hubs in the company, they can be connected to each other using cables. Since each worker of the company must have access to the whole network, each hub must be accessible by cables from any other hub (with possibly some intermediate hubs).
Since cables of different types are available and shorter ones are cheaper, it is necessary to make such a plan of hub connection, that the cost is minimal. partychen will provide you all necessary information about possible hub connections. You are to help partychen to find the way to connect hubs so that all above conditions are satisfied.

Input
The first line of the input contains two integer numbers: N - the number of hubs in the network (2 <= N <= 1000) and M - the number of possible hub connections (1 <= M <= 15000). All hubs are numbered from 1 to N. The following M lines contain information about possible connections - the numbers of two hubs, which can be connected and the cable cost required to connect them. cost is a positive integer number that does not exceed 106. There will always be at least one way to connect all hubs.

Output
Output the minimize cost of your hub connection plan.

Sample Input
4 6
1 2 1
1 3 1
1 4 2
2 3 1
3 4 1
2 4 1

Sample Output
3

#include
#include

using namespace std;
struct Edge{
int a,b;
int cost;
}E[15010];

int Tree[1010];
int findRoot(int x)
{
if(Tree[x]==-1)
return x;
else
{
int tmp=findRoot(Tree[x]);
Tree[x]=tmp;
return tmp;
}
}
bool Cmp(Edge a,Edge b)
{
return a.costt ans=0;
for(i=1;i<=m;i++)
{
int a=findRoot(E[i].a);
int b=findRoot(E[i].b);
if(a!=b)
{
Tree[a]=b;
ans+=E[i].cost;
}
}
printf("%d\n",ans);
}
return 0;
}
*编译原理
Principles of Compiler
Description
After learnt the Principles of Compiler,partychen thought that he can solve a simple expression problem.So he give you strings of less than 100 characters which strictly adhere to the following grammar (given in EBNF):
A:= '(' B')'|'x'.
B:=AC.
C:={'+'A}.
Can you solve them too?

Input
The first line of input gives the number of cases, N(1 ≤ N ≤ 100). N test cases follow.
The next N lines will each contain a string as described above.

Output
For each test case,if the expression is adapt to the EBNF above output “Good”,else output “Bad”.

Sample Input
3
(x)
(x+(x+x))
()(x)

Sample Output
Good
Good
Bad

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;
char ex[110];
int index;
bool A();
bool B();
bool C();
bool A()
{
if(ex[index]=='x')
{
index++;
while(ex[index]==' ') index++;
return true;
}
if(ex[index]=='(')
{
index++;
while(ex[index]==' ') index++;
if(B()&&ex[index]==')')
{
index++;
while(ex[index]==' ') index++
return true;
}
}
return false;
}
bool B()
{
return A()&&C();
}
bool C()
{
while(ex[index]=='+')
{
index++;
while(ex[index]==' ') index++;
//return A();
if (!A())
return false;
}
return true;
}
int main()
{
int N;
scanf("%d",&N);
getchar();
while(N--)
{
gets(ex);
index=0;
printf("%s\n",A()&&ex[index]=='\0'?"Good":"Bad");
}
return 0;
}
*分开连接
Separate Connections
Description
Partychen are analyzing a communications network with at most 18 nodes. Character in a matrix i,j (i,j both 0-based,as matrix[i][j]) denotes whether nodes i and j can communicate ('Y' for yes, 'N' for no). Assuming a node cannot communicate with two nodes at once, return the maximum number of nodes that can communicate simultaneously. If node i is communicating with node j then node j is communicating with node i.

Input
The first line of input gives the number of cases, N(1 ≤ N ≤ 100). N test cases follow.
In each test case,the first line is the number of nodes M(1 ≤ M ≤ 18),then there are a grid by M*M describled the matrix.

Output
For each test case , output the maximum number of nodes that can communicate simultaneously

Sample Input
2
5
NYYYY
YNNNN
YNNNN
YNNNN
YNNNN
5
NYYYY
YNNNN
YNNNY
YNNNY
YNYYN

Sample Output
2
4
Hint
The first test case:
All communications must occur with node 0. Since node 0 can only communicate with 1 node at a time, the output value is 2.
The second test case:
In this setup, we can let node 0 communicate with node 1, and node 3 communicate with node 4.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;
#define MAXN 250
#define MAXE MAXN*MAXN*2
#define SET(a,b) memset(a,b,sizeof(a))
deque Q;

bool g[MAXN][MAXN],inque[MAXN],inblossom[MAXN];
int match[MAXN],pre[MAXN],base[MAXN];
int findancestor(int u,int v)
{
bool inpath[MAXN]= {false};
while(1)
{
u=base[u];
inpath[u]=true;
if(match[u]==-1)break;
u=pre[match[u]];
}
while(1)
{
v=base[v];
if(inpath[v])return v;
v=pre[match[v]];
}
}
void reset(int u,int anc)
{
while(u!=anc)
{
int v=match[u];
inblossom[base[u]]=1;
inblossom[base[v]]=1;
v=pre[v];
if(base[v]!=anc)pre[v]=match[u];
u=v;
}
}
void contract(int u,int v,int n)
{
int anc=findancestor(u,v);
SET(inblossom,0);
reset(u,anc);
reset(v,anc);
if(base[u]!=anc)pre[u]=v;
if(base[v]!=anc)pre[v]=u;
for(int i=1; i<=n; i++)
if(inblossom[base[i]])
{
base[i]=anc;
if(!inque[i])
{

Q.push_back(i);
inque[i]=1;
}
}
}
bool dfs(int S,int n)
{
for(int i=0; i<=n; i++)pre[i]=-1,inque[i]=0,base[i]=i;
Q.clear();
Q.push_back(S);
inque[S]=1;
while(!Q.empty())
{
int u=Q.front();
Q.pop_front();
for(int v=1; v<=n; v++)
{
if(g[u][v]&&base[v]!=base[u]&&match[u]!=v)
{
if(v==S||(match[v]!=-1&&pre[match[v]]!=-1))contract(u,v,n);
else if(pre[v]==-1)
{
pre[v]=u;
if(match[v]!=-1)Q.push_back(match[v]),inque[match[v]]=1;
else
{
u=v;
while(u!=-1)
{
v=pre[u];
int w=match[v];
match[u]=v;
match[v]=u;
u=w;
}
return true;
}
}
}
}
}
return false;
}

int solve(int n)
{
SET(match,-1);
int ans=0;
for(int i=1; i<=n; i++)
if(match[i]==-1&&dfs(i,n))
ans++;
return ans;
}

int main()
{
int ans;
int n,m;
char tmp[30];
scanf("%d",&n);
while(n--)
{
ans=0;
memset(g,0,sizeof(g));
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%s",tmp+1);
for(int j=1;j<=m;j++)
{
if(tmp[j]=='Y')
{
g[i][j]=g[j][i]=1;
}
}
}
ans=solve(m)
printf("%d\n",ans*2);
}
return 0;
}
2023机试
ECNU的含义
Welcome to 2023 ACM selective trial
Description
Welcome to 2023 ACM selective trial. ACM is a long way to go, and it's not just a match. So what you need to do for now is do your best! And as members of ACM lab, we are going to teach you something important. Firstly you should be proud that you are a member of ECNU, because 'E' represents "Excellent", 'C' represents "Cheer", 'N' represents "Nice", 'U' represents "Ultimate". Second you should remember Impossible is nothing, because "Impossible" represents "I'm possible". Third for today you should keep ACM, because for you ACM represents "Accept More".
Do you remember them clearly?
Now we will give you a string either "E" ,"C", "N","U","Impossible" or"ACM", you need to tell me what does it means?

Input
The first line of input gives the number of cases N(1 ≤ N ≤ 10). N test cases follow.
Each test consists of a string which will be one of "E" ,"C", "N","U","Impossible" or"ACM".

Output
Tell me what does it means.

Sample Input
3
E
Impossible
ACM

Sample Output
Excellent
I'm possible
Accept More

#include
#inclu