2017年蓝桥杯第八届C&C++大学B组真题及代码

目录
1A：购物单（填空5分）
2B：等差素数列（填空7分）（枚举）
3C：承压计算（填空13分）
4D：方格分割（填空17分）（dp）
5E：取数位（代码填空9分）
6F：递增三元组（编程题11分）（前缀和）
剖析代码
7G：螺旋折线（编程题19分）
剖析代码
8H：日志统计（编程题21分）
剖析代码（过78%数据）
9I：举世变暖（编程题23分
剖析代码
10J：乘积最大（编程题25分）
剖析代码

---

1A：购物单（填空5分）

.................答案：5200

---

2B：等差素数列（填空7分）（枚举）

答案：210

2. #include<iostream>
3. using namespace std;
4. long long int prime[100019];
5. bool  isprime(long long int n)
6. {
7.         for (long long int i = 2; i * i <= n; i++)
8.         {
9.                 if (n % i == 0)
10.                         return false;
11.         }
12.         return true;
13. }
14. int main()
15. {
16.         for (long long int i = 2; i <= 100009; i++)       //素数打表
17.         {
18.                 if (isprime(i))
19.                         prime[i] = 1;
20.         }
21.         for (int i = 1; i <= 1000; i++) // 枚举公差
22.         {
23.                 for (int j = 1; j <= 8000; j++) // 枚举首项
24.                 {
25.                         int flag = 0;
26.                         for (int k = 1; k <= 9; k++)
27.                         {
28.                                 if (prime[j + k * i] == 0)
29.                                 {
30.                                         flag = 1;
31.                                         break;
32.                                 }
33.                         }
34.                         if (!flag)
35.                         {
36.                                 printf("%d\n", i);
37.                                 return 0;
38.                         }
39.                 }
40.         }
41.         return 0;
42. }
43. // 答案210

复制代码

---

3C：承压计算（填空13分）

1.                              7
2.                             5 8
3.                            7 8 8
4.                           9 2 7 2
5.                          8 1 4 9 1
6.                         8 1 8 8 4 1
7.                        7 9 6 1 4 5 4
8.                       5 6 5 5 6 9 5 6
9.                      5 5 4 7 9 3 5 5 1
10.                     7 5 7 9 7 4 7 3 3 1
11.                    4 6 4 5 5 8 8 3 2 4 3
12.                   1 1 3 3 1 6 6 5 5 4 4 2
13.                  9 9 9 2 1 9 1 9 2 9 5 7 9
14.                 4 3 3 7 7 9 3 6 1 3 8 8 3 7
15.                3 6 8 1 5 3 9 5 8 3 8 1 8 3 3
16.               8 3 2 3 3 5 5 8 5 4 2 8 6 7 6 9
17.              8 1 8 1 8 4 6 2 2 1 7 9 4 2 3 3 4
18.             2 8 4 2 2 9 9 2 8 3 4 9 6 3 9 4 6 9
19.            7 9 7 4 9 7 6 6 2 8 9 4 1 8 1 7 2 1 6
20.           9 2 8 6 4 2 7 9 5 4 1 2 5 1 7 3 9 8 3 3
21.          5 2 1 6 7 9 3 2 8 9 5 5 6 6 6 2 1 8 7 9 9
22.         6 7 1 8 8 7 5 3 6 5 4 7 3 4 6 7 8 1 3 2 7 4
23.        2 2 6 3 5 3 4 9 2 4 5 7 6 6 3 2 7 2 4 8 5 5 4
24.       7 4 4 5 8 3 3 8 1 8 6 3 2 1 6 2 6 4 6 3 8 2 9 6
25.      1 2 4 1 3 3 5 3 4 9 6 3 8 6 5 9 1 5 3 2 6 8 8 5 3
26.     2 2 7 9 3 3 2 8 6 9 8 4 4 9 5 8 2 6 3 4 8 4 9 3 8 8
27.    7 7 7 9 7 5 2 7 9 2 5 1 9 2 6 5 3 9 3 5 7 3 5 4 2 8 9
28.   7 7 6 6 8 7 5 5 8 2 4 7 7 4 7 2 6 9 2 1 8 2 9 8 5 7 3 6
29. 5 9 4 5 5 7 5 5 6 3 5 3 9 5 8 9 5 4 1 2 6 1 4 3 5 3 2 4 1
30. X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X

复制代码

        为什么要求最小值？因为单元的不同，因此无法正确的数字，好比7无法正常从推出5 和 8，所以我们要求出单元
        单元的求法就是：题目给出了最小值，所以我们也要计算出我们得出的最小值，如许就可以得到了单元，再用这个单元去乘以最大值，就得到了题目标正确所求最大值

2. #include <cstdio>
3. #include <iostream>
4. using namespace std;
6. double g[40][40];
8. int main()
9. {
10.         for (int i = 1; i <= 30; i++)
11.                 for (int j = 1; j <= i; j++)
12.                         cin >> g[i][j];
13.         for (int i = 1; i <= 29; i++)
14.         {
15.                 for (int j = 1; j <= i; j++)
16.                 {
17.                         g[i + 1][j] += g[i][j] / 2;
18.                         g[i + 1][j + 1] += g[i][j] / 2;
19.                 }
20.         }
21.         double maxv = 0, minv = 0x3f3f3f3f;
22.         for (int i = 1; i <= 30; i++)
23.         {
24.                 maxv = max(maxv, g[30][i]);
25.                 minv = min(minv, g[30][i]);
26.         }
27.         printf("%f", 2086458231 / minv * maxv);
28.         return 0;
29. }
30. // 答案72665192664

复制代码

答案72665192664

---

4D：方格分割（填空17分）（dp）

---

答案：19

1. #include <iostream>
3. using namespace std;
4. #define endl '\n'
5. #define int long long
7. int dp[1010][5];
8. // 状态表示：[[i][j]为i层j个手机的最多(最优)测试次数
9. signed main()
10. {
11.         ios::sync_with_stdio(0);
12.         cin.tie(0);
13.         cout.tie(0);
15.         for (int i = 1;i <= 1000;i++) // 边界初始化
16.         {
17.                 dp[i][1] = i; // 如果只有一个手机，则n层最多测试指数为n（本身层数）
18.         }
20.         for (int j = 2;j <= 3;j++) // 循环手机部数 ，从2开始，因为1已经知道了
21.         {
22.                 for (int i = 1;i <= 1000;i++) // 循环楼层数
23.                 {
24.                         dp[i][j] = dp[i - 1][j] + 1; // 第j层楼还有i部手机时的测试次数=第j-1层楼还有i部手机时测试次数加1
25.                         for (int k = 2;k <= i;k++) // 假设从第k层摔手机
26.                         {
27.                                 dp[i][j] = min(dp[i][j], max(dp[k - 1][j - 1], dp[i - k][j]) + 1);
28.                         }
29.                 }
30.         }
31.         cout << dp[1000][3] << endl;
32.         return 0;
33. }
34. // 答案19

复制代码

---

5E：取数位（代码填空9分）

        快速排序，就是每次选择一个数，然后做比力使得左边的数小于所选择的数，右边的数大于所选择的数。然后将左右双方在举行快速排序。
题目答案：

1. a, i+1, r, k-(i-l+1)

复制代码

---

6F：递增三元组（编程题11分）（前缀和）

---

剖析代码

排序 + 双指针
        分析题目我们可以发现三元组中b[j] 可以同时制约 a 和 c[k]，由此可以先排序 后枚举b 对于每个 b 我们找到比它大的c[k] 的数目和比它小的a的数目，因为我们排过序全部 a,b,c 只需遍历一遍即可。

1. #include <bits/stdc++.h>
2. #include <iostream>
3. #include <vector>
4. #include <algorithm>
5. using namespace std;
6. #define endl '\n'
7. #define int long long
9. signed main()
10. {
11.         ios::sync_with_stdio(0);
12.         cin.tie(0);
13.         cout.tie(0);
15.         int n = 0;
16.         cin >> n;
17.         vector<int> A, B, C;
19.         for (int t = 0; t != 3; ++t)
20.         {
21.                 for (int i = 0; i != n; ++i)
22.                 {
23.                         int a = 0;
24.                         cin >> a;
25.                         if (t == 0)
26.                                 A.push_back(a);
27.                         else if (t == 1)
28.                                 B.push_back(a);
29.                         else
30.                                 C.push_back(a);
31.                 }
32.         }
33.         sort(A.begin(), A.end());
34.         sort(B.begin(), B.end());
35.         sort(C.begin(), C.end());
36.         int i, j, k;
37.         i = j = k = n - 1;
38.         int res = 0;
39.         while (j >= 0)
40.         {
41.                 while (k >= 0 && B[j] < C[k])
42.                         --k;
43.                 while (i >= 0 && A[i] >= B[j])
44.                         --i;
45.                 res += (n - k - 1) * (i + 1);
46.                 --j;
47.         }
48.         cout << res << endl;
49.         return 0;
50. }

复制代码

---

7G：螺旋折线（编程题19分）

---

剖析代码

找规律+模仿
        这道题的解法为 先找各个极点坐标对应的长度，我们可以发现极点 （-1，0） （-1，1） （1，1） （1 ，-1） （-2，-1） （-2，2）对应长度 1 1+1 1+1+2 1+1+2+2 1+1+2+2+3 1+1+2+2+3+3发现规律。细节的我们找到极点的规律之后，给我们一个点我们先判定它在谁人环上，然后求出对应极点的长度，最后加或减即可

1. #include <bits/stdc++.h>
2. #include <iostream>
3. #include <vector>
4. #include <algorithm>
5. #include <cstdio>
6. #include <cmath>
7. using namespace std;
8. #define endl '\n'
9. #define int long long
11. signed main()
12. {
13.         ios::sync_with_stdio(0);
14.         cin.tie(0);
15.         cout.tie(0);
16.         int x, y, t, ans;
17.         cin >> x >> y;
18.         int abx = abs(x), aby = abs(y);
20.         if (x >= 0 && y >= 0) // 第一象限
21.         {
22.                 t = max(abx, aby);
23.                 ans = (t * 2 - 1) * (t * 2 - 1 + 1);
24.                 if (abx == t)
25.                         ans += t * 2 + t - aby;
26.                 else
27.                         ans += t + abx;
28.         }
29.         else if (x > 0 && y < 0) // 第四象限
30.         {
31.                 t = max(abx, aby);
32.                 ans = (t * 2 - 1) * (t * 2 - 1 + 1);
33.                 if (abx == t)
34.                         ans += 3 * t + aby;
35.                 else
36.                         ans += 4 * t + t - abx;
37.         }
38.         else if (x <= 0 && y <= 0) // 第三象限
39.         {
40.                 t = max(abx - 1, aby);
41.                 ans = (t * 2) * (t * 2 + 1);
42.                 if (abx - 1 == t)
43.                         ans += 2 * t + 1 + t - aby;
44.                 else
45.                         ans += t + abx;
47.         }
48.         else // 第二象限
49.         {
50.                 t = max(abx, aby);
51.                 ans = (t * 2 - 1) * (t * 2 - 1 + 1);
52.                 if (abx == t)
53.                         ans -= t - aby;
54.                 else
55.                         ans += t - abx;
56.         }
57.         cout << ans << endl;
58.         return 0;
59. }

复制代码

---

8H：日志统计（编程题21分）

---

剖析代码（过78%数据）

哈希+排序
        用哈希存储每个id的全部点赞的时间数据，然后遍历哈希，将时间排序再用双指针查抄是否有区间D符合热帖要求。

1. #include <bits/stdc++.h>
2. #include <iostream>
3. #include <algorithm>
4. #include <cstdio>
5. #include <cmath>
6. #include <string>
7. #include <vector>
8. #include <unordered_map>
9. using namespace std;
10. #define endl '\n'
11. #define int long long
13. signed main()
14. {
15.         ios::sync_with_stdio(0);
16.         cin.tie(0);
17.         cout.tie(0);
18.         int N, D, K;
19.         cin >> N >> D >> K;
20.         unordered_map<int, vector<int>> map;
21.         for (int i = 0; i != N; i++)
22.         {
23.                 int ts, id;
24.                 cin >> ts >> id;
25.                 map[id].push_back(ts);
26.         }
28.         vector<int> ans;
29.         for (auto& m : map)
30.         {
31.                 int n = m.second.size();
32.                 if (n < K)continue;
33.                 sort(m.second.begin(), m.second.end());
34.                 int i = 0, j = 0;
35.                 int temp = 0;
36.                 while (j < n && i < n)
37.                 {
38.                         if (n - i < K)
39.                                 break;
40.                         while (j < n && m.second[j] - m.second[i] < D)
41.                         {
42.                                 temp++;
43.                                 j++;
44.                                 if (temp >= K)
45.                                         break;
46.                         }
47.                         if (temp >= K)
48.                         {
49.                                 ans.push_back(m.first);
50.                                 break;
51.                         }
52.                         i++;
53.                         temp--;
54.                 }
55.         }
56.         sort(ans.begin(), ans.end());
57.         for (auto e : ans)
58.         {
59.                 cout << e << endl;
60.         }
61.         return 0;
62. }

复制代码

---

9I：举世变暖（编程题23分

---

剖析代码

记录改变前和改变后的海疆情况 然后计数
必要留意的是不能简单通过 计算原来的 和 后来的岛屿数差值来计算答案
原因是 例如：

1. ........
2. .##.....
3. .####...
4. ..#.#...
5. ...###..
6. ...###..
7. ........
8. ........

复制代码

这种情况原来只有一个岛屿 改变后 却有2个
计数的方法为遍历原来的每个岛屿，只要这个岛屿改变后不存在任意一个元素，那么ans++；

1. #include<iostream>
2. #include<algorithm>
3. #include<vector>
4. #include<string>
6. using namespace std;
8. typedef long long ll;
10. int dis[][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
12. bool sign;
14. void dfs(vector<vector<int>>& a, int i, int j, vector<vector<int>>& b){
15.         if (i<1 || i>a.size() - 1 || j<1 || j>a.size() - 1||a[i][j]==0){
16.                 return;
17.         }
18.         a[i][j] = 0;
19.         if (b[i][j] != 0)sign = false;
20.         for (int k = 0; k != 4; k++){
21.                 dfs(a, i + dis[k][0], j + dis[k][1],b);
22.         }
24. }
27. int main()
28. {
29.         int N;
30.         cin >> N;
32.         vector<vector<int>> before;
33.         vector<vector<int>> later;
35.         for (int i = 0; i != N; i++){
36.                 before.push_back(vector<int>());
37.                 for (int j = 0; j != N; j++){
38.                         char t;
39.                         cin >> t;
40.                         if (t == '.')before[i].push_back(0);
41.                         else before[i].push_back(1);
42.                 }
43.         }
44.         later = before;
46.         for (int i = 1; i != N - 1; i++){
47.                 for (int j = 1; j != N - 1; j++){
48.                         if (later[i][j] == 1){
49.                                 bool b = true;
50.                                 for (int k = 0; k != 4; k++){
51.                                         if (before[i + dis[k][0]][j + dis[k][1]] == 0){
52.                                                 b = false;
53.                                         }
54.                                 }
55.                                 if (!b)later[i][j] = 0;
56.                         }
57.                 }
58.         }
60.         int ans = 0;
62.         for (int i = 1; i != N - 1; i++){
63.                 for (int j = 1; j != N - 1; j++){
64.                         if (before[i][j]){
65.                                 sign = true;
66.                                 dfs(before, i, j,later);
67.                                 if (sign)ans++;
68.                         }
69.                 }
70.         }
72.         cout << ans << endl;
74.        
75.         system("pause");
77.         return 0;
79. }

复制代码

---

10J：乘积最大（编程题25分）

---

剖析代码

思路
1、如果k== n的话，那么全部数字都要选
2、如果k%2== 0(即k为偶数)，那么选出来的一个好坏负数
3、如果k%2== 1(即k为奇数)分两种：
（1）如果全部都为负数，那么全部都为负数，把最大最大负数取出来，然后变成了k为偶数的情况，要把符号改变过来
（2）否则的话,则肯定至少有 1个非负数, 那么我们将最大的数取出来,然后变成了k为偶数的情况。

1. #include<bits/stdc++.h>
2. #define x first
3. #define y second
4. #define mem1(h) memset(h,-1,sizeof h)
5. #define mem0(h) memset(h,0,sizeof h)
6. #define mcp(a,b) memcpy(a,b,sizeof b)
7. using namespace std;
8. typedef long long LL;
9. typedef unsigned long long ull;
10. typedef pair<int,int>PII;
11. typedef pair<double,double>PDD;
12. namespace IO{
13.     inline LL read(){
14.         LL o=0,f=1;char c=getchar();
15.         while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
16.         while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();}
17.         return o*f;
18.     }
19. }using namespace IO;
20. //#############以上是自定义技巧（可忽略）##########
21. const int N=1e5+7,M=2e5+7,INF=0x3f3f3f3f,mod=1e9+9,P=131;
22. int n,k;
23. int a[N];
24. int main(){
25.     cin>>n>>k;
26.     for(int i=0;i<n;i++){
27.         cin>>a[i];
28.     }
29.     sort(a,a+n);
30.     int res=1;
31.     int l=0,r=n-1;
32.     int sign=1;
33.     if(k&1){//k为奇数
34.         res=a[r--];//取最大的数
35.         k--;
36.         if(res<0)sign=-1;//如果是最大为负数，要改变符号
37.     }
38.     while(k){//k为偶数的情况
39.         LL x=(LL)a[l]*a[l+1],y=(LL)a[r]*a[r-1];//取最小的两个与最大两个数乘积
40.         if(x*sign>y*sign){//看两个数与当前符号相乘哪个大取哪个
41.             res=x%mod*res%mod;
42.             l+=2;
43.         }else{
44.             res=y%mod*res%mod;
45.             r-=2;
46.         }
47.         k-=2;
48.     }
49.     cout<<res<<endl;
50.     return 0;
51. }

复制代码

本篇完。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。