【比赛记录】24.10.29

· · 个人记录

记录

A 一个 n 写成 m 挂 10 分，C 的 n=m 写了但是后来写前面的暴力时改小了数组，挂 8 分。

题解

A. T392580 palin

考虑从左上角和右下角向中间 DP，显然可以设 f_{i,x,y,X,Y} 表示步数和两个结尾的坐标，但是只有步数合法的坐标才有意义，这样会有很多无用状态。

所以设 f_{i,j,k} 表示两边各走了 i 步，左上角出发向下 j 步，向右 (i-j) 步，右下角出发向上 k 步，向左 (i-k) 步，且已走的路径两边回文的方案数。此时即从左上走到了 (j+1,i-j+1)，从右下走到了 (n-k,m-i+k)，先判断一下这两点是否相同，转移时枚举两边分别是竖着走还是横着走即可。

一共各走 \lfloor\frac {n+m-2}2\rfloor 步。统计答案时，若 n+m-2 为偶数，则两边最终会走到同一点，直接枚举走到的点。否则两边会走到距离恰为 1 的两点，分一共竖着走了 (n-1) 和 (n-2) 步分别枚举即可。时间复杂度 O(n^3)。

#include<iostream>
using namespace std;
const int N=5e2+10;
const int mod=993244853;
void add(int &a,int b){a+=b;if(a>=mod)a-=mod;}
int n,m,res,st,f[2][N][N];
char a[N][N];
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m,st=(n+m-2)/2;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        for(int j=m;j>=1;j--) a[i][j]=a[i][j-1];
    }
    if(a[1][1]!=a[n][m]) {cout<<0; return 0;}
    f[0][0][0]=1;
    for(int i=1;i<=st;i++)
    {
        int now=i%2,last=1-now;
        for(int j=0;j<=i;j++) for(int k=0;k<=i;k++)
        {
            f[now][j][k]=0;
            if(j>=n||k>=n||i-j>=m||i-k>=m) continue; 
            if(a[j+1][i-j+1]!=a[n-k][m-(i-k)]) continue;
            if(j&&k) add(f[now][j][k],f[last][j-1][k-1]);
            if(j&&i-k) add(f[now][j][k],f[last][j-1][k]);
            if(k&&i-j) add(f[now][j][k],f[last][j][k-1]);
            if(i-j&&i-k) add(f[now][j][k],f[last][j][k]);
        }
    }
    if((n+m-2)%2) for(int i=0;i<n;i++)
    {
        add(res,f[st%2][i][n-1-i]);
        if(n-2-i>=0) add(res,f[st%2][i][n-2-i]);
    }
    else for(int i=0;i<n;i++) add(res,f[st%2][i][n-1-i]);
    cout<<res;
    return 0;
}

B. T392683 Qsort

模拟一下发现，若 nan 作为基准值，则所有的 a_l<a_i 均为假，没有数会被放到该 nan 前面，也即整个数组都不会变。若某个数 x 作为基准值，则所有小于 x 的数会被一起放到 x 前面，其他的数和 nan 仍留在后面。不难发现此时前面的区间里只有数，因此最终一定会被排好序。

因此从左到右处理每个数，若已经被其他的数排序时提前，或者该数是 nan 则跳过，否则将后面所有小于 x 的数升序放在 x 前，最后放入 x。用优先队列可以实现该过程，时间复杂度 O(n\log n)。

#include<iostream>
#include<vector>
#include<queue>
#define pii pair<int,int>
using namespace std;
const int N=5e5+10;
int n,ct,a[N],res[N];
bool vis[N];
string ts;
int getn()
{
    int len=ts.size(),tr=0;
    for(int i=0;i<len;i++) tr=tr*10+ts[i]-'0';
    return tr;
}
priority_queue <pii,vector<pii>,greater<pii> > q;
void sol()
{
    cin>>n,ct=0;
    while(q.size()) q.pop();
    for(int i=1;i<=n;i++) cin>>ts,a[i]=(ts[0]=='n'?0:getn()),vis[i]=0;
    for(int i=1;i<=n;i++) if(a[i]) q.push({a[i],i});
    for(int i=1;i<=n;i++) if(!vis[i])
    {
        if(!a[i]) {res[++ct]=a[i]; continue;}
        while(q.size())
        {
            pii te=q.top(); int x=te.first,y=te.second;
            if(x>=a[i]) break;
            if(y<=i) {q.pop(); continue;}
            vis[y]=1,res[++ct]=a[y],q.pop();
        }
        res[++ct]=a[i];
    }
    for(int i=1;i<=ct;i++)
    {
        if(res[i]) cout<<res[i]<<' ';
        else cout<<"nan ";
    }
    cout<<'\n';
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int TT; cin>>TT;
    while(TT--) sol();
    return 0;
}

C. T392686 chaoticevil

首先若 n 为奇数，添加 a_{n+1}=0 变成偶数情况。

考虑如果给 x 赋 1，给 y 赋 -1，相当于给最终结果加上 x-y 或减去 y-x，也就是说给两数赋上不同系数时，相当于只加或减了两数的差值。

因此我们将 a 数组排序，并转化为 b_i=a_{2i}-a_{2i-1}，则 b 数组长度 k=\frac n2。此时由于 a 中每个数在 \sum b 中都有贡献，只是有些取反了，所以 \sum b 奇偶性不变，仍是偶数。同时由于原数两两不同，b 数组中也没有 0。若能构造出一组 e_i 使得 \sum e_ib_i=0，就可以构造出一组原问题的解。

由于原题中保证 $\frac {2m}3<n$，我们取 $n=\frac {2m}3$ 代入上式，也即 $m-\frac n2<m-\frac m3=\frac {2m}3<n$，有 $\sum b<n=2k$。我们得到的新问题即为：给出长为 $k$，元素非 $0$ 的数组 $b$，满足 $\sum b<2k$ 且为偶数，构造一组 $e_i$ 使得 $\sum e_ib_i=0$。 不难想到如果 $b$ 中是偶数个 $1$，就可以给一半赋为 $-1$ 使得最终和为 $0$。如果有大于 $1$ 的数，考虑像最开始的转换一样再次转化，取出 $\max b$ 和 $\min b$，并加入它们的差值。由于 $\sum b<2k$，最大值和最小值此时不相等，因此差值仍为正。 $\sum b$ 减少了 $2\min b$，至少减少了 $2$ ，保证新的 $\sum b'<2k'$ 且仍为偶数，这样直到 $b$ 中数字全为 $1$ 即得解。 因此我们证明了在原问题条件下一定有解，并可以给出一组解。具体实现上可以使用优先队列维护目前的最值，并记录每个元素的来源（是哪两个元素相减所得），最终从所有的 $\pm 1$ 开始 dfs 一遍即可得到答案。时间复杂度 $O(n\log n)$。 ```cpp #include<iostream> #include<queue> #include<algorithm> #define pii pair<int,int> using namespace std; const int N=1e6+10; int n,m,ct,a[N],v[N],c[N],lc[N],rc[N],p[N]; bool vis[N]; priority_queue <pii> qi,qa; bool cmpa(int x,int y){return a[x]<a[y];} void dfs(int x,int k) { if(x<=0) {c[-x]=k; return;} dfs(lc[x],-k),dfs(rc[x],k); } void solv() { for(int i=1;i<=ct;i++) qi.push({-v[i],i}),qa.push({v[i],i}); while(qa.size()) { int x=qa.top().second; qa.pop(); while(vis[x]) x=qa.top().second,qa.pop(); if(v[x]==1) { int k=1; for(int i=1;i<=ct;i++) if(!vis[i]) dfs(i,k),k=-k; return; } int y=qi.top().second; qi.pop(); while(vis[y]) y=qi.top().second,qi.pop(); ct++,vis[x]=vis[y]=1,lc[ct]=y,rc[ct]=x,v[ct]=v[x]-v[y]; qi.push({-v[ct],ct}),qa.push({v[ct],ct}); } } signed main() { ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i],p[i]=i; sort(p+1,p+1+n,cmpa); for(int i=n;i>0;i-=2) ct++,v[ct]=a[p[i]]-a[p[i-1]],lc[ct]=-p[i-1],rc[ct]=-p[i]; cout<<"NP-Hard solved\n",solv(); for(int i=1;i<=n;i++) cout<<c[i]<<' '; return 0; } ``` ### D. T392687 pigeons 发现一个点 $u$ 被区间 $[L,R]$ 选中当且仅当该点被区间完全包含，而该点的父亲节点不被完全包含，也即 $L\le l_u\le r_u\le R$ 成立且 $L\le l_{fa_u}\le r_{fa_u}\le R$ 不成立。另外由于 $u$ 被完全包含，所以其父亲区间跟 $[L,R]$ 一定有交。 所以我们考虑用 $L-1$ 和 $R+1$ 来刻画限制。具体地，我们发现根节点到 $L-1$ 的链上的点一定包含 $L-1$，那么它们的右子节点若不在链上，则一定不包含 $L-1$，且表示的区间左端点 $\ge L$，$R+1$ 到根节点的路径同理。 那么我们先找到 $L-1$ 和 $R+1$ 的 LCA $x$，则 $lc_x$ 到 $L-1$ 的链和 $rc_x$ 到 $R+1$ 这两条链不合法，且前者的不在链上的右儿子和后者不在链上的左儿子均合法，即在 $[L,R]$ 区间内。所以我们对这两条链进行操作，以他们的某个儿子所代表的区间长度为系数加上 $d$ 即可。 因此考虑树链剖分，对每一条重链维护其相邻的右子节点和左子节点的值，分在两棵线段树里维护即可。这样我们就可以把每条链剖成不超过 $\log n$ 条重链和轻边，那么我们用线段树维护重链的区间加，另外维护轻边的贡献。由于每个点只会连一条轻边，直接开数组维护每个点上轻边的值即可。时间复杂度 $O(n\log^2 n) 
#include<iostream>
#define int long long
using namespace std;
const int N=8e5+10;
int n,m,q,rt,ct,sr,ch[N][2],fa[N],w[N],aa[N][2];
int son[N],top[N],de[N],siz[N],id[N],ta[N];
struct sgmtt
{
    int t=1,lc[N],rc[N],le[N],s[N],tag[N];
    void pushup(int u) {s[u]=s[lc[u]]+s[rc[u]];}
    void pt(int u,int k) {s[u]+=k*le[u],tag[u]+=k;}
    void pushdown(int u) {if(tag[u]) pt(lc[u],tag[u]),pt(rc[u],tag[u]),tag[u]=0;}
    void build(int u,int l,int r,bool tf)
    {
        if(l==r) {le[u]=aa[l][tf]; return;}
        int mid=(l+r)/2;
        lc[u]=++t,build(t,l,mid,tf);
        rc[u]=++t,build(t,mid+1,r,tf);
        pushup(u),le[u]=le[lc[u]]+le[rc[u]];
    }
    void update(int u,int l,int r,int ll,int rr,int k)
    {
        if(l>=ll&&r<=rr) {pt(u,k); return;}
        int mid=(l+r)/2; pushdown(u);
        if(ll<=mid) update(lc[u],l,mid,ll,rr,k);
        if(rr>mid) update(rc[u],mid+1,r,ll,rr,k);
        pushup(u);
    }
    int query(int u,int l,int r,int ll,int rr)
    {
        if(l>=ll&&r<=rr) return s[u];
        int mid=(l+r)/2,res=0; pushdown(u);
        if(ll<=mid) res+=query(lc[u],l,mid,ll,rr);
        if(rr>mid) res+=query(rc[u],mid+1,r,ll,rr);
        return res;
    }
}T[2];
void dfs(int u)
{
    siz[u]=1,de[u]=de[fa[u]]+1;
    if(u<=n) {w[u]=1; return;}
    for(int i=0;i<2;i++)
    {
        int c=ch[u][i]; dfs(c),w[u]+=w[c],siz[u]+=siz[c];
        if(siz[c]>siz[son[u]]) son[u]=c;
    }
}
void dfsb(int u,int to)
{
    id[u]=++ct,top[u]=to;
    if(!son[u]) return;
    dfsb(son[u],to);
    for(int i=0;i<2;i++)
    {
        int c=ch[u][i];
        if(c!=son[u]) dfsb(c,c),aa[id[u]][i]=w[c];
    }
}
void update(bool tf,int l,int r,int k) {T[tf].update(1,1,m,l,r,k);}
int query(bool tf,int l,int r) {return T[tf].query(1,1,m,l,r);}
int flca(int x,int y)
{
    if(x<0||y>n) return -1;
    while(top[x]!=top[y])
    {
        if(de[top[x]]<de[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    if(de[x]>de[y]) swap(x,y);
    return x;
}
void add(int x,int to,int k,bool tf)
{
    while(top[x]!=top[to])
    {
        if(x!=top[x]) update(tf,id[top[x]],id[fa[x]],k),x=top[x];
        if(x!=ch[fa[x]][tf]) ta[x]+=k;
        x=fa[x];
    }
    if(x!=to) update(tf,id[to],id[fa[x]],k);
}
int ask(int x,int to,bool tf)
{
    int res=0;
    while(top[x]!=top[to])
    {
        if(x!=top[x]) res+=query(tf,id[top[x]],id[fa[x]]),x=top[x];
        if(x!=ch[fa[x]][tf]) res+=ta[x]*w[ch[fa[x]][tf]];
        x=fa[x];
    }
    if(x!=to) res+=query(tf,id[to],id[fa[x]]);
    return res;
}
void opa(int l,int r,int lca,int x)
{
    if(l==1&&r==n) sr+=x*n;
    else if(l==1) add(r+1,rt,x,0);
    else if(r==n) add(l-1,rt,x,1);
    else add(l-1,ch[lca][0],x,1),add(r+1,ch[lca][1],x,0);
}
int opb(int l,int r,int lca)
{
    if(l==1&&r==n) return sr;
    if(l==1) return ask(r+1,rt,0);
    if(r==n) return ask(l-1,rt,1);
    return ask(l-1,ch[lca][0],1)+ask(r+1,ch[lca][1],0);
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>q,m=n*2-1;
    for(int i=n+1;i<=m;i++) cin>>ch[i][0]>>ch[i][1],fa[ch[i][0]]=fa[ch[i][1]]=i;
    for(int i=n+1;i<=m;i++) if(!fa[i]) rt=i;
    dfs(rt),dfsb(rt,rt),T[0].build(1,1,m,0),T[1].build(1,1,m,1);
    while(q--)
    {
        int op,l,r,x,lca; cin>>op>>l>>r,lca=flca(l-1,r+1);
        if(op==1) cin>>x,opa(l,r,lca,x);
        else cout<<opb(l,r,lca)<<'\n';
    }
    return 0;
}