B

思路：

1.最小质除数：

奇数的最小质除数为奇数偶数的最小质除数为2

奇-奇=偶，偶-2=偶

2.get函数找最小质除数

如果是奇数那么就先get找到并减去最小质除数后得到偶数/2+1即为操作次数

如果是偶数直接/2即可

代码实现：

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

int n,m,t=1;
int get(int n){
    for(int i=2;i<=n/i;i++)
        if(n%i==0) return i;
    return n;
}

signed main(){
    cin >> n;
    if(n&1){
        m = get(n);
        t += (n-m)/2+1;
    }
    else t += n/2;
    cout << t << endl;
    return 0;
}

F

思路：

选择两个数操作(ai+aj)/2*2,只有奇+偶才会使结果-1，而奇+奇，偶+偶不会使结果发生改变

题意为AB两操作来最大化最小化结果，通过统计奇数偶数个数发现规律，当b[i]%3=1时，损耗数为b[i]/3+1,否则损耗数为b[i]/3,通过以上规律即可实现

代码实现：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int a[N],b[N],s[N];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    for(int i = 1;i <= n;i ++){
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
        if(a[i] % 2 == 1) b[i] = b[i - 1] + 1;
        else b[i] = b[i - 1];
    }
    
    cout << a[1] << " ";
    for(int i = 2;i <= n;i ++){
        if(b[i] % 3 == 1) cout << s[i] - b[i] / 3 - 1 << " ";
        else cout << s[i] - b[i] / 3 << " ";
}
    return 0;
}

**总结：**前缀和+计数思想统计奇数个数，利用了奇数个数与最终结果的规律

当奇数个数b[i]%3 == 1时，结果为s[i] - b[i]/3 - 1，否则为s[i] - b[i]/3，展示了从问题中提炼数学规律以简化求解过程

D dp+dfs

思路：

1.状态定义定义dp[x][j]为以节点x为根的子树，在花费j个魔法水晶时能获取的最大生命灵气总和。

2.初始化对于每个节点x，当花费i从节点x的维系代价b[x]到总魔法水晶上限m时，dp[x][i]初始化为节点x的生命灵气值a[x]

3.递归与状态转移 DFS遍历树结构，对于节点x，先递归处理其子节点；处理完子节点后，通过两层循环合并子节点状态到当前节点x：外层循环从m递减到 0，遍历所有可能花费。内层循环遍历分配给子节点的花费k，确保k加上当前节点x的维系代价b[x]不超过当前总花费j；状态转移方程为dp[x][j] = max(dp[x][j], dp[a][k] + dp[x][j - k])，用于选择是否要包含子节点来获取最大价值。

4.结果获取最终dp[1][m]即为在整个树中花费m个魔法水晶时能获得的最大生命灵气总和。

代码实现：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 110,M = 1100;
int n,m;
int a[N],b[N],dp[N][M];
vector<int> tree[N];

void dfs(int x,int fa){
    for(int i=b[x];i<=m;i++) dp[x][i] = a[x];
    
    for(auto r:tree[x]){
        if(r == fa) continue;
        dfs(r,x);
        for(int j=m;j>=1;j--)
            for(int k =0;k+b[x]<=j;k++)
                dp[x][j] = max(dp[x][j],dp[x][j-k]+dp[r][k]);
    }
}

signed main(){
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++) cin >> b[i];
    for(int i=1;i<=n-1;i++){
        int u,v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    dfs(1,-1);
    cout << dp[1][m] << endl;
    return 0;
}

核心思路：

dp[x][j] = max( dp[x][j] , dp[x][j-k] + dp[r][k] )，不选择子节点r 和选择子节点r花费k这两种情况下，哪种能获得更大的生命灵气总和。如果选择子节点r（花费k）能带来更大的生命灵气总和，那么就更新dp[x][j]为这个更大的值；否则，保持dp[x][j]不变（即不选择子节点r）

总结：整个算法通过树形动态规划，自底向上地计算每个子树在不同花费下的最大价值。在计算过程中，巧妙地利用了动态规划的思想和背包问题的优化技巧，有效地处理了节点选择的依赖关系和代价限制，最终得到最优解。

C 树的遍历+gcd累积计算+两次 DFS

思路：

利用两次不同顺序的 DFS，从根节点（代码中以 1 为根）向子树传播 gcd 累积值，从而覆盖节点在不同方向上的路径信息，最终合并得到每个节点的结果。

第一次 DFS（dfs1）：正序遍历子节点，计算从根到某方向子树的 gcd 累积值，更新s[u]。

第二次 DFS（dfs2）：逆序遍历子节点，计算从根到另一方向子树的 gcd 累积值，再次更新s[u]。

两次遍历的目的是：让s[u]同时包含来自 “父节点方向” 和 “子节点方向” 的 gcd 信息，从而覆盖节点在树中所有可能路径的影响。

操作细节： 用邻接表tree存储树的结构。用s[u]存储节点u的最终结果，通过gcd(s[u], x)（x为当前累积的 gcd 值）逐步更新。递归中通过x = gcd(x, a[u])累积当前路径的 gcd 值（将当前节点的值纳入计算）

代码实现：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 10;
int a[N],s[N];
vector<int> tree[N];

void dfs1(int u,int fa,int &x){
    s[u] = gcd(s[u],x);
    for(int i:tree[u]){
        if(i==fa) continue;
        dfs1(i,u,x);
    }
    x = gcd(x,a[u]);
}

void dfs2(int u,int fa,int &x){
    s[u] = gcd(s[u],x);
    for(int j = tree[u].size() - 1;j >= 0;j --){
        int i = tree[u][j];
        if(i==fa) continue;
        dfs2(i,u,x);
    }
    x = gcd(x,a[u]);
}

signed main(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    for(int i = 1;i <= n - 1;i ++){
        int u,v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    
    int x1 = 0,x2 = 0;
    dfs1(1,0,x1);
    dfs2(1,0,x2);
    for(int i = 1;i <= n;i ++) cout << s[i] << " ";
    
    return 0;
}

总结：

利用两次 DFS 结合 gcd 的累积性，计算树中节点的路径相关结果，体现了树结构问题中 “分方向遍历” 和 “数学性质（gcd）应用” 的典型思路。

I数组旋转匹配离散化+高效统计

思路

离散化处理 a 和 b 中的元素可能是大范围数值（如 1e9），无法直接作为数组索引。

用 map 离散化，确保相同元素对应同一编号，不同元素对应不同编号。

记录位置信息

快速找到 b 中与 a[i] 相等的所有位置，避免暴力遍历。

解决：用 vector v[N] 存储 b 中每个离散化编号对应的位置（v[x] 包含 b 中所有值为 x 的位置）。

计算有效旋转次数

原理：若 a[i] 与 b[j] 相等，旋转次数 k 需满足 (i + k) % n = j，推导得 k = (j - i + n) % n（加 n 确保非负）。

遍历逻辑：对 a 中每个元素 a[i]，遍历 b 中所有与 a[i] 相等的位置 j（即 v[a[i]] 中的元素），计算 k 并统计次数（c[k]++）。

寻找最优旋转次数

遍历统计数组 c，找到最大值对应的 k。

代码实现：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int a[N],b[N],c[N];
vector<int> v[N];
map<int,int> mp;
int res;

signed main(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    for(int i = 1;i <= n;i ++) cin >> b[i];
    
    for(int i = 1;i <= n;i ++)
        if(mp[b[i]] == 0){
            res ++;
            mp[b[i]] = res;
        }
    
    for(int i = 1;i <= n;i ++)
    a[i] = mp[a[i]],b[i] = mp[b[i]];
    
    for(int i = 1;i <= n;i ++)
    v[b[i]].push_back(i);
    
    for(int i = 1;i <= n;i ++)
    for(int j = 0;j < v[a[i]].size();j ++){//不能取等
        int k = (v[a[i]][j] - i + n) % n;
        c[k] ++;
    }
    
    int res_max = -1;
    for(int i = 0;i <= n;i ++){//从0起，k=0也可能
        if(c[i] > res_max){
            res_max = c[i];
            res = i;
        }
    }
    cout << res_max << " " << res << endl;
    return 0;
}

总结： 用离散化压缩数值，用向量存位置，只算有效匹配的旋转次数

a 和 b 的元素 “种类和数量完全相同”，所以可以把它们的原始值换成小范围的编号（比如用 1、2、3 代替大数字），这样方便用数组存位置，不会浪费空间。

v[a[i]][j]不是严格的二维数组，而是按编号分类的位置列表

v[x] 是一个向量（动态数组），存着 b 中所有值为 x（编号后）的位置。 v[a[i]][j] 就是 b 中第 j 个和 a[i] 相等的位置。j 只遍历 v[a[i]] 里的有效位置（j < 列表长度），这些位置对应的 b 元素一定和 a[i] 相等。

这时k = (位置 - i + n) % n 才是让 a[i] 和 b 中这个位置匹配的旋转次数，所以 c[k]++ 统计的是有效匹配。

H 滑动窗口双指针

                                       时间复杂度为O(n)（每个字符最多被l和r各遍历一次）                                         
                                       **思路：**

用双指针维护一个 “有效区间”，右指针负责扩展，左指针负责在区间无效时收缩，过程中记录最大有效长度，适用于各种 “寻找最长 / 最短符合条件子串” 的场景。

代码实现：

#include <bits/stdc++.h>
using namespace std;
int n,l=0,r=0,res;
string s;

int main(){
    cin >> n >> s;
    while(r<n){
        while(l<=r-2 && s[r]==s[r-2]) l++;
        while(l<=r-1 && s[r]==s[r-1]) l++;
        res = max(res,r-l+1);
        r++;
    }
    cout << res << endl;
    return 0;
}

总结： 通过动态维护窗口的有效性，高效找到最长合规子串，是处理 “连续区间约束” 类问题的经典方法

L dfs+数论

奇偶性对质因子的影响：偶数次质因子可通过转移操作完全消除，奇数次质因子最终必留 1；

将复杂操作序列（约去公因子、转移因子）转化为质因子分配问题”

思路：

先约去公因子：将 X 和 Y 简化为互质的 a 和 b；

处理质因子次数：通过操作 2 和 3 消除偶数次质因子，剩余质因子均为 1 次；

分配剩余质因子：用 DFS 枚举所有质因子分给 X 或 Y 的方案，计算最小和

代码实现：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

//记录奇数次质因子并x被除最后变为1或x
void cal(ll& x, vector<ll>& cnt)
{
	ll s = sqrt(x);
	for (int i = 2;i <= s;i++)
	{
		int d = 0;
		while (x % i == 0)
		{
			x /= i;
			d++;
		}
		if (d % 2) cnt.push_back(i);
		if (i > x) break;//优化
	}
}

void dfs(ll a, ll b, ll pos, vector<ll>& cnt, ll& ansA, ll& ansB)
{
	if (a + b >= ansA + ansB) return;
	if (pos >= cnt.size())
	{
		if (ansA + ansB > a + b)
		{
			ansA = a;
			ansB = b;
		}
		return;
	}
    //质因子必须被包含在a或b中
	dfs(a * cnt[pos], b, pos + 1, cnt, ansA, ansB);
	dfs(a, b * cnt[pos], pos + 1, cnt, ansA, ansB);
}

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		ll a, b;
		cin >> a >> b;
		ll g = gcd(a, b);
		a /= g, b /= g;
		vector<ll> cnt;
		cal(a, cnt);
		cal(b, cnt);

		ll ansA = 1e9 + 10, ansB = 1e9 + 10;
		dfs(a, b, 0, cnt, ansA, ansB);
		cout << ansA + ansB << "\n";
	}
}

总结：

通过 pos 控制分配顺序

cal 函数高效提取关键质因子

dfs 基于乘积不变性枚举分配方案，最终在固定乘积约束下找到最小和。

核心是将复杂的操作问题转化为质因子分配问题结合数论性质和递归枚举实现高效求解。

7/30河南理工大学_补题

B

F

D dp+dfs

C 树的遍历+gcd累积计算+两次 DFS

I数组旋转匹配 离散化+高效统计

H 滑动窗口双指针

L dfs+数论

I数组旋转匹配离散化+高效统计