CF1965D Missing Subarray Sum题解

题目链接

点击打开链接

题目解法

感觉一点都不好想\fn

因为最后的序列 \(a\) 是回文的，所以只有以中心点对称的子段和出现次数为奇数，其他都为偶数
考虑有没有什么知道所有子段和的做法，可以方便推出缺失一个的答案
令 \(g_{l,r}\) 为 \(l\) 到 \(r\) 的子段和

1. 知道 \(g_{1,n}\)
   删除 \(g_{1,n}\) 之后，\(s\) 的最大值一定是 \(g_{1,n-1}\)，这可以推出 \(a_1\) 和 \(a_n\)
   如何得到 \(g_{1,n-2}\)？比 \(g_{1,n-2}\) 大的只可能是 \(g_{1,n-1}\) 和 \(g_{2,n-1}\)，把这两个在 \(s\) 中删掉，剩下的 \(s\) 中的最大值就是 \(g_{1,n-2}\)
   以此类推，我们就可以得出答案
2. 不知道 \(g_{1,n}\)
   把出现奇数次的数拉出来，从小到大排序，不难得出 \(a_2,...,a_{n-1}\)
   \(a_1\) 和 \(a_n\) 只要用 \(g_{1,n-1}\) 减去 \(g_{2,n-1}\) 即可

时间复杂度 \(O(n^2\log n)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=2010;
int n,a[N];
map<int,int> mp;
void del(int v){ mp[v]--;if(mp[v]<=0) mp.erase(v);}
int ED(){ return (*mp.rbegin()).first;}
void solve1(){
    int prv=ED();del(prv);
    int sum=prv;
    int i=1,j=n;
    while(i<=j){
        int x=ED();
        a[i]=a[j]=prv-x;prv=x;
        sum-=a[i]+a[j];
        int cur=sum;del(cur);
        DF(k,i,1) cur+=a[k],del(cur),del(cur);
        i++,j--;
    }
}
int b[N];
void solve2(){
    int len=0;
    for(auto [x,y]:mp) if(y&1) b[++len]=x;
    int i=(n+1)/2,j=n/2+1;
    F(k,1,len) a[i]=a[j]=(b[k]-b[k-1])/2,i--,j++;
    if(n&1) a[(n+1)/2]=b[1];
    a[1]=a[n]=ED()-b[len];
}
void work(){
    mp.clear();
    read(n);
    F(i,1,n*(n+1)/2-1){ int x;read(x);mp[x]++;}
    if(mp[ED()]==1) solve1();else solve2();
    F(i,1,n) printf("%d ",a[i]);puts("");
}
int main(){
    int T;read(T);
    while(T--) work();
    return 0;
}