2024.2.18 梦熊模拟赛 T1 题解
__vector__ · · 个人记录
这道题我记得原题是图灵杯（CF 也有），并且洛谷上有，这道题应该是个 well-known。
当时爆零，没补题
这次奋战 4h（晚了 0.5h 参赛，算到赛后 0.5h）通过了这道题，写题解记录一下。
为了迎接寒冬，Farer John 准备了 堆木材用来修补他牛圈的围栏！其中第 块木材的长度为
a_i 。虽然木材的长度参差不齐，但是 Farer John 不想把围栏修补坑坑洼洼的形状，而且要修建的围栏有两条。因此 Farer John 决定把这 堆木材分成两排，每排的木材的长度依次能构成一个公差非负的的等差序列。但是堆积的木材实在是太多了！Farer John 感到无从下手，于是奶牛 Bassie 邀请了你来制订方案，或是判断不存在合法的方案。
设
由此计算出第一个等差数列的公差
然后不断跳转到第
怎么跳转到下一个符合要求的点是个关键。
假设当前点
也就是说，我们需要对于
容易想到
但是显然过不去，于是想到主席树。可以发现每个点
那么第二序列如何判断呢？
可以预处理出每个点向前（延伸到
然后在第一序列跳转过程中分情况讨论，判断第二序列合法性。
另外我们每跳转到一个点，都判断如果第一序列以此结尾，那么是否合法。
只要我们找出一个方案合法，那么立刻退出，如果当前方案一旦判断不合法，也立刻退出。
那么复杂度看上去似乎不对啊。
简单推导可得复杂度是
我能想到的让跳转总次数最长的构造方式：
这样跳转总次数是
总复杂度
如果错了，请大佬们指出。
// By __vector__ (luoguid = 507348) , real name = liumonong
#include <bits/stdc++.h>
using namespace std;
const int inf=INT_MAX;
const int maxn=1e5+5;
int n;
int a[maxn];
struct Node{
int ls,rs,l,r,val;
};
struct HJT{
Node node[maxn*25];
int nodecnt=0;
int rt[maxn];
inline int ls(int pos){
return node[pos].ls;
}
inline int rs(int pos){
return node[pos].rs;
}
int build(int l,int r){
int now=++nodecnt;
node[now].l=l,node[now].r=r;
if(l==r){
node[now].val=inf;
return now;
}
int mid=(l+r)/2;
node[now].ls=build(l,mid);
node[now].rs=build(mid+1,r);
return now;
}
int chg(int oldnode,int x,int val){
int nwnode=++nodecnt;
node[nwnode]=node[oldnode];
if(node[oldnode].l==node[oldnode].r){
node[nwnode].val=val;
return nwnode;
}
int mid=(node[oldnode].l+node[oldnode].r)/2;
if(mid>=x)node[nwnode].ls=chg(ls(oldnode),x,val);
else node[nwnode].rs=chg(rs(oldnode),x,val);
return nwnode;
}
int query(int pos,int x){
if(node[pos].l==node[pos].r){
return node[pos].val;
}
int mid=(node[pos].l+node[pos].r)/2;
if(mid>=x)return query(ls(pos),x);
return query(rs(pos),x);
}
}hjt;
struct Disc{
int disc[maxn];
int top;
void init(int* a,int n){
for(int i=1;i<=n;i++){
disc[i]=a[i];
}
sort(disc+1,disc+n+1);
top=unique(disc+1,disc+n+1)-disc-1;
}
int rank(int val){
int pos=lower_bound(disc+1,disc+top+1,val)-disc;
if(pos==top+1)return -1;
if(disc[pos]!=val)return -1;
return pos;
}
int rktoval(int rk){
return disc[rk];
}
}disc;
int len[maxn];
bool tag[maxn];
int main(){
// freopen("fence.in","r",stdin);
//freopen("fence.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
if(n==2){
printf("1\n%d\n1\n%d\n",a[1],a[2]);
return 0;
}
sort(a+1,a+n+1);
disc.init(a,n);
for(int i=1;i<=n;i++){
// printf("i = %d val = %d\n",i,a[i]);
a[i]=disc.rank(a[i]);
}
hjt.rt[n]=hjt.build(1,n);
for(int i=n-1;i>=1;i--){
hjt.rt[i]=hjt.chg(hjt.rt[i+1],a[i+1],i+1);
}
for(int i=1;i<=n;i++){
if(i==1){
len[i]=1;
}else{
if(i==2){
len[i]=2;
}else{
len[i]=2;
if(disc.rktoval(a[i])-disc.rktoval(a[i-1])==disc.rktoval(a[i-1])-disc.rktoval(a[i-2])){
len[i]=len[i-1]+1;
}
}
}
}
for(int sec=2;sec<=n;sec++){
// printf("sec2 = %d\n",sec);
if(sec-2>=1){
if(len[sec-1]<sec-2){
break;
}
}
bool ok=1;
int now=sec;
int d=disc.rktoval(a[sec])-disc.rktoval(a[1]);// 1 序列公差
int d2=-1;// 2 序列公差
if(sec>=4)d2=disc.rktoval(a[sec-1])-disc.rktoval(a[sec-2]);
int lst2=-1;
if(sec>=3)lst2=a[sec-1];// 2 序列目前遍历到的最后一个数
vector<int> seq1;
// printf("i = %d\n",sec);
seq1.emplace_back(1);
while(now<n){
// printf("now = %d d = %d\n",now,d);
seq1.emplace_back(now);
int _new=disc.rank(disc.rktoval(a[now])+d);
if(_new==-1||hjt.query(hjt.rt[now],_new)==inf){
// printf("fail can't find %d + %d = %d\n",disc.rktoval(a[now]),d,disc.rktoval(a[now])+d);
// 不存在 _new，所以 now 是最后一个
// 应该判断之后是否合法
if(len[n]<n-(now+1)+1)ok=0;
if(now==n-1){
// 2 序列最后一个单位只有一个数
if(d2!=-1){// 2 序列存在公差
if(lst2!=-1&&disc.rktoval(a[n])-disc.rktoval(lst2)!=d2){
ok=0;
}
}
}else{
if(d2==-1){// 没有公差，先设定
d2=disc.rktoval(a[n])-disc.rktoval(a[n-1]);
}else{
if(disc.rktoval(a[n])-disc.rktoval(a[n-1])!=d2){
ok=0;// 判断最后一段是否满足公差
}
}
if(lst2!=-1&&disc.rktoval(a[now+1])-disc.rktoval(lst2)!=d2){
ok=0;// 连接处是否满足公差
}
}
break;
}
if(1){
// 假设从 now 截止
int oldd2=d2;
bool ok2=1;
if(len[n]<n-(now+1)+1)ok2=0;
if(now==n-1){
// 2 序列最后一个单位只有一个数
if(d2!=-1){// 2 序列存在公差
if(lst2!=-1&&disc.rktoval(a[n])-disc.rktoval(lst2)!=d2){
ok2=0;
}
}
}else{
if(d2==-1){// 没有公差，先设定
d2=disc.rktoval(a[n])-disc.rktoval(a[n-1]);
}else{
if(disc.rktoval(a[n])-disc.rktoval(a[n-1])!=d2){
ok2=0;// 判断最后一段是否满足公差
}
}
if(lst2!=-1&&disc.rktoval(a[now+1])-disc.rktoval(lst2)!=d2){
ok2=0;// 连接处是否满足公差
}
}
if(ok2){
// printf("stop = %d\n",now);
// printf("stop = %d\n",now);
break;
}else{
// printf("failstopping = %d\n",now);
d2=oldd2;
}
}
// 记得更新 lst2
_new=hjt.query(hjt.rt[now],_new);
// printf("_new = %d\n",_new);
if(_new-now-1==1){
// 中间一个数
if(lst2==-1){
lst2=a[now+1];
now=_new;
continue;
}
if(d2==-1){
// 2没有公差，建立
d2=disc.rktoval(a[now+1])-disc.rktoval(lst2);
}else{
if(lst2!=-1&&disc.rktoval(a[now+1])-disc.rktoval(lst2)!=d2){
ok=0;
break;
}
}
}else if(_new-now-1>=2){
// 中间超过两个数
if(len[_new-1]<_new-now-1)ok=0;
if(d2==-1){
d2=disc.rktoval(a[_new-1])-disc.rktoval(a[_new-2]);
}else{
if(disc.rktoval(a[_new-1])-disc.rktoval(a[_new-2])!=d2){
ok=0;
}
}
if(lst2!=-1&&disc.rktoval(a[now+1])-disc.rktoval(lst2)!=d2){
ok=0;
}
}
if(_new-now-1>=1)lst2=a[_new-1];
now=_new;
if(!ok)break;
}
if(ok){
seq1.emplace_back(now);
// printf("seq1.size() = %d\n",seq1.size());
int cnt1=1;
tag[seq1[0]]=1;
for(int i=1;i<seq1.size();i++){
if(seq1[i]!=seq1[i-1])tag[seq1[i]]=1,cnt1++;
}
printf("%d\n",cnt1);
for(int i=1;i<=n;i++){
if(tag[i])printf("%d ",disc.rktoval(a[i]));
}
printf("\n");
printf("%d\n",n-cnt1);
for(int i=1;i<=n;i++){
if(!tag[i])printf("%d ",disc.rktoval(a[i]));
}
return 0;
}
}
puts("-1");
return 0;
}