SCAU算法设计与分析—— 一般方法

By 三石吖 2026.2

1.一般方法

9715 相邻最大矩形面积

最终形成矩形的高度必然不超过给定高度的最大值，于是考虑枚举所有高度作为最终矩形高度

形式化地，对于每个位置$i$，有高度$a[i]$，我们要找在它左侧小于$a[i]$的第一个位置$l[i]$，在它右侧小于$a[i]$的第一个位置$r[i]$ ，那么以$a[i]$为高度的矩形面积就是 $S = a[i] \times (r[i] - l[i] - 1)$

于是考虑单调栈，我们维护一个单调递增的栈，对于每个位置$i$，首先弹出栈内大于等于$a[i]$的位置，此时若栈非空，则找到了第一个小于$a[i]$的位置，正反各跑一遍即可

初始化：若左侧找不到比$a[i]$更小的值，将$l[i]$置为$-1$，若右侧找不到，将$r[i]$置为$n$（上述索引均从$0$开始）

• 时间复杂度$O(n)$

• 看半天不知道为啥 $n$ 范围 $1e5$ 时限 $1s$ 推荐$O(n^2)$的做法，测了一下测试数据中$n$不超过70。。

#include<bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using pii = std::pair<int,int>;
using pll = std::pair<i64,i64>;
using pli = std::pair<i64,int>;
using pil = std::pair<int,i64>;
constexpr i64 INF = 0x3f3f3f3f3f3f3f3fll;
constexpr int inf = 0x3f3f3f3f;void solve(){int n;std::cin >> n;std::vector<int>a(n);for(int i = 0; i < n; i++){std::cin >> a[i];}std::vector<int>l(n, -1), r(n, n), stk;for(int i = 0; i < n; i++){while(!stk.empty() && a[stk.back()] >= a[i]){stk.pop_back();} if(!stk.empty()){l[i] = stk.back();}stk.push_back(i);}stk.clear();for(int i = n - 1; i >= 0; i--){while(!stk.empty() && a[stk.back()] >= a[i]){stk.pop_back();} if(!stk.empty()){r[i] = stk.back();}stk.push_back(i);}i64 ans = 0;for(int i = 0; i < n; i++){ans = std::max(ans, 1LL * a[i] * (r[i] - l[i] - 1));}std::cout << ans << "\n";
}             int main(){ std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);#ifdef LOCALfreopen("make.txt", "r", stdin);freopen("a.txt", "w", stdout);
#endifint T = 1;// std::cin >> T;while(T--){solve();}return 0; 
}   
/* */  

10345 前缀平均值

记录出现值的和，再除$i$即可，由于不涉及多次询问，不需要单独开一个前缀和数组

• 时间复杂度$O(n)$

• 学校$oj$不能用$std::setprecision()$

#include<bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using pii = std::pair<int,int>;
using pll = std::pair<i64,i64>;
using pli = std::pair<i64,int>;
using pil = std::pair<int,i64>;
constexpr i64 INF = 0x3f3f3f3f3f3f3f3fll;
constexpr int inf = 0x3f3f3f3f;void solve(){int n;std::cin >> n;double sum = 0;for(int i = 1; i <= n; i++){double x;std::cin >> x;sum += x;printf("%.2f%c", sum / i, " \n"[i == n]);}
}             int main(){ std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);#ifdef LOCALfreopen("make.txt", "r", stdin);freopen("a.txt", "w", stdout);
#endifint T = 1;// std::cin >> T;while(T--){solve();}return 0; 
}   
/* */  

11075 强盗分赃

假设初始有$n$个金币，第一个强盗拿走$1$个，剩$n - 1$个，分成五份后留下四份，剩$\frac{4(n - 1)}{5}$

第二个强盗拿走一个，剩$\frac{4n - 9}{5}$个，分成五份后留下四份，剩$\frac{16n - 36}{25}$

第三个强盗拿走一个，剩$\frac{16n - 61}{25}$个，分成五份后留下四份，剩$\frac{64n - 244}{125}$

第四个强盗拿走一个，剩$\frac{64n - 369}{125}$个，分成五份后留下四份，剩$\frac{256n - 1476}{625}$

第五个强盗拿走一个，剩$\frac{256n - 2101}{625}$个，分成五份后留下四份，剩$\frac{1024n - 8404}{3125}$

数据范围$1e8$，考虑枚举初始的金币数$n$，满足$(1024n - 8404) \ % 3125 \ = 0$即合法

• 注意乘法可能爆$int$

• 时间复杂度$O(n)$

#include<bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using pii = std::pair<int,int>;
using pll = std::pair<i64,i64>;
using pli = std::pair<i64,int>;
using pil = std::pair<int,i64>;
constexpr i64 INF = 0x3f3f3f3f3f3f3f3fll;
constexpr int inf = 0x3f3f3f3f;void solve(){int n;std::cin >> n;std::vector<int>res;for(int i = 1; i <= n; i++){if((1024LL * i - 8404) % 3125 == 0){res.push_back(i);}}if(res.empty()){std::cout << "impossible\n";return;}for(int i = 0; i < res.size(); i++){std::cout << res[i] << " \n"[i == res.size() - 1];}
}             int main(){ std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);#ifdef LOCALfreopen("make.txt", "r", stdin);freopen("a.txt", "w", stdout);
#endifint T = 1;// std::cin >> T;while(T--){solve();}return 0; 
}   
/* */  

11076 浮点数的分数表达

提示讲的很详细了，这里搬运一下提示：

（1）假设输入为有限小数：$X \ = \ 0.a_1a_2...a_n$，其中$a_1a_2...a_n$都是数字$0-9$

$X \ = \ 0.a_1a_2...a_n \ = \ \frac{a_1a_2...a_n}{10^n}$

然后约分即可

（2）假设输入为无限循环小数：$X \ = \ 0.a_1a_2...a_n(b_1b_2...b_m)$，其中$a_1a_2...a_n$，$b_1b_2...b_m$都是数字$0-9$，括号内为循环节

①先将$X$转化为只有循环部分的纯小数

$X \ = \ 0.a_1a_2...a_n(b_1b_2...b_m)$，左右同乘$10^n$

$10^n \times X \ = \ a_1a_2...a_n \ + \ 0.(b_1b_2...b_m)$

上式中，$a_1a_2...a_n$是整数部分，可单独处理

②然后考虑循环节部分的转化

令$Y \ = \ 0.(b_1b_2...b_m)$，左右同乘$10^m$

$10^m \times Y \ = \ b_1b_2...b_m \ + \ 0.(b_1b_2...b_m)$，左右同时$- Y$，消去小数点后的循环节

$(10^m \ - \ 1) \times Y \ = \ b_1b_2...b_m$

得$Y \ = \ \frac{b_1b_2...b_m}{10^m \ - \ 1}$

将①②步结果相加：$X \ = \ \frac{a_1a_2...a_n}{10^n} \ + \ \frac{b_1b_2...b_m}{10^m \ - \ 1} \ = \ \frac{(10^m \ - \ 1) \times (a_1a_2...a_n) \ + \ (b_1b_2...b_m)}{(10^m - 1) \times 10^n}$

最后约分即可

• 时间复杂度$O(n)$，$n$为字符串长度
• 代码中的$p1$为$10^{n$，$p2$为$10}m$

#include<bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using pii = std::pair<int,int>;
using pll = std::pair<i64,i64>;
using pli = std::pair<i64,int>;
using pil = std::pair<int,i64>;
constexpr i64 INF = 0x3f3f3f3f3f3f3f3fll;
constexpr int inf = 0x3f3f3f3f;void solve(){   std::string s;std::cin >> s;int n = s.size();i64 a = 0, b = 0, p1 = 1, p2 = 1;for(int i = 2; i < n && s[i] != '('; i++){a = a * 10 + (s[i] - '0');p1 *= 10;}i64 up, down, g;if(s.back() == ')'){for(int i = n - 2; i >= 0 && s[i] != '('; i--){b += p2 * (s[i] - '0');p2 *= 10;}up = (p2 - 1) * a + b, down = (p2 - 1) * p1;g = std::__gcd(up, down);}else{up = a, down = p1;g = std::__gcd(up, down);}std::cout << up / g << " " << down / g << "\n";
}             int main(){ std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);#ifdef LOCALfreopen("make.txt", "r", stdin);freopen("a.txt", "w", stdout);
#endifint T = 1;// std::cin >> T;while(T--){solve();}return 0; 
}   
/* */  

17963 完美数

按提示模拟即可

#include<bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using pii = std::pair<int,int>;
using pll = std::pair<i64,i64>;
using pli = std::pair<i64,int>;
using pil = std::pair<int,i64>;
constexpr i64 INF = 0x3f3f3f3f3f3f3f3fll;
constexpr int inf = 0x3f3f3f3f;void solve(){int a[] = {2, 3, 5, 7, 13, 17, 19, 31};for(int i = 0; i < 8; i++){i64 res = (1LL << (a[i] - 1)) * ((1LL << a[i]) - 1);std::cout << i + 1 << " " << res << "\n";}
}             int main(){ std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);#ifdef LOCALfreopen("make.txt", "r", stdin);freopen("a.txt", "w", stdout);
#endifint T = 1;// std::cin >> T;while(T--){solve();}return 0; 
}   
/* */  

17086 字典序的全排列

法一：直接用$C++$的$STL$模拟

• 时间复杂度$O(n! \times n)$

#include<bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using pii = std::pair<int,int>;
using pll = std::pair<i64,i64>;
using pli = std::pair<i64,int>;
using pil = std::pair<int,i64>;
constexpr i64 INF = 0x3f3f3f3f3f3f3f3fll;
constexpr int inf = 0x3f3f3f3f;void solve(){int n;std::string s;std::cin >> n >> s;std::sort(s.begin(), s.end());int cnt = 1;do{std::cout << cnt << " " << s << "\n";cnt++;}while(std::next_permutation(s.begin(), s.end()));
}             int main(){ std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);#ifdef LOCALfreopen("make.txt", "r", stdin);freopen("a.txt", "w", stdout);
#endifint T = 1;// std::cin >> T;while(T--){solve();}return 0; 
}   
/* */  

法二：写个真的$dfs$，由于字符串不含重复元素，因此可以先对字符串排序，后进行深搜，这样必然是按字典序升序排列的

• 时间复杂度$O(n! \times n)$

#include<bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using pii = std::pair<int,int>;
using pll = std::pair<i64,i64>;
using pli = std::pair<i64,int>;
using pil = std::pair<int,i64>;
constexpr i64 INF = 0x3f3f3f3f3f3f3f3fll;
constexpr int inf = 0x3f3f3f3f;void solve(){int n;std::string s;std::cin >> n >> s;std::sort(s.begin(), s.end());int cnt = 1;std::string v;std::vector<int>vis(n);auto dfs = [&] (auto &&self) -> void {if(v.size() == n){std::cout << cnt << " " << v << "\n";cnt++;return;}for(int i = 0; i < n; i++){if(!vis[i]){vis[i] = 1;v.push_back(s[i]);self(self);v.pop_back();vis[i] = 0;}}};dfs(dfs);
}             int main(){ std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);#ifdef LOCALfreopen("make.txt", "r", stdin);freopen("a.txt", "w", stdout);
#endifint T = 1;// std::cin >> T;while(T--){solve();}return 0; 
}   
/* */  

8593 最大覆盖问题

根据定义，一个合法的区间受到最右侧元素的约束，考虑枚举右端点

题目要求线性的做法，于是考虑双指针

发现正着跑双指针好像很困难，右端点从$i$位置到$i + 1$位置，左端点的移动不具有规律性

于是想到反着跑双指针

首先固定右端点$i$，对于左端点$j$，满足$a[j] < | \ a[i] \ |$即可进行左移，最后合法的区间就是$(j,i]$，即对$j + 1 \le k \le i$，都有$a[k] \le | \ a[i]\ |$

此时若$j \ge 0$，我们移动右端点，找到第一个$| \ a[i'] \ | \ge a[j]$的位置$i'$，这样就找到了一个新的右端点，使得$j$能够被覆盖，此时$[j,i']$这个区间必然是合法的

证明：

设$j \lt k \le i'$，首先必然有$a[k] \le |\ a[i]\ |$，又$| \ a[i] \ | < a[j]$，则$a[j] > a[k]$

由于$| \ a[i'] \ | \ge a[j]$，可推出$| \ a[i'] \ | \ge a[j] \gt a[k]$，说明合法

• 对于每个位置，最多左右指针各经过一次，时间复杂度$O(n)$

#include<bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using pii = std::pair<int,int>;
using pll = std::pair<i64,i64>;
using pli = std::pair<i64,int>;
using pil = std::pair<int,i64>;
constexpr i64 INF = 0x3f3f3f3f3f3f3f3fll;
constexpr int inf = 0x3f3f3f3f;void solve(){int n;std::cin >> n;std::vector<int>a(n);for(int i = 0; i < n; i++){std::cin >> a[i];}int ans = 1;for(int i = n - 1, j = n - 1; i >= 0; i--){if(std::abs(a[i]) < a[j]){continue;}while(j >= 0 && a[j] <= std::abs(a[i])){j--;}ans = std::max(ans, i - j);}std::cout << ans << "\n";
}             int main(){ std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);#ifdef LOCALfreopen("make.txt", "r", stdin);freopen("a.txt", "w", stdout);
#endifint T = 1;// std::cin >> T;while(T--){solve();}return 0; 
}   
/* */  

如果不限制复杂度$O(n)$，这题有没有别的做法呢，好像是有的！

法二：

观察到答案显然不超过$n$，并且具有单调性，也就是说，如果存在一个长度为$x$的合法区间，那么长度小于$x$的合法区间必然存在，于是想到二分答案

于是问题变成了，给定一个长度$d$，如何检查是否存在长度为$d$的合法区间

首先对于$i \lt d - 1$，区间长度不足$d$，不考虑

一个合法的区间满足：区间最大值不超过右端点值的绝对值

对于静态区间最值，不难想到用$st$表维护，于是可以枚举右端点询问最值进行检查

• $st$表预处理复杂度$O(logn)$，二分答案复杂度$O(logn)$，每次检查需要$O(n)$，询问最值$O(1)$

• 总复杂度$O(nlogn)$

• 数据范围要是达到$1e7$这个做法会超时

#include<bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using pii = std::pair<int,int>;
using pll = std::pair<i64,i64>;
using pli = std::pair<i64,int>;
using pil = std::pair<int,i64>;
constexpr i64 INF = 0x3f3f3f3f3f3f3f3fll;
constexpr int inf = 0x3f3f3f3f;template<typename T>
struct SpareTable{int n;std::vector<std::vector<T>>stmx, stmn;SpareTable(std::vector<T>a){init(a);}void init(std::vector<T>a){n = a.size();stmx.resize(n), stmn.resize(n);int siz = std::__lg(2 * n - 1);for(int i = 0; i < n; i++){stmx[i].assign(siz, T{});stmn[i].assign(siz, T{});stmx[i][0] = stmn[i][0] = a[i];}for(int j = 1; 1 << j <= n; j++){for(int i = 0; i + (1 << j) - 1 < n; i++){stmx[i][j] = std::max(stmx[i][j - 1], stmx[i + (1 << j - 1)][j - 1]);stmn[i][j] = std::min(stmn[i][j - 1], stmn[i + (1 << j - 1)][j - 1]);}}}T askmn(int l, int r){int k = std::__lg(r - l + 1);return std::min(stmn[l][k], stmn[r - (1 << k) + 1][k]);}T askmx(int l, int r){int k = std::__lg(r - l + 1);return std::max(stmx[l][k], stmx[r - (1 << k) + 1][k]);}
};
void solve(){int n;std::cin >> n;std::vector<int>a(n);for(int i = 0; i < n; i++){std::cin >> a[i];}SpareTable<int>st(a);int ans, lo = 1, hi = n;auto check = [&] (int mid){for(int i = mid - 1; i < n; i++){if(st.askmx(i - mid + 1, i) <= std::abs(a[i])){return true;}}return false;};while(lo <= hi){int mid = lo + hi >> 1;if(check(mid)){ans = mid;lo = mid + 1;}else{hi = mid - 1;}}std::cout << ans << "\n";
}             int main(){ std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);#ifdef LOCALfreopen("make.txt", "r", stdin);freopen("a.txt", "w", stdout);
#endifint T = 1;// std::cin >> T;while(T--){solve();}return 0; 
}   
/* */