A完美序列 数组统计频率+目标和组合优化
核心特征
问题目标：找到一个目标和s，使得数组中能组成最多数量元素对，每个元素对的和为 s，最终求最大的总元素个数（或对数量）。
数据特点：输入元素的取值范围较小（如题目中ai ≤5000），因此目标和s的范围可枚举（2≤s≤2×5000)
核心操作：对每个可能的目标和s，统计数组中能组成和为s的元素对数量。
分两种情况计算：元素对中两个元素相等（j=s−j）和不相等（j!=s−j）。
取所有目标和中能组成的最大元素总数作为答案.
核心思路
1.频率统计，用数组统计每个元素的出现次数，降低重复计算成本
2.目标和枚举，根据元素取值范围枚举所有可能的目标和s
3.分情况计算匹配数，j==i-j和j!=i-j
4.取最大值，对所有目标和的结果取最大值即为最优解
代码实现
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e3;
void solve(){
int n;
cin >> n;
vector<int> a(2*N+1);//（）非[]
for(int i = 1;i <= n;i ++){
int x;
cin >> x;
a[x]++;
}
int ans = 0;
for(int i = 1;i <= 2*N;i++){
int res = 0;
for(int j = 1;j <= i - j;j ++){
if(j==i-j) res += a[j] / 2 * 2;
else res += min(a[j],a[i-j]) * 2;
}
ans = max(ans,res);
}
cout << ans << endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
//cin >> T;
while(T--) solve();
return 0;
}
相关问题衍生
1.完美序列问题：要求序列中所有相邻元素对的和相等，本质是找到最优目标和s并计算最大匹配数
2.两数之和问题，统计和为s的元素对有多少组
3.计数类优化问题，需要枚举所有可能的目标值，通过统计频率，避免暴力O（n^2）->O(V^2)其中V为元素取值范围，通常V<<n
总结
基于频率统计的目标和组合优化问题，利用元素取值范围小的特点，通过枚举目标和与分情况计数求解
B-0 数论分块 由末尾0想到10由质数2和5相乘得
推导过程
f函数：统计1 到 n 的所有整数中，每个数的所有因数里，质因数 x 的总出现次数
代码实现
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int L,R;
cin >> L >> R;
auto f = [&](int x,int lim) ->int{
int num = 0;
for(int i = x;i <= lim;i *= x){
int n = lim / i;
for(int l = 1;l <= n;l = n / (n / l) + 1){
int r = n / (n / l);
num += (r - l + 1) * (n / l);
}
}
return num;
};
int cnt2 = f(2,R) - f(2,L-1);
int cnt5 = f(5,R) - f(5,L-1);
cout << min(cnt2,cnt5) << endl;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
// std::cin >> T;
while(T--) {
solve();
}
return 0;
}
相关题型+共同思路
质因数+统计
1.阶乘末尾0个数
2.阶乘中质因数p的总个数
3.组合数C(n,m)的末尾0个数
计算 n!、m!、(n-m)! 中质因数 5 的个数，三者相减后即为 C (n,m) 中 5 的个数（2通常比5多）
4.判断一个数a是否为阶乘n!的倍数
将a分解为质因数，若对每个pi，都比其在 n! 中的总个数多，则a为n!的倍数
G 枚举
算法基础积累
set容器存储数组中的元素,去重且有序aa.insert(a[i])数组元素插入 set会处理重复值
aa.contains()高效判断某值是否存在于数组中
vector数组排序：sort(a.begin(),a.end());
代码实现
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int n;
cin >> n;
vector<int> a(n);
set<int> aa;//有序且去重
for(int i = 0;i < n;i ++){
cin >> a[i];
aa.insert(a[i]);//数组元素插入
}
sort(a.begin(),a.end());
for(int i = 0;i < n;i ++)
for(int j = 0;j < n;j ++){
if(!aa.contains(a[i] | a[j])){
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
}
signed main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
//cin >> T;
while(T--) solve();
return 0;
}
C-合并石子 贪心+递推+前后缀
思路
1.问题聚焦：所有石子合并到某一个位置的最小总代价
2.问题分解：左右代价分离，合并到位置i的总代价 = 左边所有元素移到i的代价 + 右边所有元素移到i的代价
3.递推计算：lr[i]：从左到右递推，存储 1 - i-1 号元素合并到 i 号的总代价。
递推关系：lr[i] = lr[i-1] + 新增代价（新增代价是将 i-1 号位置的所有元素移到 i 号的趟数）。
rl[i]：从右到左递推，存储 i+1 - n 号元素合并到 i 号的总代价。
递推关系：rl[i] = rl[i+1] + 新增代价（新增代价是将 i+1 号位置的所有元素移到 i 号的趟数）。
递推意义：复用前一步的计算结果，避免重复累加元素和，时间复杂度从O(n²)降至O(n)
4.向上取整没搬完剩下<k个石子也要占一次体力消耗(sum + k - 1) / k，k-1作为偏移量只要sum/k还有余数就会向上取整
5.贪心选择：遍历终点体力消耗最小值找最优合并点
代码实现
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int n,k;
cin >> n >> k;
vector<int> a(n+1),lr(n+1),rl(n+1);
for(int i = 1;i <= n;i ++) cin >> a[i];
int sum = 0;
for(int i = 2;i <= n;i ++){
sum += a[i-1];
lr[i] = lr[i-1] + (sum + k - 1) / k;
}
sum = 0;
for(int i = n - 1;i >= 1;i --){
sum += a[i+1];
rl[i] = rl[i+1] + (sum + k - 1) / k;
}
int ans = 2e18;
for(int i = 1;i <= n;i ++)
ans = min(ans,lr[i] + rl[i]);
cout << ans << endl;
}
signed main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
//cin >> T;
while(T--) solve();
return 0;
}
总结
用分治拆解决策，左右代价分离
靠递推优化，计算前后缀累加
细节技巧向上取整公式
最后贪心遍历找全局最优
J 贪心 +特殊值
思路：多关键字比较+特殊值
操作使a1的值最大，选择最大值索引j（2-n）
如果存在多个最大值，选择编号最大的索引
如果最大值为0，不进行操作（a1无变化而长度减小）
代码实现
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
vector<int> a(n+1);
for(int i = 1;i <= n;i ++) cin >> a[i];
int idx = 0;
for(int i = 2;i <= n;i ++){
if(a[i]==0) continue;
//if(std::tie(a[i], i) > std::tie(a[idx], idx)) idx = i;
if(a[i] > a[idx] || (a[i] == a[idx] && i > idx)) idx = i;
}
cout << n - (idx != 0) << endl;
a[1] += a[idx];
for(int i = 1;i <= n;i ++){
if(i==idx) continue;
cout << a[i] << " " ;
}
cout << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
while(T--) solve();
return 0;
}
总结
代码的精细处学习
1.if(a[i]==0) continue;
2.if(a[i] > a[idx] || (a[i] == a[idx] && i > idx)) idx = i;
D 01-BFS
处理带有两种不同移动代价的二维网格路径搜索问题
问题场景
给定一个二维字符网格，要求从左上角走到右下角，并且根据每个位置的字符方向（U、D、L、R）来决定移动的代价。如果按照字符方向移动，代价为 0，否则代价为 1。需要判断是否能在不超过给定步数k的情况下到达右下角。由于移动代价只有 0 和 1 两种情况，这符合 01BFS 的典型特征。通过双端队列来有效处理。
思路
一、数据结构与初始化：
1.deque<tuple<int, int, int>>（dq）双端队列存储待处理的节点，包含坐标(x,y)和到达该点的代价num
2.vis(n, vector(m, - 1))来记录是否被访问过，及从起点到该位置的最小代价num
3.vector<pair<int, int>> d来表示四个方向坐标偏移量，string idx = "UDLR"对应方向字符
二、BFS：
1.起点入队：将起点(0,0)以代价 0 入队，即dq.push_back({0, 0, 0})
2.循环处理队列：auto [x, y, num] = dq.front();取出队首节点， 如果该节点已被访问过（vis[x][y] != -1），则跳过。 标记该节点已访问，并记录到达该节点的代价vis[x][y] = num;
遍历四个方向： 获取方向偏移量const auto &[dx, dy] = d[i];，计算新坐标int xx = x + dx; int yy = y + dy;
如果新坐标越界或者已被访问，则跳过。
根据当前位置(x,y)的字符v[x][y]与移动方向idx[i]是否一致来决定新节点插入队首还是队尾
如果一致（v[x][y] == idx[i]），则将新节点(xx,yy,num)插入队首，表示代价为 0 的移动。
如果不一致，则将新节点(xx,yy,num + 1)插入队尾，表示代价为 1 的移动。
3.结果判断：最后判断vis[n - 1][m - 1]是否小于等于k判断输出
代码实现
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> PII;
typedef tuple<int,int,int> TIII;
vector<PII> d = {{-1,0},{1,0},{0,-1},{0,1}};
string idx = "UDLR";
void solve() {
int n,m,k;
cin >> n >> m >> k;
vector<string> v(n);
for(int i = 0;i < n;i ++) cin >> v[i];
vector vis(n,vector<int>(m,-1));
deque<TIII> dq;
dq.push_back({0,0,0});
while(!dq.empty()){
auto[x,y,num] = dq.front();
dq.pop_front();
if(vis[x][y] != -1) continue;
vis[x][y] = num;
for(int i = 0;i < 4;i ++){
auto[dx,dy] = d[i];
int xx = x + dx,yy = y + dy;
if(xx < 0 || xx >= n || yy < 0 || yy >= m || vis[xx][yy] != -1) continue;
if(v[x][y] == idx[i]) dq.push_front({xx,yy,num});
else dq.push_back({xx,yy,num+1});
}
}
cout << (vis[n-1][m-1] <= k ? "YES": "NO" ) << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
while(T--) solve();
return 0;
}
L 素数筛+数论
一个数的因数个数为质数且非2 则加到最后结果中
思路
数学上：这类数等价于质数的（质数 - 1）次幂
预处理：用线性筛找质数，枚举其幂次，标记符合条件的数的平方根
验证：对输入数，判断是否为完全平方数且平方根已标记，累加符合条件的数。
代码实现
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6;
vector<int> pri; // 存储质数列表
vector<bool> not_prime; // 标记非质数的数组
// 线性筛预处理质数
void pre(int n) {
not_prime.resize(n + 1);
for (int i = 2; i <= n; ++i) {
if (!not_prime[i]) {
pri.push_back(i);
}
for (int p : pri) {
if (i * p > n) break;
not_prime[i * p] = true;
if (i % p == 0) break;
}
}
}
void solve() {
vector<bool> valid_sqrt(N + 1); // 标记符合条件的数的平方根
// 预处理符合条件的平方根标记
for (int a : pri) {
for (int b = 2, y = a * a; y <= N * N; ++b, y *= a) {
if (!not_prime[b + 1]) { // 若因数个数是质数（b+1为质数）
valid_sqrt[(int)sqrtl(y)] = true;
}
}
}
// 处理输入并计算结果
int n;
cin >> n;
int ans = 0;
while (n--) {
int x;
cin >> x;
int sqx = (int)sqrtl(x);
if (sqx * sqx == x && valid_sqrt[sqx]) {
ans += x;
}
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
pre(N); // 预处理质数
int T = 1;
// cin >> T; // 多组测试数据取消注释
while (T--) solve();
return 0;
}
总结
完全平方数是满足因数个数为质数且非2的一种常见且易筛选的情况
京公网安备 11010502036488号