7-1 银行业务队列简单模拟分数 25作者 DS课程组单位 浙江大学设某银行有A、B两个业务窗口且处理业务的速度不一样其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处理完2个顾客时B窗口处理完1个顾客。给定到达银行的顾客序列请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔并且当不同窗口同时处理完2个顾客时A窗口顾客优先输出。输入格式:输入为一行正整数其中第1个数字N(≤1000)为顾客总数后面跟着N位顾客的编号。编号为奇数的顾客需要到A窗口办理业务为偶数的顾客则去B窗口。数字间以空格分隔。输出格式:按业务处理完成的顺序输出顾客的编号。数字间以空格分隔但最后一个编号后不能有多余的空格。输入样例:8 2 1 3 9 4 11 13 15输出样例:1 3 2 9 11 4 13 15参考代码#includebits/stdc.h using namespace std; int main(){ int n; cinn; vectorint a,b; int num; for(int i0;in;i){ cinnum; if(num%20){ b.push_back(num); }else a.push_back(num); } vectorintre; while(!a.empty()||!b.empty()){ if(a.size()2){ re.push_back(a[0]); re.push_back(a[1]); a.erase(a.begin()); a.erase(a.begin()); }else if(!a.empty()){ re.push_back(a[0]); a.erase(a.begin()); } if(!b.empty()){ re.push_back(b[0]); b.erase(b.begin()); } } for(int i0;ire.size();i){ coutre[i]; if(i!re.size()-1) cout ; } }7-2 表达式转换分数 25作者 DS课程组单位 浙江大学算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。输入格式:输入在一行中给出不含空格的中缀表达式可包含、-、*、/以及左右括号()表达式不超过20个字符。输出格式:在一行中输出转换后的后缀表达式要求不同对象运算数、运算符号之间以空格分隔但结尾不得有多余空格。输入样例:23*(7-4)8/4输出样例:2 3 7 4 - * 8 4 / 参考代码#includestdio.h #includestring.h int main(){ char he[100]; int top-1; int pr[100]; pr[]1;pr[-]1; pr[*]2;pr[/]2; pr[(]3;pr[)]3; char str[20]; scanf(%s,str); int lenstrlen(str); int flag0; for(int i0;ilen;i){ if(((!i||str[i-1]()(str[i]||str[i]-)) ||(str[i]0str[i]9) ||str[i].){ if(flag) printf( ); if(str[i]!) printf(%c,str[i]); while(str[i1].||(str[i1]0str[i1]9)){ i; printf(%c,str[i]); } flag1; }else{ if(str[i])){ while(top!-1he[top]!(){ printf( %c,he[top--]); } top--; }else if(top-1||pr[str[i]]pr[he[top]]){ he[top]str[i]; }else{ while(top!-1he[top]!(){ printf( %c,he[top--]); } he[top]str[i]; } } } while(top!-1){ printf( %c,he[top--]); } return 0; }7-3 堆栈模拟队列分数 25作者 DS课程组单位 浙江大学设已知有两个堆栈S1和S2请用这两个堆栈模拟出一个队列Q。所谓用堆栈模拟队列实际上就是通过调用堆栈的下列操作函数:int IsFull(Stack S)判断堆栈S是否已满返回1或0int IsEmpty (Stack S )判断堆栈S是否为空返回1或0void Push(Stack S, ElementType item )将元素item压入堆栈SElementType Pop(Stack S )删除并返回S的栈顶元素。实现队列的操作即入队void AddQ(ElementType item)和出队ElementType DeleteQ()。输入格式:输入首先给出两个正整数N1和N2表示堆栈S1和S2的最大容量。随后给出一系列的队列操作A item表示将item入列这里假设item为整型数字D表示出队操作T表示输入结束。输出格式:对输入中的每个D操作输出相应出队的数字或者错误信息ERROR:Empty。如果入队操作无法执行也需要输出ERROR:Full。每个输出占1行。输入样例:3 2 A 1 A 2 A 3 A 4 A 5 D A 6 D A 7 D A 8 D D D D T输出样例:ERROR:Full 1 ERROR:Full 2 3 4 7 8 ERROR:Empty参考代码#includebits/stdc.h using namespace std; stack inta,b; int main(){ int n,m; cinnm; if(nm) swap(n,m); while(1){ char t; int k; cint; if(tT) break; if(tA){ cink; if(a.size()n){ a.push(k); }else if(b.empty()){ while(!a.empty()){ b.push(a.top()); a.pop(); } a.push(k); }else coutERROR:Fullendl; }else if(tD){ if(!b.empty()){ coutb.top()endl; b.pop(); }else if(!a.empty()){ while(!a.empty()){ b.push(a.top()); a.pop(); } coutb.top()endl; b.pop(); }else coutERROR:Emptyendl; } } }7-4 输出全排列分数 20作者 DS课程组单位 浙江大学请编写程序输出前n个正整数的全排列n10并通过9个测试用例即n从1到9观察n逐步增大时程序的运行时间。输入格式:输入给出正整数n10。输出格式:输出1到n的全排列。每种排列占一行数字间无空格。排列的输出顺序为字典序即序列a1,a2,⋯,an排在序列b1,b2,⋯,bn之前如果存在k使得a1b1,⋯,akbk 并且 ak1bk1。输入样例3输出样例123 132 213 231 312 321参考代码#includebits/stdc.h using namespace std; int main(){ int n; cinn; string str; for(int i0;in;i){ stri10; } sort(str.begin(),str.end()); do{ coutstrendl; }while(next_permutation(str.begin(),str.end())); }7-5 出栈序列的合法性分数 25作者 陈越单位 浙江大学给定一个最大容量为 m 的堆栈将 n 个数字按 1, 2, 3, ..., n 的顺序入栈允许按任何顺序出栈则哪些数字序列是不可能得到的例如给定 m5、n7则我们有可能得到{ 1, 2, 3, 4, 5, 6, 7 }但不可能得到{ 3, 2, 1, 7, 5, 6, 4 }。输入格式输入第一行给出 3 个不超过 1000 的正整数m堆栈最大容量、n入栈元素个数、k待检查的出栈序列个数。最后 k 行每行给出 n 个数字的出栈序列。所有同行数字以空格间隔。输出格式对每一行出栈序列如果其的确是有可能得到的合法序列就在一行中输出YES否则输出NO。输入样例5 7 5 1 2 3 4 5 6 7 3 2 1 7 5 6 4 7 6 5 4 3 2 1 5 6 4 3 7 2 1 1 7 6 5 4 3 2输出样例YES NO NO YES NO参考代码#includebits/stdc.h using namespace std; int main(){ int m,n,k; cinmnk; while(k--){ queueint q; stackint sta; int flag0; for(int i0;in;i){ int num; cinnum; q.push(num); } for(int i1;in;i){ sta.push(i); while(!sta.empty()q.front()sta.top()){ sta.pop(); q.pop(); } if(sta.size()m) flag1; } if(!q.empty()){ flag1; } if(flag) coutNOendl; else coutYESendl; } }7-6 括号匹配分数 18作者 周强单位 青岛大学检查一段C语言代码的小括号( )、 中括号[ ]和大括号{ }是否匹配。输入格式:在一行中输入一段C语言代码长度不超过1000个字符行末以换行符结束。输出格式:第一行输出左括号的数量和右括号的数量中间以一个空格间隔。若括号是匹配的在第二行打印YES否则打印NO。输入样例1:for(int i0; iv; i){ visited[i] 0; for(int j0; jv; j) scanf(%d,(g-Adj[i][j])); }输出样例1:8 8 YES输入样例2:for(int i0; iv; i) a(i]0;输出样例2:2 2 NO参考代码#includestdio.h #includestring.h int main(){ char s[1001]; fgets(s,1001,stdin); int lenstrlen(s); int lp0,rp0; int lb0,rb0; int lB0,rB0; for(int i0;ilen;i){ switch(s[i]){ case (:lp;break; case ):rp;break; case [:lb;break; case ]:rb;break; case {:lB;break; case }:rB;break; default:break; } } int tllplblB; int trrprbrB; printf(%d %d\n,tl,tr); char stack[1001]; int top-1; int march1; for(int i0;ilen;i){ char cs[i]; if(c(||c[||c{){ stack[top]c; }else if(c)||c]||c}){ if(top-1){ march0; break; } char top_charstack[top--]; if((c)top_char!()|| (c]top_char![)|| (c}top_char!{)){ march0; break; } } } if(top!-1){ march0; } printf(%s\n,march?YES:NO); }7-7 后缀式求值分数 25作者 周强单位 青岛大学我们人类习惯于书写“中缀式”如3 5 * 2其值为13。 (p.s. 为什么人类习惯中缀式呢是因为中缀式比后缀式好用么而计算机更加习惯“后缀式”也叫“逆波兰式”Reverse Polish Notation。上述中缀式对应的后缀式是3 5 2 * 现在请对输入的后缀式进行求值。输入格式:在一行中输入一个后缀式运算数和运算符之间用空格分隔运算数长度不超过6位运算符仅有 - * /四种。输出格式:在一行中输出后缀式的值保留一位小数。输入样例:3 5.4 2.2 * 输出样例:14.9参考代码#include bits/stdc.h using namespace std; string s; double n1, n2; stackdouble stk; int main() { getline(cin, s); int n s.size(); for(int i 0; i n; i ) { if(s[i] ) continue; else if ((s[i] || s[i] - || s[i] * || s[i] /) (i n - 1 || s[i 1] )) { n1 stk.top(); stk.pop(); n2 stk.top(); stk.pop(); if(s[i] ) stk.push(n1 n2); else if (s[i] -) stk.push(n2 - n1); else if (s[i] *) stk.push(n1 * n2); else stk.push(n2 / n1); } else { string t ; while(s[i] ! ) { t s[i]; i ; } n1 stof(t); stk.push(n1); } } printf(%.1f, stk.top()); }7-8 进制转换分数 10作者 sy单位 宁波财经学院输入十进制整数N和待转换的进制x2、8、16分别代表十进制N转换成二进制、八进制和十六进制输出对应的结果。十六进制中A~F用大写字母表示。输入格式:输入两个整数N十进制整数N和xx进制中间用空格隔开。输出格式:输出对应的结果。输入样例:在这里给出一组输入。例如123 2输出样例:在这里给出相应的输出。例如1111011输入样例:在这里给出一组输入。例如123 16输出样例:在这里给出相应的输出。例如7B参考代码#includebits/stdc.h using namespace std; int main(){ int n,m; cinnm; stackint sta; if(m2){ while(n){ sta.push(n%2); n/2; } while(!sta.empty()){ coutsta.top(); sta.pop(); } }else if(m8) printf(%o,n); else printf(%X,n); }7-9 行编辑器分数 10作者 夏仁强单位 贵州工程应用技术学院一个简单的行编辑程序的功能是接受用户从终端输入的程序或数据并存入用户的数据区。由于用户在终端上进行输入时不能保证不出差错因此若在编辑程序中“每接受一个字符即存入用户数据区”的做法显然不是最恰当的。较好的做法是设立一个输入缓冲区用以接受用户输入的一行字符然后逐行存入用户数据区。允许用户输入出差错并在发现有误时可以及时更正。例如当用户发现刚刚键入的一个字符是错的时可补进一个退格符#以表示前一个字符无效如果发现当前键入的行内差错较多或难以补救则可以键入一个退行符以表示当前行中的字符均无效。如果已经在行首继续输入#符号无效。输入格式:输入一个多行的字符序列。但行字符总数包含退格符和退行符不大于250。输出格式:按照上述说明得到的输出。输入样例1:在这里给出一组输入。例如whli##ilr#e(s#*s)输出样例1:在这里给出相应的输出。例如while(*s)输入样例2:在这里给出一组输入。例如outchaputchar(*s#);输出样例2:在这里给出相应的输出。例如putchar(*s);参考代码#includebits/stdc.h using namespace std; int main(){ string s; while(getline(cin,s)){ string ss; int k0; for(int i0;is.size();i){ if(i0s[i]#) continue; else if(s[i]#) k--; else if(s[i]) k0; else ss[k]s[i]; } for(int i0;ik;i){ coutss[i]; } coutendl; } }7-10 选数分数 20作者 lg单位 成都锦城学院已知n个整数x1,x2,x3...xi以及1个整数k(kn)。从 n 个整数中任选 k个整数相加可分别得到一系列的和。例如当 n4k34个整数分别为3,7,12,19 时可得全部的组合与它们的和为37122237192971219383121934现在要求你计算出和为素数共有多少种。例如上例只有一种的和为素数371929输入格式:第一行两个空格隔开的整数 n,k1≤n≤20kn第二行n个整数两数之间空格隔开1≤xi≤1000000输出格式:输出一个整数表示种类数。输入样例:在这里给出一组输入。例如4 3 3 7 12 19输出样例:在这里给出相应的输出。例如1参考代码#include bits/stdc.h using namespace std; int a[M], b[M], c[N], p[N]; int n, m, d, ans; int prime(int n) { if(n 0 || n 1) return 0; for(int i 2; i n / i; i ) if(n % i 0) return 0; return 1; } void dfs(int x, int y) { if(x m) { if(c[d] 0) { c[d] 1; p[d] prime(d); } if(p[d]) ans ; return; } for(int i y; i n; i ) { if(b[i] 0) { b[i] 1; d a[i]; dfs(x 1, i 1); b[i] 0; d - a[i]; } } } int main() { cin n m; for(int i 1; i n; i ) cin a[i]; sort(a 1, a n 1); dfs(0, 1); cout ans; }7-11 猴子选大王分数 20作者 黄正鹏单位 贵州工程应用技术学院由M只猴子围成一圈从1到M进行编号打算从中选出一个大王经过协商决定选出大王的规则从第一个开始循环报数数到K的猴子出圈下一个猴子从1开始报数如此循环下去最后剩下的一只猴子选为猴王。输入格式:输入一行中给两个正整数m,k。输出格式:输出当选猴王的编号。输入样例:在这里给出一组输入。例如3 2输出样例:在这里给出相应的输出。例如3参考代码#includestdio.h int main(){ int m,k; scanf(%d %d,m,k); int king0; for(int i2;im;i){ king(kingk)%i; } printf(%d,king1); }
