2020-2021:teams:wangzai_milk:atcoder_beginner_contest_128_vp
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:atcoder_beginner_contest_128_vp [2020/07/21 11:24] wzx27 创建 |
2020-2021:teams:wangzai_milk:atcoder_beginner_contest_128_vp [2020/07/21 11:32] (当前版本) wzx27 |
||
|---|---|---|---|
| 行 107: | 行 107: | ||
| === 题意 === | === 题意 === | ||
| + | 在一条数轴上有 $N$ 个点 $0,1,2 \dots n-1$，每个点权值为 $s_i$。在开始前选两个正整数 $A,B$，青蛙从 $0$ 开始跳，跳的序列为$0,A,A-B,2A-B\cdots k(A-B),k(A-B)+A = n-1$。 | ||
| + | 每次必须跳在 $0 \cdots n-1$ 上，且每个点最多跳一次，求跳过得所有点的最大权值和。 | ||
| === 数据范围 === | === 数据范围 === | ||
| + | $3 \le N \lt 10^5$ | ||
| + | $-10^9 \le s_i \le 10^9$ | ||
| + | === 题解 === | ||
| + | |||
| + | 将序列拆分成两个序列：$k*(A-B)$ 和 $k*(A-B) + A$。 | ||
| + | |||
| + | 记 $d = A-B$,可以看成是两个等差数列 $k*d$ 和 $n-1 - k*d$ | ||
| + | |||
| + | 所以预处理每个 $d$ 的前后缀，再枚举 $k$ 和 $d$ 取最大值。 | ||
| + | |||
| + | <hidden><code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | #define ll long long | ||
| + | #define pii_ pair<int,int> | ||
| + | #define mp_ make_pair | ||
| + | #define pb push_back | ||
| + | #define fi first | ||
| + | #define se second | ||
| + | #define rep(i,a,b) for(int i=(a);i<=(b);i++) | ||
| + | #define per(i,a,b) for(int i=(a);i>=(b);i--) | ||
| + | #define show1(a) cout<<#a<<" = "<<a<<endl | ||
| + | #define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl | ||
| + | using namespace std; | ||
| + | const ll INF = 1LL<<60; | ||
| + | const int inf = 1<<30; | ||
| + | const int maxn = 1e5+5; | ||
| + | inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);} | ||
| + | |||
| + | int s[maxn]; | ||
| + | vector<ll> pre[maxn],suf[maxn]; | ||
| + | int main() | ||
| + | { | ||
| + | fastio(); | ||
| + | int n; cin>>n; | ||
| + | rep(i,0,n-1) cin>>s[i]; | ||
| + | rep(i,1,n-1){ | ||
| + | for(int j=0;j<n;j+=i){ | ||
| + | if(pre[i].size() == 0) pre[i].pb(s[j]); | ||
| + | else pre[i].pb(pre[i].back() + s[j]); | ||
| + | } | ||
| + | for(int j=n-1;j>=0;j-=i){ | ||
| + | if(suf[i].size() == 0) suf[i].pb(s[j]); | ||
| + | else suf[i].pb(suf[i].back() + s[j]); | ||
| + | } | ||
| + | } | ||
| + | ll ans = 0; | ||
| + | rep(k,1,n-1){ | ||
| + | for(int d=1;d*k<n-1;d++){ | ||
| + | int A = n-1-k*d; | ||
| + | int B = A-d; | ||
| + | if(B <= 0) break; | ||
| + | if(A%d==0 && A/d<=k) continue; | ||
| + | ans = max(ans,pre[d][k] + suf[d][k]); | ||
| + | } | ||
| + | } | ||
| + | cout<<ans<<endl; | ||
| + | return 0; | ||
| + | } | ||
| + | </code> </hidden> | ||
| + | \\ | ||
| === 题解 === | === 题解 === | ||
2020-2021/teams/wangzai_milk/atcoder_beginner_contest_128_vp.1595301884.txt.gz · 最后更改: 2020/07/21 11:24 由 wzx27
