站长统计是什么意思_宁波网站建设制作推广_seo在线培训机构排名_杭州seo工作室

题目大意

你需要构造一个长度为 $n$ 的回文序列 $a_1,\cdots ,a_n$，在这个序列的所有子串中，除了一个子串的和你不知道，其他所有 $a$ 的子串的元素和你都知道，换句话说，你分别知道所有子串中 $\frac{n(n+1)}{2}-1$ 个子串的和。请构造任意一个符合要求的序列。

“子串”的定义是整个序列中某个连续的一段。

$t\le 200$，$n\le 1000$，$s_i\le 10^9$。

题解

有趣的题，然而我是看了题解才会的。

首先考虑如果知道了全部子串的和应该怎么做。

发现原序列是回文的，就说明除了位于中间（l=n-r+1）的区间和外，每个区间和都会出现偶数次（左右对称），而位于中间的区间的区间和只会出现奇数次。于是我们就可以找出所有中间的区间，将他们排序后作差便可以得到整个序列。

可是对于这道题，如果缺失的子串和是这 $\frac{n}{2}$ 个中的某个时就用不了这个方法了。

然后我就不会了，以下部分是看了题解后才会的，用自己的理解讲一讲。

对于知道全部子串的和的问题，其实还有一种解法。

首先， $\frac{n(n+1)}{2}$ 个子串中最大值显然是 $l=1,r=n$ 的子串的和，也就是整个序列的和，次大值显然是 $l=1,r=n-1$ 和 $l=2,r=n$ 的子串和，于是我们就可以推出 $a_1,a_n$。第三大的值有可能是 $l=1,r=n-2$ （对称的就不赘述了）或 $l=2,r=n-1$，但是此时因为我们知道了 $a_1,a_n$ 的值，所以也可以推出 $l=2,r=n-1$ 的值，把这个值删除后第三大的一定是 $l=1,r=n-2$，于是我们又可以推出 $a_2,a_{n-1}$ 的值。第四大的值有可能是 $l=1,r=n-3$，$l=2,r=n-2$，我们可以推出 $l=2,r=n-2$ 的值，把这个值删去后第四大的一定是 $l=1,r=n-3$ ，我们又可以推出 $a_3,a_{n-2}$ 的值……以此类推，我们可以得到整个序列。

考虑下这个做法在什么情况下能使用。

如果缺失的子串是方法1中的位于中间的区间，即只出现奇数次，那么是会出问题的，反之其他的串都出现了偶数次，这个方法只需要找最大值，所以缺失一个不会有什么影响。在观察一下，发现大多数的区间最后都是要被删除的，真正需要用到的区间其实只有 $1,n$，$1,n-1$，$1,n-2$ ……而这些区间中，只有 $1,n$ 是位于中间的。

也就是说，只要缺失的子串不是 $1,n$ ，就可以用方法2得出答案。而如果是 $1,n$，在解法1中， $1,n$ 的用处是和 $2,n-1$ 作差得到 $a_1,a_n$，但其实这也可以通过 $1,n-1$ 和 $2,n-1$ 作差得到。 $1,n-1$ 是此时的最大值（因为本来的最大值缺失了，次大值就成了最大值）， $2,n-1$ 是所有出现过奇数次的数中的最大值，于是我们可以很快找到这两个数，求出 $a_1,a_n$ 后使用方法1就做完了。

复杂度 $O(mlogm)$ （$m=\frac{n(n+1)}{2}-1$），瓶颈在排序。

代码

调了挺久的……感觉写起来有点鬼畜，当然也可能是因为我太笨了。

#include<bits/stdc++.h>
using namespace std;const int N=1000+5;int kase,n,m,cnt,a[N],b[N*N],c[N];
map<int,int> mp;bool cmp(int x,int y){return x>y;
}void init(){memset(a,0,sizeof(a));memset(c,0,sizeof(c));mp.clear();cnt=0;
}int main(){scanf("%d",&kase);while(kase--){init();scanf("%d",&n);m=n*(n+1)/2-1;for(int i=1;i<=m;i++)scanf("%d",&b[i]);sort(b+1,b+1+m,cmp);if(b[1]!=b[2]){int sum=b[1];for(int i=1;i<=m;i++){if(mp[b[i]]){mp[b[i]]--;continue;}c[++cnt]=b[i];mp[b[i]]++;if(cnt>1){a[cnt-1]=a[n-cnt+2]=c[cnt-1]-c[cnt];if(cnt*2>=n) break;mp[a[cnt-1]]+=2;sum-=2*a[cnt-1];int now=sum;mp[now]++;for(int i=cnt-1;i>1;i--){now+=a[i];mp[now]+=2;}}}if(n&1) a[n/2+1]=c[cnt]-(c[1]-c[cnt]);else a[n/2]=(c[cnt]-(c[1]-c[cnt]))/2;}else{int now=0;for(int i=1;i<=m;i++){now++;if(b[i]!=b[i+1]){if(now&1) c[++cnt]=b[i];now=0;}}a[cnt+1]=(n&1)?c[cnt]:c[cnt]/2;for(int i=cnt;i>=2;i--)a[i]=(c[i-1]-c[i])/2;a[1]=b[1]-c[1];}for(int i=1;i*2<=n;i++)printf("%d ",a[i]);if(n&1) printf("%d ",a[n/2+1]);for(int i=n/2;i>=1;i--)printf("%d ",a[i]);printf("\n");}return 0;
}