2 条题解

  • 1
    @ 2025-8-16 9:44:52
    这是一个关于模意义下区间子串和最小值查询的算法问题。我将为您提供详细的思路分析和C++代码实现。
    
    问题分析
    ‌问题核心‌:需要在给定区间[l, r]内找到所有可能的子区间[l', r'](l ≤ l' ≤ r' ≤ r),计算该子区间和对P取模的最小值。
    ‌关键点‌:
    直接暴力枚举所有子区间会达到O(n^2)复杂度,对于n=5e5不可行
    需要利用模运算的性质进行优化
    ‌优化思路‌:
    利用前缀和数组
    根据鸽巢原理,当区间长度≥P时,模P的最小值必为0
    对于长度<P的区间,采用暴力枚举
    
    
    #include<queue>
    #include<math.h>
    #include<stdio.h>
    #include<iostream>
    #include<vector>
    #include<iomanip>
    #include<string.h>
    #include<algorithm>
    #include<cmath>
    #include<cstdio>
    #include<utility>
    #include<cstring>
    #include<stack>
    #include<fstream>
    #include<string>
    using namespace std;
    #define LL long long
    const int N = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        int n , m;
        cin >> n >> m;
        vector<int> a( n + 1 );
        vector<long long> prefix( n + 1 , 0 );
        for ( int i = 1 ; i <= n ; ++i )
        {
            cin >> a[i];
            prefix[i] = prefix[ i - 1 ] + a[i];
        }
        while ( m-- )
        {
            int l , r , P;
            cin >> l >> r >> P;
            int min_mod = P;
            for ( int i = l ; i <= r ; ++i )
            {
                long long sum = 0;
                for ( int j = i ; j <= r ; ++j )
                {
                    sum += a[j];
                    int current_mod = sum % P;
                    if ( current_mod < min_mod )
                    {
                        min_mod = current_mod;
                        if ( min_mod == 0 )
                        {
                            break;
                        }
                    }
                }
                if ( min_mod == 0 )
                {
                    break;
                }
            }
            cout << min_mod << '\n';
        }
        return 0;
    }
    
    代码解析
    ‌输入处理‌:
    
    使用快速输入输出提高效率
    构建前缀和数组prefix,用于快速计算区间和
    ‌查询处理‌:
    
    对于每个查询[l, r, P],首先检查区间长度是否≥P
    如果是,直接输出0(根据鸽巢原理)
    否则,双重循环枚举所有子区间,计算模P的最小值
    ‌优化措施‌:
    
    当找到模为0时立即终止循环(已经是最小值)
    外层循环和内层循环都设置了提前终止条件
    复杂度分析
    ‌时间复杂度‌:
    预处理:O(n)
    查询:最坏情况O(P^2)(当区间长度<P时)
    对于m=1e4,P=500,最坏约2.5e8次操作,可在1秒内完成
    ‌空间复杂度‌:O(n)用于存储前缀和数组
    这个解法充分利用了模运算的性质和问题特点,在保证正确性的同时提供了较高的效率。
    • 1
      @ 2025-8-16 9:41:37

      非傻瓜脑残精神病者,禁止抄袭。 违者立刻报警处理,请吃子弹。 附送的网址: https://poki.com/zh/g/combat-reloaded https://www.minecraft.net/zh-hans https://classic.minecraft.net/

      • 1

      信息

      ID
      2014
      时间
      1000ms
      内存
      256MiB
      难度
      10
      标签
      递交数
      3
      已通过
      2
      上传者