蓝桥杯小白打卡第五天
123
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 +
; 1
, … , A j A_i, A_{i +
; 1
}, \ldots, A_j Ai,Ai+
;1
,…,Aj 之和是 K K K 的倍数，我们就称这个区间 [ i , j ] 是 K K K 倍区间。
你能求出数列中统共有多少个 K K K 倍区间吗࿱
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
输入样例
5 2
1
2
3
4
5
输出样例
6
//如果按照模拟，那么则有下面的三重循环int res
1
;0;for(int l
1
;1
;l<
1
;n;l+
;+
;){ for(int r
1
;1
;r<
1
;n;r+
;+
;){ int sum
1
;0; for(int i
1
;l;i<
1
;r;i+
;+
;){ sum+
;
1
;a; sum%k
1
;
1
;0; res+
;+
;; } }}//此时，最内里的一重循环，由于是盘算一段连续的子序列，因此可以使用前缀和来简化盘算//那么此时，就变成了for(int l
1
;1
;l<
1
;n;l+
;+
;){ for(int r
1
;1
;r<
1
;n;r+
;+
;){ if(s-s[l-1
]%k
1
;
1
;0) res+
;+
;; }}//此时，s-s[l-1
]%k
1
;
1
;0 -->也就是指s%k
1
;
1
;s[l-1
]%k//所以我们只需要盘算当前存在多少位于l之前的具有相同k的余数的前缀和//对以上进行累加，那么就可以得到最终的效果#include <iostream>#include <cstdio>using namespace std;typedef long long ll;const int N
1
;1
e5+
;1
0;int n,k;//使用数组进行相关数据的保存long long a,s,res;//一共有1
e5个数字，余数最高为1
e5，那么数值最大为1
e1
0//int 最大大约为2e9，所以要用long longint main(){ cin>>n>>k; for(int i
1
;1
;i<
1
;n;i+
;+
;){ scanf(
4;%lld
4;,&a);//输入数据 a+
;
1
;a[i-1
];//前缀和盘算 }//彻底完成数据输入 s
1
;1
;//遍历出首个为k倍的前缀和时，它不需要模k左端点即可形成模k区间，为满足通解将0作为其模k左端点 for(int i
1
;1
;i<
1
;n;i+
;+
;){ int t
1
;a%k; res+
;
1
;s; s+
;+
;; } cout<<res; return 0;} 1
205. 买不到的数目
小明开了一家糖果店，他采用别出心裁的包装方式࿱
a;把水果糖包成4颗一包和7颗一包的两种，且糖果不能拆包卖。当小朋侪来买糖时，他就用这两种包装来组合。然而，有些糖果数目是无法通过这两种包装组合出来的，例如要买1
0颗糖。
经测试，在这种4颗一包和7颗一包的包装情况下，最大不能买到的数目是1
7
，即大于1
7
的任何数字都可以用4和7组合出来。
本题要求
在已知两个包装的数目时，求最大不能组合出的数字。
输入格式
两个正整数 n，m，表示每种包装中糖的颗数。
输特别式
一个正整数，表示最大不能买到的糖数。
数据范围
[*]2 ≤ n, m ≤ 1
000
[*]包管数据肯定有解。
输入样例
4 7
输出样例
1
7
由于这种题目属于数学题目，在不知道相应定理的情况下，无法写出最优解，所以这里只提供暴力解法（会超时间）
//由思索可知，本题目实际是差别包装糖果的排列组合，那么我们可以使用dfs#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int n,m,res;bool dfs(int u){ if(u
1
;
1
;0) return true; if(u>
1
;m&&dfs(u-m)) return true; if(u>
1
;n&&dfs(u-n)) return true; return false;}int main(){ cin>>n>>m;//输入每一包中糖果的数目 for(int i
1
;0;i<
1
;1
000;i+
;+
;){ if(!dfs(i)) res
1
;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
3
5 -2 8
输出样例1
1
输入样例2
5-1
0 8 -20 1
2 25 输出样例2
3
#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N 
1
; 55;int n;int x;int main(){ cin >> n; for (int i 
1
; 0; i < n; i +
;+
; ) cin >> x; int left 
1
; 0, right 
1
; 0; // 分别表示初始位置小于x0且左边向右走的蚂蚁数目， //和初始位置大于x0且右边向左走的蚂蚁数目 for (int i 
1
; 1
; i < n; i +
;+
; ) if (abs(x) < abs(x) && x > 0) left +
;+
; ; else if (abs(x) > abs(x) && x < 0) right +
;+
; ; if (x > 0 && right 
1
;
1
; 0 || x < 0 && left 
1
;
1
; 0) cout << 1
<< endl; else cout << left +
; right +
; 1
<< endl; return 0;} 1
21
6
. 饮料换购
乐羊羊饮料厂正在举行促销优惠活动。乐羊羊C型饮料，依附3
个瓶盖就可以再换一瓶C型饮料，而且该活动可以一直循环下去（但不允许暂借或赊账）。
现在需要你盘算一下，如果小明不浪费瓶盖，并且尽可能地参加活动，那么对于他初始买入的(n)瓶饮料，最后他统共能喝到多少瓶饮料。
输入格式
输入一个整数(n)， 表示初始买入的饮料数目。
输特别式
输出一个整数，表示一共能够喝到的饮料数目。
数据范围
(0 < n < 1
0000)
输入样例
1
00 输出样例
1
49 #include <iostream>using namespace std;int main(){ int n; cin >> n; int res 
1
; n; while (n >
1
; 3
) { res +
;
1
; n / 3
; n 
1
; n / 3
+
; n % 3
; } cout << res << endl; return 0;}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao1
23
.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]