本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-30 20:33:48
记录
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$，就可以构造出一组原问题的解。
$a$ 和 $b$ 似乎一样，但是后者有更强的性质，有 $\sum b\le m-\frac n2$。证明的话由于 $a_i\in [0,m]$，极差不超过 $m$，同时有 $\frac n2$ 个 $a_{2i+1}-a_{ai}$ 的空没有选，这些空的和至少为 $\frac n2$。
由于原题中保证 $\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)$。
#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;
}
鲁ICP备2025150228号