省队集训-0423模拟赛
allenchoi
·
·
个人记录
A.树
题意：
CF1958I
有两棵树，大小为 n，以 1 为根。定义一次操作，为选择某棵树上的一个非根节点，把它删除，并把它的儿子全部连到它的父亲上。求最少几次操作，使得两棵树完全相同。
#### Sol：
显然两棵树保留的点集是一样的，要最大化这个电集。
新树等价于删点之后按祖先关系连边。也就是说，如果 $(x,y)$ 在两棵树上的祖先关系不一样，则不能都保留。
考虑折半搜索，右边的点集会对左边的点集产生限制，要求不能包含某些点。因此先把左边的点集跑出来，做个高维前缀和即可，总复杂度 $O(2^{\frac{n}{2}}n)$。
#### Code：
~~~cpp
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define pcnt __builtin_popcount
using namespace std;
typedef long long ll;
const int N = 45;
int n,U,ans,step[2],siz[N][2],dfn[N][2],f[1 << 21];
ll anc[N][2],bnd[N];
vector <int> v[N][2];
void dfs1(int x,int lst,int t)
{
siz[x][t] = 1,dfn[x][t] = ++step[t];
for(int y : v[x][t]) if(y != lst) dfs1(y,x,t),siz[x][t] += siz[y][t];
}
void dfs2(int x,int c,ll s)
{
if(x == n / 2)
{
f[U ^ (s & U)] = max(f[U ^ (s & U)],c);
return ;
}
dfs2(x - 1,c,s);
if(!(s & (1LL << x))) dfs2(x - 1,c + 1,s | bnd[x]);
}
void dfs3(int x,int s1,ll s2)
{
if(x == n / 2 + 1)
{
ans = max(ans,f[s1] + pcnt(s1));
return ;
}
dfs3(x + 1,s1,s2);
if(!(s2 & (1 << x))) dfs3(x + 1,s1 | (1 << x),s2 | bnd[x]);
}
int main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
scanf("%d",&n);
for(int t = 0;t < 2;t++)
for(int i = 1,a,b;i < n;i++)
{
scanf("%d%d",&a,&b);
v[a][t].pb(b),v[b][t].pb(a);
}
dfs1(1,0,0),dfs1(1,0,1);
for(int t = 0;t < 2;t++)
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
if(dfn[j][t] <= dfn[i][t] && dfn[i][t] <= dfn[j][t] + siz[j][t] - 1)
anc[i][t] |= (1LL << j);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
if((anc[i][0] & (1LL << j)) != (anc[i][1] & (1LL << j)))
bnd[i] |= (1LL << j),bnd[j] |= (1LL << i);
for(int i = 1;i <= n / 2;i++) U |= (1 << i);
dfs2(n,0,0);
for(int i = 1;i <= n / 2;i++)
for(int j = 2;j <= (1 << (n / 2 + 1));j += 2)
if(j & (1 << i))
f[j ^ (1 << i)] = max(f[j ^ (1 << i)],f[j]);
dfs3(1,0,0);
printf("%d\n",(n - ans) * 2);
return 0;
}
~~~
### B.序列
#### 题意：
ARC066D
给定一个长为 $n$ 的序列和一个常数 $C$，定义序列代价为：
$$\max\limits_{S\subseteq\set{1,2,...,n}}C\times\sum\limits_{1\le l\le r\le n}[\set{l,l+1,...,r}\subseteq S]-\sum\limits_{i\in S}a_i$$
先查询原序列权值，然后 $m$ 次：单点修改 $a_x\leftarrow y$，查询序列价值，然后撤销修改。
$n,m\le3\times10^5,1\le C\le10^5,a_i,y\le10^9$。
#### Sol：
DP 式子为 $f_i=\max\limits_jmaxn_{j-1}+\frac{(i-j+1)(i-j+2)}{2}C-s_i+s_{j-1}$，$maxn$ 为 $f$ 前缀 $\max$，$s$ 为前缀和。可以斜率优化做到线性。
然后考虑怎么求每次单点修改后的答案。先正着、反着各 $DP$ 一次。如果 $x\notin S$ 则不受影响，这一部分的答案等于前缀 $\max$ 加后缀 $\max$；如果 $x\in S$，考虑分治，钦定 $x$ 所在的极长连续段 $\subseteq[l,r]$ 并跨过 $mid$，在区间内再跑两次斜优，加上两侧前后缀 $\max$ 的贡献即可。
总复杂度 $O(n\log n)$。
#### Code：
~~~cpp
#include <bits/stdc++.h>
#define pii pair <int,int>
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 3e5 + 5,M = 3e7 + 5;
int n,m,C,top,a[N],st[N];
ll s[N],X[N],Y[N],maxn1[N],maxn2[N],ans[N],val[N];
vector <pii> v[N];
bool K(int a,int b,int c){return (__int128)(Y[b] - Y[a]) * (X[c] - X[b]) < (__int128)(Y[c] - Y[b]) * (X[b] - X[a]);}
ll calc(int f,int x){return Y[f] - 1LL * X[f] * x;}
void solve(int l,int r)
{
if(l == r)
{
for(pii p : v[l]) ans[p.se] = max(ans[p.se],maxn1[l - 1] + maxn2[l + 1] + 2 * (C - p.fi));
return ;
}
int mid = (l + r) / 2;
ll maxn = -1e18;
top = 0;
for(int i = r;i > mid;i--)
{
X[i] = -1LL * C * i,Y[i] = 1LL * C * i * i + maxn2[i + 1] - 2 * s[i];
while(top > 1 && K(st[top - 1],st[top],i)) top--;
st[++top] = i;
}
for(int i = mid;i >= l;i--)
{
while(top > 1 && calc(st[top - 1],-2 * i + 3) > calc(st[top],-2 * i + 3)) top--;
val[i] = calc(st[top],-2 * i + 3) + 1LL * C * (i - 1) * (i - 2) + 2 * s[i - 1];
}
for(int i = l;i <= mid;i++)
{
maxn = max(maxn,maxn1[i - 1] + val[i]);
for(pii p : v[i]) ans[p.se] = max(ans[p.se],maxn + 2 * (a[i] - p.fi));
}
maxn = -1e18;
top = 0;
for(int i = l;i <= mid;i++)
{
X[i] = 1LL * C * i,Y[i] = 1LL * C * i * i + maxn1[i - 1] + 2 * s[i - 1];
while(top > 1 && K(st[top - 1],st[top],i)) top--;
st[++top] = i;
}
for(int i = mid + 1;i <= r;i++)
{
while(top > 1 && calc(st[top - 1],2 * i + 3) > calc(st[top],2 * i + 3)) top--;
val[i] = calc(st[top],2 * i + 3) + 1LL * C * (i + 1) * (i + 2) - 2 * s[i];
}
for(int i = r;i > mid;i--)
{
maxn = max(maxn,maxn2[i + 1] + val[i]);
for(pii p : v[i]) ans[p.se] = max(ans[p.se],maxn + 2 * (a[i] - p.fi));
}
solve(l,mid),solve(mid + 1,r);
}
int main()
{
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
scanf("%d%d%d",&n,&m,&C);
for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
for(int i = 1;i <= n;i++) s[i] = s[i - 1] + a[i];
for(int i = 1;i <= n;i++)
{
X[i] = 1LL * C * i,Y[i] = 1LL * C * i * i + maxn1[i - 1] + 2 * s[i - 1];
while(top > 1 && K(st[top - 1],st[top],i)) top--;
st[++top] = i;
while(top > 1 && calc(st[top - 1],2 * i + 3) > calc(st[top],2 * i + 3)) top--;
maxn1[i] = max(maxn1[i - 1],calc(st[top],2 * i + 3) + 1LL * C * (i + 1) * (i + 2) - 2 * s[i]);
}
top = 0;
for(int i = n;i >= 1;i--)
{
X[i] = -1LL * C * i,Y[i] = 1LL * C * i * i + maxn2[i + 1] - 2 * s[i];
while(top > 1 && K(st[top - 1],st[top],i)) top--;
st[++top] = i;
while(top > 1 && calc(st[top - 1],-2 * i + 3) > calc(st[top],-2 * i + 3)) top--;
maxn2[i] = max(maxn2[i + 1],calc(st[top],-2 * i + 3) + 1LL * C * (i - 1) * (i - 2) + 2 * s[i - 1]);
}
printf("%lld\n",maxn1[n] / 2);
for(int i = 1,x,y;i <= m;i++)
{
scanf("%d%d",&x,&y);
v[x].pb(mkp(y,i));
ans[i] = maxn1[x - 1] + maxn2[x + 1];
}
solve(1,n);
for(int i = 1;i <= m;i++) printf("%lld\n",ans[i] / 2);
return 0;
}
~~~
### C.栈
#### 题意：
有三个栈 $s1,s2,s3$，初始时 $s1$ 从栈顶到栈底依次是 $p_1,p_2...p_n$，$p$ 为一个排列。给定 $A,B$，每一次操作，可以选择将 $s1$ 顶部的 $x\le A$ 个元素整体平移到 $s2$ 栈顶，或将 $s2$ 顶部的 $x\le B$ 个元素整体平移到 $s3$ 栈顶，要求最后 $s3$ 从顶到底依次是 $1,2,...,n$。问是否有解，有解则构造方案。
多测，$\sum n\le10^6$。
#### Sol：
大力模拟。
如果 $s2$ 中出现了 $p_i+1<p_{i+1}$ 的情况则一定无解。
所以，对于 $s1$ 中 $p_i+1<p_{i+1}$ 的位置，显然不能一次移到 $s2$ 中，那么依此分段考虑。
假设某一段中形成若干极长连续上升段 $[l_1,r_1],[l_2,r_2],...,[l_m,r_m]$。这些段的值域显然是递减的。
如果 $[l_1,r_1]$ 顶到了剩下的数的最大值，则把 $[l_1,r_1]$ 一个一个地放入 $s2$，再一个一个地放入 $s3$，一定最优。然后去掉 $[l_1,r_1]$ 归约到子问题。
如果这些段值域不连续，则只能一次性移过去。
否则，如果每一段长度都不超过 $A$，且加起来不超过 $B$，则可以把 $[l_1,r_1]...[l_m,r_m]$ 依次丢进 $s2$ 中形成一个大的连续段，这样可以尽量避免非法。
否则，如果 $m>2$ 那么只能一次全移到 $s2$ 里面。
然后只剩 $m=1,m=2$ 两种情况。
若 $m=1$，则将这一段一个一个地塞进 $s2$，后面再一个一个地塞进 $s3$，因为如果 $s2$ 中会出现非法情况则一定是无法避免的，这样做不会劣。
然后是 $m=2$ 的情况，最多分两步移走。考虑枚举第一步移动的长度 $k$。
设第一段长为 $x$，第二段长为 $y$。
如果 $k<x$，则 $s2$ 中会形成 $x-k,y+k$ 两段，所以要求 $\max(k,x-k+y)\le A,\max(x-k,y+k)\le B$；
如果 $k>x$，则 $s2$ 中会形成 $2x+y-k,k-x$ 两段，所以要求 $\max(k,x+y-k)\le A,\max(2x+y-k,k-x)\le B$。
由于两段在 $s2$ 中无法拼在一起，所以非法情况无法避免，所以随便找个满足上述条件的 $p$ 即可。
往 $s2$ 里加东西时判一下和栈顶的关系是否非法就做完了，线性。
#### Code：
~~~cpp
#include <bits/stdc++.h>
#define pii pair <int,int>
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
using namespace std;
const int N = 1e6 + 5;
int T,n,A,B,val,p[N];
vector <pii> v,opt;
stack <pii> st;
void work1(vector <pii> a)
{
//s1->s2
int sum = 0;
for(pii p : a) sum += p.se - p.fi + 1;
opt.pb(mkp(1,sum));
for(int i = a.size() - 1;i >= 0;i--)
if(!st.empty() && st.top().fi == a[i].se + 1) st.top().fi = a[i].fi;
else st.push(a[i]);
}
bool work2()
{
//s2->s3
while(!st.empty() && st.top().se == val - 1)
{
if(st.top().se - st.top().fi + 1 > B) return false;
opt.pb(mkp(2,st.top().se - st.top().fi + 1));
val = st.top().fi,st.pop();
}
return true;
}
bool solve()
{
scanf("%d%d%d",&n,&A,&B);
val = n + 1;
for(int i = 1;i <= n;i++) scanf("%d",&p[i]);
for(int l = 1,r;l <= n;l = r + 1)
{
for(r = l;r < n && p[r] + 1 >= p[r + 1];r++);
v.clear();
for(int i = l,j;i <= r;i = j + 1)
{
for(j = i;j < r && p[j + 1] == p[j] + 1;j++);
v.pb(mkp(p[i],p[j]));
}
int siz = v.size(),cur = 0,sum = 0;
while(cur < siz && v[cur].se == val - 1)
{
for(int i = 1;i <= v[cur].se - v[cur].fi + 1;i++) opt.pb(mkp(1,1));
for(int i = 1;i <= v[cur].se - v[cur].fi + 1;i++) opt.pb(mkp(2,1));
val = v[cur].fi,cur++;
if(!work2()) return false;
}
v.erase(v.begin(),v.begin() + cur);
if(!(siz -= cur)) continue;
bool flag = false,h = true;
for(pii p : v) sum += p.se - p.fi + 1;
for(int i = 1;i < siz;i++) flag |= (v[i - 1].fi > v[i].se + 1);
for(pii p : v) h &= (p.se - p.fi + 1 <= A);
if(flag)
{
if(sum > A) return false;
if(!st.empty() && v.back().se + 1 < st.top().fi) return false;
for(pii p : v) if(p.se - p.fi + 1 > B) return false;
work1(v);
continue;
}
if(h && sum <= B)
{
if(!st.empty() && v[0].se + 1 < st.top().fi) return false;
for(pii p : v) work1(vector <pii> {p});
continue;
}
if(siz == 1)
{
if(!st.empty() && v[0].se + 1 < st.top().fi) return false;
if(v[0].se - v[0].fi + 1 <= min(A,B)) work1(v);
else if(!st.empty() && v[0].fi + 1 < st.top().fi) return false;
else for(int i = v[0].fi;i <= v[0].se;i++) work1(vector <pii> {mkp(i,i)});
continue;
}
if(siz == 2)
{
if(!st.empty() && v[0].se + 1 <= st.top().fi) return false;
int x = v[0].se - v[0].fi + 1,y = v[1].se - v[1].fi + 1,k = 0;
for(int i = 1;i < x;i++)
if(max(i,x + y - i) <= A && max(i + y,x - i) <= B)
{
k = i;
break;
}
if(k)
{
work1(vector <pii> {mkp(v[0].fi,v[0].fi + k - 1)});
work1(vector <pii> {mkp(v[0].fi + k,v[0].se),mkp(v[1].fi,v[1].se)});
continue;
}
for(int i = x + 1;i < x + y;i++)
if(max(i,x + y - i) <= A && max(i - x,2 * x + y - i) <= B)
{
k = i;
break;
}
if(k)
{
work1(vector <pii> {mkp(v[0].fi,v[0].se),mkp(v[1].fi,v[1].fi + k - x - 1)});
work1(vector <pii> {mkp(v[1].fi + k - x,v[1].se)});
continue;
}
if(sum <= A && max(v[0].se - v[0].fi + 1,v[1].se - v[1].fi + 1) <= B)
{
work1(v);
continue;
}
return false;
}
if(sum > A) return false;
if(!st.empty() && v.back().se + 1 < st.top().fi) return false;
for(pii p : v) if(p.se - p.fi + 1 > B) return false;
work1(v);
}
return true;
}
int main()
{
freopen("stack.in","r",stdin);
freopen("stack.out","w",stdout);
scanf("%d",&T);
while(T--)
{
opt.clear();
while(!st.empty()) st.pop();
if(!solve()) puts("-1");
else
{
printf("%d\n",(int)opt.size());
for(pii p : opt) printf("%d %d\n",p.fi,p.se);
}
}
return 0;
}
~~~