機試算法相關真題

1、2009 機試2計算和的數位2大寫改小寫3素數對4求最大公約數和最小公倍數6排序后求位置處的數7*路由器連接8*編譯原理10*連接132010 機試17ECNU 的含義17空瓶換啤酒18統計字符202010 機試熱身21粽子買三送一，買五送二21工程流水線問題222011 機試24hello world24Special judge26成績282011 機試熱身30貪吃蛇30仰望星空34*編輯距離362012 機試38字母排序38幸運數39十六進制的加法42號碼簿合并排序42*五子棋43*正則表達式匹配452013 機試46斐波那契數列的素數個數46*將 a 字符變成 b 字符最少修改次數47

2、2013 機試熱身49去重排序49蛇形圖案51數學手稿542009 機試計算和的數位Sum of digitDescriptionWrite a program which computes the digit number of sum of two integers a and b.InputThe 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

3、by a space(0<=a,b<=100000000).in a line.OutputFor each test case, print the number of digits of a + b.Sample Input35 71 991000 999Sample Output234#include<stdio.h> int main()int n; int a,b; int sum;while(scanf("%d",&n)!=EOF)while(n-)int an=0; scanf("%d%d",&a,&

4、amp;b); sum=a+b;while(sum)an+;sum/=10;printf("%dn",an+);return 0;大寫改小寫CapitalizeDescriptionWrite a program which replace all the lower-case letters of a given text with the corresponding captital letters.InputA text including lower-case letters, periods, and space.OutputOutput The converte

5、d text.Sample Inpute to eastnormal university.Sample OutputE TO EASTNORMAL UNIVERSITY.#include<stdio.h>#include<string.h> char str1000;int main()int l; while(gets(str)l=strlen(str); int i; for(i=0;i<l;i+)if(stri>='a'&&stri<='z')printf("%c",stri-

6、32); else printf("%c",stri);printf("n");return 0;素數對Primes PairDescriptionWe 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 . . . NN . . . 9 8 7 6 5 4 3 2 1Two numbers faced each other form a pair.

7、Your task is to compute the number of pairs P suchthat both numbers in the pairs are prime.InputThe first line of input gives the number of cases, C (1 Each test case consists of an integer N in one line.C 100). C test cases follow.OutputFor each test case, output P . Sample Input414751Sample Output

8、0226#include<stdio.h>#include<string.h> bool prime10005; void init()int i;int j;prime0=prime1=false;/不是素數prime2=true;/是素數for(i=3;i<=10005;i+=2)primei=true;/是素數primei+1=false;/不是素數 除 0 和 2 之外的偶數都不是素數 for(i=3;i<=10005;i+=2)if(primei=true)/是素數j=i+i; while(j<=10005)primej=false;/不是素

9、數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(primei=true&&primen+1-i=true) sum+;sum*=2; if(n%2=1)/n 為奇數if(primen/2+1=true) sum+=1;printf("%dn",sum);return 0;求最大公約數和最小公

10、倍數and LCMDescriptionWrite a program which computes the greatest common divisor ( multiple (LCM) of given a and b (0 < a, b 44000).) and the least commonInputThe 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 b

11、y a single space in a line.OutputFor each test case, printand LCM separated by a single space in a line.Sample Input28 65000 3000Sample Output2 241000 15000#include<stdio.h>int getint(int a,int b);int t1,t2;t1=a; t2=b;=t1%t2;while(t1=t2; t2=!=0);=t1%t2;return t2;int main()int n; int a,b;while(

12、scanf("%d",&n)!=EOF)while(n-)scanf("%d%d",&a,&b);printf("%d %dn",getreturn 0;(a,b),a*b/(get(a,b);排序后求位置處的數Sort itDescriptionThere is a database,partychen want you to sort the databases data in the order from the least up to the greatest element,then do the q

13、uery: "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.InputThe standard input of the problem consists of two parts. At first, a database is written, and then there's a sequence of queries

14、. 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

15、 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.OutputThe output should consist of K lines. In each line there should be an answer to the correspondingquery. The answer

16、 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 Input5712112371213325Sample Output1217123#include<stdio.h> #include<algorithm> using namespace std; int num100010;int pos105; int main()

17、int n; int i; int k;while(scanf("%d",&n)!=EOF)for(i=1;i<=n;i+) scanf("%d",&numi);scanf("%d",&k); for(i=1;i<=k;i+) scanf("%d",&posi); sort(num+1,num+1+n); for(i=1;i<=k;i+) printf("%dn",numposi);return 0;*路由器連接Hub Connection pl

18、anDescriptionPartychen 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 beaccessibl

19、e 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 c

20、onnections. You are to help partychen to find the way toconnect hubs so that all above conditions are satisfied.InputThe 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 <= 1

21、5000). 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

22、way to connect all hubs.OutputOutput the minimize cost of your hub connection plan.Sample Input4 61 2 112 4 1Sample Output3#include<stdio.h>#include<algorithm>using namespace std;struct Edge int a,b;int cost;E15010;int Tree1010;int findRoot(int x)if(Treex=-1)return x;elseint tmp=findRoot

23、(Treex); Treex=tmp;return tmp;bool Cmp(Edge a,Edge b)return a.cost<b.cost;int main()int n; int m; int i;while(scanf("%d",&n)!=EOF)scanf("%d",&m); for(i=1;i<=m;i+)scanf("%d%d%d",&Ei.a,&Ei.b,&Ei.cost); sort(E+1,E+1+m,Cmp);/排序for(i=1;i<=n;i+)Tr

24、eei=-1; int ans=0;for(i=1;i<=m;i+)int a=findRoot(Ei.a); int b=findRoot(Ei.b); if(a!=b)Treea=b; ans+=Ei.cost;printf("%dn",ans);return 0;*編譯原理Principles of CompilerDescriptionAfter learnt the Principles of Compiler,partychen thought that he can solve a simple expression problem.So he give

25、 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?InputThe first line of input gives the number of cases, N(1 N 100). N test cases follow. The next N lines wi

26、ll each contain a string as described above.OutputFor each test case,if the expression is adapt to the EBNF above output “Good”,else output “Bad”.Sample Input3(x) (x+(x+x)()(x)Sample OutputGood Good Bad#include <cstdio>#include <cstring> #include <cstdlib> #include <vector> #

27、include <cmath> #include <iostream> #include <algorithm> #include <functional> #include <string> #include <map> #include <cctype>using namespace std;char ex110; int index; bool A();bool B();bool C(); bool A()if(exindex='x')index+;while(exindex='

28、') index+; return true;if(exindex='(')index+;while(exindex=' ') index+; if(B()&&exindex=')')index+;while(exindex=' ') index+; return true;return false;bool B()return A()&&C();bool C()while(exindex='+')index+;while(exindex=' ') index

29、+;/return A(); if (!A()return false;return true;int main()int N; scanf("%d",&N); getchar();while(N-)gets(ex); index=0;printf("%sn",A()&&exindex='0'?"Good":"Bad");return 0;*連接Separate ConnectionsDescriptionPartychen are analyzing a communica

30、tions network with at most 18 nodes. Character in a matrix i,j (i,j both 0-based,as matrixij) 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 theumnumber of nodes that can communicate simultaneo

31、usly. If node i is communicating with node jthen node j is communicating with node i.InputThe 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.OutputFor

32、each test case , output theum number of nodes that can communicate simultaneouslySample Input25NYYYY YNNNN YNNNN YNNNN YNNNN 5 NYYYY YNNNN YNNNY YNNNYYNYYNSample Output24HintThe first test case:All communications must occur with node 0. Since node 0 can only communicate with 1 node at a time, the ou

33、tput 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 <cstdio>#include <cstring> #include <cstdlib> #include <vector> #include <cmath> #include <iostream> #include <algorithm&g

34、t; #include <functional> #include <string> #include <map> #include <queue>using namespace std;#define MAXN 250#define MAXE MAXN*MAXN*2 #define SET(a,b) memset(a,b,sizeof(a) deque<int> Q;bool gMAXNMAXN,inqueMAXN,inblossomMAXN;int matchMAXN,preMAXN,baseMAXN; int findances

35、tor(int u,int v)bool inpathMAXN= false; while(1)u=baseu; inpathu=true; if(matchu=-1)break; u=prematchu;while(1)v=basev; if(inpathv)return v; v=prematchv;void reset(int u,int anc)while(u!=anc)int v=matchu; inblossombaseu=1; inblossombasev=1; v=prev;if(basev!=anc)prev=matchu; u=v;void contract(int u,i

36、nt v,int n)int anc=findancestor(u,v); SET(inblossom,0); reset(u,anc);reset(v,anc); if(baseu!=anc)preu=v;if(basev!=anc)prev=u; for(int i=1; i<=n; i+)if(inblossombasei)basei=anc; if(!inquei)Q.push_back(i); inquei=1;bool dfs(int S,int n)for(int i=0; i<=n; i+)prei=-1,inquei=0,basei=i; Q.clear();Q.

37、push_back(S); inqueS=1; while(!Q.empty()int u=Q.front(); Q.pop_front();for(int v=1; v<=n; v+)if(guv&&basev!=baseu&&matchu!=v)if(v=S|(matchv!=-1&&prematchv!=-1)contract(u,v,n); else if(prev=-1)prev=u;if(matchv!=-1)Q.push_back(matchv),inquematchv=1; elseu=v; while(u!=-1)v=pr

38、eu;int w=matchv; matchu=v; matchv=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(matchi=-1&&dfs(i,n)ans+; return ans;int main()int ans; int n,m;char tmp30; scanf("%d",&n);while(n-)ans=0;memset(g,0,sizeof(g);scanf("%d&q

39、uot;,&m); for(int i=1;i<=m;i+)scanf("%s",tmp+1); for(int j=1;j<=m;j+)if(tmpj='Y')gij=gji=1;ans=solve(m); printf("%dn",ans*2);return 0;2010 機試ECNU 的含義e to 2009 ACM selective trialDescriptione to 2009 ACM selective trial. ACM is a long way to go, and it's not

40、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

41、9; 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 r

42、emember them clearly?Now we will give you a string either "E" ,"C", "N","U","Impossible" or"ACM", you need to tell mewhat does it means?InputThe first line of input gives the number of cases, N(1 N 10). N test cases follow. Each test consis

43、ts of a string which will be one of "E" ,"C", "N","U","Impossible" or"ACM".OutputTell me what does it means.Sample Input3EImpossible ACMSample OutputExcellent I'm possibleAccept More#include<stdio.h>#include<string.h>char st

44、r20;int main()int N; scanf("%d",&N); while(N-)scanf("%s",str);if(strcmp(str,"E")=0) printf("Excellentn");else if(strcmp(str,"C")=0) printf("Cheern");else if(strcmp(str,"N")=0) printf("Nicen");else if(strcmp(str,"

45、;U")=0) printf("Ultimaten");else if(strcmp(str,"Impossible")=0) printf("I'm possiblen");else if(strcmp(str,"ACM")=0) printf("Accept Moren");return 0;空瓶換啤酒Soda SurplerDescriptionTim is an absolutely obsessive soda drinker,he simply cannot get

46、 enough. Most annoyingly though, he almost never has any money, so his only obvious legal way to obtain more soda is to take the money he gets when he recycles empty soda bottles to buy new ones. In addition to the empty bottles resulting from his own consumption he sometimes find empty bottles in t

47、he street.One day he was extra thirsty, so he actually drank sodas until he couldn't aford a new one.InputThree non-negative integers e,f, c, where e < 1000 equals the number of empty soda bottles in Tim's possession at the start of the day, f < 1000 the number of empty soda bottles fo

48、und during the day, and 1 < c < 2000 the number of empty bottles required to buy a new soda.OutputHow many sodas did Tim drink on his extra thirsty day?Sample Input9 0 35 5 2Sample Output49#include<stdio.h>#include<string.h> int main()int e,f,c; int t;int sum;int full,empty; while(

49、scanf("%d%d%d",&e,&f,&c)!=EOF)sum=0;empty=e+f;/空瓶數量while(empty>=c)/空瓶數量可換sum+=empty/c;/換的滿瓶empty=empty/c+empty%c;/新的空瓶數量printf("%dn",sum);return 0;統計字符統計字符Description輸入一行字符，分別統計其中 英文字母、空格、數字和其他字符的個數。Input輸入一個整數 t，表示有幾組數據接下來有 t 行，每行字符不超過 10000 個Hint 可能有空格之類的字符Output

50、對于每行字符輸出其中1 英文字母（大小寫都算）的個數2 數字的個數3 其他字符的個數Sample Input2q2 e2qweqrwwerr232424fwetetg=2342gdsg3.,/-=321Sample Outputcharacter:2 number:2 others:1 character:21 number:14 others:9 #include<stdio.h> #include<string.h> char str10010; int main()int t; int i;intn,on;scanf("%d",&t);

51、getchar();/清除上一個換行符while(t-)gets(str);int l=strlen(str);n=on=0; for(i=0;i<l;i+)if(stri>='0'&&stri<='9') nn+;else if(stri>='A'&&stri<='Z'|stri>='a'&&stri<='z') cn+;else on+;printf("character:%dn",cn

52、); printf("number:%dn",nn); printf("others:%dn",on);return 0;2010 機試熱身粽子買三送一，買五送二端午節(jié)Description今天是端午節(jié)，ECNU 決定請大家吃粽子。恰好，今天超市為了迎合"端午節(jié)"，推出了"端午大酬賓"，即促銷活動。嚴格的買三送一，買五送二。ECNU 想用現有的錢，買最多的粽子，但是他自己又算，所以希望你能幫幫他。Input輸入第一行為一個數 N(1<=N<=100),表示測試數據的組數。每組測試數據有兩個整數，A,B

53、(0<=A<=1000,0<B<10)表示 ECNU 有 A 元錢,每個粽子價格為 B元錢,超市推出了買 5 個送 2 個,和買 3 個送 1 個的活動。Output輸出 ECNU 最多能買到的粽子數量。Sample Input210 322 3Sample Output49Hint:有兩組測試數據:對于第一組測試數據:有 10 元錢,粽子 3 元一個,可以買 3 個,但是買 3 送 1,所以最后有 4 個。對于第二組測試數據:有 22 元錢,粽子 3 元一個,可以買 7 個,但是買 5 送 2,所以最后有 9 個。#include<stdio.h>#inc

54、lude<string.h> int main()int n; int a,b; int zn;int num; scanf("%d",&n); while(n-)scanf("%d%d",&a,&b);/輸入錢數和粽子單價zn=a/b;/買了 zn 個num=zn;if(zn/5!=0)num+=zn/5*2; zn=zn%5;if(zn/3!=0)num+=zn/3;printf("%dn",num);return 0;工程流水線問題工程DescriptionCastor 在 ECNU 工廠工作

55、?？倧S有一條生產線，現在生產流水線上排隊的零件總數為 M。當前 Castor 開始加工第一個零件。流水線上的零件總是按順序加工的。例如零件 i 必須是在零件 i+1 之前加工.現在 Castor 只需要再加工 K(K<=M)個零件就能休息了，Castor 想知道他還要工作多長時間才能休息.Input第一行為一個整數 T,表示測數數據的組數.對每組測試數據第一行有兩個整數 M,K(1<=K<=M<=1000)然后一行有 M 個數ti(1<=ti<=10000)Outputi 個數字表示零件隊列的第 i 個零件需要加工的時間為每組數據輸出一行,每行只有一個整數表

56、示 Castor 還需要工作多長時間Sample Input23 25 2 33 11 2 3Sample Output71#include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> int main()int T; int M,K; int i;int t1005; int sum;scanf("%d",&T); while(T-)sum=0; scanf("%d%d",&M,&K); f

57、or(i=0;i<M;i+)scanf("%d",&ti); for(i=0;i<K;i+)sum+=ti;printf("%dn",sum);return 0;2011 機試hello worldHello World!Description當開始學習程序語言，第一個程序肯定是在屏幕上輸出一些字符，比如輸出”Hello World!”。遇到輸出的句子過長時，輸出的句子由于換行將被屏幕截斷。現在給你一些文本，文本的文法如下：TEXT(文本):= SENTENCE | SENTENCE SPACE TEXT SENTENCE(句子):=

58、 WORD SPACE SENTENCE | WORD END END(結束符):= '.', '?', '!'WORD(單詞):= LETTER | LETTER WORD LETTER(字母):= 'a'.'z', 'A'.'Z'SPACE(空格):= ' '你的任務是把滿足上述文法的文本分割成多行（每行文本的長度都不超過n）。并且滿足如下條件：一、 輸出的句子不能被截斷。如：”Hi! 被截斷，即不合法。二、 文本分割后保證行數最小。如：”Hi!度要求在n=20的情況下，可以分割為：”Hi!”“e to ECNU.”若被分割成”Hi!e”則認為e to ECNU. Have a nice day!”在每行文本長e to ECNU.”“Have a nice day!”,也可以被分割為：”Hi!e to ECNU.”Have a nice day!”此時認為