首页 > 其他分享 >P9032 [COCI2022-2023#1] Neboderi

P9032 [COCI2022-2023#1] Neboderi

时间:2024-07-19 11:42:17浏览次数:11  
标签:COCI2022 P9032 le gcd suf int mid Neboderi ans

题意

给长度为 \(n\) 的数组 \(a\),求长度不小于 \(k\) 的区间 \([l,r]\) 使得 \(\gcd_{i = l}^r a_i \times \sum_{i = l}^r a_i\) 最大,输出这个最大值。

\(1\le k\le n\le 10^6,1\le a_i \le 10^6\qquad \text{2.5s 512MB}\)

题解

考虑分治(这是套路,想不到只能说做题少别打我)。

递归求解区间 \([l,r]\),若 \(r - l + 1\le k\) 则直接返回,\(l = r\) 且 \(k = 1\) 就用 \(a_i^2\) 更新答案。

引入一个结论,当一段区间 \(\gcd\) 相同时,肯定是选的数越多,答案越大。

对于一般情况,我们将 \([l,r]\) 分为 \([l,mid],(mid,r]\)。由上述结论可得,我们可以维护区间中每一段 \(\gcd\) 相同的区间,分别记录 \([l,mid]\) 和 \((mid,r]\) 的 \(\gcd\) 变化的位置,这样的位置至多只有 \(\log V\) 个。具体地,对于 \([l,mid]\) 维护后缀 \(\gcd\) 和后缀 \(\gcd\) 变化位置,同理 \((mid,r]\) 维护前缀 \(\gcd\) 和前缀 \(\gcd\) 变化位置(注意 \(l,r\) 同样也算作变化位置),存在 vector 里面,然后枚举区间 \([l,mid]\) 的变化位置 \(L\),区间 \((mid,r]\) 的变化位置 \(R\),若 \(R - L + 1 \ge k\),那么用 \(\gcd(suf_L,pre_R)\times(s_R - s_{L - 1})\) 更新答案。

枚举时间复杂度 \(\mathcal{O}(\log^2V)\),所以最终复杂度 \(\mathcal{O}(n\log n\log^2 V)\)。

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

const int N = 1e6 + 5;

int n,k,a[N];

#define ll long long

ll s[N],ans;

int pre[N],suf[N];

vector<int> P,S;

void solve(int l,int r){
    if (r - l + 1 < k) return ;
    if (l == r && k == 1){
        ans = max(ans,1ll * a[l] * a[l]);
        return ;
    }
    int mid = (l + r) >> 1;
    solve(l,mid), solve(mid + 1,r);
    for (int i = mid;i >= l;i--){
        suf[i] = __gcd(suf[i + 1],a[i]);
        if (i == mid) suf[i] = a[i];
        else if (suf[i] != suf[i + 1]) S.push_back(i + 1);
    }
    for (int i = mid + 1;i <= r;i++){
        pre[i] = __gcd(pre[i - 1],a[i]);
        if (i == mid + 1) pre[i] = a[i];
        else if (pre[i] != pre[i - 1]) P.push_back(i - 1);
    }
    P.push_back(r), S.push_back(l);
    for (int L : S)
        for (int R : P)
            if (R - L + 1 >= k)
                ans = max(ans,1ll * __gcd(suf[L],pre[R]) * (s[R] - s[L - 1]));
    P.clear(), S.clear();
}

int main(){
    scanf("%d%d",&n,&k);
    for (int i = 1;i <= n;i++)
        scanf("%d",&a[i]), s[i] = s[i - 1] + a[i];
    solve(1,n);
    printf("%lld",ans);
    return 0;
}

标签:COCI2022,P9032,le,gcd,suf,int,mid,Neboderi,ans
From: https://www.cnblogs.com/y1wei/p/-/solution_Luogu_P9032

相关文章

  • 打卡信奥刷题(249)用Scratch图形化工具信奥P9735[普及组][COCI2022-2023#2] Tramvaji
    [COCI2022-2023#2]Tramvaji题目描述Patrik和Josip在坐电车。他们共坐了nnn站。除了上车的那一站,其他每一站到站时,都会发生以下事件中的一种:Patrik说:从上车到......
  • P9175 [COCI2022-2023#4] Mreža 题解
    P9175[COCI2022-2023#4]Mreža题解前言我发现,有整体二分与主席树的地方总有莫队(不是那个莫队,是那个莫队)。知识点(树上)倍增,(树上)莫队,树状数组(“树”含量满满),分块。题意分析给定一棵树,每条边有一个权值\(v\),以及可以用一个花费\(c\)将它变成更大的权值\(s\)。再给定一......
  • [COCI2022-2023#1] Berilij 题解
    SolutionP9030[COCI2022-2023#1]Berilij本题解转载翻译自官方题解:COCI2022/2023CONTEST1Part1让我们定义图形\(G\),顶点代表飞船,边代表两艘飞船外部接触的情况。此外,让边的边权成为它所连接的圆之间的距离。现在的任务等同于为顶点找到非负值,使得每条边所连接的两个顶......
  • P9757 [COCI2022-2023#3] Dirigent 题解
    分析对于一个从小到大(按编号排序)的长度为\(n\)的序列\(A\),有性质:相邻两个数之差的绝对值为\(1\)的数量为\(n-1\)。那么,对于这道题,能使环剪开一条边使其按编号排序,必有相邻两个\(i,j\),满足\((A_i-A_j=1)\)的数量为\(n-1\)。注意,因为这是个环,所以\(i,j\)大小关系不能......
  • P9032 [COCI2022-2023#1] Neboderi 题解
    P9032考试题。发现\(g\)的值是若干个相同的段,且段数很少,因为每次取\(\gcd\)至少会将值域变为原来的一半。所以段数是\(\mathcal{O}(\logV)\)的。然后就可以从小到大枚举左端点,然后枚举\(g\)的值,找的是最远的满足\(\gcd(a_l,\dots,a_r)=g\)的\(r\),这里可以使用二分......