一. 编程题

1. 第一题 50%

题目：环形数组，长为 n，数组每个位置的值表示大小，一个字符串只包含 ‘R’、’P’ 两种字符，代表数组对应位置为红色 or 紫色。小红和小紫都从数组起点开始一起走，每次走一格，走到红色格子则小红的分数加上对应格子的数值，走到紫色格子则小紫的分数加上对应格子的数值。求问走了 x 步后，小红和小紫的分数。

  • 直接做只过了 50% ```cpp

    include

    include

    include

    using namespace std;

int main() { int n; cin >> n; vector nums(n); for(int i = 0; i < n; ++i) cin >> nums[i]; string colors; cin >> colors; long long allVal1 = 0; long long allVal2 = 0; for(int i = 0; i < n; ++i) { if(colors[i] == ‘R’) allVal1 += nums[i]; else if(colors[i] == ‘P’) allVal2 += nums[i]; }

  1. int Q;    // 询问次数
  2. cin >> Q;
  3. for(int q = 0; q < Q; ++q)
  4. {
  5.     int x;    // 第 x 天后
  6.     cin >> x;
  8.     int completeDays = x / n;
  9.     int remainDays = x % n;
  10.     long long val1 = completeDays * allVal1;
  11.     long long val2 = completeDays * allVal2;
  12.     for(int i = 0; i < remainDays; ++i)
  13.     {
  14.         if(colors[i] == 'R')
  15.             val1 += nums[i];
  16.         else if(colors[i] == 'P')
  17.             val2 += nums[i];
  18.     }
  19.     cout << val1 << " " << val2 << endl;
  20. }
  22. return 0;

}

  2. - 优化：前缀和、q/n、q%n 之类的优化
  4. <a name="rQG5u"></a>
  5. ## 2. 第二题 95%
  6. 两人沿三角形边界匀速跑，小红从顶点 A 开始跑，小明从顶点 B 开始走。给定三角形顶点 A、B、C 的坐标，以及小红的速度 v1，小红的方向 d1，小明的速度 v2，小明的速度 d2，问两人第一次相遇的时间，如果不能相遇则输出 -1。（方向为 0 代表：A->B->C->A，方向为 1 代表：A->C->B->A）
  8. - 下面的代码过了 95%，应该是忘了一圈内追不上取余之类的操作
  9. - 没有考虑两人反向（不是相向），但速度都为 0 的 case
  10. ```cpp
  11. #include <iostream>
  12. #include <vector>
  13. #include <algorithm>
  14. #include <math.h>
  15. using namespace std;
  17. int main()
  18. {
  19.     int xa, ya, xb, yb, xc, yc;
  20.     cin >> xa >> ya >> xb >> yb >> xc >> yc;
  21. //     vector<int> posArr(6);
  22. //     for(int i = 0; i < 6; ++i)
  23. //         cin >> posArr[i];
  24.     int v1, d1, v2, d2;
  25.     cin >> v1 >> d1 >> v2 >> d2;
  27.     double t = 0.0;
  29.     double lenAB = sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya- yb));
  30.     double lenBC = sqrt((xb - xc) * (xb - xc) + (yb - yc) * (yb- yc));
  31.     double lenAC = sqrt((xa - xc) * (xa - xc) + (ya - yc) * (ya- yc));
  32.     double lenAll = lenAB + lenBC + lenAC;
  33.     // cout << lenAB << ", " << lenBC << ", " << lenAC << endl;
  35.     if(d1 == 0 && d2 == 1)
  36.         t = lenAB / (v1 + v2);
  37.     else if(d1 == 1 && d2 == 0)
  38.         t = (lenAC + lenBC) / (v1 +v2);
  39.     else if(v1 == v2)
  40.         t = -1;
  41.     else
  42.     {
  43.         if(d1 == 0 && d2 == 0)
  44.         {
  45.             if(v1 > v2)
  46.                 t = lenAB / (v1 - v2);
  47.             else
  48.                 t = (lenBC + lenAC) / (v2 - v1);
  49.         }
  50.         else if(d1 == 1 && d2 == 1)
  51.         {
  52.             if(v2 > v1)
  53.                 t = lenAB / (v2 - v1);
  54.             else
  55.                 t = (lenBC + lenAC) / (v1 - v2);
  56.         }
  57.     }
  59.     cout << t << endl;
  61.     return 0;
  62. }

3. 第三题 88.24%

题目：长为 n 的数组，存储的元素代表数值，长为 n 的字符串代表数组对应位置的颜色（只包含红 R、蓝 B 两种颜色），要求最短的连续区间长度，要满足：区间内红色格子的积 x、区间内蓝色格子的积 y，x 末尾 0 的数量 + y 末尾 0 的数量要大于等于给定的 k

思路：只过了 88.24%

  • 滑动窗口
  • 末尾 0 的个数，取决于所有乘数的因子中 2 的个数、5 的个数的最小值（参考：[中等] 172. 阶乘后的零） ```cpp

    include

    include

    include

    include

    using namespace std;

int calCnt5(int num) { int div = 5; int result = 0; while(div <= num) { if(num % div == 0) { ++result; div *= 5; } else break; } return result; }

int calCnt2(int num) { int div = 2; int result = 0; while(div <= num) { if(num % div == 0) { ++result; div *= 2; } else break; } return result; }

int main() { int n, k; cin >> n >> k; vector nums(n); for(int i = 0; i < n; ++i) cin >> nums[i]; string colors; cin >> colors;

  1. int left = 0;
  2. int right = 0;
  3. int red2 = 0;
  4. int red5 = 0;
  5. int blue2 = 0;
  6. int blue5 = 0;
  7. int result = n;
  8. while(right < n)
  9. {
  10.     int num = nums[right];
  11.     ++right;
  13.     int cnt5 = calCnt5(num);
  14.     if(colors[right - 1] == 'R')
  15.         red5 = red5 + cnt5;
  16.     else if(colors[right - 1] == 'B')
  17.         blue5 = blue5 + cnt5;
  19.     int cnt2 = calCnt2(num);
  20.     if(colors[right - 1] == 'R')
  21.         red2 = red2 + cnt2;
  22.     else if(colors[right - 1] == 'B')
  23.         blue2 = blue2 + cnt2;
  25.     while(min(red2 + red5) + min(blue2 + blue5) >= k)
  26.     {
  27.         result = min(result, right - left);
  29.         int deleteNum = nums[left];
  30.         ++left;
  32.         int dCnt5 = calCnt5(deleteNum);
  33.         if(colors[left - 1] == 'R')
  34.             red5 = red5 - dCnt5;
  35.         else if(colors[left - 1] == 'B')
  36.             blue5 = blue5 - dCnt5;
  38.         int dCnt2 = calCnt2(deleteNum);
  39.         if(colors[left - 1] == 'R')
  40.             red2 = red2 - dCnt2;
  41.         else if(colors[left - 1] == 'B')
  42.             blue2 = blue2 - dCnt2;
  43.     }
  44. }
  46. cout << result << endl;
  48. return 0;

}

  2. <a name="CLl4Q"></a>
  3. ## 4. 第四题 0%
  4. n 行 m 列的矩阵，存的都是正整数，输入 Q 个 target：
  6. - 对于每个 target，如果数组中的元素 = target，则标为红色（若之前已被标记过则仍为红色），求红色连通块的数量。连通块指的是上、下、左、右有一格相邻
  8. 解法：dfs，示例是对的，但是提交就只能过 0%。。。
  9. ```cpp
  10. #include <iostream>
  11. #include <vector>
  12. using namespace std;
  14. void dfs(vector<vector<int>>& matrix, int row, int col, int target)
  15. {
  16.     int n = matrix.size();
  17.     int m = matrix[0].size();
  18.     if(row < 0 || row >= n || col < 0 || col >= m || matrix[row][col] != target)
  19.         return;
  21.     matrix[row][col] = -1;
  22.     dfs(matrix, row - 1, col, target);
  23.     dfs(matrix, row + 1, col, target);
  24.     dfs(matrix, row, col - 1, target);
  25.     dfs(matrix, row, col + 1, target);
  26.     // matrix[row][col] = target;
  27. }
  29. int main()
  30. {
  31.     int n, m;
  32.     cin >> n >> m;
  33.     vector<vector<int>> matrix(n, vector<int>(m));
  34.     for(int i = 0; i < n; ++i)
  35.     {
  36.         for(int j = 0; j < m; ++j)
  37.             cin >> matrix[i][j];
  38.     }
  39.     int Q;
  40.     cin >> Q;
  41.     for(int q = 0; q < Q; ++q)
  42.     {
  43.         int target;
  44.         cin >> target;
  45.         // cout << "target = " << target << endl;
  47. //         vector<vector<int>> temp(n, vector<int>(m));
  48. //         for(int i = 0; i < n; ++i)
  49. //         {
  50. //             for(int j = 0; j < m; ++j)
  51. //                 temp[i][j] = matrix[i][j];
  52. //         }
  53.         int result = 0;
  54.         for(int i = 0; i < n; ++i)
  55.         {
  56.             for(int j = 0; j < m; ++j)
  57.             {
  58.                 if(matrix[i][j] == target)
  59.                 {
  60.                     ++result;
  61.                     dfs(matrix, i, j, target);
  62.                     // cout << "i = " << i << ", j = " << j << ", matrix[i][j] = " << temp[i][j] << endl;
  63.                 }
  64.             }
  65.         }
  66.         cout << result;
  67.         if(q != Q - 1)
  68.             cout << " ";
  69.     }
  70.     cout << endl;
  72.     return 0;
  73. }
  • 看到有人说用：并查集+map记录同一个数的所有位置

二. 问答题

实现垃圾邮件过滤器：1 百万条的数据集，5 万条是垃圾邮件，95 万条是正常邮件。写下数据处理、特征、模型构建等思路