第三节课贪心River Hopscotch解题思路二分贪心用二分法求最大的最短距离 mid (left right 1) / 2; 向上取整寻找最大可行解用贪心保留尽可能多的岩石所以最后一个保留岩石是尽可能靠右的如果它到终点距离不足那么任何更靠左的岩石到终点距离更大#include iostream #include vector #include algorithm using namespace std; int L, N, M; vectorint rocks; // 判断当最短距离至少为 d 时能否通过移除不超M个岩石实 bool check(int d) { int cnt 0; // 移除的岩石数? int last 0; // 上一个保留的岩石位置起点为 for (int i 0; i N; i) { if (rocks[i] - last d) { cnt; // 距离不足移除当前岩 } else { last rocks[i]; // 距离足够保留当前岩 } } // 检查终点与最后一个保留岩石的距离 if (L - last d) { if (last 0) return false; // 起点不可移除且距离不足 cnt; // 移除最后一个保留岩 } return cnt M; } int main() { cin L N M; rocks.resize(N); // rocks 的大小调整为 N for (int i 0; i N; i) { cin rocks[i]; } sort(rocks.begin(), rocks.end()); int lo 0, hi L; // 最短距离不可能超过 L while (lo hi) { int mid (lo hi 1) / 2; // 上取整寻找最大可行解 if (check(mid)) { lo mid; } else { hi mid - 1; } } cout lo endl; //输出最大的最少距离 return 0; }稀疏表Balanced Lineup(不太?)利用稀疏表(直接用数组会超时)#include iostream // 用于输入输出 #include vector // 用于动态数组 #include cmath // 用于 log2 函数 #include algorithm // 用于 min max 函数 using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, Q; cin N Q; vectorint height(N 1); // 高度数组下标从 1 开始方便与区间起点对 for (int i 1; i N; i) { cin height[i]; // 读入每头奶牛的高 } // 预处log2 值便于查询时快速计k floor(log2(len)) vectorint log2(N 1); log2[1] 0; // 2^0 1 for (int i 2; i N; i) { log2[i] log2[i / 2] 1; // 递推计算 log2(i) 的整数部分 } int K log2[N] 1; // 稀疏表的层数因为最大区间长度为 N // 创建两个稀疏表st_min[k][i] 表示 i 开始长度为 2^k 的区间最小值 // st_max[k][i] 表示最大值 vectorvectorint st_min(K, vectorint(N 1)); vectorvectorint st_max(K, vectorint(N 1)); // ? 0 层长度? 1 的区间最小值与最大值都是该位置的高? for (int i 1; i N; i) { st_min[0][i] height[i]; st_max[0][i] height[i]; } // 构建稀疏表k ? 1 ? K-1 for (int k 1; k K; k) { int len 1 (k - 1); // 左半段和右半段的长度均为 2^(k-1) for (int i 1; i (1 k) - 1 N; i) { // 区间 [i, i2^k-1] 的最小? min(左半段最小?, 右半段最小?) st_min[k][i] min(st_min[k-1][i], st_min[k-1][i len]); // 最大值同? st_max[k][i] max(st_max[k-1][i], st_max[k-1][i len]); } } // 处理每一个查? for (int q 0; q Q; q) { int A, B; cin A B; // 读取查询的区? [A, B] int len B - A 1; // 区间长度 int k log2[len]; // 最大的 k 使得 2^k len // 对于区间 [A, B]用两个长度? 2^k 的子区间覆盖? // 左子区间 [A, A2^k-1]右子区? [B-2^k1, B] int min_val min(st_min[k][A], st_min[k][B - (1 k) 1]); int max_val max(st_max[k][A], st_max[k][B - (1 k) 1]); cout max_val - min_val \n; // 输出最高与最矮的身高? } return 0; // 程序正常结束 }二分法幂次方快速幂算法:利用指数每次除以2的思路来大幅减少乘法次数核心思想:要计算ana^nan可以按指数奇偶性分解如果ana^nan是偶数an(an/2)2a^n (a^{n/2})^2an(an/2)2如果ana^nan是奇数ana∗(a(n−1)/2)2a^n a *(a^{(n-1)/2})^2ana∗(a(n−1)/2)2这样每次将指数减半只需要O(logn)O(logn)O(logn)次乘法运算而不是O(n)O(n)O(n)次举例说明计算3133^{13}31313 是奇数 →3133×(36)23^{13}3×(3^6)^23133×(36)26 是偶数 →36(33)23 ^6 (3 ^3)^236(33)23 是奇数 →333×(31)23^ 3 3×(3^ 1 ) ^2333×(31)21 是奇数 →3133^1 3313整个过程只需要很少的乘法而不是真的乘 13 次。#include iostream using namespace std; const int MOD 1000007; long long mod(long long a, long long n,long long m) { int r 1; a % m; while(n 0) { if(n1) { r (r*a) % m; // 奇数情况乘一次当前底数 } a (a*a) % m; // 底数平方对应指数折半 n 1; // 指数右移一位相当于除以2 } return r; } int main() { int T; cin T; while(T--) { long long a,n; cin a n; cout mod(a,n,MOD) endl; } return 0; }队列和栈熟悉队列和栈的函数用法区分清楚两者的使用区别栈定义仅限定在表头进行删除或插入操作的线性表允许插入删除的一端称为栈顶(top)另一端称为栈底(bottom)特点后进先出元素个数对出栈时间没有影响常见操作定义std::stack a;进栈a.push(10); //把10压进栈里出栈a.pop(); //弹出栈顶储存的取栈顶a.top(); //取栈顶元素判断栈是否空a.empty();判断栈的大小a.size();队列定义只允许在表的一端进行插入另一端进行删除元素的线性表在队列中允许插入的一端叫队尾允许删除的一端叫队头特点先进先出常见操作定义std::queue a;进队a.push(10); //元素10进队出队a.pop(); //队首出队取队头a.front();取队尾a.back();判断栈是否空a.empty();判断栈的大小a.size();例题Largest Rectangle in a Histogram(单调栈)思路考虑一个柱子X其高度为h将柱子向左右延伸找到左边第一个低于它的柱子L右边第一个低于它的柱子R那么L和R之间的柱子可以构成一个高为h宽为(R-L-1)的矩阵。从每个柱子出发向左右延伸到不能再延伸形成矩形找到面积最大的那个矩形即可。做法建立一个单调递减栈每次需要弹出的栈顶元素(因为比进栈元素大所以需要弹出)的右边第一个比它小的即为当前进栈元素当前栈顶元素比当前进栈元素小则当前进栈元素左边第一个比它小的即为当前栈顶元素;若当前栈顶元素与当前进栈元素相等则当前进栈元素左边第一个比它小的即为当前栈顶元素左边第一个比它小的元素#include iostream #include vector #include stack using namespace std; typedef long long ll; ll largestRectangleArea(vectorll heights) { stackint st; ll max_area 0; int n heights.size(); for (int i 0; i n; i) { ll h (i n) ? 0 : heights[i]; while (!st.empty() h heights[st.top()]) { int top_idx st.top(); st.pop(); int width; if (st.empty()) { width i; } else { width i - st.top() - 1; } ll area heights[top_idx] * width; if (area max_area) { max_area area; } } st.push(i); } return max_area; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; while (cin n n ! 0) { vectorll heights(n); for (int i 0; i n; i) { cin heights[i]; } cout largestRectangleArea(heights) endl; } return 0; }Sliding Window最小值思路维护一个单增的队列那么每次滑动窗口入队之后就要得到一个区间最小值直接取队首元素就可以了做法每次滑动窗口要得到最小值的时候判断队首元素是否过期如果过期就从队首出队继续找。最大值与求最小值类似维护一个单减的队列#include iostream #include deque #include vector #include cstdio using namespace std; int main() { int n, k; scanf(%d %d, n, k); vectorint arr(n); for (int i 0; i n; i) { scanf(%d, arr[i]); } dequeint minDeque, maxDeque; vectorint minRes, maxRes; for (int i 0; i n; i) { if (!minDeque.empty() minDeque.front() i - k) { minDeque.pop_front(); } if (!maxDeque.empty() maxDeque.front() i - k) { maxDeque.pop_front(); } while (!minDeque.empty() arr[minDeque.back()] arr[i]) { minDeque.pop_back(); } minDeque.push_back(i); while (!maxDeque.empty() arr[maxDeque.back()] arr[i]) { maxDeque.pop_back(); } maxDeque.push_back(i); if (i k - 1) { minRes.push_back(arr[minDeque.front()]); maxRes.push_back(arr[maxDeque.front()]); } } for (size_t i 0; i minRes.size(); i) { if (i 0) {printf( );} printf(%d, minRes[i]); } printf(\n); // 输出最大值 for (size_t i 0; i maxRes.size(); i) { if (i 0) {printf( );} printf(%d, maxRes[i]); } printf(\n); return 0; }
