专栏文章

省队集训-0423模拟赛

aallenchoi
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip5jot8
此快照首次捕获于
2025/12/03 06:31
3 个月前
此快照最后确认于
2025/12/03 06:31
3 个月前
查看原文

A.树

题意：

CF1958I
有两棵树，大小为 nn，以 11 为根。定义一次操作，为选择某棵树上的一个非根节点，把它删除，并把它的儿子全部连到它的父亲上。求最少几次操作，使得两棵树完全相同。
n≤40n\le40。

Sol：

显然两棵树保留的点集是一样的，要最大化这个电集。
新树等价于删点之后按祖先关系连边。也就是说，如果 (x,y)(x,y) 在两棵树上的祖先关系不一样，则不能都保留。
考虑折半搜索，右边的点集会对左边的点集产生限制，要求不能包含某些点。因此先把左边的点集跑出来，做个高维前缀和即可，总复杂度 O(2n2n)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
给定一个长为 nn 的序列和一个常数 CC，定义序列代价为：
max⁡S⊆{ 1,2,...,n }C×∑1≤l≤r≤n[{ l,l+1,...,r }⊆S]−∑i∈Sai\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
先查询原序列权值，然后 mm 次：单点修改 ax←ya_x\leftarrow y，查询序列价值，然后撤销修改。
n,m≤3×105,1≤C≤105,ai,y≤109n,m\le3\times10^5,1\le C\le10^5,a_i,y\le10^9。

Sol：

DP 式子为 fi=max⁡jmaxnj−1+(i−j+1)(i−j+2)2C−si+sj−1f_i=\max\limits_jmaxn_{j-1}+\frac{(i-j+1)(i-j+2)}{2}C-s_i+s_{j-1}，maxnmaxn 为 ff 前缀 max⁡\max，ss 为前缀和。可以斜率优化做到线性。
然后考虑怎么求每次单点修改后的答案。先正着、反着各 DPDP 一次。如果 x∉Sx\notin S 则不受影响，这一部分的答案等于前缀 max⁡\max 加后缀 max⁡\max；如果 x∈Sx\in S，考虑分治，钦定 xx 所在的极长连续段 ⊆[l,r]\subseteq[l,r] 并跨过 midmid，在区间内再跑两次斜优，加上两侧前后缀 max⁡\max 的贡献即可。
总复杂度 O(nlog⁡n)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,s3s1,s2,s3，初始时 s1s1 从栈顶到栈底依次是 p1,p2...pnp_1,p_2...p_n，pp 为一个排列。给定 A,BA,B，每一次操作，可以选择将 s1s1 顶部的 x≤Ax\le A 个元素整体平移到 s2s2 栈顶，或将 s2s2 顶部的 x≤Bx\le B 个元素整体平移到 s3s3 栈顶，要求最后 s3s3 从顶到底依次是 1,2,...,n1,2,...,n。问是否有解，有解则构造方案。
多测，∑n≤106\sum n\le10^6。

Sol：

大力模拟。
如果 s2s2 中出现了 pi+1<pi+1p_i+1<p_{i+1} 的情况则一定无解。
所以，对于 s1s1 中 pi+1<pi+1p_i+1<p_{i+1} 的位置，显然不能一次移到 s2s2 中，那么依此分段考虑。
假设某一段中形成若干极长连续上升段 [l1,r1],[l2,r2],...,[lm,rm][l_1,r_1],[l_2,r_2],...,[l_m,r_m]。这些段的值域显然是递减的。
如果 [l1,r1][l_1,r_1] 顶到了剩下的数的最大值，则把 [l1,r1][l_1,r_1] 一个一个地放入 s2s2，再一个一个地放入 s3s3，一定最优。然后去掉 [l1,r1][l_1,r_1] 归约到子问题。
如果这些段值域不连续，则只能一次性移过去。
否则，如果每一段长度都不超过 AA，且加起来不超过 BB，则可以把 [l1,r1]...[lm,rm][l_1,r_1]...[l_m,r_m] 依次丢进 s2s2 中形成一个大的连续段，这样可以尽量避免非法。
否则，如果 m>2m>2 那么只能一次全移到 s2s2 里面。 然后只剩 m=1,m=2m=1,m=2 两种情况。
若 m=1m=1，则将这一段一个一个地塞进 s2s2，后面再一个一个地塞进 s3s3，因为如果 s2s2 中会出现非法情况则一定是无法避免的，这样做不会劣。
然后是 m=2m=2 的情况，最多分两步移走。考虑枚举第一步移动的长度 kk。
设第一段长为 xx，第二段长为 yy。
如果 k<xk<x，则 s2s2 中会形成 x−k,y+kx-k,y+k 两段，所以要求 max⁡(k,x−k+y)≤A,max⁡(x−k,y+k)≤B\max(k,x-k+y)\le A,\max(x-k,y+k)\le B；
如果 k>xk>x，则 s2s2 中会形成 2x+y−k,k−x2x+y-k,k-x 两段，所以要求 max⁡(k,x+y−k)≤A,max⁡(2x+y−k,k−x)≤B\max(k,x+y-k)\le A,\max(2x+y-k,k-x)\le B。
由于两段在 s2s2 中无法拼在一起，所以非法情况无法避免，所以随便找个满足上述条件的 pp 即可。
往 s2s2 里加东西时判一下和栈顶的关系是否非法就做完了，线性。

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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...