3.26复试练习

OJ丑数问题描述对于一给定的素数集合 S {p1, p2, ..., pK}, 来考虑那些质因数全部属于S 的数的集合。这个集合包括p1, p1p2即p1乘以p2, p1p3, 和 p1p2p3 (还有其它很多)。这是个对于一个集合S的丑数集合。注意我们不认为1 是一个丑数。你的工作是对于输入的集合S去寻找集合中的第N个丑数。说明结果不超过32位整数能表示的范围比如S{2, 3, 5, 7}则前15个丑数为2,3,4,5,6,7,8,9,10,12,14,15,16,18,20输入说明第 1 行: 2个被空格分开的整数:K 和 N 1 K100 1 N100,000.第 2 行: K 个被空格分开的整数即集合S的元素输出说明单独的一行即第N个丑数。输入范例4 152 3 5 7输出范例20代码--set自动排序和去重盒子里放着所有已知的丑数从小到大每次从盒子里拿出最小的丑数用这个丑数繁殖出新的丑数乘以每个素数把新生的丑数放回盒子重复这个过程拿出来的顺序就是从小到大的丑数序列#includebits/stdc.h using namespace std; int main() { int k, n; cin k n; long long a[100]; long long b; setlong long st; for (int i 0; i k; i) { cin a[i]; st.insert(a[i]); } for (int i 1; i n; i) { b *st.begin(); st.erase(st.begin()); for (int j 0; j k; j) { st.insert(a[j] * b); } } b *st.begin(); cout b endl; return 0; }笨小猴问题描述笨小猴的词汇量很小所以每次做英语选择题的时候都很头疼。但是他找到了一种方法经试验证明用这种方法去选择选项的时候选对的几率非常大这种方法的具体描述如下假设maxn是单词中出现次数最多的字母的出现次数minn是单词中出现次数最少的字母的出现次数如果maxn-minn是一个质数那么笨小猴就认为这是个Lucky Word这样的单词很可能就是正确的答案。样例输入error样例输出Lucky Word2样例说明单词error中出现最多的字母r出现了3次出现次数最少的字母出现了1次3-122是质数。样例输入olympic样例输出No Answer0样例说明单词olympic中所有字母都只出现了1次1-100不是质数。输入说明输入文件只有一行是一个单词其中只可能出现小写字母并且长度小于100。输出说明输出文件共两行第一行是一个字符串假设输入的的单词是Lucky Word那么输出“Lucky Word”否则输出“No Answer”第二行是一个整数如果输入单词是Lucky Word输出maxn-minn的值否则输出0。输入范例error输出范例Lucky Word2代码#includebits/stdc.h using namespace std; bool is_prime(int n) { if(n2) return false; if(n2) return true; if(n%20) return false; for(int i3;isqrt(n);i) { if(n%i0) return false; } return true; } int main() { string s; cins; int maxnINT_MIN,minnINT_MAX; int count[26]{0}; for(int i0;is.length();i) count[s[i]-a]; for(int i0;i26;i) { if(count[i]0) { if(count[i]minn) minncount[i]; if(count[i]maxn) maxncount[i]; } } int diffmaxn-minn; if(is_prime(diff)) { coutLucky Wordendl; coutdiffendl; } else { coutNo Answerendl; cout0endl; } return 0; }字串统计问题描述给定一个长度为n的字符串S还有一个数字L统计长度大于等于L的出现次数最多的子串不同的出现可以相交如果有多个输出最长的如果仍然有多个输出第一次出现最早的。输入说明第一行一个数字L。第二行是字符串S。L大于0且不超过S的长度。n60S中所有字符都是小写英文字母。输出说明一行题目要求的字符串。输入样例14bbaabbaaaaa输出样例1bbaa输入样例22bbaabbaaaaa输出样例2aa输入范例4bbaabbaaaaa输出范例bbaa代码#includebits/stdc.h using namespace std; int main() { int L; string s; cin L; cin s; string res ; int maxcount 0; // 全局最大出现次数 // 遍历所有可能的子串长度 L for(int i 0; i s.length() - L; i) // 起始位置 { for(int len L; len s.length() - i; len) // 子串长度 { string temp s.substr(i, len); int count 0; // 统计temp在s中出现的次数 for(int j 0; j s.length() - len; j) { if(temp s.substr(j, len)) { count; } } // 更新结果 if(count maxcount) { maxcount count; res temp; } else if(count maxcount maxcount 0) { // 出现次数相同选择更长的 if(temp.length() res.length()) { res temp; } // 长度也相同选择第一次出现最早的默认就是因为按顺序遍历 } } } cout res endl; return 0; }Anagrams问题问题描述Anagrams指的是具有如下特性的两个单词在这两个单词当中每一个英文字母不区分大小写所出现的次数都是相同的。例如“Unclear”和“Nuclear”、“Rimon”和“MinOR”都是Anagrams。编写一个程序输入两个单词然后判断一下这两个单词是否是Anagrams。每一个单词的长度不会超过80个字符而且是大小写无关的。输入说明输入有两行分别为两个单词。输出说明输出只有一个字母Y或N分别表示Yes和No。输入范例aabbccccbbaa输出范例Y代码#includebits/stdc.h using namespace std; int main() { string s1,s2; cins1s2; if(s1.length()!s2.length()) coutNendl; int lens1.length(); for(int i0;ilen;i) { if(s1[i]As1[i]Z) s1[i]s1[i]-Aa; } for(int i0;ilen;i) { if(s2[i]As2[i]Z) s2[i]s2[i]-Aa; } sort(s1.begin(),s1.end()); sort(s2.begin(),s2.end()); if(s1s2) coutYendl; else coutNendl; return 0; }身份证号码升级问题描述从1999年10月1日开始公民身份证号码由15位数字增至18位。(18位身份证号码简介)。升级方法为1、把15位身份证号码中的年份由2位(7,8位)改为四位。2、最后添加一位验证码。验证码的计算方案将前 17 位分别乘以对应系数 (7 9 10 5 8 4 2 1 6 3 7 9 10 5 8 4 2) 并相加然后除以 11 取余数0-10 分别对应 1 0 x 9 8 7 6 5 4 3 2。请编写一个程序用户输入15位身份证号码程序生成18位身份证号码。假设所有要升级的身份证的四位年份都是19××年输入说明一个15位的数字串作为身份证号码不用判断输入的15位字符串是否合理输出说明一个18位的字符串作为升级后的身份证号码输入范例110105491231002输出范例11010519491231002x代码--未AC#includebits/stdc.h using namespace std; int main() { string s; cin s; string s2 s.substr(0, 6) 19 s.substr(6, 9); int weights[17] {7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2}; char check[] {1, 0, X, 9, 8, 7, 6, 5, 4, 3, 2}; int sum 0; for(int i 0; i 17; i) { int digit s2[i] - 0; sum digit * weights[i]; } int remainder sum % 11; char verifyCode check[remainder]; s2 verifyCode; cout s2 endl; return 0; }彩票问题描述为丰富男生节活动女生设置彩票抽奖环节规则如下1、每张彩票上印有7个各不相同的号码且这些号码的取值范围为[1, 33]2、每次在兑奖前都会公布一个由七个互不相同的号码构成的中奖号码3、共设置7个奖项特等奖和一等奖至六等奖。兑奖规则如下特等奖要求彩票上的7个号码都出现在中奖号码中一等奖要求彩票上的6个号码出现在中奖号码中二等奖要求彩票上的5个号码出现在中奖号码中……六等奖要求彩票上的1个号码出现在中奖号码中注不考虑号码出现的顺序例如若中奖号码为23 31 1 14 19 17 18则彩票12 8 9 23 1 16 7由于其中有两个号码23和1出现在中奖号码中所以该彩票中了五等奖。现已知中奖号码和李华买的若干彩票的号码请你写一个程序判断他的彩票中奖情况。输入说明第一行一个正整数n表示彩票数量第二行7个整数表示中奖号码下面n行每行7个整数描述n张彩票。n100000输出说明7个数字第1个数字表示特等奖的中奖张数第2个数字表示一等奖的中奖张数第3个数字表示二等奖的中奖张数……第7个数字表示六等奖的中奖张数。每个数字后都跟一个空格。输入范例31 2 3 4 5 6 711 12 13 14 15 16 1712 13 14 15 16 17 188 7 10 9 31 30 29输出范例0 0 0 0 0 0 1代码#includebits/stdc.h using namespace std; int main() { int n; cin n; int winning[7]; for(int i 0; i 7; i) { cin winning[i]; } setint winSet(winning, winning 7); // index0-6分别对应特等奖到六等奖 int awards[7] {0}; // 处理每张彩票 for(int i 0; i n; i) { int matchCount 0; // 读取一张彩票的7个号码 for(int j 0; j 7; j) { int num; cin num; // 如果这个号码在中奖号码中匹配数1 if(winSet.find(num) ! winSet.end()) { matchCount; } } if(matchCount 1) { awards[7 - matchCount]; } } for(int i 0; i 7; i) { cout awards[i] ; } return 0; }质数的后代问题描述如果一个合数由两个质数相乘而得那么我们就叫它是质数们的直接后代。现在给你一系列自然数判断它们是否是质数的直接后代。输入说明第一行一个正整数T表示需要判断的自然数数量接下来T行每行一个要判断的自然数1T202要判断的自然数105输出说明共T行依次对于输入中给出的自然数判断是否为质数的直接后代是则输出Yes否则输出No输入范例434612输出范例NoYesYesNo代码#includebits/stdc.h using namespace std; bool is_prime(int n) { if(n2) return false; if(n2) return true; if(n%20) return false; for(int i3;isqrt(n);i) { if(n%i0) return false; } return true; } int main() { int N; cinN; while(N--) { int num; cinnum; bool foundfalse; for(int i2;inum;i) { if(num%i0) { int jnum/i; if(is_prime(i)is_prime(j)) { foundtrue; break; } } } if(found) coutYesendl; else coutNoendl; } return 0; }高精度乘法问题描述在C/C语言中整型所能表示的范围一般为-231到231大约21亿,即使long long型一般也只能表示到-263到263。要想计算更加规模的数就要用软件来扩展了比如用数组或字符串来模拟更多规模的数及共运算。现在输入两个整数请输出它们的乘积。输入说明两行每行一个正整数每个整数不超过10000位输出说明一行两个整数的乘积。输入范例10000234输出范例2340000代码#includebits/stdc.h using namespace std; int main() { string s1, s2; cin s1 s2; if(s1 0 || s2 0) { cout 0 endl; return 0; } int len1 s1.length(); int len2 s2.length(); int a[10005] {0}, b[10005] {0}; for(int i 0; i len1; i) { a[i] s1[len1 - 1 - i] - 0; } for(int i 0; i len2; i) { b[i] s2[len2 - 1 - i] - 0; } int c[20005] {0}; // 模拟竖式乘法 for(int i 0; i len1; i) { for(int j 0; j len2; j) { c[i j] a[i] * b[j]; // 累加乘积 // 处理进位 c[i j 1] c[i j] / 10; c[i j] % 10; } } // 确定结果长度 int len len1 len2; while(len 1 c[len - 1] 0) { len--; } // 逆序输出 for(int i len - 1; i 0; i--) { cout c[i]; } cout endl; return 0; }阶乘末尾问题描述给定n和len输出n!末尾len位。输入说明一行两个正整数n和len。n30, len10。输出说明一行一个字符串表示答案。长度不足用前置零补全。输入范例6 5输出范例00720代码#includebits/stdc.h using namespace std; int main() { int n,len; cinnlen; //10^len long long mod1; for(int i0;ilen;i) mod*10; long long result1; for(int i2;in;i) { result(result*i)%mod;//防止溢出 } coutsetw(len)setfill(0)resultendl; return 0; }寂寞的数问题描述道德经曰一生二二生三三生万物。对于任意正整数n我们定义d(n)的值为为n加上组成n的各个数字的和。例如d(23)232328, d(1481)148114811495。因此给定了任意一个n作为起点你可以构造如下一个递增序列n,d(n),d(d(n)),d(d(d(n)))....例如从33开始的递增序列为33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...我们把n叫做d(n)的生成元在上面的数列中33是39的生成元39是51的生成元等等。有一些数字甚至可以有两个生成元比如101可以由91和100生成。但也有一些数字没有任何生成元如42。我们把这样的数字称为寂寞的数字。输入说明一行一个正整数n。n10000输出说明按照升序输出小于n的所有寂寞的数字每行一个。输入范例40输出范例135792031代码--生成数一定大于生成元遍历无需考虑大于n的情况#includebits/stdc.h using namespace std; int d(int n) { int sumn; while(n0) { sumn%10; n/10; } return sum; } int main() { int n; cinn; bool hasgenerator[10005]{false}; for(int i1;in;i) { int generatedd(i); if(generatedn) hasgenerator[generated]true; } for(int i1;in;i) { if(!hasgenerator[i]) coutiendl; } return 0; }数列问题描述给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列例如当k3时这个序列是1349101213…该序列实际上就是303130313230323132303132…请你求出这个序列的第N项的值用10进制数表示。例如对于k3N100正确答案应该是981。输入说明只有1行为2个正整数用一个空格隔开k Nk、N的含义与上述的问题描述一致且3≤k≤1510≤N≤1000。输出说明计算结果是一个正整数在所有的测试数据中结果均不超过2.1*109。整数前不要有空格和其他符号。输入范例3 100输出范例981代码#include bits/stdc.h using namespace std; int main() { int k, n; cin k n; long long ans 0; long long power 1; // k^i //10101 while (n 0) { if (n 1) { // 当前二进制位为 1 ans power; } power * k; // 更新为 k^(i1) n 1; // n 右移一位 } cout ans endl; return 0; }孪生素数问题描述孪生素数就是指相差2的素数对例如3和55和711和13…。这个猜想正式由希尔伯特在1900年国际数学家大会的报告上第8个问题中提出可以这样描述存在无穷多个素数p使得p 2是素数。素数对p, p 2称为孪生素数。现在给定任何正整数 N ( 10 ^ 5), 请你计算不大于 N 的孪生素数的对数。输入说明你的程序必须从标准输入中读取测试用例。输入文件由几组测试用例组成。每组测试用例占一行, 其中包含一个整数 N。当输入的 N为负数表示结束输入。输出说明对于每组测试数据输出一行包括一个整数表示不大于 N 的孪生素数的对数输入范例5713815-16输出范例12323代码#includebits/stdc.h using namespace std; bool is_prime(int n) { if(n2) return false; if(n2) return true; if(n%20) return false; for(int i3;isqrt(n);i) { if(n%i0) return false; } return true; } int main() { int N; while(cinN) { if(N0) return 0; int count0; for(int p3;p2N;p) { if(is_prime(p)is_prime(p2)) count; } coutcountendl; } return 0; }区间k大数查询问题描述给定一个序列每次询问序列中第l个数到第r个数中第K大的数是哪个。注意由于存在相等的元素因此第2大的数可能和第1大的数相等。输入说明第一行包含一个数n表示序列长度。第二行包含n个正整数表示给定的序列。第三个包含一个正整数m表示询问个数。接下来m行每行三个数l,r,K表示询问序列从左往右第l个数到第r个数中从大往小第K大的数是哪个。序列元素从1开始标号。n,m1000保证k(r-l1)序列中的数106。输出说明总共输出m行每行一个数表示询问的答案。输入范例51 5 3 4 521 5 22 3 2输出范例53代码#includebits/stdc.h using namespace std; bool cmp(int a,int b) { return ab; } int main() { int n; cinn; int a[n]; for(int i0;in;i) cina[i]; int m; cinm; int l,r,k; while(m--) { cinlrk; vectorint arr; for(int il-1;ir-1;i) arr.push_back(a[i]); sort(arr.begin(),arr.end(),cmp); coutarr[k-1]endl; } return 0; }数的统计问题描述在一个有限的正整数序列中有些数会多次重复出现在这个序列中。如序列3121512。其中1就出现3次2出现2次3出现1 次5出现1次。你的任务是对于给定的正整数序列从小到大依次输出序列中出现的数及出现的次数。输入说明第一行正整数n表示给定序列中正整数的个数。第二行是n 个用空格隔开的正整数x代表给定的序列。n10000x1000,000。输出说明若干行每行两个用一个空格隔开的数第一个是数列中出现的数第二个是该数在序列中出现的次数。输入范例128 2 8 2 2 11 1 1 8 1 13 13输出范例1 32 38 311 113 2代码#includebits/stdc.h using namespace std; int a[1000005]{0}; int main() { int n; cinn; int max0; for(int i0;in;i) { int b; cinb; a[b]; if(bmax) maxb; } for(int i0;imax;i) { if(a[i]!0) couti a[i]endl; } return 0; }数字黑洞问题描述任意一个四位数只要它们各个位上的数字是不全相同的就有这样的规律1)将组成该四位数的四个数字由大到小排列形成由这四个数字构成的最大的四位数2)将组成该四位数的四个数字由小到大排列形成由这四个数字构成的最小的四位数(如果四个数中含有0则得到的数不足四位)3)求两个数的差得到一个新的四位数(高位零保留)。重复以上过程最后一定会得到的结果是6174。比如4312 3087 8352 6174经过三次变换得到6174输入说明一个四位整数输入保证四位数字不全相同输出说明一个整数表示这个数字经过多少次变换能得到6174输入范例4312输出范例3代码#includebits/stdc.h using namespace std; int func(int n) { string sto_string(n); while(s.length()4) { s0s; } sort(s.begin(),s.end()); string minss; string maxss; reverse(maxs.begin(),maxs.end()); int maxnstoi(maxs); int minnstoi(mins); return maxn-minn; } int main() { int n; cinn; int count0; while(n!6174) { nfunc(n); count; } coutcountendl; return 0; }质数的乘积问题描述Torry从小喜爱数学。一天老师告诉他像2、3、5、7……这样的数叫做质数。Torry突然想到一个问题前10、100、1000、10000……个质数的乘积是多少呢他把这个问题告诉老师。老师愣住了一时回答不出来。于是Torry求助于会编程的你请你算出前n个质数的乘积。不过考虑到你才接触编程不久Torry只要你算出这个数模上50000的值。输入说明仅包含一个正整数n其中n100000。输出说明输出一行即前n个质数的乘积模50000的值。输入范例3输出范例30代码#includebits/stdc.h using namespace std; bool isPrime(int x) { if(x 2) return false; if(x 2) return true; if(x % 2 0) return false; for(int i 3; i * i x; i 2) { if(x % i 0) return false; } return true; } int main() { int n; cin n; long long product 1; const int MOD 50000; int count 0; int num 2; while(count n) { if(isPrime(num)) { product (product * num) % MOD; count; } num; } cout product endl; return 0; }暗恋问题描述同在一个高中他却不敢去找她虽然在别人看来那是再简单不过的事。暗恋是他唯一能做的事。他只能在每天课间操的时候望望她的位置看看她倾心的动作就够了。操场上的彩砖啊你们的位置就是他们能够站立的地方他俩的关系就像砖与砖之间一样固定无法动摇。还记得当初铺砖的工人将整个操场按正方形铺砖整个操场可视为R行C列的矩阵矩阵的每个元素为一块正方形砖块正方形砖块有两种一种为蓝色另一种为红色。我们定义他和她之间的“爱情指标”为最大纯色正方形的面积请你写一个程序求出“爱情指标”。输入说明第一行两个正整数R和CR和C都不超过200。接下来R行C列描述整个操场红色砖块用1来表示蓝色砖块用0来表示。输出说明一个数表示他和她之间的“爱情指标”。输入范例5 80 0 0 1 1 1 0 11 1 0 1 1 1 1 10 1 1 1 1 1 0 11 0 1 1 1 1 1 01 1 1 0 1 1 0 1输出范例9代码#includebits/stdc.h using namespace std; #define MAX 1005 int p[MAX][MAX]; //以ab为左上角ans为边长的正方形是否为纯色 int check(int a,int b,int ans){ int tempp[a][b]; for(int i0;ians;i) for(int j0;jans;j){ if(p[ai][bj]!temp)return 0; } return 1; } int main(void){ int R,C; cinRC; int mmaxRC?R:C;// int ans0; for(int i0;iR;i) for(int j0;jC;j) cinp[i][j]; for(int i0;iR;i) for(int j0;jC;j) for(int kans1;kmmax;k){ if(ikRjkC) if(check(i,j,k)) ansk; else break; } coutans*ans; return 0; }约瑟夫环问题描述有一次明明的公司举行忘年会。忘年会的高潮部分是最后的抽大奖环节。公司为了增加活动的气氛并没有按传统的抽奖方式来抽而是进行了一个游戏逐步逐步地淘汰人而最后剩下的人将会得到大奖。这个游戏的方式如下首先公司的全部职员围成一个圈然后确定一个淘汰数X接着就从其中的一个人开始从1数数当数到X时那个人就被淘汰出局接着下一个人再从1开始数数一直这样重复下去直到剩下最后一个人那个人就是最后的大奖得主。例如公司有5个人淘汰数定为2则一开始五个人排成一圈依次编号为1、2、3、4、5 首先从编号1的人开始数数数到2后编号2淘汰这样只剩下4个人1、3、4、5 接着从编号3的人开始数数到2后编号4淘汰这样只剩下3个人13、5 接着从编号5的人开始数数到2后编号1淘汰这样只剩下2个人3、5 最后从编号为3的人开始数数到2后编号5淘汰最后编号为3的那个人就获得了最终的大奖。 注以上的淘汰顺序为2 4 1 5 3。由于明明的运气十分地差最后第二个被淘汰与大奖失之交臂十分郁闷。他想知道自己被淘汰的全过程于是他想请你帮个忙帮他写一个程序明明把他公司的人数告诉你并且把那个淘汰数也告诉你你的程序能够根据这两个数计算出淘汰人的具体顺序即把淘汰人的编号按顺序输出。明明的问题可以归结为给你一个公司的人数N和一个淘汰数X你的程序模拟上面描述的淘汰方式输出淘汰人的编号顺序。输入说明你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据每组测试数据仅一行每组测试数据有两个整数N1N100和X0X10N表示公司的人数X表示淘汰数两个整数用一个空格隔开。每组测试数据与其后一组测试数据之间没有任何空行第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。输出说明对于每一组测试数据你写的程序要求计算出一组相应的运算结果并将这一组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。每组运算结果为N个整数即淘汰人的编号的顺序每个数之间用一个空格隔开。每组运算结果单独形成一行数据其行首和行尾都没有任何空格每组运算结果与其后一组运算结果之间没有任何空行第一组运算结果前面以及最后一组运算结果后面也都没有任何空行。 注通常显示屏为标准输出设备。输入范例5 25 699 1输出范例2 4 1 5 31 3 2 5 41 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99代码#includebits/stdc.h using namespace std; int main() { int N,X; while(cinNX) { int people[N]; for(int i0;iN;i) people[i]i1; int index0; int remainingN; for(int i0;iN;i) { index(indexX-1)%remaining; coutpeople[index]; if(iN-1) cout ; for(int jindex;jN-i-1;j) people[j]people[j1]; remaining--; } coutendl; } return 0; }连续正整数的和问题描述78这个数可以表示为连续正整数的和12318192021252627。输入一个正整数 n(10000)输出 m 行(n有m种表示法)每行是两个正整数ab表示a(a1)...bn。对于多种表示法a小的方案先输出。输入说明输入一个正整数 n(10000)输出说明输出 m 行(n有m种表示法)每行是两个正整数ab对于多种表示法a小的方案先输出。输入范例78输出范例1 1218 2125 27代码#includebits/stdc.h using namespace std; int main() { int n; cin n; // 枚举起点 a for(int a 1; a n; a) { int sum 0; for(int b a; b n; b) { sum b; if(sum n) { cout a b endl; break; } if(sum n) break; } } return 0; }英语