济南网站建设公司排行,网站的建设求职简历,创手机网站,哪些网站可以做调查赚钱#x1f63d;PREFACE#x1f381;欢迎各位→点赞#x1f44d; 收藏⭐ 评论#x1f4dd;#x1f4e2;系列专栏#xff1a;算法经典题集#x1f50a;本专栏涉及到的知识点或者题目是算法专栏的补充与应用#x1f4aa;种一棵树最好是十年前其次是现在前缀和一维前缀和k倍…PREFACE欢迎各位→点赞 收藏⭐ 评论系列专栏算法经典题集本专栏涉及到的知识点或者题目是算法专栏的补充与应用种一棵树最好是十年前其次是现在前缀和一维前缀和k倍区间给定一个长度为 N 的数列A1,A2,…AN如果其中一段连续的子序列 Ai,Ai1,…Aj之和是 K 的倍数我们就称这个区间 [i,j] 是 K 倍区间。你能求出数列中总共有多少个 K 倍区间吗输入格式第一行包含两个整数 N 和 K。以下 N 行每行包含一个整数 Ai。输出格式输出一个整数代表 K 倍区间的数目。数据范围1≤N,K≤1000001≤Ai≤100000输入样例5 212345输出样例6分析求区间[l,r]的和是k的倍数的个数。求区间和我们可以通过前缀和来求出。我们规定sum[i]表示第1个元素到第i个元素的和。那么sum[r] - sum[l-1]就是区间[l,r]的和。区间[l,r]的和是k的倍数即(sum[r] - sum[l-1])%k 0 即sum[r]%k sum[l-1]%k。对前缀和取模之后两个相等的前缀和就能组成一个k倍区间。总共出现了3次模为1的情况而每两次模为1组合起来可以模0比如1,2加起来模为11,2,3,4,5加起来模为1那么这两种情况组合起来区间做减是3,4,5就是模为0的情况。所以一共出现了3次模为1的情况那么两两组合的情况一共有三种再加上本来模为0的情况有3次一共就6次模为0的情况。“k倍区间就加上cnt[sum[i]]”只是实现了计算模不为0的时候的情况两两组合的组合数量。按前缀和做差来想①11②123③1236④123410⑤12345153次模为1的情况是①②⑤两两组合后模为0即②-①2⑤-①234514⑤-②34512本来模为0的情况有③④组合后得到4即一共3种情况336#include iostream
#include cstdio
using namespace std;
int n, k;
int sum[100005], cnt[100005];
long long ans 0;
int main()
{scanf(%d%d, n, k);for (int i 1; i n; i){int x;scanf(%d, x);sum[i] (sum[i - 1] x) % k;// 求前缀和 ans cnt[sum[i]];// 加上在此之前与它同余的前缀和模k后 cnt[sum[i]];// 对前缀和模k后的余数统计出现次数 }printf(%lld, ans cnt[0]);return 0;
}二维前缀和激光炸弹地图上有 N 个目标用整数 Xi,Yi表示目标在地图上的位置每个目标都有一个价值 Wi。注意不同目标可能在同一位置。现在有一种新型的激光炸弹可以摧毁一个包含 R×R个位置的正方形内的所有目标。激光炸弹的投放是通过卫星定位的但其有一个缺点就是其爆炸范围即那个正方形的边必须和 xy轴平行。求一颗炸弹最多能炸掉地图上总价值为多少的目标。输入格式第一行输入正整数 N 和 R分别代表地图上的目标数目和正方形包含的横纵位置数量数据用空格隔开。接下来 N 行每行输入一组数据每组数据包括三个整数 Xi,Yi,Wi分别代表目标的 x 坐标y 坐标和价值数据用空格隔开。输出格式输出一个正整数代表一颗炸弹最多能炸掉地图上目标的总价值数目。数据范围0≤R≤10^90N≤100000≤Xi,Yi≤50000≤Wi≤1000输入样例2 10 0 11 1 1输出样例1#include bits/stdc.husing namespace std;const int N 5e3 10; int s[N][N];
int n, r;int main() {cin n r;r min(5001, r); // 因为r最大可以取 10^9for (int i 0; i n; i) {int x, y, w;cin x y w;s[x][y] w; //右移一位, 就不需要考虑边界了, 并且必须是, 不能是, 因为1个位置可能有多个目标}for (int i 1; i 5001; i) {for (int j 1; j 5001; j) {s[i][j] s[i - 1][j] s[i][j - 1] - s[i - 1][j - 1];}}int ans 0;for (int i r; i 5001; i) {for (int j r; j 5001; j) {ans max(ans, s[i][j] - s[i - r][j] - s[i][j - r] s[i - r][j - r]);}}cout ans endl;return 0;
}数学买不到的数目小明开了一家糖果店。他别出心裁把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。小朋友来买糖的时候他就用这两种包装来组合。当然有些糖果数目是无法组合出来的比如要买 10 颗糖。你可以用计算机测试一下在这种包装情况下最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。本题的要求就是在已知两个包装的数量时求最大不能组合出的数字。输入格式两个正整数 n,m表示每种包装中糖的颗数。输出格式一个正整数表示最大不能买到的糖数。数据范围2≤n,m≤1000保证数据一定有解。输入样例4 7输出样例17#include bits/stdc.h
using namespace std;
int main()
{int p,q;cinpq;cout(p-1)*(q-1)-1endl;return 0;
}蚂蚁感冒长 100 厘米的细长直杆子上有 n 只蚂蚁。它们的头有的朝左有的朝右。每只蚂蚁都只能沿着杆子向前爬速度是 1 厘米/秒。当两只蚂蚁碰面时它们会同时掉头往相反的方向爬行。这些蚂蚁中有 1 只蚂蚁感冒了。并且在和其它蚂蚁碰面时会把感冒传染给碰到的蚂蚁。请你计算当所有蚂蚁都爬离杆子时有多少只蚂蚁患上了感冒。输入格式第一行输入一个整数 n, 表示蚂蚁的总数。接着的一行是 n 个用空格分开的整数 Xi, Xi 的绝对值表示蚂蚁离开杆子左边端点的距离。正值表示头朝右负值表示头朝左数据中不会出现 0 值也不会出现两只蚂蚁占用同一位置。其中第一个数据代表的蚂蚁感冒了。输出格式输出1个整数表示最后感冒蚂蚁的数目。数据范围1n50,0|Xi|100输入样例135 -2 8输出样例11输入样例25-10 8 -20 12 25输出样例23#include bits/stdc.husing 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; // 分别表示左边向右走的蚂蚁数量和右边向左走的蚂蚁数量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;
}饮料换购乐羊羊饮料厂正在举办一次促销优惠活动。乐羊羊C型饮料凭3个瓶盖可以再换一瓶C型饮料并且可以一直循环下去(但不允许暂借或赊账)。请你计算一下如果小明不浪费瓶盖尽量地参加活动那么对于他初始买入的 n 瓶饮料最后他一共能喝到多少瓶饮料。输入格式输入一个整数 n,表示初始买入的饮料数量。输出格式输出一个整数表示一共能够喝到的饮料数量。数据范围0n10000输入样例100输出样例149#include iostreamusing 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;
}
