专栏文章

题解：P12074 [OOI 2025] The arithmetic exercise

1123456xwd
P12074题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mion53kz
此快照首次捕获于
2025/12/02 21:55
3 个月前
此快照最后确认于
2025/12/02 21:55
3 个月前
查看原文
比较神秘的题目。
考虑既然 xix_i 之间是独立的，且若从前往后考虑的话，每次都要乘上一个 −1-1，不妨将其翻转，倒着考虑，这样子第一次贡献一定是正，第二次一定为负，...，这样就方便储存信息。
设 fi,jf_{i,j} 表示考虑了搞了前 ii 个，目前 jj 个若得到贡献会为负数（即 jj 个接受了奇数次贡献）的最大值。
则 f0,0=0f_{0,0}=0，且 fi,j=max⁡(fi−1,j−1+xi,fi−1,j+1−xi)f_{i,j}=\max(f_{i-1,j-1}+x_i,f_{i-1,j+1}-x_i)。
那么一个加，一个减，不好看，变化为：fi,j=max⁡(fi−1,j−1+2xi,fi−1,j+1)−xif_{i,j}=\max(f_{i-1,j-1}+2x_i,f_{i-1,j+1})-x_i，那么最后减去 ∑xi\sum x_i，式子变为：fi,j=max⁡(fi−1,j−1+2xi,fi−1,j+1)f_{i,j}=\max(f_{i-1,j-1}+2x_i,f_{i-1,j+1})。
那么发现一个非常有趣的性质，由于 j−1,j+1j-1,j+1 的奇偶性相同，根据我们的初始状态，那么当 i,ji,j 奇偶性相同的时候，fi,jf_{i,j} 才有实际意义。
那么不妨把 2j,2j+1(j≥0)2j,2j+1(j\ge 0) 视作一个东东，那么有：
  1. ii 为奇数：fi,j=max⁡(fi−1,j+2xi,fi−1,j+1)f_{i,j}=\max(f_{i-1,j}+2x_i,f_{i-1,j+1})。
  2. ii 为偶数：fi,j=max⁡(fi−1,j,fi−1,j−1+2xi)f_{i,j}=\max(f_{i-1,j},f_{i-1,j-1}+2x_i)。
一眼丁真，鉴定为 slope trick。
凸性如何证明，设 Δi,j=fi,j−fi,j−1\Delta_{i,j}=f_{i,j}-f_{i,j-1}，实际上我们可以证明其是单调递减的，即是一个上凸包。
  1. 若 ii 为偶数，那么 fi,j=fi−1,j−1+max⁡(Δi−1,j,2xi)f_{i,j}=f_{i-1,j-1}+\max(\Delta_{i-1,j},2x_i)。
    那么前面一段会选择 Δ\Delta，后面一段会选择 2xi2x_i。
    考虑取到 Δ\Delta 的那一段，有：Δi,j=fi,j−fi,j−1=(fi−1,j−1+Δi−1,j)−(fi−1,j−2+Δi−1,j−1)=Δi−1,j\Delta_{i,j}=f_{i,j}-f_{i,j-1}=(f_{i-1,j-1}+\Delta_{i-1,j})-(f_{i-1,j-2}+\Delta_{i-1,j-1})=\Delta_{i-1,j}
    对于取到 2xi2x_i 那一段，更简单，Δi,j=Δi−1,j−1\Delta_{i,j}=\Delta_{i-1,j-1}。
    对于分界点，Δi,k=(fi−1,k−1+2xi)−(fi−1,k−2+Δi−1,k−1)=2xi\Delta_{i,k}=(f_{i-1,k-1}+2x_i)-(f_{i-1,k-2}+\Delta_{i-1,k-1})=2x_i
    由于有 2xi≥Δi−1,k=Δi,k+12x_i\ge \Delta_{i-1,k}=\Delta_{i,k+1}，那么显然 Δ\Delta 继续单调递增。
  2. 若 ii 为奇数，那么 fi,j=fi−1,j+max⁡(2xi,Δi−1,j+1)f_{i,j}=f_{i-1,j}+\max(2x_i,\Delta_{i-1,j+1})。
    那么前面一段会选择 Δ\Delta，后面一段会选择 2xi2x_i。
    考虑取到 Δ\Delta 的那一段，有：Δi,j=fi,j−fi,j−1=(fi−1,j+Δi−1,j+1)−(fi−1,j−1+Δi−1,j)=Δi−1,j+1\Delta_{i,j}=f_{i,j}-f_{i,j-1}=(f_{i-1,j}+\Delta_{i-1,j+1})-(f_{i-1,j-1}+\Delta_{i-1,j})=\Delta_{i-1,j+1}
    对于取到 2xi2x_i 那一段，更简单，Δi,j=Δi−1,j\Delta_{i,j}=\Delta_{i-1,j}。
    对于分界点，Δi,j=(fi−1,j+2xi)−(fi−1,j−1+Δi−1,j)=2xi\Delta_{i,j}=(f_{i-1,j}+2x_i)-(f_{i-1,j-1}+\Delta_{i-1,j})=2x_i
    Δ\Delta 递减的证明同上，不再赘述。
那么直接用 multiset 维护这个 Δ\Delta 即可。
细节：
  1. ii 为奇数的时候，由上面，可知我们要把 Δ1\Delta_{1} 计入答案并在 multiset 中删除。
  2. ii 奇偶性不同的时候，jj 的上界不同。
C
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define p_b push_back
#define m_p make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define ls k<<1
#define rs k<<1|1
#define mid ((l+r)>>1)
#define gcd __gcd
#define lowbit(x) (x&(-x))
using namespace std;
int rd(){
    int x=0,f=1; char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if (ch=='-') f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return x*f;
}
void write(int x){
    if(x>9) write(x/10);
    putchar('0'+x%10);
}
const int N=3e5+5,INF=0x3f3f3f3f3f3f3f3f;
int n,m,a[N],ans,val;
multiset<int,greater<int> > s;
void solve(){
	n=rd();m=rd();for(int i=1;i<=m;i++)a[i]=rd(),val-=a[i];
	reverse(a+1,a+1+m);
	for(int i=1;i<=m;i++){
		s.insert((a[i]<<1ll));
		if(i&1) val+=(*s.begin()),s.erase(s.begin());
		int lim=(n+2-(i&1))>>1;
		while(s.size()>=lim) s.erase(prev(s.end()));
	}
	ans=val;
	for(auto u : s) val+=u,ans=max(ans,val);
	printf("%lld\n",ans);
}
void clean(){
	ans=val=0;
	s.clear();
}
signed main(){
	int T=rd();while(T--)solve(),clean();
    return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...