当前位置:首页 > 洛谷 > 洛谷P10916题解:动态规划与数学优化的解题思路与代码实现

洛谷P10916题解:动态规划与数学优化的解题思路与代码实现

2个月前 (07-01)

洛谷P10916题解:动态规划与数学优化的解题思路与代码实现  算法竞赛 动态规划 数学优化 第1张

一、题目解读

洛谷P10916题是一道典型的算法竞赛题目,要求根据给定的数列a,计算每个位置x对应的答案ans[x]。题目核心在于分析数列元素的特性,通过动态规划数学优化策略,高效求解每个位置对应的答案。该题目考验选手对GCD(最大公约数)计算、集合维护及特殊情况处理的综合能力。

二、解题思路

解题思路分为两部分:特殊情况和一般情况。

1. 特殊处理(当a_i = i时):

若数列a满足每个元素a[i]等于其下标i(即a_i=i),则答案可直接通过数学规律推导。此时ans[i] = n - (i!= 1),即除首元素外,其余答案均为n-1。该特殊情况简化了计算复杂度,避免遍历操作。

2. 一般情况(存在a_i ≠ i):

采用动态规划思想,利用vector和unordered_set维护GCD集合。通过迭代更新每个位置x的GCD集合,统计集合大小即为答案。具体步骤涉及:

    将a[pos[x]]临时置为1,避免x自身影响;

    遍历数列,动态计算当前元素a[i]与历史GCD的新值,更新集合;

    通过排序与去重确保集合唯一性,最终统计集合大小。

三、解题步骤

1. 输入n及数列a,记录元素位置pos[i]=a[i]的下标;

2. 判断是否为特殊情况(所有a_i=i),若是则调用solve_special_case();

3. 否则执行一般情况处理:

    初始化GCD集合数组gcd_sets;

    遍历每个x,临时修改a[pos[x]]为1;

    迭代计算新GCD值,更新集合并去重;

    统计集合大小存入ans[x],恢复a[pos[x]]原值;

4. 输出答案数组ans。

四、代码与注释

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

const int MAXN = 5e5 + 5;  
int a[MAXN], pos[MAXN], ans[MAXN];  

void solve_special_case(int n) {  
    // 当a_i=i时的特殊处理  
    for(int i = 1; i <= n; ++i) {  
        ans[i] = n - (i!= 1);  // 首元素为n,其余为n-1  
    }  
}  

void solve_general_case(int n) {  
    vector<unordered_set<int>> gcd_sets(n + 1);  
    for(int x = 1; x <= n; ++x) {  
        int modified_pos = pos[x];  
        a[modified_pos] = 1;  // 临时修改避免自影响  
        unordered_set<int> S;  
        vector<int> current_gcds;  

        for(int i = 1; i <= n; ++i) {  
            vector<int> new_gcds;  
            int new_gcd = a[i];  
            S.insert(new_gcd);  
            new_gcds.push_back(new_gcd);  

            for(int g : current_gcds) {  
                new_gcd = __gcd(g, a[i]);  
                if(new_gcd!= g || new_gcd == 1) {  
                    S.insert(new_gcd);  
                    new_gcds.push_back(new_gcd);  
                }  
            }  
            current_gcds = new_gcds;  
            sort(current_gcds.begin(), current_gcds.end());  
            current_gcds.erase(unique(current_gcds.begin(), current_gcds.end()), current_gcds.end());  
        }  
        ans[x] = S.size();  
        a[modified_pos] = x;  // 恢复原值  
    }  
}  

int main() {  
    ios::sync_with_stdio(false);  
    cin.tie(nullptr);  

    int n;  
    cin >> n;  
    bool is_special_case = true;  

    for(int i = 1; i <= n; ++i) {  
        cin >> a[i];  
        pos[a[i]] = i;  
        if(a[i]!= i) is_special_case = false;  
    }  

    if(is_special_case) {  
        solve_special_case(n);  
    } else {  
        solve_general_case(n);  
    }  

    for(int i = 1; i <= n; ++i) {  
        cout << ans[i] << " \n"[i == n];  // 优化输出格式  
    }  
    return 0;  
}

五、总结

洛谷P10916题通过巧妙区分特殊与一般情况,结合动态规划与数学优化,实现了高效的答案计算。特殊情况的直接推导显著降低了时间复杂度,而一般情况利用集合维护GCD的动态变化,并通过排序去重保证结果准确性。该题目展现了算法设计中“分类讨论”与“数据结构优化”的重要性,对提升选手逻辑与代码能力具有实践价值。

原创内容 转载请注明出处

分享给朋友:

相关文章

牛客DP41精讲:当背包必须装满时,你的状态转移方程该如何调整?

牛客DP41精讲:当背包必须装满时,你的状态转移方程该如何调整?

题目重解我们面对一个经典背包问题的变体:给定n个物品,每个物品有重量w和价值v,背包容量为V。需要回答两个问题:1) 普通情况下能获得的最大价值;2) 必须恰好装满背包时的最大价值(若无法装满则输出0...

从零到一掌握背包问题:洛谷P1164题解精讲,附带优化

从零到一掌握背包问题:洛谷P1164题解精讲,附带优化

题目重解:小A带着m元钱来到餐馆,菜单上有n道菜,每道菜都有确定的价格。现在需要计算出刚好花完m元的点菜方案总数。这个问题看似简单,但当菜品数量增多时,暴力枚举就会变得不可行,需要更高效的算法来解决。...

CSP-J 2019纪念品题解(洛谷P5662):动态规划+完全背包问题的实战应用

CSP-J 2019纪念品题解(洛谷P5662):动态规划+完全背包问题的实战应用

一、题目解读2019年CSP-J的“纪念品”问题(对应洛谷P5662)要求玩家在T天内通过买卖纪念品最大化金币收益。每天可交易N种商品,需计算最优策略下的最终金币数。题目强调动态规划思维与资源分配优化...

CSP-J方格取数题解|动态规划解法|洛谷P7074代码解析

CSP-J方格取数题解|动态规划解法|洛谷P7074代码解析

一、题目解读题目要求在一个n×m的网格中,从左上角到右下角选择一条路径,路径上的数字可重复取用,求取数之和的最大值。路径限制为仅能向右或向下移动。需注意路径的灵活性与重复取数的可能性,传统单向动态规划...

NOIP 2008火柴棒等式题解(C++代码实现)  动态规划与枚举算法详解

NOIP 2008火柴棒等式题解(C++代码实现) 动态规划与枚举算法详解

一、题目解读火柴棒等式问题(NOIP 2008,洛谷P1149)要求使用给定数量的火柴棒,构造形如 A + B = C 的等式,其中A、B、C均为整数,且火柴棒总数恰好等于输入值。需统计符合条件的等式...

2024蓝桥杯省赛B组“传送阵”题解(C++代码+图论算法优化)

2024蓝桥杯省赛B组“传送阵”题解(C++代码+图论算法优化)

一、题目解读2024年蓝桥杯省B组“传送阵”题目要求处理一个包含n个节点的图,节点间存在单向传输关系。每个节点i可传送至a[i]指定的节点,形成可能存在的环结构。题目需求解从任意节点出发能到达的最长路...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。