Wuyanru's blog
0%

[GYM104023B] Recruitment

发表于 分类于 ，

哦，牛魔构造。

题目链接。

题意

现在有 个数字排成一列，现在进行了 次操作。

每一次操作会选择两个相邻的元素 ，将他们删掉，然后替换成一个数字 。

现在告诉你第 次操作后所有元素和为 ，构造数字及操作的方案。

。。

题解

考虑一个数字 与 合并之后，数字总和一定会 ，这样我们就能知道哪些位置是和 合并了。

这一部分是简单的，因为数字 和任意一个数字合并，都不影响之后的情况。

那考虑把所有 拿出来，统一放到数组最右边进行合并。

那也就是说，只需要解决，初始的时候没有数字 的情况。

考虑 ，也就是说初始的时候最多就只有 左右个数字。

考虑第 次合并完之后，可以知道当前有 个数字，和是 ，积是 。

打表可以发现这部分方案数并不多，这意味着我们可以暴力转移。

目前我们知道第 次操作之后，序列肯定长这个样子：。

考虑从后往前推，枚举每一个可能的样子并进行扩展，即对于每一个 ，推出第 次操作之后，序列可能长什么样。

去重之后，一个位置的可能性最多只有 余种。

最后只需要看一下，第 次操作之后，有没有可能的序列，就知道是否有解了。

构造的话，只需要把这个序列的变化方式找出来，建成一棵树的样子，然后合并即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
using pl=pair<ll,ll>;
using ti=tuple<int,int,int>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
const int P=114514191;
map<pl,bool>vis[100001];
vc<vc<int> >b[100001];
vc<ti>nx[100001];
int a[100001];
vc<int>ans[51];
int val[70],siz[70],dfn[70];
int ls[70],rs[70];
int wt[70];
int n,cnt,tim;
inline pl run(vc<int>&a)
{
    ll ans1=0,ans2=0;
    for(int i:a)
    {
        ans1+=i^P;
        ans2+=(ll)(i^P)*(i^P);
    }
    return pl(ans1,ans2);
}
inline int S(ll v)
{
    if(v<0) return -1;
    int p=sqrt(v)+0.5;
    if((ll)p*p!=v) return -1;
    return p;
}
inline int check(int v1,int v2)
{
    //a+b=v1,a*b=v2;
    int num=S((ll)v1*v1-4ll*v2);
    if(num==-1||num>v1) return -1;
    if((num+v1)&1) return -1;
    return (num+v1)>>1;
}
inline void output(int p)
{
    dfn[p]=tim;
    if(val[p]) printf("%d ",val[p]),tim++;
    else assert(ls[p]&&rs[p]),output(ls[p]),output(rs[p]);
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    b[n].push_back(vc<int>(1,a[n]));

    int c=1,v=0,lst=n;
    for(int i=n-1;i;i--)
    {
        if(a[i]>a[i+1])
        {
            if(a[i]!=a[i+1]+1)
            {
                printf("-1\n");
                return 0;
            }
            v++;
        }
        else
        {
            c++;int d=a[i+1]-a[i];
            for(unsigned id=0;id<b[lst].size();id++)
            {
                auto &p=b[lst][id];
                map<int,bool>vvis;
                for(unsigned I=0;I<p.size();I++)
                {
                    int v=p[I];
                    if(vvis.count(v)) continue;
                    vvis[v]=1;if(v<d) continue;
                    //(a,b)  a+b=v-d,a*b=v
                    int a=check(v-d,v),b=v-d-a;
                    if(a==-1) continue;
                    auto q=p;q[I]=a,q.push_back(b);
                    pl V=run(q);if(vis[i].count(V)) continue;
                    vis[i][V]=1,::b[i].push_back(q);
                    nx[i].push_back(ti(lst,id,I));
                }
            }
            lst=i;
        }
    }
    if(b[lst].size()==0)
    {
        printf("-1\n");
        return 0;
    }
    int id=0,all=c;
    for(int v:b[lst][0]) cnt++,val[cnt]=v,siz[cnt]=1,wt[cnt-1]=cnt;

    while(lst<n)
    {
        auto [to,w,i]=nx[lst][id];
        //merge wt[i] wt[c]
        cnt++,c--,ls[cnt]=wt[i],rs[cnt]=wt[c],wt[i]=cnt;
        siz[cnt]=siz[ls[cnt]]+siz[rs[cnt]];
        lst=to,id=w;
    }

    output(cnt);
    for(int i=all+1;i<=n;i++) printf("1 ");
    putchar('\n');

    int now=n-1,Y=all;
    for(int i=1;i<n;i++)
    {
        if(a[i]>a[i+1]) printf("%d\n",now--);
        else Y++,printf("%d\n",dfn[Y]+siz[ls[Y]]);
    }
    return 0;
}
/*
6
21 26 25 29 72 720
*/