题目一解析
给定一个按照升序排列的长度为n的整数数组,以及 q 个查询。
对于每个查询,返回一个元素k的起始位置和终止位置(位置从0开始计数)。
如果数组中不存在该元素,则返回“-1 -1”。
输入格式
第一行包含整数n和q,表示数组长度和询问个数。
第二行包含n个整数(均在1~10000范围内),表示完整数组。
接下来q行,每行包含一个整数k,表示一个询问元素。
输出格式
共q行,每行包含两个整数,表示所求元素的起始位置和终止位置。
如果数组中不存在该元素,则返回“-1 -1”。
数据范围
1≤n≤100000
1≤n≤100000
1≤q≤10000
1≤q≤10000
1≤k≤10000
1≤k≤10000
样例
输入样例:
6 3
1 2 2 3 3 4
3
4
5
输出样例:
3 4
5 5
-1 -1
算法原理
本题是练习二分很好的一道题目,二分程序虽然简单,但是如果写之前不考虑好想要查找的是什么,十有八九会是死循环或者查找错误,就算侥幸写对了也只是运气好而已。
用二分去查找元素要求数组的有序性或者拥有类似于有序的性质,对本题而言,一个包含重复元素的有序序列,要求输出某元素出现的起始位置和终止位置,翻译一下就是:在数组中查找某元素,找不到就输出−1
找到了就输出不小于该元素的最小位置和不大于该元素的最大位置。所以,需要写两个二分,一个需要找到>=x的第一个数,另一个需要找到<=x的最后一个数。查找不小于x的第一个位置,较为简单:
int l = 0, r = n - 1; while (l < r) { int mid = l + r >> 1; if (a[mid] < x) l = mid + 1; else r = mid; }
当a[mid]<x时,令l=mid+1,mid及其左边的位置被排除了,可能出现解的位置是mid+1及其后面的位置。
当a[mid]>=x时,说明mid及其左边可能含有值为x的元素。
当查找结束时,l与r相遇,l所在元素若是x则一定是x出现最小位置,因为l左边的元素必然都小于x。
查找不大于x的最后一个位置,便不容易了:
int l1 = l, r1 = n; while (l1 + 1 < r1) { int mid = l1 + r1 >> 1; if (a[mid] <= x) l1 = mid; else r1 = mid; }
要查找不大于x的最后一个位置:
当a[mid]<=x时,待查找元素只可能在mid及其后面,所以l=mid;
当a[mid]>x时,待查找元素只会在mid左边,令r=mid。
int l = 0, r = n - 1; while (l < r) { int mid = l + r + 1 >> 1; if (a[mid] <= x) l = mid; else r = mid - 1; }
int l1 = l, r1 = n - 1; while (l1 < r1) { int mid = l1 + r1 >> 1; if (a[mid] <= x) l1 = mid + 1; else r1 = mid - 1; } printf("%d %d\n", l, l1 - (a[l1] == x ? 0 : 1));
代码实现
#include <iostream> using namespace std; const int maxn = 100005; int n, q, x, a[maxn]; int main() { cin>>n>>q; for (int i = 0; i < n; i++) cin>>a[i]; while (q--) { scanf("%d", &x); int l = 0, r = n - 1; while (l < r) { int mid = l + r >> 1; if (a[mid] < x) l = mid + 1; else r = mid; } if (a[l] != x) { printf("-1 -1\n"); continue; } int l1 = l, r1 = n; while (l1 + 1 < r1) { int mid = l1 + r1 >> 1; if (a[mid] <= x) l1 = mid; else r1 = mid; } cout<<l<<" "<<l1<<endl; } return 0; }
题目二解析
给定一个浮点数 n,求它的三次方根。
输入格式
共一行,包含一个浮点数 n。
输出格式
共一行,包含一个浮点数,表示问题的解。
注意,结果保留 6 位小数。
数据范围
−10000≤n≤10000
输入样例:
1000.00
输出样例:
10.000000
算法原理
这道题是一个浮点二分的题目
代码实现
#include <iostream> #include <cstdio> using namespace std; double x; int main() { cin >> x; // 确定边界值 double l = -100000, r = 100000; // 注意循环条件处理精度问题 while (r - l > 1e-8) { // 步骤 A: 找中间值 double mid = (l + r) / 2; // 步骤 B: 判断 if (mid * mid * mid < x) l = mid; else r = mid; } printf("%.6f", r); return 0; }
题目三解析
输入一个长度为 n 的整数序列。
接下来再输入 m个询问,每个询问输入一对 l,r。
对于每个询问,输出原序列中从第 l个数到第 r个数的和。
输入格式
第一行包含两个整数 n和 m。
第二行包含 n个整数,表示整数数列。
接下来 m行,每行包含两个整数 l 和 r,表示一个询问的区间范围。
输出格式
共 m行,每行输出一个询问的结果。
数据范围
1 ≤l ≤ r ≤ n,
1 ≤ n,m ≤ 100000,
−1000≤数列中元素的值≤1000
输入样例:
5 3
2 1 3 6 4
1 2
1 3
2 4
输出样例:
3
6
10
算法原理
本题用到了前缀和的知识:
什么是前缀和?
数列的和时,Sn = a1+a2+a3+…an; Sn就是数列的前 n 项和。
前缀和就是新建一个数组,新建数组中保存原数组前 n 项的和。
前缀和有什么用?
快速求某个区间中所有元素的加和。
例 S4 = a1 + a2 + a3 + a4; S1 = a1。所以可以通过 S4-S1 得到 a2+a3+a4 的值。
代码实现
#include <iostream> using namespace std; const int N = 100010; int a[N];//保存原数组 int s[N];//保存前缀和 int main() { int n, m; cin >> n >> m; //从a[1]开始保存。a[0]是0 for(int i = 1; i <= n; ++i) { cin >> a[i]; } s[0] = 0; //计算前缀和 for(int i = 1; i <= n; ++i) s[i] = s[i - 1] + a[i]; for(int i = 0; i < m; ++i) { int l, r;//保存区间 cin >> l >> r; //s[r] = a[1]+ ··· + a[r] //s[l - 1] = a[1]+ ··· + a[l - 1] //s[r] - s[l - 1] = a[l] + ··· + a[r] cout << s[r] - s[l - 1] << endl; } }
题目四解析
输入一个 n 行 m列的整数矩阵,再输入 q个询问,每个询问包含四个整数 x1,y1,x2,y2,表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 n,m,q
。
接下来 n行,每行包含 m个整数,表示整数矩阵。
接下来 q行,每行包含四个整数 x1,y1,x2,y2,表示一组询问。
输出格式
共 q 行,每行输出一个询问的结果。
算法原理
一步一步学会二维前缀和的推导
给出一个二维数组,在给出一个子数组的左上角坐标、右下角坐标,求出子数组中的所有元素的和。
用s[i,j]表示(1,1)~(i,j)的和。
先看看s[i,j]怎么求:
s[1,1] = a[1,1] s[1,2] = a[1,1] + a[1,2] = s[1,1] + a[1,2] s[1,3] = a[1,1] + a[1,2] + a[1,3] = s[1,2] + a[1,3] s[2,1] = a[1,1] + a[2,1] = s[1,1] + a[2,1] s[2,2] = a[1,1] + a[1,2] + a[2,1] + a[2,2] = s[1,2] + s[2,1] - s[1,1] + a[2, 3] s[2,3] = a[1,1] + a[1,2] + a[1,3] + a[2,1] + a[2,2] + a[2,3] = s[1,3] + s[2,2] - s[1,2] + a[2, 3]
可以得到一下公式:
s[i,j] = s[ i−1,j ]+ s [ i , j−1 ] - s[ i−1, j−1 ]+ a[ i ][ j ]
也就是,可以在o(n2)的时间复杂度内求出所有s
当求出 s,求 (x1,y1)~(x2,y2)的和
如图所示:黄色部分 = 紫色框 - 蓝色框 - 红色框 + 黑色框。
也就是:
所以当求出 s 后,就能在 o(1)的时间复杂度内,求出子矩阵的和。
所以总时间复杂度是:o(n2)
#include <iostream> using namespace std; const int N = 1010; int a[N][N]; int s[N][N]; int m, n, q; int main(){ cin >> n >> m >> q; for(int i = 1; i <= n; i++) { for(int j = 1; j <=m; j++) { cin >> a[i][j]; } } // 求 s[i, j] for(int i = 1; i <= n; i++) { for(int j = 1; j <=m; j++) { s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]; } } while(q > 0) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; // 求子矩阵和 cout << s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] << endl; q --; } }
题目五解析
算法原理
算法一(贪心)
题意:就是要我们找到最小值让机器人可以达到终点
我们先看一组样例:3 4 3 2 4
要想它最小,我们可以直接从最后面开始运算,初始化他的代价为0,我们设初值为x
代码实现
#include<bits/stdc++.h> using namespace std; const int N=100010; int num[N]; int n; int main() { cin>>n; for(int i=0;i<n;i++)cin>>num[i]; int res = 0; for(int i = n - 1; i >= 0; i--) { if((num[i] + res) % 2 == 0) res = (num[i] + res) / 2; else res = (num[i] + res) / 2 + 1; } cout<<res<<endl; }
算法二:容器
#include<bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> v(n); for (int i = 0; i < n; ++i) cin >> v[i]; int res = 0; for (int i = n-1; i >= 0; i--) { if((v[i] + res) % 2 == 0) res = (v[i] + res) / 2; else res = (v[i] + res) / 2 + 1; } cout << res << endl; return 0; }
题目六解析
四平方和定理,又称为拉格朗日定理:
每个正整数都可以表示为至多 4个正整数的平方和。
如果把 0包括进去,就正好可以表示为 4个数的平方和。
比如:
5=02+02+12+22
7=12+12+12+22
对于一个给定的正整数,可能存在多种平方和的表示法。
要求你对 4个数排序:
0 ≤ a ≤ b ≤ c ≤ d
并对所有的可能表示法按 a,b,c,d为联合主键升序排列,最后输出第一个表示法。
输入格式
输入一个正整数 N。
输出格式
输出4个非负整数,按从小到大排序,中间用空格分开。
数据范围
0<N<5∗106
输入样例:
5
输出样例:
0 0 1 2
算法原理
根据题意,直接四重循环暴力枚举a,b,c,d,意料之中的超时了,后来慢慢优化,优化成三重循环,仍然不行(当时没有理解清楚到 a <= b<= c<= d这个关系),再然后,就想到了打表
- 建立哈希表,存储小于n的数c,假设e = c^2 + d^2,则h[e] = c,从小到大遍历c, d只存储先出现的(因为字典序小)
- 从小到大遍历a、b,查找1中建立的哈希表,若 h[n - a^2 - b^2]存在,则算出d,
代码实现
#include<iostream> #include<cmath> using namespace std; const int N = 1e8 + 10; int h[N]; int main() { int n; cin >> n; //打表,找出1 - n,所有完全平方数两两之和,如果存在只记第一次出现(题目要求找出字典序小的) for (int i = 0; i * i * 2<= n; i++) { for (int j = i; j * j + i * i <= n; j++) { if (!h[i * i + j * j]) h[i * i + j * j] = i + 1;//防止i = 0时在后面判断查找跳过 i = 0的情况 } } //0<= a <= b <= c <= d,可以得出a^2 <= n / 4, a^2 + b^ 2 <= n / 2; for (int i = 0; i * i * 4 <= n; i++) { for (int j = i; j * j + i * i <= n / 2; j++) { int t = n - i * i - j * j; if (h[t]) { int c = h[t] - 1; //防止开根号后因为精度关系,向下取整,例:25 开根号得到4.99999向下取整为4; int d = (sqrt(t - c * c) + 1e-4); printf("%d %d %d %d", i, j, c, d); return 0; } } } return 0; }
题目七解析
儿童节那天有 K 位小朋友到小明家做客。
小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N块巧克力,其中第 i块是 Hi×Wi的方格组成的长方形。
为了公平起见,小明需要从这 N块巧克力中切出 K块巧克力分给小朋友们。
切出的巧克力需要满足:
形状是正方形,边长是整数大小相同
例如一块 6×5的巧克力可以切出 6
块 2×2 的巧克力或者 2块 3×3的巧克力。
当然小朋友们都希望得到的巧克力尽可能大,你能帮小明计算出最大的边长是多少么?
输入格式
第一行包含两个整数 N和 K。
以下 N行每行包含两个整数 Hi和 Wi。
输入保证每位小朋友至少能获得一块 1×1
的巧克力。
输出格式
输出切出的正方形巧克力最大可能的边长。
数据范围
1≤N,K≤105,
1≤Hi,Wi≤105
输入样例:
2 10
6 5
5 6
输出样例:
2
算法原理
思路:
小巧克力边长 a 一定在 1 – 100000 之间
答案即为:在 1 – 100000 之间找到一个最大的数,使得所有的 (w[i]/a) * (h[i]/a) 之和大于要求的数量 k。
使用二分法找到 a 的最大取值即为答案。
代码实现
#include <iostream> using namespace std; int const N = 100010; int w[N], h[N];//存储长、宽 int n, k; bool chack(int a) { int num = 0;//记录分成长度为 a 的巧克力数量 for (int i = 0; i < n; i++) { num += (w[i] / a) * (h[i] / a);//每一大块可以分成的边长为 a 的巧克力数量 if (num >= k) return true;//大于要求数量,返回真 } return false; } int main() { cin >> n >> k; for (int i = 0; i < n; i++) cin >> h[i] >> w[i]; int l = 1, r = 1e5;//小巧克力数量边长一定在 1 -- 100000 之间 while (l < r)//二分小巧克力边长范围,找到符合要求的最大值 { int mid = l + (r - l + 1 >> 1);//因为l = mid ,所以 mid 取 l + r + 1 >> 1,为了防止加和越界,改写成 l + (r - l + 1 >> 1) if (chack(mid)) l = mid; else r = mid - 1; } cout << r; }
题目八解析
地图上有 N个目标点,用整数 Xi,Yi表示目标在地图上的位置,每个目标都有一个价值 Wi。
注意:不同目标可能在同一位置。
现在有一种新型的激光炸弹,可以摧毁一个包含 R×R个位置的正方形内的所有目标。
激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆炸范围,即那个正方形的边必须和 x,y轴平行。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。
输入格式
第一行输入正整数 N和 R,分别代表地图上的目标数目和正方形包含的横纵位置数量,数据用空格隔开。
接下来 N 行,每行输入一组数据,每组数据包括三个整数 Xi,Yi,Wi,分别代表目标的 x 坐标,y坐标和价值,数据用空格隔开。
输出格式
输出一个正整数,代表一颗炸弹最多能炸掉地图上目标的总价值数目。
算法原理
代码实现
// // Created by Genes on 2020/12/2. // // 激光炸弹 #include <algorithm> #include <iostream> #define ios \ ios::sync_with_stdio(false); \ cin.tie(nullptr); \ cout.tie(nullptr) using namespace std; const int N = 5e3 + 10; //不能开 1e5+10, 内存限制比较严格 int s[N][N]; int n, r; int main() { ios; cin >> n >> r; r = min(5001, r); // 因为r最大可以取 10^9 for (int i = 0; i < n; i++) { int x, y, w; cin >> x >> y >> w; // s[++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] + s[i][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; }
题目九解析
给定一个长度为 N 的数列,A1,A2,…AN,如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K的倍数,我们就称这个区间 [i,j]是 K倍区间。
你能求出数列中总共有多少个 K倍区间吗?
输入格式
第一行包含两个整数 N 和 K。
以下 N
行每行包含一个整数 Ai。
输出格式
输出一个整数,代表 K倍区间的数目。
算法原理
思路:一眼看去我们就可以知道这个算法用的前缀和,
分析:
求区间[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
如果你觉得文字难以理解,那么看图:
代码实现
#include<bits/stdc++.h> using namespace std; const int N=100010; typedef long long ll; int sum[N],a[N],res[N]; int n,k; ll ans=0; int main() { cin>>n>>k; for(int i=1;i<=n;i++) { cin>>a[i]; sum[i]=(sum[i-1]+a[i])%k;//前缀和取模 ans+=res[sum[i]];//更新答案 res[sum[i]]++;//两个相等的前缀和就能组成一个k倍区间 } cout<<ans+res[0]<<endl; return 0; }