[关闭]
@wsndy-xx 2018-06-25T01:04:12.000000Z 字数 7436 阅读 858

2018 拉勾专业算法能力测评 A-I

题解

A

题意：给定一个十进制正整数N，写下从1开始，到N的所有正数，计算出其中出现所有1的个数
思路：分块打表或者分类讨论

  1. #include<stdio.h>  
  3. long long int Count(long long int n){  
  4.     //1的个数  
  5.     long long int count = 0;  
  6.     //当前位  
  7.     long long int Factor = 1;  
  8.     //低位数字  
  9.     long long int LowerNum = 0;  
  10.     //当前位数字  
  11.     long long int CurrNum = 0;  
  12.     //高位数字  
  13.     long long int HigherNum = 0;  
  14.     if(n <= 0){  
  15.         return 0;  
  16.     }  
  17.     while(n / Factor != 0){  
  18.         //低位数字  
  19.         LowerNum = n - (n / Factor) * Factor;  
  20.         //当前位数字  
  21.         CurrNum = (n / Factor) % 10;  
  22.         //高位数字  
  23.         HigherNum = n / (Factor * 10);  
  24.         //如果为0,出现1的次数由高位决定  
  25.         if(CurrNum == 0){  
  26.             //等于高位数字 * 当前位数  
  27.             count += HigherNum * Factor;  
  28.         }  
  29.         //如果为1,出现1的次数由高位和低位决定  
  30.         else if(CurrNum == 1){  
  31.             //高位数字 * 当前位数 + 低位数字 + 1  
  32.             count += HigherNum * Factor + LowerNum + 1;  
  33.         }  
  34.         //如果大于1,出现1的次数由高位决定  
  35.         else{  
  36.             //（高位数字+1）* 当前位数  
  37.             count += (HigherNum + 1) * Factor;  
  38.         }  
  39.         //前移一位  
  40.         Factor *= 10;  
  41.     }  
  42.     return count;  
  43. }  
  45. int main(){  
  46.     long long int a;  
  47.     while(scanf("%lld",&a) != EOF){  
  48.         printf("%lld\n",Count(a));  
  49.     }  
  50.     return 0;  
  51. }

B

题意：有编号1-n的n个格子，机器人从1号格子顺序向后走，一直走到n号格子，并需要从n号格子走出去。机器人有一个初始能量，每个格子对应一个整数A[i]，表示这个格子的能量值。如果A[i] > 0，机器人走到这个格子能够获取A[i]个能量，如果A[i] < 0，走到这个格子需要消耗相应的能量，如果机器人的能量 < 0，就无法继续前进了。问机器人最少需要有多少初始能量，才能完成整个旅程。

思路：判断最小前缀和

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  5. #define LL long long
  7. const int N = 50010;
  9. LL A[N], Minn;
  10. int n;
  12. int main() {
  13.     std:: cin >> n;
  14.     for(int i = 1; i <= n; i ++) std:: cin >> A[i];
  15.     Minn = A[1];
  16.     for(int i = 2; i <= n; i ++) {
  17.         A[i] += A[i - 1];
  18.         Minn = std:: min(A[i], Minn);
  19.     }
  20.     if(Minn >= 0) std:: cout << 0;
  21.     else std:: cout << -Minn;   
  23.     return 0;
  24. }

C

题意：有一口井，井的高度为N，每隔1个单位它的宽度有变化。现在从井口往下面扔圆盘，如果圆盘的宽度大于井在某个高度的宽度，则圆盘被卡住（恰好等于的话会下去）。
盘子有几种命运：1、掉到井底。2、被卡住。3、落到别的盘子上方。
盘子的高度也是单位高度。给定井的宽度和每个盘子的宽度，求最终落到井内的盘子数量。

思路：前缀最小值优化，对每一个盘子找到最优的位置

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  5. const int N = 50010;
  7. int A[N], B[N], At, Bt;
  8. int Minn[N]; //前缀最小值
  10. int main() {
  11.     std:: cin >> At >> Bt;
  12.     for(int i = 1; i <= At; i ++) std:: cin >> A[i];
  13.     for(int i = 1; i <= Bt; i ++) std:: cin >> B[i];
  14.     Minn[1] = A[1];
  15.     for(int i = 2; i <= At; i ++) Minn[i] = std:: min(Minn[i - 1], A[i]);
  16.     int down = At, i;
  17.     for(i = 1; i <= Bt && down > 0; i ++) {
  18.         if(Minn[down] >= B[i]) {down --; continue;}
  19.         while(Minn[down] < B[i] && down) down --;
  20.         if(down == 0) break;
  21.         down --;
  22.     }
  23.     std:: cout << i - 1;
  24.     return 0;
  25. }

D

题意: n个人，已知每个人体重。独木舟承重固定，每只独木舟最多坐两个人，可以坐一个人或者两个人。显然要求总重量不超过独木舟承重，假设每个人体重也不超过独木舟承重，问最少需要几只独木舟？

思路: 排序后贪心

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  5. const int N = 10010;
  7. int A[N], n, m;
  9. int main() {
  10.     std:: cin >> n >> m;
  11.     for(int i = 1; i <= n; i ++) std:: cin >> A[i];
  12.     std:: sort(A + 1, A + n + 1);
  13.     int l = 1, r = n, js = 0, Answer = 0;
  14.     while(js != n) {
  15.         if(A[l] + A[r] <= m) l ++, r --, js += 2, Answer ++;
  16.         else r --, js ++, Answer ++;
  17.         if(l == r) {Answer ++; break;} 
  18.     }
  19.     std:: cout << Answer;
  21.     return 0;
  22. }

E

题意：平面上有N个点，任意2个点确定一条直线，求出所有这些直线中，斜率最大的那条直线所通过的两个点。
（点的编号为1-N，如果有多条直线斜率相等，则输出所有结果，按照点的X轴坐标排序，正序输出。数据中所有点的X轴坐标均不相等，且点坐标为随机。）

思路： 暴力判断

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cmath>
  6. const int N = 10010;
  7. const double eps = 1e-10;
  9. struct Node {int x, y;} Point[N];
  10. int n, Ans_js;
  11. Node Ans[N];
  13. inline double Get_k(int a, int b) {
  14.     return (double)(Point[a].y - Point[b].y) / (double)(Point[a].x - Point[b].x); 
  15. }
  17. int main() {
  18.     std:: cin >> n;
  19.     for(int i = 1; i <= n; i ++) std:: cin >> Point[i].x >> Point[i].y;
  20.     double Max_k = 0;
  21.     for(int i = 1; i <= n; i ++)
  22.         for(int j = i + 1; j <= n; j ++) {
  23.             double Now_k = Get_k(i, j);
  24.             if(Now_k > Max_k) {
  25.                 Max_k = Now_k; Ans_js = 0;
  26.                 if(Point[i].x < Point[j].x) Ans[++ Ans_js].x = i, Ans[Ans_js].y = j;
  27.                 else Ans[++ Ans_js].x = j, Ans[Ans_js].y = i;
  28.             } else if(Now_k == Max_k) {
  29.                 if(Point[i].x < Point[j].x) Ans[++ Ans_js].x = i, Ans[Ans_js].y = j;
  30.                 else Ans[++ Ans_js].x = j, Ans[Ans_js].y = i;
  31.             }
  32.         }
  33.     for(int i = 1; i <= Ans_js; i ++) std:: cout << Ans[i].x << " " << Ans[i].y << "\n";
  34.     return 0;
  35. }

F

题意：现有的统计工具只能统计某一个窗口中，用户的满意程度的均值。夹克老爷想让你为统计工具添加一个新feature，即在统计均值的同时，计算窗口中满意程度的标准差和中位数（均值需要向下取整）。

思路：线段树维护

  1. #include<stdio.h>  
  2. #include<string.h>  
  3. #include<math.h>  
  4. #include<queue>  
  5. #include<algorithm>  
  6. using namespace std;  
  7. #define LL long long  
  8. double he[2];  
  9. int shu;  
  10. struct node{int l,r,shu;}PP[300];  
  11. void creat(int l,int r,int x)  
  12. {  
  13.     PP[x].l=l;PP[x].r=r;  
  14.     PP[x].shu=0;  
  15.     if (l==r) return ;  
  16.     int m=(l+r)>>1;  
  17.     creat(l,m,x*2);  
  18.     creat(m+1,r,x*2+1);  
  19. }  
  20. void add(int wei,int x)  
  21. {  
  22.     PP[x].shu++;  
  23.     if (PP[x].l==PP[x].r) return ;  
  24.     int m=(PP[x].l+PP[x].r)>>1;  
  25.     if (wei>m) add(wei,x*2+1);  
  26.     else add(wei,x*2);  
  27. }  
  28. void jian(int wei,int x)  
  29. {  
  30.     PP[x].shu--;  
  31.     if (PP[x].l==PP[x].r) return ;  
  32.     int m=(PP[x].l+PP[x].r)>>1;  
  33.     if (wei>m) jian(wei,x*2+1);  
  34.     else jian(wei,x*2);  
  35. }  
  36. int query(int ll,int x)  
  37. {  
  38.     if (PP[x].l==PP[x].r)  
  39.         return PP[x].l;  
  40.     else if (PP[x*2].shu<ll)  
  41.         query(ll-PP[x*2].shu,x*2+1);  
  42.     else  
  43.         query(ll,x*2);  
  44. }  
  45. int main()  
  46. { 
  47.     queue<int> que;  
  48.     int n,k;  
  49.     scanf("%d%d",&n,&k);  
  50.     int s=0,a,b;  
  51.     shu=0;  
  52.     creat(0,100,1);  
  53.     while (n--)  
  54.     {  
  55.         scanf("%d",&a);  
  56.         switch(a)  
  57.         {  
  58.             case 1:  
  59.                 if (shu==k)  
  60.                 {  
  61.                     b=que.front();  
  62.                     que.pop();  
  63.                     he[0]-=b;  
  64.                     he[1]-=b*b;  
  65.                     jian(b,1);  
  66.                 }  
  67.                 else shu++;  
  68.                 scanf("%d",&b);  
  69.                 que.push(b);  
  70.                 he[0]+=b;he[1]+=b*b;  
  71.                 add(b,1);  
  72.                 break;  
  73.             case 2:  
  74.                 printf("%d.00\n",((int)he[0])/shu);  
  75.                 break;  
  76.             case 3:  
  77.                 printf("%.2lf\n",he[1]/shu-(he[0]/shu)*(he[0]/shu));  
  78.                 break;  
  79.             case 4:  
  80.                 if (shu%2==0)  
  81.                 {  
  82.                     a=query(shu/2,1);  
  83.                     b=query(shu/2+1,1);  
  84.                     printf("%.2lf\n",(a+b)/2.0);  
  85.                 }  
  86.                 else  
  87.                 {  
  88.                     b=query(shu/2+1,1);  
  89.                     printf("%.2lf\n",(double)b);  
  90.                 }  
  91.                 break;  
  92.         }  
  93.     }  
  94.     return 0;  
  95. }

从此题稍有思维难度

G

题意：有N只兔子，每只有一个血量B[i]，需要用箭杀死免子。有M种不同类型的箭可以选择，每种箭对兔子的伤害值分别为D[i]，价格为P[i](1 <= i <= M)。假设每种箭只能使用一次，每只免子也只能被射一次，计算要消灭地图上的所有兔子最少需要多少Q币。如不能杀死所有兔子，请输出No Solution。
特别说明：1、当箭的伤害值大于等于兔子的血量时，能将兔子杀死；2、血量B[i]，箭的伤害值D[i]，箭的价格P[i]，均小于等于100000。

思路：对血量贪心找到最合适的剑，优先队列优化

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <queue>
  7. using namespace std;
  8. const int N = 50010;
  10. int B[N];
  11. struct Node {
  12.     int hit, money;
  13. }A[N];
  14. int n, m;
  16. bool operator <(Node a, Node b) {return a.money > b.money;}
  17. bool cmp_1(int a, int b) {return a > b;}
  18. bool cmp_2(Node a, Node b) {return a.hit > b.hit;}
  19. priority_queue <Node> Q;
  22. int main() {
  23.     cin >> n >> m;
  24.     if(n > m) {cout << "No Solution"; return 0;}
  25.     for(int i = 1; i <= n; i ++) cin >> B[i];
  26.     for(int i = 1; i <= m; i ++) cin >> A[i].hit >> A[i].money;
  27.     std:: sort(B + 1, B + n + 1, cmp_1);
  28.     std:: sort(A + 1, A + m + 1, cmp_2);
  29.     int Answer = 0;
  30.     for(int i = 1, j = 1; i <= n; i ++) { // 对于每一只兔子寻找合适的炮 
  31.         for(; j <= m; j ++)
  32.             if(A[j].hit >= B[i]) Q.push(A[j]);
  33.             else break;
  34.         if(!Q.empty()) {
  35.             Node topp = Q.top();
  36.             Q.pop();
  37.             Answer += topp.money;
  38.         } else {
  39.             cout << "No Solution"; return 0; 
  40.         }
  41.     }
  42.     std:: cout << Answer;
  43.     return 0;
  44. }

H

题意：一个长度为M的正整数数组A，表示从左向右的地形高度。测试一种加农炮，炮弹平行于地面从左向右飞行，高度为H，如果某处地形的高度大于等于炮弹飞行的高度H（A[i] >= H），炮弹会被挡住并落在i - 1处，则A[i - 1] + 1。如果H <= A[0]，则这个炮弹无效，如果H > 所有的A[i]，这个炮弹也无效。现在给定N个整数的数组B代表炮弹高度，计算出最后地形的样子。
例如：地形高度A = {1, 2, 0, 4, 3, 2, 1, 5, 7}, 炮弹高度B = {2, 8, 0, 7, 6, 5, 3, 4, 5, 6, 5}，最终得到的地形高度为：{2, 2, 2, 4, 3, 3, 5, 6, 7}。

思路：对于每一个高度，预处理出应该落在哪里，对于每一发炮弹下落后影响的高度为 级别的，可以判断后调整，预处理时可以前缀最大值优化。

  1. #include <bits/stdc++.h>
  3. const int N = 50010;
  5. int n, m;
  6. int A[N], B[N];
  7. int hight[N * 22], Max_hight;
  8. int Maxn[N];
  9. int Answer[N];
  11. int main() {
  12.     std:: cin >> n >> m;
  13.     for(int i = 1; i <= n; i ++) std:: cin >> A[i];
  14.     for(int i = 1; i <= m; i ++) std:: cin >> B[i];
  15.     for(int i = 1; i <= m; i ++) Max_hight = std:: max(Max_hight, B[i]);
  16.     for(int i = 1; i <= n; i ++) Maxn[i] = std:: max(Maxn[i - 1], A[i]); // 前缀最大值
  17.     for(int i = 1; i <= n; i ++)
  18.         if(Maxn[i] != Maxn[i - 1])
  19.             for(int j = Maxn[i - 1] + 1; j <= Maxn[i]; j ++)
  20.                 hight[j] = i;
  21.     for(int j = Maxn[n] + 1; j <= Max_hight; j ++) hight[j] = n + 2;
  22.     for(int i = 1; i <= m; i ++) {
  23.         int H = hight[B[i]];
  24.         if(H > n || !H) continue ;
  25.         A[H - 1] ++;
  26.         hight[A[H - 1]] = std:: min(hight[A[H - 1]], H - 1);
  27.         hight[A[H - 1] - 1] = std:: min(hight[A[H - 1] - 1], H - 1);
  29.     }
  30.     for(int i = 1; i <= n; i ++) std:: cout << A[i] << "\n";
  31.     return 0;
  32. }

I

题意：有N行M列的正方形盒子。每个盒子有三种状态0, -1, +1。球从盒子上边或左边进入盒子，从下边或右边离开盒子。规则：
如果盒子的模式是-1，则进入它的球从下面出去。（方向变为向下）
如果盒子的模式是+1，则进入它的球从右面出去。 （反向变为向右）
如果盒子的模式是0， 则进入它的球方向不变。从上面进入的，从下面出去，从左面进入的，从右面出去。

思路：每个格子在经过后会变为相反数，经过一个格子的球的数目可以由该格子上方的格子向下走的数量 + 该格子左边的格子向右走的数量相加得到，该格子向右或向下走的数量又可以由该格子的初始状态决定
因此就可以完美递推啦

  1. #include <bits/stdc++.h>
  3. const int N = 1e3 + 10;
  5. int A[N][N];
  6. int n, m;
  7. long long k, Sum[N][N][2];
  9. inline long long read() {
  10.     long long x; char c = getchar();
  11.     while(c < '0' || c > '9') c = getchar();
  12.     while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  13.     return x;
  14. }
  16. int main() {
  17.     std:: cin >> m >> n >> k;
  18.     for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) std:: cin >> A[i][j];
  19.     for(int i = 1; i <= n; i ++) {
  20.         for(int j = 1; j <= m; j ++) {
  21.             if(i == 1 && j == 1) {
  22.                 if(A[1][1] == 1) Sum[1][1][1] = (k + 1) >> 1, Sum[1][1][0] = k >> 1;
  23.                 else if(A[1][1] == -1) Sum[1][1][0] = (k + 1) >> 1, Sum[1][1][1] = k >> 1;
  24.                 else Sum[1][1][0] = k;
  25.             } else {
  26.                 long long tmp = Sum[i - 1][j][0] + Sum[i][j - 1][1];
  27.                 if(!A[i][j]) Sum[i][j][0] = Sum[i - 1][j][0], Sum[i][j][1] = Sum[i][j - 1][1];
  28.                 else if(A[i][j] == 1) Sum[i][j][1] = (tmp + 1) >> 1, Sum[i][j][0] = tmp >> 1;
  29.                 else Sum[i][j][0] = (tmp + 1) >> 1, Sum[i][j][1] = tmp >> 1;
  30.             }
  31.         }
  32.     }
  33.     std:: cout << Sum[n][m][0];
  34.     return 0;
  35. }
  36. /*
  37. 3 2 4
  38. -1 0 -1
  39. 1 0 0
  40. */
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注