蓝桥杯小白打卡第五天

1230. 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 ] [i, j] [i,j] 是 K K K 倍区间。

你能求出数列中总共有多少个 K K K 倍区间吗？

输入格式

第一行包含两个整数 N N N 和 K K K。

以下 N N N 行每行包含一个整数 A i A_i Ai​。

输出格式

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

数据范围

1 ≤ N , K ≤ 100000 1 \leq N, K \leq 100000 1≤N,K≤100000， 1 ≤ A i ≤ 100000 1 \leq A_i \leq 100000 1≤Ai​≤100000

输入样例 5 2 1 2 3 4 5 输出样例 6 //如果按照模拟，那么则有下面的三重循环 int res=0; for(int l=1;l<=n;l++){ for(int r=1;r<=n;r++){ int sum=0; for(int i=l;i<=r;i++){ sum+=a[i]; sum%k==0; res++; } } } //此时，最里面的一重循环，由于是计算一段连续的子序列，因此可以使用前缀和来简化计算 //那么此时，就变成了 for(int l=1;l<=n;l++){ for(int r=1;r<=n;r++){ if(s[r]-s[l-1]%k==0) res++; } } //此时，s[r]-s[l-1]%k==0 -->也就是指s[r]%k==s[l-1]%k //所以我们只需要计算当前存在多少位于l之前的具有相同k的余数的前缀和 //对以上进行累加，那么就可以得到最终的结果 #include <iostream> #include <cstdio> using namespace std; typedef long long ll; const int N=1e5+10; int n,k;//使用数组进行相关数据的保存 long long a[N],s[N],res;//一共有1e5个数字，余数最高为1e5，那么数值最大为1e10 //int 最大大约为2e9，所以要用long long int main(){ cin>>n>>k; for(int i=1;i<=n;i++){ scanf("%lld",&a[i]);//输入数据 a[i]+=a[i-1];//前缀和计算 }//彻底完成数据输入 s[0]=1;//遍历出首个为k倍的前缀和时，它不需要模k左端点即可形成模k区间，为满足通解将0作为其模k左端点 for(int i=1;i<=n;i++){ int t=a[i]%k; res+=s[t]; s[t]++; } cout<<res; return 0; } 1205. 买不到的数目

小明开了一家糖果店，他采用别出心裁的包装方式：把水果糖包成4颗一包和7颗一包的两种，且糖果不能拆包卖。当小朋友来买糖时，他就用这两种包装来组合。然而，有些糖果数目是无法通过这两种包装组合出来的，例如要买10颗糖。

经测试，在这种4颗一包和7颗一包的包装情况下，最大不能买到的数量是17，即大于17的任何数字都可以用4和7组合出来。

本题要求

在已知两个包装的数量时，求最大不能组合出的数字。

输入格式

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

输出格式

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

数据范围 2 ≤ n, m ≤ 1000保证数据一定有解。 输入样例 4 7 输出样例 17

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

//由思考可知，本题目实际是不同包装糖果的排列组合，那么我们可以使用dfs #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n,m,res; bool dfs(int u){ if(u==0) return true; if(u>=m&&dfs(u-m)) return true; if(u>=n&&dfs(u-n)) return true; return false; } int main(){ cin>>n>>m;//输入每一包中糖果的数量 for(int i=0;i<=1000;i++){ if(!dfs(i)) res=i;//查看当前数字是不是最大的，无法表示出来的数字 } cout<<res; return 0; } 1211. 蚂蚁感冒

长100厘米的细长直杆子上有 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 ∣ < 100 0 < |X_i| < 100 0<∣Xi​∣<100 输入样例1 3 5 -2 8 输出样例1 1 输入样例2 5 -10 8 -20 12 25 输出样例2 3 #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 55; int n; int x[N]; int main() { cin >> n; for (int i = 0; i < n; i ++ ) cin >> x[i]; int left = 0, right = 0; // 分别表示初始位置小于x0且左边向右走的蚂蚁数量， //和初始位置大于x0且右边向左走的蚂蚁数量 for (int i = 1; i < n; i ++ ) if (abs(x[i]) < abs(x[0]) && x[i] > 0) left ++ ; else if (abs(x[i]) > abs(x[0]) && x[i] < 0) right ++ ; if (x[0] > 0 && right == 0 || x[0] < 0 && left == 0) cout << 1 << endl; else cout << left + right + 1 << endl; return 0; } 1216. 饮料换购

乐羊羊饮料厂正在举办促销优惠活动。乐羊羊C型饮料，凭借3个瓶盖就可以再换一瓶C型饮料，而且该活动可以一直循环下去（但不允许暂借或赊账）。

现在需要你计算一下，如果小明不浪费瓶盖，并且尽可能地参加活动，那么对于他初始买入的(n)瓶饮料，最后他总共能喝到多少瓶饮料。

输入格式

输入一个整数(n)， 表示初始买入的饮料数量。

输出格式

输出一个整数，表示一共能够喝到的饮料数量。

数据范围

(0 < n < 10000)

输入样例 100 输出样例 149 #include <iostream> using namespace std; int main() { int n; cin >> n; int res = n; while (n >= 3) { res += n / 3; n = n / 3 + n % 3; } cout << res << endl; return 0; }