编程考试试卷

最新题目 更多

•    一只小猪要买 N 件物品 (N 不超过 1000)。它要买的所有物品在两家商店里都有卖。第 i 件物品在第一家商店的价格是 a[i]，在第二家商店的价格是 b[i]，两个价格都不小于 0 且不超过 10000。如果在第一家商店买的物品的总额不少于50000，那么在第一家店买的物品都可以打95 折(价格变为原来的 0.95 倍)。求小猪买齐所有物品所需最少的总额。输入：第一行一个数 N。接下来 N 行，每行两个数。第 i 行的两个数分别代表 a[i], b[i]。输出：输出一行一个数，表示最少需要的总额，保留两位小数。试补全程序。#include <cstdio> #include <algorithm> using namespace std; const int Inf = 1000000000; const int threshold = 50000; const int maxn = 1000; int n, a[maxn], b[maxn]; bool put_a[maxn]; int total_a, total_b; double ans; int f[threshold]; int main() {     scanf("%d", &n);     total_a = total_b = 0;     for (int i = 0; i < n; ++i) {         scanf("%d%d", a + i, b + i);         if (a[i] <= b[i]) total_a += a[i];         else total_b += b[i];     }     ans = total_a + total_b;     total_a = total_b = 0;     for (int i = 0; i < n; ++i) {         if (____(1)____) {             put_a[i] = true;             total_a += a[i];         }         else{             put_a[i] = false;             total_b += b[i];         }     }     if (____(2)____) {         printf("%.2f", total_a * 0.95 + total_b);         return 0;     }     f[0] = 0;     for (int i = 1; i < threshold; ++i)         f[i] = Inf;     int total_b_prefix = 0;     for (int i = 0; i < n; ++i) {         if (!put_a[i]) {             total_b_prefix += b[i];             for (int j = threshold - 1; j >= 0; --j) {                 if (____(3)____ >= threshold && f[j] != Inf)                     ans = min(ans, (total_a + j + a[i]) * 0.95 + ____(4)____);                 f[j] = min(f[j] + b[i], j >= a[i] ? ____(5)____ : Inf);             }         }     }     printf("%.2f", ans);     return 0; }
•    对于一个 1 到 n 的排列 P（即 1 到 n 中每一个数在 P 中出现了恰好一次），令 qi 为第 i 个位置之后第一个比 Pi 值更大的位置，如果不存在这样的位置，则 qi=n+1。举例来说，如果 n=5 且 P 为 1 5 4 2 3，则 q 为2 6 6 5 6 。下列程序读入了排列 P，使用双向链表求解了答案。试补全程序。数据范围1≤n≤105。#include <iostream> using namespace std; const int N = 100010; int n; int L[N], R[N], a[N]; int main(){     cin >> n;     for (int i = 1; i <= n; ++i){         int x;         cin >> x;         ____(1)____;     }     for (int i = 1; i <= n; ++i){         R[i] = ____(2)____;         L[i] = i - 1;     }     for (int i = 1; i <= n; ++i){         L[____(3)____] = L[a[i]];         R[L[a[i]]] = R[____(4)____];     }     for (int i = 1; i <= n; ++i){         cout << ____(5)____ << " ";     }     cout << endl;     return 0; }
•    #include <cstdio> using namespace std; const int N = 110; bool isUse[N]; int n, t; int a[N], b[N]; bool isSmall(){     for (int i = 1; i <= n; ++i)         if (a[i] != b[i]) return a[i] < b[i];     return false; } bool getPermutation(int pos){     if (pos > n){         return isSmall();     }     for (int i = 1; i <= n; ++i){         if (!isUse[i]){             b[pos] = i; isUse[i] = true;             if (getPermutation(pos + 1)){                 return true;             }             isUse[i] = false;         }     }     return false; } void getNext(){     for (int i = 1; i <= n; ++i){         isUse[i] = false;     }     getPermutation(1);     for (int i = 1; i <= n; ++i){         a[i] = b[i];     } } int main(){     scanf("%d%d", &n, &t);     for (int i = 1; i <= n; ++i){         scanf("%d", &a[i]);     }     for (int i = 1; i <= t; ++i){         getNext();     }     for (int i = 1; i <= n; ++i){         printf("%d", a[i]);         if (i == n) putchar(&#39; &#39;); else putchar(&#39; &#39;);     }     return 0; }输入1：6 10 1 6 4 5 3 2输出1：________输入2：6 200 1 5 3 4 2 6输出2：________
•    #include <iostream> using namespace std; string s; long long magic(int l, int r){     long long ans = 0;     for (int i = l; i <= r; ++i){         ans = ans * 4 + s[i] - &#39;a&#39; + 1;     }     return ans; } int main(){     cin >> s;     int len = s.length();     int ans = 0;     for (int l1 = 0; l1 < len; ++l1){         for (int r1 = l1; r1 < len; ++r1){             bool bo = true;             for (int l2 = 0; l2 < len; ++l2){                 for (int r2 = l2; r2 < len; ++r2){                     if (magic(l1, r1) == magic(l2, r2) && (l1 != l2 || r1 != r2)){                         bo = false;                     }                 }             }             if (bo){                 ans += 1;             }         }     }     cout << ans << endl;     return 0; }输入 ：abacaba输出 ：________
•    #include <cstdio> int n, d[100]; bool v[100]; int main(){     scanf("%d", &n);     for (int i = 0; i < n; ++i){         scanf("%d", d + i);         v[i] = false;     }     int cnt = 0;     for (int i = 0; i < n; ++i){         if (!v[i]){             for (int j = i; !v[j]; j = d[j]){                 v[j] = true;             }             ++cnt;         }     }     printf("%d ", cnt);     return 0; }输入 ：10 7 1 4 3 2 5 9 8 0 6输出 ：________
•    #include <cstdio> int main(){     int x;     scanf("%d", &x);     int res = 0;     for (int i = 0; i < x; ++i){         if (i * i % x == 1){             ++res;         }     }     printf("%d", res);     return 0; }输入 ：15输出 ：________
•    方程 a*b = (a or b) *(a and b)，在 a,b 都取 [0, 31]中的整数时，共有_____组解。(*∗ 表示乘法；or 表示按位或运算；and 表示按位与运算)
•    甲乙丙丁四人在考虑周末要不要外出郊游。已知①如果周末下雨，并且乙不去，则甲一定不去；②如果乙去，则丁一定去；③如果丙去，则丁一定不去；④如果丁不去，而且甲不去，则丙一定不去。如果周末丙去了，则甲________(去了/没去)，乙________(去了/没去)，丁________(去了/没去)，周末________(下雨/没下雨)。
•    对于一个 1 到 n 的排列 P（即 1 到 n 中每一个数在 P 中出现了恰好一次），令 qi 为第 i 个位置之后第一个比 Pi 值更大的位置，如果不存在这样的位置，则 qi=n+1。举例来说，如果n=5 且 P 为 15423，则 q 为 2, 6, 6, 5, 6下列程序读入了排列 P，使用双向链表求解了答案。试补全程序。数据范围 1≤n≤105。#include <iostream> using namespace std; const int N = 100010; int n; int L[N], R[N], a[N]; int main() {     cin >> n;     for (int i = 1; i <= n; ++i) {         int x;         cin >> x;         ① ;     }     for (int i = 1; i <= n; ++i) {         R[i] = ② ;         L[i] = i - 1;     }     for (int i = 1; i <= n; ++i) {         L[ ③ ] = L[a[i]];         R[L[a[i]]] = R[ ④ ];     }     for (int i = 1; i <= n; ++i) {         cout << ⑤ << " ";     }     cout << endl;     return 0; }
•    （最大公约数之和）下列程序想要求解整数 n 的所有约数两两之间最大公约数的和对10007 求余后的值，试补全程序。举例来说，4 的所有约数是 1,2,4。1 和 2 的最大公约数为 1；2 和 4 的最大公约数为 2；1 和 4 的最大公约数为 1。于是答案为 1 + 2 + 1 = 4。要求 getDivisor 函数的复杂度为 O(√n)，gcd 函数的复杂度为O(log max(a,b))。例如:#include <iostream> using namespace std; const int N = 110000, P = 10007; int n; int a[N], len; int ans; void getDivisor() {     len = 0;     for (int i = 1; ① <= n; ++i)         if (n % i == 0) {             a[++len] = i;             if ( ② != i) a[++len] = n / i;         }     } } int gcd(int a, int b) {     if (b == 0) {         ③ ;     }     return gcd(b, ④ ); } int main() {     cin >> n;     getDivisor();     ans = 0;     for (int i = 1; i <= len; ++i) {         for (int j = i + 1; j <= len; ++j) {             ans = ( ⑤ ) % P;         }     }     cout << ans << endl;     return 0; }
•    #include <cstdio> int n, d[100]; bool v[100]; int main() {     scanf("%d", &n);     for (int i = 0; i < n; ++i) {         scanf("%d", d + i);         v[i] = false;     }     int cnt = 0;     for (int i = 0; i < n; ++i) {         if (!v[i]) {             for (int j = i; !v[j]; j = d[j]) {                 v[j] = true;             }             ++cnt;         }     }     printf("%d ", cnt);     return 0; }输入：10 7 1 4 3 2 5 9 8 0 6输出：（ ）
•    #include <iostream> using namespace std; int n, m; int findans(int n, int m) {     if (n == 0) return m;     if (m == 0) return n % 3;     return findans(n - 1, m) - findans(n, m - 1) + findans(n - 1, m - 1); } int main(){     cin >> n >> m;     cout << findans(n, m) << endl;     return 0; }输入：5 6输出：（ ）
•    #include <cstdio> int main() {     int x;     scanf("%d", &x);     int res = 0;     for (int i = 0; i < x; ++i) {         if (i * i % x == 1) {             ++res;         }     }     printf("%d", res);     return 0; }输入：15输出：（ ）
•    #include <cstdio> char st[100]; int main() {     scanf("%s", st);     for (int i = 0; st[i]; ++i) {         if (&#39;A&#39; <= st[i] && st[i] <= &#39;Z&#39;)             st[i] += 1;     }     printf("%s ", st);     return 0; }输入：QuanGuoLianSai输出：（ ）
•    从 1 到 2018 这 2018 个数中，共有___个包含数字 8 的数。包含数字 8 的数是指有某一位是“8”的数，例如“2018”与“188”。
•    甲乙丙丁四人在考虑周末要不要外出郊游。已知①如果周末下雨，并且乙不去，则甲一定不去；②如果乙去，则丁一定去；③如果丙去，则丁一定不去；④如果丁不去，而且甲不去，则丙一定不去。如果周末丙去了，则甲____（去了/没去），乙____（去了/没去），丁 ___ （去了/没去），周末____（下雨/没下雨）。
•    （切割绳子）有 n 条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出m条长度相同的绳段，求绳段的最大长度是多少。输入：第一行是一个不超过 100 的正整数 n，第二行是 n 个不超过 10^6的正整数，表示每条绳子的长度，第三行是一个不超过 10^8 的正整数 m。输出 ：绳段的最大长度，若无法切割，输出 Failed。#include <iostream> using namespace std; int n, m, i, lbound, ubound, mid, count; int  len[100]; //绳子长度 int main() {     cin >> n;     count = 0;     for (i = 0; i < n; i++) {         cin >> len[i];         ①;     }     cin >> m;     if (②) {         cout << "Failed" << endl;         return 0;     }     lbound = 1 ;     ubound = 1000000 ;     while (③) {         mid = ④;         count =0 ;         for (i = 0; i < n; i++ )             ⑤;         if (count < m)             ubound = mid - 1 ;         else             lbound = mid ;     }     cout << lbound << endl;     return 0; }
•    （快速幂）请完善下面的程序，该程序使用分治法求 xp mod m 的值。输入：三个不超过 10000 的正整数 x, p, m。输出：xp mod m 的值。提示：若 p 为偶数，xp = (x2)p/2；若 p 为奇数，xp = x  (x2)(p-1)/2。#include <iostream> using namespace std; int x, p, m, i, result; int main() {     cin >> x >> p >> m;     result = ①;     while(②)     {         if(p % 2 == 1)             result = ③;         p /= 2;         x = ④;     }     cout << ⑤ << endl;     return  0 ; }
•    #include <iostream> using namespace std; int main() {     int n, m;     cin >> n >> m;     int x = 1;     int y = 1;     int dx = 1;     int dy = 1;     int cnt = 0;     while(cnt != 2) {         cnt = 0;         x = x + dx;         y = y + dy;         if(x == 1 || x == n) {             ++cnt;             dx = -dx;         }         if(y == 1 || y == m) {             ++cnt;             dy = -dy;         }     }     cout << x << " " << y << endl;     return  0 ; }1）输入：4 3输出：（ ）2）输入：2017 1014输出：（ ）
•    #include <iostream> #include <string> using namespace std; int main() {     string ch;     int a[200];     int b[200];     int n, i, t, res;     cin >> ch;     n = ch.length();     for(i = 0; i < 200; i++) b[i] = 0;     for(i = 1; i <= n ; i++) {         a[i] = ch[i-1] - &#39;0&#39;;         b[i] = b[i-1] + a[i];     }     res = b[n];     t = 0;     for(i = n; i > 0; i--) {         if(a[i] == 0) t++;         if(b[i-1] + t < res) res = b[i-1] + t;     }     cout << res << endl;     return 0; }输入：1001101011001101101011110001输出：（ ）
•    #include <stdio.h> int g(int m, int n, int x) {     int ans=0;     int i;     if(n == 1)         return 1;     for(i = x; i <= m / n; i++)         ans += g(m - i, n - 1, i);     return ans; } int main() {     int t, m, n;     scanf("%d%d", &m, &n);     printf("%d ", g(m, n, 0));     return  0; }输入：7 3输出：（ ）
•    #include <iostream> #include <cstring> using namespace std; int main() {     int t[256];     char s[10];     int i;     scanf("%s", s);     for(i = 0; i < 256; i++) t[i] = 0;     for(i = 0; i < strlen(s); i++) t[s[i]]++;     for(i = 0; i < strlen(s); i++)         if(t[s[i]] == 1) {             cout << s[i] << endl;             return 0;         }     cout << "no" << endl;     return 0; }输入：xyzxyw输出：（ ）
•    如下图所示，共有 13 个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变（由 1 变 0，或由 0 变 1）。现在要使得所有的格子中的数字都变为 0，至少需要_____次操作。
•    一个人站在坐标（0，0）处，面朝 x 轴正方向。第一轮，他向前走 1 单位距离，然后右转；第二轮，他向前走 2 单位距离，然后右转；第三轮，他向前走 3 单位距离，然后右转……他一直这么走下去。请问第 2017 轮后，他的坐标是：（___ , ___）。
•    (交通中断）有一个小国家，国家内有 n 座城市和 m 条双向的道路，每条道路连接着两座不同的城市。其中 1 号城市为国家的首都。由于地震频繁可能导致某一个城市与外界交通全部中断。这个国家的首脑想知道，如果只有第i(i>1) 个城市因地震而导致交通中断时，首都到多少个城市的最短路径长度会发生改变。如果因为无法通过第 i 个城市而导致从首都出发无法到达某个城市，也认为到达该城市的最短路径长度改变。对于每一个城市 i，假定只有第 i 个城市与外界交通中断，输出有多少个城市会因此导致到首都的最短路径长度改变。我们采用邻接表的方式存储图的信息，其中 head[x] 表示顶点 x 的第一条 边的编号，next[i] 表示第 i 条边的下一条边的编号, point[i] 表示第 i 条边的终点，weight[i] 表示第 i 条边的长度。#include <iostream> #include <cstring> using namespace std; #define MAXN 6000 #define MAXM 100000 #define infinity 2147483647 int head[MAXN], next[MAXM], point[MAXM], weight[MAXM]; int queue[MAXN], dist[MAXN], visit[MAXN]; int n, m, x, y, z, total = 0, answer; void link(int x,int y,int z) {     total++;     next[total] = head[x]; head[x] = total; point[total] = y; weight[total] = z; total++;     next[total] = head[y]; head[y] = total; point[total] = x; weight[total] = z; } int main() {     int i, j, s, t; cin >> n >> m;     for (i = 1; i <= m; i++) {         cin >> x >> y >> z;         link(x, y, z);     }     for (i = 1; i <= n; i++) dist[i] = infinity;     ___(1)___ ;     queue[1] = 1;     visit[1] = 1;     s = 1;     t = 1;     // 使用 SPFA 求出第一个点到其余各点的最短路长度     while (s <= t) {         x = queue[s % MAXN];         j = head[x];         while (j != 0) {             if ( ___(2)___ ) {                 dist[point[j]] = dist[x] + weight[j];                 if (visit[point[j]] == 0) {                     t++;                     queue[t % MAXN] = point[j];                     visit[point[j]] = 1;                 }             }             j = next[j];         }         ___(3)___ ;         s++;     }     for (i = 2; i <= n; i++) {         queue[1] = 1;         memset(visit, 0, sizeof(visit));         visit[1] = 1;         s = 1;         t = 1;         while (s <= t) { // 判断最短路长度是否不变             x = queue[s];             j = head[x];             while (j != 0) {                 if (point[j] != i && ___(4)___ &&visit[point[j]] == 0) {                     ___(5)___ ;                     t++;                     queue[t] = point[j];                 }                 j = next[j];             }             s++;         }         answer = 0;         for (j = 1; j <= n; j++)             answer += 1 - visit[j];         cout << i << ":" << answer - 1 << endl;     }     return 0; }
•    （交朋友）根据社会学研究表明，人们都喜欢找和自己身高相近的人做朋友。 现在有 n 名身高两两不相同的同学依次走入教室，调查人员想预测每个人在走入教室的瞬间最想和已经进入教室的哪个人做朋友。当有两名同学和这名同学的身高差一样时，这名同学会更想和高的那个人做朋友。比如一名身高为 1.80 米的同学进入教室时，有一名身高为 1.79 米的同学和一名身高为 1.81 米的同学在教室里，那么这名身高为1.80 米的同学会更想和身高为 1.81 米的同学做朋友。对于第一个走入教室的同学我们不做预测。由于我们知道所有人的身高和走进教室的次序，所以我们可以采用离线的做法来解决这样的问题，我们用排序加链表的方式帮助每一个人找到在他之前进入教室的并且和他身高最相近的人。#include <iostream> using namespace std; #define MAXN 200000 #define infinity 2147483647 int answer[MAXN], height[MAXN], previous[MAXN], next[MAXN]; int rank[MAXN]; int n; void sort(int l, int r) {     int x = height[rank[(l + r) / 2]], i = l, j = r, temp;     while (i <= j)     {         while (height[rank[i]] < x) i++;         while (height[rank[j]] > x) j--;         if ( ___(1)___ ) {             temp = rank[i]; rank[i] = rank[j]; rank[j] = temp;              i++; j--;         }     }     if (i < r) sort(i, r);     if (l < j) sort(l, j); } int main() {     cin >> n;     int i, higher, shorter;     for (i = 1; i <= n; i++) {         cin >> height[i];         rank[i] = i;     }     sort(1, n);     for (i = 1; i <= n; i++) {         previous[rank[i]] = rank[i - 1];            ___(2)___ ;     }     for (i = n; i >= 2; i--){         higher = shorter = infinity;         if (previous[i] !=0)             shorter = height[i] - height[previous[i]];         if (next[i] != 0)             ___(3)___ ;         if ( ___(4)___ )             answer[i] = previous[i];         else             answer[i] = next[i];         next[previous[i]] = next[i];         ___(5)___ ;     }     for (i = 2; i <= n; i++)         cout << i << ":" << answer[i];     return 0; }
•    #include <iostream> #include <cstring> using namespace std; int map[100][100]; int sum[100], weight[100]; int visit[100]; int n; void dfs(int node) {     visit[node] = 1;     sum[node] = 1;     int v, maxw = 0;     for (v = 1; v <= n; v++) {         if (!map[node][v] || visit[v])             continue;         dfs(v);         sum[node] += sum[v];         if (sum[v] > maxw)             maxw = sum[v];     }     if (n - sum[node] > maxw)         maxw = n - sum[node];     weight[node] = maxw; } int main() {     memset(map, 0, sizeof(map));     memset(sum, 0, sizeof(sum));     memset(weight, 0, sizeof(weight));     memset(visit, 0, sizeof(visit));     cin >> n;     int i, x, y;     for (i = 1; i < n; i++) {         cin >> x >> y;         map[x][y] = 1;         map[y][x] = 1;     }     dfs(1);     int ans = n, ansN = 0;     for (i = 1; i <= n; i++)         if (weight[i] < ans) {             ans = weight[i];             ansN = i;         }     cout << ansN << " " << ans << endl;     return 0; }输入 :111 21 32 42 52 63 77 87 116 99 10输出 : ____
•    #include<iostream> using namespace std; int lps(string seq, int i, int j) {     int len1, len2;     if (i == j)         return 1;     if (i > j)         return 0;     if (seq[i] == seq[j])         return lps(seq, i + 1, j - 1) + 2;     len1 = lps(seq, i, j - 1);     len2 = lps(seq, i + 1, j);     if (len1 > len2)         return len1;     return len2; } int main() {     string seq = "acmerandacm";     int n = seq.size();     cout << lps(seq, 0, n - 1) << endl;     return 0; }输出 ：____
•    #include <iostream> using namespace std; int main() {     char a[100][100], b[100][100];     string c[100];     string tmp;     int n, i = 0, j = 0, k = 0, total_len[100], length[100][3];     cin >> n;     getline(cin, tmp);     for (i = 0; i < n; i++) {         getline(cin, c[i]);         total_len[i] = c[i].size();     }     for (i = 0; i < n; i++) {         j = 0;         while (c[i][j] != &#39;:&#39;) {             a[i][k] = c[i][j];             k = k + 1;             j++;         }         length[i][1] = k - 1;         a[i][k] = 0;         k = 0;         for (j = j + 1; j < total_len[i]; j++) {             b[i][k] = c[i][j];             k = k + 1;         }         length[i][2] = k - 1;         b[i][k] = 0;         k = 0;     }     for (i = 0; i < n; i++) {         if (length[i][1] >= length[i][2])             cout << "NO,";         else {             k = 0;             for (j = 0; j < length[i][2]; j++) {                 if (a[i][k] == b[i][j])                     k = k + 1;                 if (k > length[i][1])                     break;             }             if (j == length[i][2])                 cout << "NO,";             else                 cout << "YES,";             }     }     cout << endl;     return 0; }输入 :3AB:ACDEbFBkBDAR:ACDBrTSARS:Severe Atypical Respiratory Syndrome输出 : ____（注：输入各行前后均无空格）
•    #include <iostream> using namespace std; int main() {     int a[6] = {1, 2, 3, 4, 5, 6};     int pi = 0;     int pj = 5;     int t , i;     while (pi < pj) {          t = a[pi];         a[pi] = a[pj];         a[pj] = t;         pi++;         pj--;     }     for (i = 0; i < 6; i++)         cout << a[i] << ",";     cout << endl;     return 0; }输出 ：____