蓝桥杯小白打卡第五天

1
23
0. K倍区间

题目描述

给定一个长度为                                    N                              N                  N 的数列，                                             A                            1
                                  ,                                   A                            2                                  ,                         …                         ,                                   A                            N                                       A_1
, A_2, \ldots, A_N                  A1
​,A2​,…,AN​，如果此中一段连续的子序列                                              A                            i                                  ,                                   A                                       i                               &#43
;                               1
                                            ,                         …                         ,                                   A                            j                                       A_i, A_{i &#43
; 1
}, \ldots, A_j                  Ai​,Ai&#43
;1
​,…,Aj​ 之和是                                    K                              K                  K 的倍数，我们就称这个区间                                    [                         i                         ,                         j                         ]                              [i, j]                  [i,j] 是                                    K                              K                  K 倍区间。
你能求出数列中统共有多少个                                    K                              K                  K 倍区间吗&#xff1
f;
输入格式

第一行包含两个整数                                    N                              N                  N 和                                    K                              K                  K。
以下                                    N                              N                  N 行每行包含一个整数                                              A                            i                                       A_i                  Ai​。
输特别式

输出一个整数，代表                                    K                              K                  K 倍区间的数目。
数据范围

                                    1
                         ≤                         N                         ,                         K                         ≤                         1
00000                              1
\leq N, K \leq 1
00000                  1
≤N,K≤1
00000，
                                    1
                         ≤                                   A                            i                                  ≤                         1
00000                              1
\leq A_i \leq 1
00000                  1
≤Ai​≤1
00000
输入样例

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

复制代码

输出样例

1. 6

复制代码

1. //如果按照模拟，那么则有下面的三重循环int res&#6
2. 1
3. ;0;for(int l&#6
4. 1
5. ;1
6. ;l<&#6
7. 1
8. ;n;l&#43
9. ;&#43
10. ;){    for(int r&#6
11. 1
12. ;1
13. ;r<&#6
14. 1
15. ;n;r&#43
16. ;&#43
17. ;){        int sum&#6
18. 1
19. ;0;        for(int i&#6
20. 1
21. ;l;i<&#6
22. 1
23. ;r;i&#43
24. ;&#43
25. ;){            sum&#43
26. ;&#6
27. 1
28. ;a[i];            sum%k&#6
29. 1
30. ;&#6
31. 1
32. ;0;            res&#43
33. ;&#43
34. ;;        }    }}//此时，最内里的一重循环，由于是盘算一段连续的子序列，因此可以使用前缀和来简化盘算//那么此时，就变成了for(int l&#6
35. 1
36. ;1
37. ;l<&#6
38. 1
39. ;n;l&#43
40. ;&#43
41. ;){    for(int r&#6
42. 1
43. ;1
44. ;r<&#6
45. 1
46. ;n;r&#43
47. ;&#43
48. ;){        if(s[r]-s[l-1
49. ]%k&#6
50. 1
51. ;&#6
52. 1
53. ;0) res&#43
54. ;&#43
55. ;;    }}//此时，s[r]-s[l-1
56. ]%k&#6
57. 1
58. ;&#6
59. 1
60. ;0 -->也就是指s[r]%k&#6
61. 1
62. ;&#6
63. 1
64. ;s[l-1
65. ]%k//所以我们只需要盘算当前存在多少位于l之前的具有相同k的余数的前缀和//对以上进行累加，那么就可以得到最终的效果#include <iostream>#include <cstdio>using namespace std;typedef long long ll;const int N&#6
66. 1
67. ;1
68. e5&#43
69. ;1
70. 0;int n,k;//使用数组进行相关数据的保存long long a[N],s[N],res;//一共有1
71. e5个数字，余数最高为1
72. e5，那么数值最大为1
73. e1
74. 0//int 最大大约为2e9，所以要用long longint main(){    cin>>n>>k;    for(int i&#6
75. 1
76. ;1
77. ;i<&#6
78. 1
79. ;n;i&#43
80. ;&#43
81. ;){        scanf(&#3
82. 4;%lld&#3
83. 4;,&a[i]);//输入数据        a[i]&#43
84. ;&#6
85. 1
86. ;a[i-1
87. ];//前缀和盘算    }//彻底完成数据输入    s[0]&#6
88. 1
89. ;1
90. ;//遍历出首个为k倍的前缀和时，它不需要模k左端点即可形成模k区间，为满足通解将0作为其模k左端点    for(int i&#6
91. 1
92. ;1
93. ;i<&#6
94. 1
95. ;n;i&#43
96. ;&#43
97. ;){        int t&#6
98. 1
99. ;a[i]%k;        res&#43
100. ;&#6
101. 1
102. ;s[t];        s[t]&#43
103. ;&#43
104. ;;    }        cout<<res;    return 0;}

复制代码

1
205. 买不到的数目

小明开了一家糖果店，他采用别出心裁的包装方式&#xff1
a;把水果糖包成4颗一包和7颗一包的两种，且糖果不能拆包卖。当小朋侪来买糖时，他就用这两种包装来组合。然而，有些糖果数目是无法通过这两种包装组合出来的，例如要买1
0颗糖。
经测试，在这种4颗一包和7颗一包的包装情况下，最大不能买到的数目是1
7
，即大于1
7
的任何数字都可以用4和7组合出来。
本题要求

在已知两个包装的数目时，求最大不能组合出的数字。
输入格式

两个正整数 n，m，表示每种包装中糖的颗数。
输特别式

一个正整数，表示最大不能买到的糖数。
数据范围

• 2 ≤ n, m ≤ 1
  000
  
• 包管数据肯定有解。
  

输入样例

1. 4 7

复制代码

输出样例

1. 1
2. 7

复制代码

由于这种题目属于数学题目，在不知道相应定理的情况下，无法写出最优解，所以这里只提供暴力解法（会超时间）

1. //由思索可知，本题目实际是差别包装糖果的排列组合，那么我们可以使用dfs#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int n,m,res;bool dfs(int u){    if(u&#6
2. 1
3. ;&#6
4. 1
5. ;0) return true;    if(u>&#6
6. 1
7. ;m&&dfs(u-m)) return true;    if(u>&#6
8. 1
9. ;n&&dfs(u-n)) return true;        return false;}int main(){    cin>>n>>m;//输入每一包中糖果的数目    for(int i&#6
10. 1
11. ;0;i<&#6
12. 1
13. ;1
14. 000;i&#43
15. ;&#43
16. ;){        if(!dfs(i)) res&#6
17. 1
18. ;i;//检察当前数字是不是最大的，无法表示出来的数字    }    cout<<res;    return 0;}

复制代码

1
21
1
. 蚂蚁感冒

长1
00厘米的细长直杆子上有                                    n                              n                  n 只蚂蚁。它们的头部朝向不一，有的朝左，有的朝右。每只蚂蚁都只能沿着杆子以1
厘米/秒的速率向前爬行。当两只蚂蚁相遇时，它们会同时掉头往相反方向爬行。这些蚂蚁中有1
只蚂蚁感冒了，并且在与其他蚂蚁碰面时，会将感冒传染给遇到的蚂蚁。要求盘算当所有蚂蚁都爬离杆子时，患上感冒的蚂蚁数目。
输入格式

• 第一行输入一个整数                                         n                                  n                     n，表示蚂蚁的总数。
  
• 第二行是                                         n                                  n                     n 个用空格分开的整数                                                    X                               i                                            X_i                     Xi​，                                                   X                               i                                            X_i                     Xi​ 的绝对值表示蚂蚁离开杆子左边端点的距离。此中正值表示蚂蚁头朝右，负值表示蚂蚁头朝左。数据中不会出现0值，也不会出现两只蚂蚁占用同一位置的情况。并且第一个数据所代表的蚂蚁是感冒的。
  

输特别式

输出一个整数，表示最后感冒蚂蚁的数目。
数据范围

•                                         1
                              <                            n                            <                            50                                  1
  < n < 50                     1
  <n<50
  
•                                         0                            <                            ∣                                       X                               i                                      ∣                            <                            1
  00                                  0 < |X_i| < 1
  00                     0<∣Xi​∣<1
  00
  

输入样例1

1. 3
3. 5 -2 8

复制代码

输出样例1

1. 1

复制代码

输入样例2

1. 5-1
2. 0 8 -20 1
3. 2 25

复制代码

输出样例2

1. 3

复制代码

1. #include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N &#6
2. 1
3. ; 55;int n;int x[N];int main(){    cin >> n;    for (int i &#6
4. 1
5. ; 0; i < n; i &#43
6. ;&#43
7. ; ) cin >> x[i];    int left &#6
8. 1
9. ; 0, right &#6
10. 1
11. ; 0;    // 分别表示初始位置小于x0且左边向右走的蚂蚁数目，    //和初始位置大于x0且右边向左走的蚂蚁数目    for (int i &#6
12. 1
13. ; 1
14. ; i < n; i &#43
15. ;&#43
16. ; )        if (abs(x[i]) < abs(x[0]) && x[i] > 0) left &#43
17. ;&#43
18. ; ;        else if (abs(x[i]) > abs(x[0]) && x[i] < 0) right &#43
19. ;&#43
20. ; ;    if (x[0] > 0 && right &#6
21. 1
22. ;&#6
23. 1
24. ; 0 || x[0] < 0 && left &#6
25. 1
26. ;&#6
27. 1
28. ; 0) cout << 1
29. << endl;    else cout << left &#43
30. ; right &#43
31. ; 1
32. << endl;    return 0;}

复制代码

1
21
6
. 饮料换购

乐羊羊饮料厂正在举行促销优惠活动。乐羊羊C型饮料，依附3
个瓶盖就可以再换一瓶C型饮料，而且该活动可以一直循环下去（但不允许暂借或赊账）。
现在需要你盘算一下，如果小明不浪费瓶盖，并且尽可能地参加活动，那么对于他初始买入的(n)瓶饮料，最后他统共能喝到多少瓶饮料。
输入格式

输入一个整数(n)， 表示初始买入的饮料数目。
输特别式

输出一个整数，表示一共能够喝到的饮料数目。
数据范围

(0 < n < 1
0000)
输入样例

1. 1
2. 00

复制代码

输出样例

1. 1
2. 49

复制代码

1. #include <iostream>using namespace std;int main(){    int n;    cin >> n;    int res &#6
2. 1
3. ; n;    while (n >&#6
4. 1
5. ; 3
6. )    {        res &#43
7. ;&#6
8. 1
9. ; n / 3
10. ;        n &#6
11. 1
12. ; n / 3
13. &#43
14. ; n % 3
15. ;    }    cout << res << endl;    return 0;}

复制代码

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