2024.10&11 总结
图论
【Luogu P8428】 Pastiri
题目描述
给定一棵 \(N\) 点的树，点编号为 \(1\) 到 \(N\)，现在在 \(K\) 个点上有羊，你的任务是在树上分配一些牧羊人。
这些牧羊人很懒，只会看管离他最近的羊。当然如果有多个离他最近的羊，那么他会都看管。
当然，牧羊人可以和羊在同一个点上，但这样牧羊人只会看管这一个点上的那个羊。
求一种牧羊人的分配方案使得牧羊人总数最小，\(1 \le n \le 5 \times 10^5\)。
解题思路
首先这题用树形 \(dp\) 是极其不现实的 ，数据大且信息不好表示。
我们可以考虑贪心：将所有羊按深度从大到小排序，每次选取一个深度最大的羊，在它的祖先中选取一个能够管到它的节点，在该节点上放牧羊人。
这个贪心的正确性是显然的，因为放的越高能照顾到的也越多，且由于深度最大，无需放到别的子树去管别的节点。
我们得到了一个 \(O(n^2)\) 的做法，考虑优化。
我们每次都需要花 \(O(n)\) 的时间复杂度来找深度最小且能照顾到自己的节点，并且将该节点能照顾到的所有节点都打上标记。
考虑优化查找，我们可以使用边定向，先求出每个节点 \(i\) 距离它最近的羊距离设为 \(dis_i\) ，然后对于所有 \(dis_u=dis_v+1\) 的边，我们在新图上建一条有向边 \((u,v)\) 表示点 \(u\) 能照顾点 \(v\) ，那我们就可以与处理出所有羊深度最小的且能处理它的节点了。
时间复杂度 \(O(n)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
int n,m,t[500005],dis[500005],deep[500005],f[500005],t1[500005],k,s;
bool v1[500005],v[500005];
vector<int> a[500005],a1[500005];
bool cmp1(int q,int w){return deep[q]>deep[w];}
void dfs1(int x,int y)
{
if(!v1[x])dis[x]=n+1;
deep[x]=deep[y]+1;
for(int i=0;i<a[x].size();i++)
{
if(a[x][i]==y)continue;
dfs1(a[x][i],x);
dis[x]=min(dis[x],dis[a[x][i]]+1);
}
return;
}
void dfs2(int x,int y,int z)
{
dis[x]=min(dis[x],z);
for(int i=0;i<a[x].size();i++)
{
if(a[x][i]==y)continue;
dfs2(a[x][i],x,dis[x]+1);
}
for(int i=0;i<a[x].size();i++)
{
if(a[x][i]==y)continue;
if(dis[a[x][i]]==dis[x]+1)a1[a[x][i]].push_back(x);
if(dis[x]==dis[a[x][i]]+1)a1[x].push_back(a[x][i]);
}
return;
}
void dfs4(int x,int y,int z)
{
f[x]=z;
for(int i=0;i<a1[x].size();i++)
{
if(a1[x][i]==y)continue;
dfs4(a1[x][i],x,z);
}
return;
}
void dfs3(int x,int y)
{
if(f[x]==n+1)dfs4(x,y,x);
for(int i=0;i<a[x].size();i++)
{
if(a[x][i]==y)continue;
dfs3(a[x][i],x);
}
return;
}
void dfs5(int x,int y)
{
v[x]=1;
for(int i=0;i<a1[x].size();i++)
{
if(a1[x][i]==y||v[a1[x][i]])continue;
dfs5(a1[x][i],x);
}
return;
}
int main()
{
int x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
a[x].push_back(y),a[y].push_back(x);
}
for(int i=1;i<=m;i++)scanf("%d",&t[i]),v1[t[i]]=1;
for(int i=1;i<=n;i++)f[i]=n+1;
dfs1(1,0),dfs2(1,0,n+1),dfs3(1,0);
sort(t+1,t+m+1,cmp1);
for(int i=1;i<=m;i++)
{
if(v[t[i]])continue;
s++,t1[++k]=f[t[i]];
dfs5(f[t[i]],0);
}
sort(t1+1,t1+k+1);
printf("%d\n",s);
for(int i=1;i<=k;i++)printf("%d ",t1[i]);
return 0;
}
【Luogu P3976】 旅游
题目描述
为了提高智商，ZJY 准备去往一个新世界去旅游。这个世界的城市布局像一棵树，每两座城市之间只有一条路径可以互达。
每座城市都有一种宝石,有一定的价格。ZJY 为了赚取最高利益,她会选择从 A 城市买入再转手卖到 B 城市。
由于ZJY买宝石时经常卖萌，因而凡是 ZJY 路过的城市，这座城市的宝石价格会上涨。让我们来算算 ZJY 旅游完之后能够赚取的最大利润。(如 A 城市宝石价格为 \(v\)，则ZJY出售价格也为 \(v\))，\(1 \le n,m \le 5 \times 10^4\) 。
解题思路
由于这题有对一条链加值的操作，所以肯定要用到树链剖分。
我们考虑如何维护题目所要求的的东西，用树链剖分将链划分为 \(log(n)\) 段，我们可以用线段树维护每一段的权值，同时段与段之间的贡献很好求，后缀最大值减去前缀最小值即可。
考虑如何维护每一段的权值，这个东西很好做，我们只需维护一段的最大值和最小值，合并时用最大值减去最小值即可。
时间复杂度 \(O(nlog^2n)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
struct datay
{
int maxx,minn,v1,v2;
}f[200005],t1[10005],t2[10005];
int n,m,v[50005],siz[50005],son[50005],deep[50005],fa[50005],top[50005],dfn[50005],num,d[200005],k1,k2,re[50005];
vector<int> a[50005];
void galaxy(int x,int v)
{
f[x].maxx+=v,f[x].minn+=v,d[x]+=v;
return;
}
void pushdown(int x)
{
if(!d[x])return;
int lc=(x<<1),rc=(x<<1)|1;
galaxy(lc,d[x]),galaxy(rc,d[x]),d[x]=0;
return;
}
void up(int x)
{
int lc=(x<<1),rc=(x<<1)|1;
f[x].maxx=max(f[lc].maxx,f[rc].maxx),f[x].minn=min(f[lc].minn,f[rc].minn);
f[x].v1=max(max(f[lc].v1,f[rc].v1),f[rc].maxx-f[lc].minn);
f[x].v2=max(max(f[lc].v2,f[rc].v2),f[lc].maxx-f[rc].minn);
return;
}
void build(int x,int l,int r)
{
if(l==r){f[x].maxx=f[x].minn=v[re[l]],f[x].v1=f[x].v2=0;return;}
int lc=(x<<1),rc=(x<<1)|1,mid=(l+r)>>1;
build(lc,l,mid),build(rc,mid+1,r);
up(x);
return;
}
void modify(int x,int l,int r,int ql,int qr,int v)
{
if(ql<=l&&r<=qr){galaxy(x,v);return;}
pushdown(x);
int lc=(x<<1),rc=(x<<1)|1,mid=(l+r)>>1;
if(ql<=mid)modify(lc,l,mid,ql,qr,v);
if(qr>mid)modify(rc,mid+1,r,ql,qr,v);
up(x);
return;
}
datay query(int x,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr)return f[x];
pushdown(x);
int lc=(x<<1),rc=(x<<1)|1,mid=(l+r)>>1;
datay h,g;
if(qr<=mid)h=query(lc,l,mid,ql,qr);
else if(ql>mid)h=query(rc,mid+1,r,ql,qr);
else
{
h=query(lc,l,mid,ql,qr);
g=query(rc,mid+1,r,ql,qr);
h.v1=max(max(h.v1,g.v1),g.maxx-h.minn);
h.v2=max(max(h.v2,g.v2),h.maxx-g.minn);
h.maxx=max(h.maxx,g.maxx);
h.minn=min(h.minn,g.minn);
}
return h;
}
void dfs1(int x,int y)
{
deep[x]=deep[y]+1,fa[x]=y,siz[x]=1;
for(int i=0;i<a[x].size();i++)
{
if(a[x][i]==y)continue;
dfs1(a[x][i],x);
siz[x]+=siz[a[x][i]];
if(siz[a[x][i]]>siz[son[x]])son[x]=a[x][i];
}
return;
}
void dfs2(int x,int y)
{
dfn[x]=++num,re[num]=x;
if(son[x]==0)return;
top[son[x]]=top[x],dfs2(son[x],x);
for(int i=0;i<a[x].size();i++)
{
if(a[x][i]==y||a[x][i]==son[x])continue;
top[a[x][i]]=a[x][i],dfs2(a[x][i],x);
}
return;
}
void update(int x,int y,int z)
{
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]])swap(x,y);
modify(1,1,n,dfn[top[x]],dfn[x],z);
x=fa[top[x]];
}
if(deep[x]>deep[y])swap(x,y);
modify(1,1,n,dfn[x],dfn[y],z);
return;
}
int ask(int x,int y)
{
int q=0,minn=1e9;k1=k2=q=0;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]){swap(x,y),q^=1;}
if(!q)t1[++k1]=query(1,1,n,dfn[top[x]],dfn[x]);
else t2[++k2]=query(1,1,n,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
if(deep[x]>deep[y])swap(x,y),q^=1;
if(!q)t2[++k2]=query(1,1,n,dfn[x],dfn[y]);
else t1[++k1]=query(1,1,n,dfn[x],dfn[y]);
q=0;
for(int i=1;i<=k1;i++)q=max(q,max(t1[i].v2,t1[i].maxx-minn)),minn=min(minn,t1[i].minn);
for(int i=k2;i>=1;i--)q=max(q,max(t2[i].v1,t2[i].maxx-minn)),minn=min(minn,t2[i].minn);
return q;
}
int main()
{
int x,y,z;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&v[i]);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
}
dfs1(1,0),top[1]=1,dfs2(1,0);
build(1,1,n);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
printf("%d\n",ask(x,y));
update(x,y,z);
}
return 0;
}
【Luogu P7897】 spxmcq
题目描述
给定一颗 \(n\) 个节点有根树，第 \(i\) 节点权值为 \(a_i\)。
在这个树上支持一种询问：
- 给定节点 \(u\) 和参数 \(x\)，假如 所有节点点权加 \(x\)，在这种情况下，求： 对于所有完全在 \(u\) 子树内并包含 \(u\) 的连通点集，权值之和最大可能为多少？
\(1 \le n,m \le 2 \times 10^5\) 。
解题思路
先不管询问，我们来考虑怎么做。
我们可以发现得到一个这样的 \(dp\) ：\(f_i=v_i+\sum_{v \in son_i} max(f_v,0)\) ，这样我们就能轻松得到一个 \(O(nm)\) 的做法。
考虑优化，由于 \(0\) 和没连没什么区别，当 \(f_v<0\) 时直接断掉那条边，状态转移方程变为 \(f_i=v_i+\sum_{v \in son_i} f_v\) 。
继续转化，设 \(val_i,size_i\) 分别为节点 \(i\) 子树的权值和与节点个数和，那么 \(f_i=val_i\) ，考虑还有加减权值， \(f_i=val_i+x \times size_i\) 。
那我们现在只需要维护一条边什么时候是连着的，随着 \(x\) 的递增，我们发现边是在不断连上的，那么只需考虑每条边什么时候连上即可。
对于一条边 \((i,fa_i)\) ，当 \(f_i \ge 0\) 时就可以连上了，即当 \(val_i+x \times size_i \ge 0\) 时即可，即为 \(x \ge -\frac{val_i}{size_i}\) ，注意要向上取整。
设 \(t_i=-\frac{val_i}{size_i}\) ，求出 \(t_i\) 我们需要维护 \(val_i\) 与 \(size_i\) ，我们先用并查集维护每个连通块与每个连通块的大小，这样每个连通块的大小就是该连通块根节点的子树大小，同时我们每次连上一条边 \((i,fa_i)\) 时，从 \(fa_i\) 往上一直到 \(fa_i\) 所属的连通块的根节点这些点的 $val $ 都需要加上都要加上 \(val_i\) ，这是一个区间修改单点查询的操作，用差分改成单点修改每次查询查一个子树即可。
不能从叶子开始做，我们再开一个优先队列维护需要连上的边，每次把发生变化的未连边加进优先队列中，按 \(t_i\) 从小到大取出，每次判断一下这条边是否连过即可。
时间复杂度 \(O(nlogn)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
struct datay
{
int x,p;
long long v,v1;
}t[1000005],d[1000005];
int n,m,dfn[1000005],deep[1000005],num,out[1000005],fa[1000005],v[1000005],f1[1000005],to[1000005];
long long minn=1e8,f2[1000005];
bool v1[1000005];
vector<int> a[1000005];
bool operator<(const datay &q,const datay &w)
{
if(q.v1!=w.v1)return q.v1>w.v1;
return q.p<w.p;
}
priority_queue<datay> l;
bool cmp1(datay q,datay w){return q.v<w.v;}
bool cmp2(datay q,datay w){return q.p<w.p;}
int lowbit(int x){return x&(-x);}
void modify1(int x,int y)
{
if(x==0)return;
while(x<=n)f1[x]+=y,x+=lowbit(x);
return;
}
void modify2(int x,long long y)
{
if(x==0)return;
while(x<=n)f2[x]+=y,x+=lowbit(x);
return;
}
int query1(int x)
{
int h=0;
while(x)h+=f1[x],x-=lowbit(x);
return h;
}
long long query2(int x)
{
long long h=0;
while(x)h+=f2[x],x-=lowbit(x);
return h;
}
void dfs(int x,int y)
{
deep[x]=deep[y]+1,fa[x]=y,dfn[x]=++num;
for(int i=0;i<a[x].size();i++)dfs(a[x][i],x);
out[x]=num;
return;
}
int search(int x)
{
if(to[x]!=x)to[x]=search(to[x]);
return to[x];
}
int main()
{
datay q;int x,y;
scanf("%d%d",&n,&m);
for(int i=2;i<=n;i++)scanf("%d",&x),a[x].push_back(i);
dfs(1,0);
for(int i=1;i<=n;i++)scanf("%d",&v[i]);
for(int i=1;i<=m;i++)scanf("%d%lld",&t[i].x,&t[i].v),t[i].p=i;
sort(t+1,t+m+1,cmp1);
for(int i=1;i<=n;i++)d[i].x=i,d[i].p=1,d[i].v=v[i],d[i].v1=-v[i],to[i]=i;
for(int i=1;i<=n;i++)modify1(dfn[i],1),modify1(dfn[fa[i]],-1),modify2(dfn[i],v[i]),modify2(dfn[fa[i]],-v[i]);
for(int i=2;i<=n;i++)l.push(d[i]);
for(int i=1;i<=m;i++)
{
while(l.size()!=0&&(l.top()).v1<=t[i].v)
{
if(v1[(l.top()).x]){l.pop();continue;}
q=l.top(),l.pop(),v1[q.x]=1;
x=search(fa[q.x]),y=search(q.x);
modify1(dfn[fa[q.x]],q.p),modify2(dfn[fa[q.x]],q.v);
if(x!=1)modify1(dfn[fa[x]],-q.p),modify2(dfn[fa[x]],-q.v);
to[y]=x;
if(x==1)continue;
q.x=x,q.p=query1(out[q.x])-query1(dfn[q.x]-1),q.v=query2(out[q.x])-query2(dfn[q.x]-1);
if(q.v%q.p==0)q.v1=-q.v/q.p;
else if(q.v<0)q.v1=-q.v/q.p+1;
else q.v1=-q.v/q.p;
l.push(q);
}
t[i].v1=query2(out[t[i].x])-query2(dfn[t[i].x]-1)+t[i].v*(query1(out[t[i].x])-query1(dfn[t[i].x]-1));
}
sort(t+1,t+m+1,cmp2);
for(int i=1;i<=m;i++)printf("%lld\n",t[i].v1);
return 0;
}
【GJOI 2024.11.13 T2】 二叉搜索树
题目描述
给出一棵 \(n\) 个点的树，每个点有权值，给出 \(m\) 个操作，每个操作修改某个点的权值，求出每次操作后有多少个节点满足以它为根的子树为二叉搜索树，\(1 \le n,m \le 2 \times 10^5\) 。
解题思路
法一
转换一下题意，按中序遍历给每个节点赋 \(dfn\) 值，转换到序列上，那么就是查询某些区间内的 \(dfn\) 值是否为递增的。
每个点 \(i\) 的权值修改只会影响到他与前一个点与后一个点的大小关系，同时一段递增区间 \([l,r]\) 就是满足前一个比后一个小的关系有 \(r-l\) 个，所以我们可以维护一段区间内满足这种大小关系的数对个数。
设前一个点为 \(pre_i\) ，后一个点为 \(las_i\) ，那么若 \(pre_i\) 与 \(i\) 的关系改变，会影响 \(lca(pre_i,i)\) 及其祖先的值，若 \(las_i\) 与 \(i\) 的关系改变，会影响 \(lca(las_i,i)\) 及其祖先的值，这可以用树剖做。
统计有多少个区间 \([l_i,r_i]\) 的权值为 \(r_i-l_i\) 不好做，但注意到 \(i\) 区间的权值小于等于 \(r_i-l_i\) ，我们可以将区间权值变为不满足的个数，记录最小值有多少个，统计时看最小值是否为 \(0\) ，并输出个数。
时间复杂度 \(O(nlog^2n)\) 。
法二
注意到每次修改一个点的权值使得产生贡献的祖先一定是连续的，说明每次我们只需统计自己节点的哪段祖先发生了变化。
可以只用树状数组维护，每次树上倍增求贡献。
时间复杂度 \(O(nlog^2n)\) ，但好打。
Code
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
struct datay
{
int v,lc,rc;
}a[200005];
int n,m,dfn1[200005],num1,dfn[200005],num,pre[200005],out[200005],siz[200005],son[200005],fa[200005],top[200005],deep[200005],f[800005],maxx[800005],d[800005],re[200005],t[200005];
void dfs1(int x,int y)
{
if(x==0)return;
deep[x]=deep[y]+1,fa[x]=y;
pre[x]=num+1,dfs1(a[x].lc,x),dfn[x]=++num,re[num]=x,dfs1(a[x].rc,x),out[x]=num;
siz[x]=siz[a[x].lc]+siz[a[x].rc]+1;
if(siz[a[x].lc]>siz[a[x].rc])son[x]=a[x].lc;
else son[x]=a[x].rc;
return;
}
void dfs2(int x)
{
if(x==0)return;
dfn1[x]=++num1;
if(son[x]==0)return;
top[son[x]]=top[x],dfs2(son[x]);
if(son[x]==a[x].rc)top[a[x].lc]=a[x].lc,dfs2(a[x].lc);
if(son[x]==a[x].lc)top[a[x].rc]=a[x].rc,dfs2(a[x].rc);
return;
}
void galaxy(int x,int v)
{
maxx[x]+=v,d[x]+=v;
return;
}
void pushdown(int x)
{
if(d[x]==0)return;
int lc=(x<<1),rc=(x<<1)|1;
galaxy(lc,d[x]),galaxy(rc,d[x]),d[x]=0;
return;
}
void up(int x,int lc,int rc)
{
if(maxx[lc]==maxx[rc])maxx[x]=maxx[lc],f[x]=f[lc]+f[rc];
else if(maxx[lc]>maxx[rc])maxx[x]=maxx[lc],f[x]=f[lc];
else maxx[x]=maxx[rc],f[x]=f[rc];
return;
}
void modify(int x,int l,int r,int ql,int qr,int v)
{
if(ql<=l&&r<=qr){galaxy(x,v);return;}
pushdown(x);
int lc=(x<<1),rc=(x<<1)|1,mid=(l+r)>>1;
if(ql<=mid)modify(lc,l,mid,ql,qr,v);
if(qr>mid)modify(rc,mid+1,r,ql,qr,v);
up(x,lc,rc);
return;
}
int LCA(int x,int y)
{
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]])swap(x,y);
x=fa[top[x]];
}
if(deep[x]>deep[y])swap(x,y);
return x;
}
void update(int x,int z)
{
while(x)
{
modify(1,1,n,dfn1[top[x]],dfn1[x],z);
x=fa[top[x]];
}
return;
}
void build(int x,int l,int r)
{
if(l==r){f[x]=1;return;}
int lc=(x<<1),rc=(x<<1)|1,mid=(l+r)>>1;
build(lc,l,mid),build(rc,mid+1,r);
f[x]=f[lc]+f[rc];
return;
}
int main()
{
int x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i].lc,&a[i].rc);
for(int i=1;i<=n;i++)scanf("%d",&a[i].v);
dfs1(1,0),top[1]=1,dfs2(1),build(1,1,n);
for(int i=2;i<=n;i++)t[i]=LCA(re[i-1],re[i]);
for(int i=2;i<=n;i++)
if(i>1&&a[re[i-1]].v>a[re[i]].v)update(t[i],-1);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
x=dfn[x];
if(x>1&&a[re[x-1]].v>a[re[x]].v&&a[re[x-1]].v<=y)update(t[x],1);
if(x>1&&a[re[x-1]].v<=a[re[x]].v&&a[re[x-1]].v>y)update(t[x],-1);
if(x<n&&a[re[x]].v>a[re[x+1]].v&&y<=a[re[x+1]].v)update(t[x+1],1);
if(x<n&&a[re[x]].v<=a[re[x+1]].v&&y>a[re[x+1]].v)update(t[x+1],-1);
a[re[x]].v=y;
if(maxx[1]!=0)printf("0\n");
else printf("%d\n",f[1]);
}
return 0;
}
【GJOI 2024.11.14 T4】 大头问题
题目描述
给出一个 \(n\) 个点 \(m\) 条边的图，现在可以任选图中的若干点，称一条两点都被选的边为连接边，设连接边个数为 \(x\) ，该选择方案的贡献为 \(x^k\) ，求所有方案总贡献，\(1 \le n,m \le 10^5,1 \le k \le 3\) 。
解题思路
首先观察数据范围，注意到 \(k\) 极小，这启示我们可以分情况讨论。
我们考虑把 \(x^k\) 给拆开，变成 \(x \times ... \times x\) ，这个计数其实等价与我们有先后顺序的选择 \(k\) 条边，可以选重的方案数。
那我们可以从每种选边方案的贡献数来考虑，我们枚举选的 \(k\) 次边，那么只有这 \(k\) 条边的顶点是一定要选的，其它点可选可不选，方案数为 \(2^{n-y}\) ，其中 \(y\) 为与 \(k\) 条边有关联的顶点个数。
因为两条边可能选同一个顶点，重点在于如何求出 \(y\)，我们需要大量的分类讨论 。
\(k=1\) 或 \(k=2\) 的情况都十分简单，我们重点考虑 \(k=3\) 的情况。
首先，若选 \(3\) 条边的时候若选重，就会转化为 \(k=1\) 或 \(k=2\) 的情况，同时注意每种 \(k=2\) 的情况对应着 \(3\) 种选择顺序，需要 \(\times 3\) 。
没有选重时，分类讨论 \(y\) ，当 \(y=3\) 时，就是图中三元环的个数，这里我们可以用一个 \(O(m \sqrt{m})\) 三元环计数的 \(trick\) 。
想一个简单的三元环计数方法：给点赋权，按点权大小给边定向，我们只需要找到自己能到的距离为 \(2\) 的点中有多少个能直接到的节点有多少个即可。
瓶颈在于点的度数，我们可以来根号分治。
我们的点权我们赋为点的度数，那么讨论每次枚举的直接到达的节点 \(x\) ，若 $x \le \sqrt{m} $ ，那么所有点最多被访问 \(m\) 次，那么会找 \(m\sqrt{m}\) 次，若 \(x>\sqrt{m}\) ，由于我们点权为点度数，那么指向它的点的度数一定比它更大，这种点最多 \(\sqrt{m}\) 个，所以会找 \(m\sqrt{m}\) 次，总时间复杂度是 \(O(m\sqrt{m})\) 的。
讨论完 \(y=3\) 的，\(y=4\) 时，有一条链或菊花图的情况，链的情况我们只需枚举第 \(2\) 和 \(3\) 个节点，边任选与与它们两点相连的边，减去三元环的情况即可，菊花图我们只需枚举中心点即可。
\(y=5\) 时就是只有两条边连在一起的情况，我们只需枚举两条边的中心点，在任选不与这些点顶点相交的边即可。
\(y=6\) 时就是没有边连在一起的情况，总方案减去上面所有方案即可。
时间复杂度 \(O(m\sqrt{m})\) 。
Code
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long n,m,k,p[200005];
bool v[100005];
vector<long long> a[100005],a1[100005];
long long poww(long long x,long long y)
{
long long h=1;
while(y)
{
if(y&1)h=(h*x)%mod;
x=(x*x)%mod,y>>=1;
}
return h;
}
long long solve1(){return m*p[n-2]%mod;}
long long solve2()
{
long long h=m*(m-1)%mod,s=0,q;
for(int i=1;i<=n;i++)
{
q=a[i].size();
h=(h-q*(q-1)%mod+mod)%mod;
if(n>=3)s=(s+((q*(q-1)%mod)*p[n-3])%mod)%mod;
}
if(n>=4)s=(s+h*p[n-4]%mod+mod)%mod;
return s;
}
long long solve3()
{
long long h=0,x,h1=0,s=0,h2=m*(m-1)*(m-2)%mod,h3=0;
for(int i=1;i<=n;i++)
for(int j=0;j<a[i].size();j++)
if(a[i].size()>a[a[i][j]].size()||(a[i].size()==a[a[i][j]].size()&&i<a[i][j]))a1[i].push_back(a[i][j]);
for(int i=1;i<=n;i++)
{
for(int j=0;j<a1[i].size();j++)v[a1[i][j]]=1;
for(int j=0;j<a1[i].size();j++)
{
x=a1[i][j];
for(int u=0;u<a1[x].size();u++)h+=v[a1[x][u]];
}
for(int j=0;j<a1[i].size();j++)v[a1[i][j]]=0;
}
for(int i=1;i<=n;i++)
for(int j=0;j<a[i].size();j++)h1=(h1+((long long)(a[i].size()-1))*(a[a[i][j]].size()-1)%mod)%mod;
h1=h1*poww(2,mod-2)%mod,h1=(h1-(h*3)%mod+mod)%mod;
for(int i=1;i<=n;i++)
for(int j=0;j<a[i].size();j++)
{
x=a[i].size()+a[a[i][j]].size()-1;
h3=(h3+(m-x)*(a[i].size()-1)%mod)%mod;
}
h3=h3*poww(2,mod-2)%mod;
h3=(h3-h1+mod)%mod;
if(n>=3)s=(s+((h*6)%mod)*p[n-3]%mod)%mod;
if(n>=4)s=(s+(h1*6%mod)*p[n-4]%mod)%mod;
if(n>=4)s=(s+(h3*6%mod)*p[n-5]%mod)%mod;
h2=(h2-(h1+h+h3)*6%mod+mod)%mod,h1=0;
for(int i=1;i<=n;i++)
if(a[i].size()>=2)h1=(h1+((long long)(a[i].size())*(a[i].size()-1)%mod)*(a[i].size()-2)%mod)%mod;
if(n>=4)s=(s+h1*p[n-4]%mod)%mod;
h2=(h2-h1+mod)%mod;
if(n>=6)s=(s+h2*p[n-6]%mod)%mod;
return s;
}
int main()
{
long long x,y;
scanf("%lld%lld%lld",&n,&m,&k),p[0]=1;
for(int i=1;i<=200000;i++)p[i]=p[i-1]*2%mod;
for(int i=1;i<=m;i++)
{
scanf("%lld%lld",&x,&y);
a[x].push_back(y),a[y].push_back(x);
}
if(n==1){printf("0");return 0;}
if(k==1){printf("%lld",solve1());return 0;}
if(k==2){printf("%lld",(solve1()+solve2()+mod)%mod);return 0;}
if(k==3){printf("%lld",(solve1()+solve2()*3+solve3()+mod*5)%mod);return 0;}
return 0;
}
【Luogu P11191】 超级演出
题目描述
巡准备了一场超级演出。舞台和候场室可以看作一个包含 \(n\) 个点 \(m\) 条边的有向图，并且这个图当中没有环，也就是说，这是一张有向无环图（DAG）。
舞台为 \(1\) 号节点，保证所有节点均有到达节点 $ 1$ 的路径。其余的节点均为候场室，每个候场室恰有一个剧团进行等待。
巡可以对一个候场室 \(u\) 发布出场命令：
- 如果这个候场室的剧团还没有出场，并且存在一条 \(u\to 1\) 的路径上没有其余候场的剧团。那么这个剧团就会沿着这条路径到达舞台进行演出，随后退场。注意：一个剧团退场后不会重新回到候场室。
- 否则，这个命令被认为是无效的。
巡有一个命令序列 \(a_1,a_2,\dots,a_k\) 和 \(q\) 次询问，每次给出一个区间 \([l,r]\)。巡想要知道如果依次对候场室 \(a_l,a_{l+1},\dots,a_r\) 发布出场命令后，候场室还会剩下多少剧团等待演出。
注意：每次询问相互独立，也就是说，每次询问之前，每个候场室都恰有一个剧团进行等待，其中 \(1 \le n,m,q \le 2 \times 10^5\)。
解题思路
我们考虑对每个命令 \(a_i\) 求出最晚从第 \(v_{a_i}\) 个命令开始执行能使第 \(a_i\) 个候场室的剧团演出，求出所有 \(v_{a_i}\) 后变成了一个二维偏序问题，时间复杂度是 \(O(nlogn)\) 的。
考虑如何求出 \(v_{a_i}\) ，我们从命令 \(1\) 开始从前往后处理，不断更新 \(v_{a_i}\) ，初始化 \(v_1=i\) ，每次处理到 \(a_i\) 时我们就找 \(a_i\) 能到达的节点中最大的 \(v_i\) 来更新 \(v_{a_i}\) ，这个做法的时间复杂度时 \(O(n^2)\) 。
考虑优化，由于每次都会找所有能到达的节点会导致超时，我们可以在做完一个节点后给所有能到达它的节点打个标记，在更新这些节点时可以快速处理，但由于出入度都可能很大，时间复杂度还是 \(O(n^2)\) 的。
注意边数 \(\le 2 \times 10^5\) ，考虑根号分治，我们每次更新完一个节点给所有能到达它的且出度 \(> \sqrt{m}\) 的节点打上标记，更新时对于出度 \(\le \sqrt{m}\) 的节点，我们直接查找即可，对于出度 \(> \sqrt{m}\) 的节点，我们用标记更新自己，由于出度 \(>\sqrt{m}\) 的节点最多 \(\sqrt{m}\) 个，时间复杂度为 \(O(n\sqrt{m})\) 。
每次只用更新一个节点的 \(v_i\) ，二维偏序的时间复杂度认为 \(O(nlogn)\) ，总时间复杂度 \(O(n\sqrt{m})\)。
Code
#include<bits/stdc++.h>
using namespace std;
struct datay
{
int l,r,v,p;
}t[400005];
int qwe,n,m,k,m1,block,pre[400005],d[400005],f[400005],tim[400005];
bool v[400005],v1[400005];
vector<int> a[400005],b[400005];
bool cmp1(datay q,datay w){return q.r<w.r;}
bool cmp2(datay q,datay w){return q.p<w.p;}
int lowbit(int x){return x&(-x);}
void modify(int x,int y)
{
x=k+1-x;
if(x==0)return;
while(x<=400000)f[x]+=y,x+=lowbit(x);
return;
}
int query(int x)
{
x=k+1-x;
int h=0;
while(x)h+=f[x],x-=lowbit(x);
return h;
}
void solve1(int x)
{
for(int i=0;i<b[x].size();i++)tim[b[x][i]]=max(tim[b[x][i]],pre[x]);
return;
}
void solve(int x,int y)
{
if(v1[x]){modify(pre[x],-1),pre[x]=y,modify(y,1);solve1(x);}
if(v[x])
{
modify(pre[x],-1);
pre[x]=max(pre[x],tim[x]);
modify(pre[x],1),solve1(x);
return;
}
modify(pre[x],-1);
for(int i=0;i<a[x].size();i++)pre[x]=max(pre[x],pre[a[x][i]]);
modify(pre[x],1);
solve1(x);
return;
}
int main()
{
int x,y;
scanf("%d%d%d%d%d",&qwe,&n,&m,&k,&m1),block=sqrt(n);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y),a[x].push_back(y);
if(y==1)v1[x]=1;
}
for(int i=1;i<=n;i++)
if(a[i].size()>block)v[i]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<a[i].size();j++)
if(v[i])b[a[i][j]].push_back(i);
for(int i=1;i<=k;i++)scanf("%d",&d[i]);
for(int i=1;i<=m1;i++)scanf("%d%d",&t[i].l,&t[i].r),t[i].p=i;
sort(t+1,t+m1+1,cmp1),modify(0,n);
for(int i=1;i<=m1;i++)
{
for(int j=t[i-1].r+1;j<=t[i].r;j++)solve(d[j],j);
t[i].v=query(t[i].l);
}
sort(t+1,t+m1+1,cmp2);
for(int i=1;i<=m1;i++)printf("%d\n",n-t[i].v-1);
return 0;
}
【AGC008F】 Black Radius
题目描述
Snuke 君有一棵 \(n\) 个节点的全白的树，其中有一些节点他喜欢，有一些节点他不喜欢。他会选择一个他喜欢的节点 \(x\)，然后选择一个距离 \(d\)，然后将所有与 \(x\) 距离不超过 \(d\) 的节点都染成黑色，问最后有多少种可能的染色后状态。
两个状态不同当且仅当存在一个节点，它在两个状态中不同色，同时 \(1 \le n \le 2 \times 10^5\)。
解题思路
方案最多有 \(n^2\) 种，难点在于如何去重。
我们将一种方案通过 \((u,v)\) 代表在点 \(u\) 将距离不超过 \(v\) 的点染黑来表示，那么可能就会有多组 \((u,v)\) 代表同一种方案，我们用钦定 \(v\) 最小的那种方案来表示。
先来考虑全部点都是喜欢的点的情况，首先我们不考虑全被染黑的情况，以节点 \(u\) 为根，在统计完后 \(+1\) 即可，那么对于每组 \((u,v)\) 中 \(v<d1_u\) ，其中 \(d1_u\) 代表 \(u\) 到最远点的问题。
同时要保证 \(v\) 是所有表示中最小的，即对于 \(u\) 旁边的所有点 \(p\) ，不存在 \((p,v-1)=(u,v)\) 。
由于 \((u,v)\) 必定包含 \((p,v-1)\) ，那么若满足条件即存在一个点 \(x\) 使得 \(dis(x,u)=v\) 同时 \(dis(x,p)=v-2\) ，那么对于每个 \(p\) ，\(v\) 最大能到除这棵子树外到 \(u\) 最远的节点，那我们把最深的节点放在 \(p\) 的子树内，即 \(v-2<\) 到 \(u\) 第二大的距离 \(d2_u\)，\(v<d2_u+2\) ，结合上一个条件，我们有 \(v=min(d1_u-1,d2_u+1)\) 。
考虑当 \(u\) 为不喜欢的节点时的情况，我们需要把 \(u\) 移到一个喜欢的节点上，但是移动会改变方案，我们需要每移动一次 \(v\) 就要 \(+1\) 是方案包含的点集不会变小，同时需要保证 \(u\) 所在的子树已经遍历完，保证点集不会变大。
那么此时只是限制了下限，我们最小只能到一个包含了喜欢的点的子树的最大深度 \(d3_u\)，即 \(v \ge d3_u\) ，此时 \(d3_u \le v \le min(d1_u-1,d2_u+1)\) 。
我们只需要求出三个数组即可，使用换根 \(dp\) ，时间复杂度 \(O(n)\) 。
Code
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
int n,root1,root2,maxx1[200005],maxx2[200005],d[200005],t[200005],f[200005],siz[200005];
long long s=0;
vector<int> a[200005];
string b;
void dfs1(int x,int y)
{
siz[x]=(b[x]=='1');
for(int i=0;i<a[x].size();i++)
{
if(a[x][i]==y)continue;
dfs1(a[x][i],x),siz[x]+=siz[a[x][i]];
if(maxx1[x]<=maxx1[a[x][i]]+1)maxx2[x]=maxx1[x],maxx1[x]=maxx1[a[x][i]]+1;
else if(maxx2[x]<maxx1[a[x][i]]+1)maxx2[x]=maxx1[a[x][i]]+1;
if(siz[a[x][i]])d[x]=min(d[x],maxx1[a[x][i]]+1);
else d[x]=min(d[x],d[a[x][i]]+1);
}
return;
}
void dfs2(int x,int y,int z1)
{
if(maxx1[x]<=z1)maxx2[x]=maxx1[x],maxx1[x]=z1;
else if(maxx2[x]<z1)maxx2[x]=z1;
int z;
if(y&&(siz[1]-siz[x]))d[x]=min(d[x],z1);
if(b[x]=='1')s+=min(maxx1[x],maxx2[x]+2);
else if(min(maxx1[x],maxx2[x]+2)>=d[x])s+=min(maxx1[x],maxx2[x]+2)-d[x];
for(int i=a[x].size()-1;i>=0;i--)
t[a[x][i]]=max(((i!=a[x].size()-1)?t[a[x][i+1]]:z1),((a[x][i]!=y)?maxx1[a[x][i]]+1:0));
for(int i=0;i<a[x].size();i++)
{
if(a[x][i]==y)continue;
z=maxx1[a[x][i]]+1;
if(i!=a[x].size()-1)dfs2(a[x][i],x,max(z1,t[a[x][i+1]])+1);
else dfs2(a[x][i],x,z1+1);
z1=max(z1,z);
}
return;
}
int main()
{
memset(d,0x3F,sizeof(d));
int x,y;
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
a[x].push_back(y),a[y].push_back(x);
}
cin>>b,b=' '+b;
dfs1(1,0);
dfs2(1,0,0);
cout<<s+1;
return 0;
}
【Luogu P7831】 Travelling Merchant
题目描述
一个国家有 \(n\) 个城市和 \(m\) 条单向道路，一个旅行商在这些城市之间旅行。
第 \(i\) 条道路从城市 \(a_i\) 到城市 \(b_i\)，只有当他的资产不少于 \(r_i\) 元才可以走这条道路，走过这条道路之后他的资产会增加 \(p_i\) 元。
他希望自己可以永远不停的游走下去，于是他想知道从任意一个城市出发至少需要多少元初始资产，\(1 \le n,m \le 2 \times 10^5,1 \le r_i,p_i \le 10^9\)。
解题思路
注意到是资产不少于 \(r_i\) 元而不是资产减去 \(r_i\) 元，说明只要一条从 \(x\) 出发的合法的路径中出现了不在起点的 \(x\) ，那么这个方案就是合法的。
考虑暴力，每次从点 \(x\) 开始做 \(dfs\) ，找能走回自己的路径，设经过路径为 \(V_{1...l}\)，答案即为 \(max_{i=1}^{l} (r_i-\sum_{j=1}^{i-1} p_j)\) ，由于每次爆搜到一个点会有点 \(x\) 、当前最大值以及 \(\sum_{j=1}^{i-1}p_j\) 三种状态，所以这种方法最多优化到 \(O(n^3)\) 。
我们考虑倒着走，这样答案为 \(max_{i=1}^l (r_i-\sum_{j=i+1}^l p_j)\) ，由于每一次的减 \(p_j\) 我们可以看成给前面的所有最大值 \(-p_j\) ，那我们可以只存储最大值，减 \(p_j\) 的操作可以等到做到这条边的时候再做，这样是可以优化到 \(O(n^2)\) 的。
我们观察上面我们的 \(dfs\) ，一个点 \(x\) 可能会做多次 \(dfs\) ，因为我们只需要求出最小的最大值，我们可以等完能到自己的点做完之后再做，可以保证当前最大值最小，但由于图有环，我们需要安排边的遍历顺序。
我们发现对于一个大于之前所有边的 \(r_j\) 的边的 \(r_i\) ，那么之前的 \(r_j\) 是不重要的，也就是说，对于若边 \(i\) 为当前答案，那么只要起点能到边 \(i\) 且仍保持目前最大值 \(<r_i\)，那么我们需要考虑 \(r_i\) 到起点就可以了，不考虑起点能到边 \(i\) 的情况，由于 \(r_i\) 最大的边之前走过的边的 \(r_j\) 必定可以不用管它，我们可以先考虑这些边，然后在考虑第二大、第三大 ...... 的边，再加边的同时做拓扑排序，即可通过这道题。
时间复杂度 \(O(m)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
struct edge
{
long long x,y,z,q;
}b[200005];
struct datay
{
long long pre,to,nex,las,v1,v2;
}a[200005];
long long n,m,num,head[200005],f[200005],d[200005];
bool v[200005];
queue<int> l;
bool cmp1(edge q,edge w){return q.z>w.z;}
void add(int x,int y,int z,int q)
{
a[++num].to=y,a[num].v1=z,a[num].v2=q,a[num].pre=x;
a[head[x]].las=num,a[num].las=0,a[num].nex=head[x],head[x]=num;
return;
}
void del(int x)
{
v[x]=true;
if(a[x].las==0)head[a[x].pre]=a[x].nex,a[a[x].nex].las=0;
else a[a[x].las].nex=a[x].nex,a[a[x].nex].las=a[x].las;
return;
}
int main()
{
int x,y;
memset(f,0x3F,sizeof(f)),memset(v,false,sizeof(v));
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++)scanf("%lld%lld%lld%lld",&b[i].x,&b[i].y,&b[i].z,&b[i].q);
sort(b+1,b+m+1,cmp1);
for(int i=1;i<=m;i++)add(b[i].y,b[i].x,b[i].z,b[i].q),d[b[i].x]++;
for(int i=1;i<=n;i++)if(!d[i])l.push(i);
for(int i=1;i<=m;i++)
{
while(l.size())
{
x=l.front(),l.pop();
for(int j=head[x];j!=0;j=a[j].nex)
{
f[a[j].to]=min(f[a[j].to],max(f[a[j].pre]-a[j].v2,a[j].v1));
d[a[j].to]--;
if(d[a[j].to]==0)l.push(a[j].to);
del(j);
}
}
if(v[i])continue;
f[a[i].to]=min(f[a[i].to],a[i].v1);
del(i),d[a[i].to]--;
if(d[a[i].to]==0)l.push(a[i].to);
}
for(int i=1;i<=n;i++)printf("%lld ",(f[i]>=1e11)?(-1):f[i]);
return 0;
}
动态规划
【Luogu P10681】 奇偶矩阵 Tablica
题目描述
考虑只包含 \(0\) 和 \(1\) 的 \(N\times M\) 矩阵 \(A\)。
我们称满足以下条件的矩阵是好的：
- \(\forall 1\le i\le N\)，\(\displaystyle \sum_{j=1}^M A_{i,j}\in \{1,2\}\)；
- \(\forall 1\le j\le M\)，\(\displaystyle \sum_{i=1}^N A_{i,j}\in \{1,2\}\)。
求出 \(N\) 行 \(M\) 列的好的矩阵的数量，对 \((10^9+7)\) 取模，\(1 \le n ,m \le 3000\)。
解题思路
法一
由于矩阵只包含 \(0\) 和 \(1\) ，我们把每个 \(1\) 的节点 \((i,j)\) 看成第 \(i\) 行所代表的点向第 \(j\) 行所代表的点连了一条边。
很明显，我们构造出了一个二分图，若这个图满足题目要求有两个条件，每个点不是独立的且每个连通块必须是一条链或一个环。
注意每个连通块在左右两边所占的个数最多只差 \(1\) ，参考 ABC180F ，做一个 \(n^2\) 的 \(dp\) 即可。
法二
我们可以枚举有多少行、列和分别为 \(1\) 或 \(2\) ，设有 \(a\) 行的和为 \(1\) ，\(b\) 行的和为 \(2\) ，\(c\) 列的和为 \(1\) ，\(d\) 列的和为 \(2\) ，满足 \(a+b=n,c+d=m,a+2b=c+2d\)。
我们可以 \(O(n)\) 枚举 \(a,b,c,d\) ，考虑如何贡献答案。
首先给每行每列安排为 \(1\) 还是 \(2\) ，即乘上 \(C_{n}^{a} C_{m}^{b}\) ，然后考虑如何将每列的 \(1\) 分配到每行。
我们看成这样一个问题：有 \(c+2d\) 个小球，共有 \(m\) 种颜色，\(c\) 种颜色的小球每种各 \(1\) 个，\(d\) 种颜色的小球每种个 \(2\) 个，分成 \(n\) 个块，要求每块里面的球的颜色不能相同。
我们考虑将其排成一个序列，共有 \(\frac{(c+2d)!}{2^d}\) 种方案，然后按顺序分成块。
可能会有两种重复，第一种为出现 \({1,2}\) 与 \({2,1}\) 的情况，这种直接除 \(2^b\) 即可。
第二种为出现 \({1,1}\) 的情况，这种情况我们需要容斥，考虑 \(t(0 \le t \le min(b,d))\) 个 \(1,1\) 的集合，每次的答案即为 \((-1)^t A_{b}^{t}C_{d}^{t} \frac{(c+2d-2t)!}{2^{b+d-t}}\)。
总答案 $ans=\sum C_{n}^a C_m^b \sum_{t=0}^{min(b,d)} (-1)^t A_{b}^t C_{d}^t \frac{(c+2d-2t)!}{2^{b+d-t}} $ 。
ABC273G 和这题差不多，只是每个点可能为 \(2\) ，枚举即可。
Code
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long n,m,C[3005][3005],p[10005],p1[10005],a,b,c,d,s,f[10005];
long long poww(long long x,long long y)
{
long long h=1;
while(y)
{
if(y&1)h=(h*x)%mod;
x=(x*x)%mod,y>>=1;
}
return h;
}
int main()
{
long long x,s1=0;
scanf("%lld%lld",&n,&m),p[0]=p1[0]=f[0]=1;
for(int i=1;i<=10000;i++)p[i]=p[i-1]*2%mod,p1[i]=poww(p[i],mod-2),f[i]=(f[i-1]*i)%mod;
for(int i=0;i<=3000;i++)C[i][i]=C[i][0]=1;
for(int i=1;i<=3000;i++)
for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
for(int i=0;i<=n;i++)
{
a=i,b=n-i,d=a+2*b-m,c=m-d,x=min(b,d),s1=0;
if(c<0||d<0)continue;
for(int j=0;j<=x;j++)
s1=(s1+((j&1)?(-1):1)*(((C[b][j]*C[d][j]%mod)*f[j]%mod)*(f[c+2*d-2*j]*p1[b+d-j]%mod)%mod)%mod)%mod;
s=(s+s1*(C[n][a]*C[m][c]%mod)%mod)%mod;
}
printf("%lld",(s+mod)%mod);
return 0;
}
【Luogu P9197】摩天大楼
题目描述
将互不相同的 \(N\) 个整数 \(A_1, A_2, \cdots, A_N\) 按照一定顺序排列。
假设排列为 \(f_1, f_2, \cdots, f_N\)，要求：\(| f_1 - f_2| + | f_2 - f_3| + \cdots + | f_{N-1} - f_N| \leq L\)。
求满足题意的排列的方案数对 \(10^9+7\) 取模后的结果，\(1 \le n \le 100, 1 \le L \le 1000,1 \le A_i \le 1000\)。
解题思路
题目中有绝对值不好处理，我们考虑将它放到平面直角坐标系中看一看，每个点为 \(i,f_i\) ，连成一条折线。
对于 $ |f_1 - f_2| + | f_2 - f_3| + \cdots + | f_{N-1} - f_N| $ 这个东西，在表格中我们可以这样看：对于 \(y=i\) ，与该折线有多少次相交，代表了它产生了多少次贡献。
对于这个东西我们如何处理呢？我们可以使用插入 \(dp\) ，将其看成一个个连续段，并计算新增的折线长度。
先将 \(A\) 从大到小排序并从大到小做 \(dp\)，我们设 \(dp\) 数组 \(dp_{i,j,k}\) 分别表示处理到第 \(i\) 位、已有 \(j\) 个连续段、目前这线段长度为 \(k\) ，设 \(v=f_{i-1}-f_i\) ，那么有三种情况，分别讨论。
若新加进来的 \(f_i\) 作为一个新的连通块，考虑它可以放在哪里以及折线延长的长度，那么有：$ dp_{i,j,k}+=j \times dp_{i-1,j-1,k-2 \times (j-1) \times v}$ 。
若新加进来的 \(f_i\) 放到了一个连通块的一侧，那么连通块的数量是不变的，有：\(dp_{i,j,k}+=2 \times j \times dp_{i-1,j,k-2 \times j \times v}\) 。
若新加进来的 \(f_i\) 连接了两个连通块，那么连通块的数量要 \(-1\) ，有：\(dp_{i,j,k}+= j \times dp_{i-1,j+1,k-2 \times (j+1) \times v}\) 。
但是有一个很重要的一点：处于两端的点不会延伸折线，所以我们还要开两维 \(0/1\) 表示左端点/右端点是否放到排列中，相应的状态转移方程也需要分类，答案即为 \(dp_{n,1,L,1,1}\)。
核心 \(dp\) 就做完了，细节注意要开滚动数组，时间复杂度 \(O(n^2m)\)。
Code
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long n,m,a[1005],f[2][105][1005][2][2],s;
bool cmp(int q,int w){return q>w;}
inline void dijah(long long &q,long long w)
{
q=(q+w>=mod)?(q+w-mod):(q+w);
return;
}
int main()
{
int q,w,e;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
sort(a+1,a+n+1,cmp);
f[1][1][0][0][0]=f[1][1][0][0][1]=f[1][1][0][1][0]=f[1][1][0][1][1]=1;
for(register int i=1;i<n;i++)
{
e=i&1,q=e^1;
for(register int k=1;k<=i;k++)
for(register int j=0;j<=m;j++)
for(register int q1=0;q1<2;q1++)
for(register int q2=0;q2<2;q2++)
{
if(!f[e][k][j][q1][q2])continue;
w=j+(2*k-q1-q2)*(a[i]-a[i+1]);
if(w>m){f[e][k][j][q1][q2]=0;continue;}
if(k>1)dijah(f[q][k+1][w][q1][q2],(k-1)*f[e][k][j][q1][q2]%mod);
if(!q1)dijah(f[q][k+1][w][q1][q2],f[e][k][j][q1][q2]),dijah(f[q][k+1][w][1][q2],f[e][k][j][q1][q2]);
if(!q2)dijah(f[q][k+1][w][q1][q2],f[e][k][j][q1][q2]),dijah(f[q][k+1][w][q1][1],f[e][k][j][q1][q2]);
if(k>1)dijah(f[q][k][w][q1][q2],2*(k-1)*f[e][k][j][q1][q2]%mod);
if(!q1)dijah(f[q][k][w][q1][q2],f[e][k][j][q1][q2]),dijah(f[q][k][w][1][q2],f[e][k][j][q1][q2]);
if(!q2)dijah(f[q][k][w][q1][q2],f[e][k][j][q1][q2]),dijah(f[q][k][w][q1][1],f[e][k][j][q1][q2]);
if(k>1)dijah(f[q][k-1][w][q1][q2],(k-1)*f[e][k][j][q1][q2]%mod);
f[e][k][j][q1][q2]=0;
}
}
for(int i=0;i<=m;i++)dijah(s,f[(n&1)][1][i][1][1]);
printf("%lld",s);
return 0;
}
【ARC118E】 Avoid Permutations
题目描述
对于一个排列 \(P\)，定义 \(F(P)\) 如下：
对于一个 \((N+2)\times (N+2)\) 的网格图，行列标号为 \(0\sim N+1\)，从 \((0,0)\) 走到 \((N+1,N+1)\) 在不经过 \((i,P_i)\) 情况下的方案数。
给定一个残缺的排列，对于其所有补全求函数之和，\(1 \le N \le 200\)。
解题思路
我们先来考虑一个完整的排列我们该如何求和，有两种方法：\(n^2\) 遍历一遍整个图做一个统计路径个数的 \(dp\) ， 同样 \(n^2\) 做一个带容斥的 \(dp\) 。
由于问题可能有缺项，直接 \(dp\) 显然是不现实的，我们考虑套一个容斥上去。
我们先转换贡献体，将贡献变成一条路径不会经过的排列个数之和，很明显，直接统计还是不好做，但我们套上一个容斥就好做了。
我们把不能经过的点叫做实点，因为是容斥，我们注意一个点：以前经过的实点对之后不会产生影响，那我们可以设计 \(dp\) 了。
设 \(dp_{i,j,0/1,0/1}\) 表示做到点 \((i,j)\) 、本行有没有实点、本列是否有实点，所有已经给出的实点都不经过，但是不是非常好转移，因为难以统计可以在那些地方放实点。
我们不妨再加一维，设 \(dp_{i,j,k,0/1,0/1}\) 表示做到点 \((i,j)\) 、已经经过了 \(k\) 个实点 、本行有没有实点、本列是否有实点，因为我们是容斥，没必要考虑是否还会经过其它实点的情况，当然，已给出的还是不经过。
转移不难，正常转移即可，设 \(m\) 为已给出点的个数，答案即为 \(\sum_{i=0}^{n-m} (n-m-i)! f_{n+1,n+1,i,0,0}\) 。
时间复杂度 \(O(n^3)\) ，常数可能略大。
Code
#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
int n,a[205],k,f[205][205][205][2][2];
long long p[1005],s=0;
bool v[205][205],v1[205],v2[205];
int main()
{
scanf("%d",&n),p[0]=1;
for(int i=1;i<=1000;i++)p[i]=p[i-1]*i%mod;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]!=-1)v[i][a[i]]=1,k++,v1[i]=1,v2[a[i]]=1;
}
f[0][0][0][1][1]=1;
for(int i=0;i<=n+1;i++)
for(int j=0;j<=n+1;j++)
for(int u=0;u<=n;u++)
for(int u1=0;u1<=1;u1++)
for(int u2=0;u2<=1;u2++)
{
if(!v[i][j+1])
{
f[i][j+1][u][u1][v2[j+1]]=(f[i][j+1][u][u1][v2[j+1]]+f[i][j][u][u1][u2])%mod;
if((!v2[j+1])&&j<n&&(u1==0))f[i][j+1][u+1][1][1]=(f[i][j+1][u+1][1][1]-f[i][j][u][u1][u2])%mod;
}
if(!v[i+1][j])
{
f[i+1][j][u][v1[i+1]][u2]=(f[i+1][j][u][v1[i+1]][u2]+f[i][j][u][u1][u2])%mod;
if((!v1[i+1])&&i<n&&(u2==0))f[i+1][j][u+1][1][1]=(f[i+1][j][u+1][1][1]-f[i][j][u][u1][u2])%mod;
}
}
for(int i=0;i<=n-k;i++)s=(s+p[n-k-i]*f[n+1][n+1][i][0][0])%mod;
printf("%lld",(s+mod)%mod);
return 0;
}
【Luogu P6047】 丝之割
题目描述
下面这部分题面只是为了帮助你理解题意，并没有详细的解释。更为严谨清晰的叙述见形式化题意。
多弦琴由两根支柱和连接两根支柱的 \(m\) 条弦组成。每根支柱上都均匀安放着 \(n\) 个固定点，第 \(i\) 条弦连接上方支柱的第 \(u_i\) 个固定点和下方支柱的第 \(v_i\) 个固定点。
为了摧毁多弦琴，你可以进行若干次切割操作。在一次切割操作中，你可以选择上方支柱的某一个固定点 \(u\) 和下方支柱的一个固定点 \(v\)，所有被 \(u\) 到 \(v\) 的连线从左到右穿过的弦都将被破坏。但同时，你需要付出 \(a_u \times b_v\) 的代价。
形式化题意：有 \(m\) 条弦，一条弦可以抽象为一个二元组 \((u,v)\)，你可以进行任意次切割操作，一次切割操作你将选择两个下标 \(i\) 和 \(j\) 满足 \(i,j \in [1,n]\)，然后所有满足 \(u>i,v<j\) 的弦 \((u,v)\) 都将被破坏，同时你将付出 \(a_i \times b_j\) 的代价。求破坏所有弦的最小代价和，\(1 \le n,m \le 3 \times 10^5\)。
解题思路
我们能发现一个东西，对于一条弦 \(i\) ，若存在 \(j\) \(u_j \le u_i,v_i \le v_j\) ，那么弦 \(i\) 是没必要记录的。
那么我们删去一些弦，那么剩余的弦按 \(u_i\) 排序后 \(v_i\) 一定是递增的。
据此我们就可以设计 \(dp\) 了，每次 \(dp\) 一段表示将一段的弦一次性割掉，时间复杂度是 \(O(n^2)\) 的。
很明显可以用斜率优化，因为有单调关系可优化到 \(O(n)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
struct datay
{
long long x,y;
}v1[1000005],v[1000005];
long long n,mm,m,a[1000005],b[1000005],d[1000005],l,r,f[1000005];
double T(long long x,long long y)
{
if(a[v[x+1].x-1]!=a[v[y+1].x-1])return double(double(double(f[x])-double(f[y]))/double(double(a[v[y+1].x-1])-double(a[v[x+1].x-1])));
else if(f[x]>f[y])return -1e9-5;
else return 1e9+5;
}
bool cmp(datay q,datay w)
{
if(q.x!=w.x)return q.x<w.x;
else return q.y<w.y;
}
int main()
{
scanf("%lld%lld",&n,&mm);
a[0]=1e9+5;
b[n+1]=1e9+5;
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
a[i]=min(a[i-1],a[i]);
}
for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
for(int i=n;i>=1;i--)b[i]=min(b[i+1],b[i]);
for(int i=1;i<=mm;i++)
{
scanf("%lld%lld",&v1[i].x,&v1[i].y);
}
sort(v1+1,v1+mm+1,cmp);
long long x=0;
for(int i=1;i<=mm;i++)
{
if(v1[i].y>x)
{
v[++m]=v1[i];
x=v1[i].y;
}
}
d[++r]=0;
l=1;
for(int i=1;i<=m;i++)
{
while(r-l>=1&&T(d[l],d[l+1])<=b[v[i].y+1])l++;
f[i]=f[d[l]]+a[v[d[l]+1].x-1]*b[v[i].y+1];
while(r-l>=1&&T(d[r-1],d[r])>T(d[r],i))r--;
d[++r]=i;
}
cout<<f[m];
return 0;
}
【Luogu P3349】 小星星
题目描述
小 Y 是一个心灵手巧的女孩子，她喜欢手工制作一些小饰品。她有 \(n\) 颗小星星，用 \(m\) 条彩色的细线串了起来，每条细线连着两颗小星星。
有一天她发现，她的饰品被破坏了，很多细线都被拆掉了。这个饰品只剩下了 \(n-1\) 条细线，但通过这些细线，这颗小星星还是被串在一起，也就是这些小星星通过这些细线形成了树。小 Y 找到了这个饰品的设计图纸，她想知道现在饰品中的小星星对应着原来图纸上的哪些小星星。如果现在饰品中两颗小星星有细线相连，那么要求对应的小星星原来的图纸上也有细线相连。小 Y 想知道有多少种可能的对应方式。
只有你告诉了她正确的答案，她才会把小饰品做为礼物送给你呢，其中 \(1 \le n\le 17\)。
解题思路
我们很容易想到一个树形 \(dp\) ：\(f_{i,j,k}\) 表示处理到第 \(i\) 个节点，把当前节点放到原 \(j\) 节点上，且被使用的原节点的方案为 \(k\) 。
状态转移方程很好推，时间复杂度是 \(O(n^23^n)\) 的。
瓶颈在于每次转移时的枚举子集，考虑优化。
枚举子集是无法避免的，考虑将 \(k\) 从状态中移出去，我们发现之所以要存 \(k\) ，是因为原节点不能有重复。
那我们可以用容斥，用不考虑重复的情况减去有重复的情况，但还是不好做。
我们这样理解：每个原节点都必须出现一遍，那我们可以这样做容斥：每次枚举一个子集 \(S\) 表示这次的原节点都必须在 \(S\) 内，然后根据 \(|S|\) 来判断前面要不要乘 \(-1\) 。
这就是一种二项式反演，每次枚举完 \(O(n^2)\) \(dp\) 求方案数即可。
时间复杂度 \(O(n^2 2^n)\) ，能过。
Code
#include<bits/stdc++.h>
using namespace std;
int n,m,p,q,d[25];
long long s,f[25][25];
vector<int> a[25],a1[25][150005];
void dfs(int x,int y)
{
long long h=0;
for(int i=1;i<=n;i++)
{
if((!((1<<(i-1))&q))||a[x].size()>d[i])f[x][i]=0;
else f[x][i]=1;
}
for(int i=0;i<a[x].size();i++)
{
if(a[x][i]==y)continue;
dfs(a[x][i],x);
for(int j=1;j<=n;j++)
{
if((!((1<<(j-1))&q))||a[x].size()>d[j])continue;
h=0;
for(int u=0;u<a1[j][q].size();u++)h+=f[a[x][i]][a1[j][q][u]];
f[x][j]*=h;
}
}
return;
}
int main()
{
int x,y,w;
scanf("%d%d",&n,&m),p=(1<<n);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y),q=(1<<(x-1)),w=(1<<(y-1)),d[x]++,d[y]++;
for(int j=0;j<p;j++)
if((q&j)&&(w&j))a1[x][j].push_back(y),a1[y][j].push_back(x);
}
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
a[x].push_back(y),a[y].push_back(x);
}
for(int i=0;i<p;i++)
{
w=n;
for(int j=0;j<n;j++)
if(!(i&(1<<j)))w--;
q=i;
dfs(1,0);
for(int j=1;j<=n;j++)
s+=f[1][j]*(((n-w)&1)?(-1):1);
}
printf("%lld",s);
return 0;
}
【Luogu P10175】 Subtree Value
题目描述
给出一棵 \(n\) 个节点的树，每个点有点权 \(a_v\)。定义一棵树的一个子连通块为一个树中点的非空集合，满足这些点在树上形成一个连通块。定义子连通块 \(S\) 的权值为 \(\prod_{v\in S}(a_v+|S|)\)。求所有子连通块的权值之和对 \(U^V\) 取模， \(1 \le n \le 2000,1 \le U \le 10,1 \le V \le 6\)。
解题思路
我们可以很快想出一个 \(O(n^3)\) 的 \(dp\) ：\(f_{i,j,k}\) 表示处理到节点 \(i\) ，预计连通块大小为 \(j\) ，当前已构成了一个大小为 \(k\) 的连通块。
这个 \(dp\) 慢就慢在要同时记录两个连通块大小，考虑去掉其中一个。
我们之所以要记录预计连通块大小是因为每个点的价值要加上连通块大小，注意到答案要模的位 \(U^V\) ，其中 \(U,V\) 都不大。
我们考虑把 \(|S|\) 拆成 \(Ux+y\) 的形式，这样对于 \(a_v+|S|\) 我们就可以改写成 \(Ux+(a_v+y)\) ，这样我们就能把贡献式看成一个多项式。
由于 \(V\) 也很小，那么选择了大于等于个 \(Ux\) 是肯定的不会产生贡献的，我们只需要考虑当前值乘上了多少个 \(Ux\) 。
对于 \(|S|\) \(mod\) \(p1=u\) 的 \(S\) ，它们的 \(a_v\) 加上的都是 \(u\) ，那么我们就可以把这些东西一起处理掉。
考虑这样设计 \(dp\) ：\(f_{i,j,k}\) 表示处理到第 \(i\) 个节点、连通块当前大小为 \(j\) 、当前项中有 \(k\) 个 \(Ux\) 的总贡献，因为 \(Ux\) 固定，我们可以 \(dp\) 结束之后在处理它。
转移我们可以使用树形背包，时间复杂度为 \(O(n^2UV^2)\) 。
有个小技巧，转移时可以枚举完在一起取模，这样会快很多。
Code
#include<bits/stdc++.h>
using namespace std;
int n,siz[2005],k;
long long mod,p1,p2,v[2005],t[2005][6],s,f[2005][2005][6];
vector<int> a[2005];
void dfs(int x)
{
f[x][1][1]=1;
f[x][1][0]=(k+v[x])%mod;
siz[x]=1;
for(int i=0;i<a[x].size();i++)
{
dfs(a[x][i]);
memset(t,0,sizeof(t));
for(int j1=0;j1<=siz[x];j1++)
for(int u1=0;u1<p2;u1++)
for(int j2=0;j2<=siz[a[x][i]];j2++)
for(int u2=0;u2<p2;u2++)
if(u1+u2<p2)t[j1+j2][u1+u2]+=f[x][j1][u1]*f[a[x][i]][j2][u2];
siz[x]+=siz[a[x][i]];
for(int j=0;j<=siz[x];j++)
for(int u=0;u<p2;u++)f[x][j][u]=(t[j][u]+f[x][j][u])%mod;
}
return;
}
int main()
{
long long x;
scanf("%d%lld%lld",&n,&p1,&p2),mod=1;
for(int i=1;i<=p2;i++)mod*=p1;
for(int i=2;i<=n;i++)scanf("%lld",&x),a[x].push_back(i);
for(int i=1;i<=n;i++)scanf("%lld",&v[i]);
for(int i=0;i<p1;i++)
{
memset(f,0,sizeof(f)),k=i;
dfs(1);
for(int j=1;j<=n;j++)
for(int u=i;u<=n;u+=p1)
{
x=1;
for(int q=0;q<p2;q++)
s=(s+x*f[j][u][q])%mod,x*=(u/p1)*p1,x%=mod;
}
}
printf("%lld",s);
return 0;
}
【ARC184D】 Erase Balls 2D
题目描述
在二维平面上有 \(N\) 个编号从 \(1\) 到 \(N\) 的球，第 \(i\) 个位于 \((X_i, Y_i)\)。其中，\(X = (X_1, X_2, \cdots, X_n)\) 以及 \(Y = (Y_1, Y_2, \cdots, Y_n)\) 分别是一个 \(1, 2, \cdots, n\) 的排列（译注：即横纵坐标分别两两不同）。
你可以执行任意次以下操作：
- 从剩下的球中选择一个球，记为 \(k\)。对剩下的每个球 \(i\)，若满足「\(X_i < X_k \) 且 \(Y_i < Y_k\)」或「\(X_i > X_k\) 且 \(Y_i > Y_k\)」（译注：即两球坐标间有二维偏序关系），将其移除。
求操作结束后，可能的剩下球的集合的数量，对 \(998244353\) 取模。
- \(1 \le N \le 300\)
解题思路
统计剩下球的集合数量不好做，我们转换贡献体，考虑选择的球的集合 \(S\)。
首先集合 \(S\) 内部不能存在两个数 \(x,y\) 使得点 \(x\) 与点 \(y\) 存在偏序关系，根据这一点我们可以想出来一个 \(O(n^2)\) 的找最长不下降子序列的 \(dp\) 。
但这个 \(dp\) 很明显会重复统计很多 \(S\)，因为很多个选择的球的集合剩下的球的集合是完全一样的，我们考虑从剩下的球的集合构建一个对应关系使得与选择的球的集合一一对应。
我们把集合 \(S\) 中一个点称作必要的当且仅当删去该点剩余球的集合会变，那么我们考虑统计全为必要点的集合 \(S\) 个数，但进行 \(dp\) 转移时，我们发现由于后效性，我们不好统计哪些点为必要点。
换一种统计方式，我们考虑统计满足再多选一个数剩余球的集合就会变的集合 \(S\) ，即把非必要点都选上。
那这样转移就很好做了，我们只需要设 \(f_i\) 满足做到第 \(i\) 个球且选择第 \(i\) 个球的方案数，转移可以从 \(j \in [0,i-1]\) 转移过来，检验是否能转移只需找区间 \((i,j)\) 是否存在非必要点即可。
时间复杂度 \(O(n^3)\) 。
Code
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
const long long mod=998244353;
struct datay
{
int x,y;
}a[305];
int n;
bool cmp1(datay q,datay w){return q.x<w.x;}
long long f[305];
int d[305];
int main()
{
int q,w;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);
sort(a+1,a+n+1,cmp1);
a[0].y=n+1,a[n+1].y=0,f[0]=1;
for(int i=1;i<=n+1;i++)
for(int j=0;j<i;j++)
{
if(a[j].y<a[i].y)continue;
w=n+2,q=0;
for(int u=j+1;u<i;u++)d[u]=0;
for(int u=j+1;u<i;u++)
{
if(a[u].y<a[i].y||a[u].y>a[j].y)continue;
if(w>a[u].y)d[u]=1;
w=min(w,a[u].y);
}
w=-1;
for(int u=i-1;u>j;u--)
{
if(a[u].y<a[i].y||a[u].y>a[j].y)continue;
if(w<a[u].y&&d[u])q=1;
w=max(w,a[u].y);
}
if(q==0)f[i]=(f[j]+f[i])%mod;
}
printf("%lld",f[n+1]);
return 0;
}
【Luogu P8162】 让我们赢得选举 (Let's Win the Election)
题目描述
JOI 共和国有 \(N\) 个州，编号为 \(1 \sim N\)。在 2022 年，JOI 共和国将举行总统大选。选举将在每个州分别举行。每个州的获胜者将赢得该州的一张选票。
Rie 将竞选总统，她正计划赢得选举。她决定以发表演讲的方式来提高自己的可靠程度。在她发表演讲后，下列事件可能会发生。
- 如果在第 \(i\) 个州的总演讲时间达到了 \(A_i\) 小时，她将赢得该州的一张选票。
- 如果在第 \(i\) 个州的总演讲时间达到了 \(B_i\) 小时，她将获得一名来自该州的协作者。
- 有可能 Rie 在第 \(i\) 个州无法获得协作者。此种情况下，\(B_i = -1\)，否则保证 \(B_i > A_i\)。
来自第 \(i\) 个州的协作者可以在第 \(i\) 个州外发表演讲。多个人可以同时在同一个州发表演讲。举个例子，如果两个人在某个州同时发表了 \(x\) 小时的演讲，则该州的总演讲时间将增加 \(2 x\) 小时。演讲的时间不必是整数个小时。我们可以忽略在两州之间的交通耗时。
大选日快到了，Rie 想要尽快得到 \(K\) 张选票。
给定州的数量和每个州的信息，写一个程序计算得到 \(K\) 张选票的最小耗时（以小时为单位），\(1 \le n \le 500\)。
解题思路
我们能很容易的想到一个贪心，按 \(A_i\) 排序，每次枚举选 \(x\) 个 \(B_i\) ，把前 \(x\) 小的 \(B_i\) 给选走，接着从 \(1\) 开始选 \(A_i\) 直到选了 \(K\) 个为止。
很容易发现这个贪心是不对的，因为有可能有些时候对于某个前 \(x\) 小的 \(B_i\) 只选 \(A_i\) 更优，我们考虑更换贪心策略。
我们按 \(B_i\) 排序，这次我们枚举前 \(x\) 个全都被选择，按原贪心策略是前 \(x\) 个全选择 \(B_i\) 的，但由于有可能选 \(A_i\) 更优，我们考虑做一个 \(dp\) ，设 \(f_{i,j,u}\) 表示做到第 \(i\) 位将要选择 \(j\) 个 \(B_i\) 已经选择了 \(u\) 个 \(B_i\) 的最小时间，前 \(x\) 个选 \(y\) 的最小时间即为 \(f_{x,y,y}\) 。
我们预处理出这个 \(dp\) 数组，枚举选前 \(x\) 个同时枚举选择了 \(y\) 个 \(B_i\) ，同时用优先队列处理出后 \(n-x\) 个中最小的 \(A_i\) ，相加即可。
时间复杂度 \(O(n^3)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
struct datay
{
double x,y;
}a[505];
int n,m;
double f[2][505][505],d[505][505];
priority_queue<double> l;
bool cmp1(datay q,datay w)
{
if(q.y==-1&&w.y==-1)return q.x<w.x;
if(q.y==-1)return false;
if(w.y==-1)return true;
if(q.y!=w.y)return q.y<w.y;
return q.x<w.x;
}
int main()
{
double s=0;
int q1,q2;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);
sort(a+1,a+n+1,cmp1);
for(int i=1;i<=m;i++)
{
while(l.size())l.pop();
for(int j=n;j>=1;j--)
{
l.push(a[j].x),s+=a[j].x;
while(l.size()>i)s-=l.top(),l.pop();
if(n-j+1>=i)d[j][i]=s;
}
s=0;
}
s=d[1][m];
for(int i=0;i<=1;i++)
for(int j=0;j<=n;j++)
for(int u=0;u<=n;u++)f[i][j][u]=1e9;
for(int i=0;i<=m;i++)f[0][i][0]=0;
for(int i=1;i<=n;i++)
{
q1=(i&1),q2=q1^1;
for(int j=0;j<=n;j++)
{
for(int u=0;u<=m;u++)
{
f[q1][j][u]=f[q2][j][u]+a[i].x/(j+1);
if(u>=1&&a[i].y!=-1)f[q1][j][u]=min(f[q1][j][u],f[q2][j][u-1]+a[i].y/u);
}
}
for(int j=0;j<=m;j++)if(i<=m)s=min(s,f[q1][j][j]+d[i+1][m-i]/(j+1));
if(i==1)
{
for(int j=0;j<=n;j++)
for(int u=0;u<=n;u++)f[0][j][u]=1e9;
}
}
printf("%.9lf",s);
return 0;
}
【ABC134F】 Permutation Oddness
题目描述
定义一个排列 \(p\) 的怪异度为 \(\sum_{i=1}^n |p_i-i|\) ，求怪异度为 \(k\) 且长度为 \(n\) 的排列数，\(1 \le n \le 50,1 \le k \le n^2\) 。
解题思路
我们可以把 \(p_i\) 看成一条由 \(i\) 指向 \(p_i\) 的边，那么怪异度即是边的长度的长度之和，我们可以拆贡献，看成每个点 \(i\) 与 \(i+1\) 之间经过边的数量 \(\times 2\) 。
因为边可以往回指，这样做很难设 \(dp\) 状态。
我们改为拆绝对值，按照原思路，每点必有两边连接，也就是对于每个 \(i\) 都可能会贡献两次，每次为 \(+i\) 或 \(-i\) 。
这样就好 \(dp\) 了，我们设 \(f_{i,j,u}\) 表示做到第 \(i\) 位，当前贡献为 \(j\) ，且前面有 \(u\) 个能被选，转移时枚举 \(3\) 种情况即可。
注意往前选时可以有不同的选择，记得乘上系数。
时间复杂度 \(O(n^4)\) 。
Code
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
const long long mod=1e9+7;
int n,m,maxn;
long long f[55][55][5005];
int main()
{
scanf("%d%d",&n,&m),maxn=n*n;
f[0][0][maxn]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=n;j++)
for(int u=0;u<=maxn*2;u++)
{
f[i][j][u]=f[i-1][j][u]*(2*j+1)%mod;
if(j>=1&&u+2*i<=maxn*2)f[i][j][u]=(f[i][j][u]+f[i-1][j-1][u+2*i])%mod;
if(j<n&&u-2*i>=0)f[i][j][u]=(f[i][j][u]+f[i-1][j+1][u-2*i]*(j+1)*(j+1)%mod)%mod;
}
printf("%lld",f[n][0][m+maxn]);
return 0;
}
【ARC121E】 Directed Tree
题目描述
给定一棵有根树，根结点为 1，结点 \(i\) 的父亲为 \(p_i\)，边的方向由父亲连向儿子。
定义一个 \(1\sim n\) 的排列 \(a\) 是合法的，当且仅当对于任意 \(i\)，不存在 \(a_i\to i\) 的，经过 至少一条边 的路径。
对合法排列计数，答案对 998244353 取模。\(1\le n\le 2\times 10^3\)。
解题思路
最开始时想到将其 \(dfn\) 序求出来转到序列上来坐，但是由于失去了树的优秀性质十分不好做，不如就做树形 \(dp\) 。
题目要求 \(a_i\) 不能指向 \(i\) 的祖先结点，我们将 \(i\) 与 \(a_i\) 对换，变成 \(a_i\) 不能指向 \(i\) 的子树内的节点。
考虑要将 \(a_i\) 指向子树外的节点其实也不好考虑，但考虑 \(a_i\) 指向子树内的节点很简单，所以我们考虑容斥。
我们考虑钦定有 \(i\) 个节点是指向子树内的，其他节点不用管，那我们可以直接设 \(f_{i,j}\) 为第 \(i\) 个节点的子树内有 \(j\) 个节点是指向自己的子树的，那么转移就是正常的树形背包并在处理完儿子后处理一下自己往子树内连的方案数即可。
做完 \(dp\) 后我们再把他们加起来，由于 \(dp\) 时只考虑那些指向子树内的节点，所以对于 \(f_{root,i}\) ，它的贡献为 \((-1)^i \times (n-i)! \times f_{root,i}\) 。
时间复杂度 \(O(n^2)\) 。
Code
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
const long long mod=998244353;
long long f[2005][2005],s=0,p[2005];
int n,siz[2005];
vector<int> a[2005];
void dfs(int x)
{
siz[x]=1,f[x][0]=1;
for(int i=0;i<a[x].size();i++)
{
dfs(a[x][i]);
for(int j=siz[x];j>=0;j--)
for(int u=siz[a[x][i]];u>=1;u--)f[x][j+u]=(f[x][j+u]+f[x][j]*f[a[x][i]][u])%mod;
siz[x]+=siz[a[x][i]];
}
for(int i=n;i>=1;i--)
{
if(i>=siz[x])f[x][i]=0;
else f[x][i]=(f[x][i]+f[x][i-1]*(siz[x]-1-(i-1))%mod)%mod;
}
return;
}
int main()
{
int x;
scanf("%d",&n),p[0]=1;
for(int i=1;i<=n;i++)p[i]=(p[i-1]*i)%mod;
for(int i=2;i<=n;i++)scanf("%d",&x),a[x].push_back(i);
dfs(1);
for(int i=0;i<=n;i++)
{
if(i&1)s=(s-f[1][i]*p[n-i]%mod)%mod;
else s=(s+f[1][i]*p[n-i]%mod)%mod;
}
printf("%lld",(s+mod)%mod);
return 0;
}
【Luogu P10592】 isn
题目描述
给你一个长度为 \(n\) 的序列 \(a\) ，重复执行以下操作直到序列 \(a\) 非降：删去序列 \(a\) 中的一个数。
问你有多少种操作方案，\(1 \le n \le 2000\) 。
解题思路
由于很难处理刚好删到非降的序列的方案个数，我们考虑容斥。
我们考虑用所以删成非降序列的方案数 \(-\) 不满足题目要求的方案数，总方案数很好求，我们考虑如何求不满足题目要求的方案数。
对于一个操作方案，若它在做完倒数第二步时就已经时非降序列，那么该序列一定不满足题目要求，那我们可以随便找一个删成非降序列的方案，从剩余数中删去一个数，那么删完后的操作方案一定不满足题目要求。
那两个问题便同意了，我们 \(dp\) 求出对于长度 \(i\) 的非降子序列个数 \(f_i\) ，那么答案就为 \(\sum_{i=0}^n (n-i)! \times f_i-\sum_{i=1}^n i\times (n-i)!\times f_i\) 。
时间复杂度 \(O(n^2)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
int n,a[2005];
long long f[2005][2005],d[2005][2005],p[2005],s=0;
set<int> l1;
map<int,int> l2;
int lowbit(int x){return x&(-x);}
void modify(int k,int x,long long y)
{
x++;
while(x<=n+2)d[k][x]=(d[k][x]+y)%mod,x+=lowbit(x);
return;
}
long long query(int k,long long x)
{
long long h=0;x++;
while(x)h=(h+d[k][x])%mod,x-=lowbit(x);
return h;
}
int main()
{
int x=0;
scanf("%d",&n),p[0]=1;
for(int i=1;i<=2003;i++)p[i]=p[i-1]*i%mod;
for(int i=1;i<=n;i++)scanf("%d",&a[i]),l1.insert(a[i]);
for(set<int>::iterator q=l1.begin();q!=l1.end();q++)l2[*q]=++x;
for(int i=1;i<=n;i++)a[i]=l2[a[i]];
f[0][0]=1,modify(0,0,1);
a[n+1]=n;
for(int i=1;i<=n+1;i++)
for(int j=i;j>=1;j--)
{
f[i][j]=query(j-1,a[i]);
modify(j,a[i],f[i][j]);
}
for(int i=1;i<=n+1;i++)s=(s+p[n-(i-1)]*f[n+1][i])%mod;
for(int i=2;i<=n+1;i++)s=(s-(p[n-(i-1)]*f[n+1][i]%mod)*(i-1)%mod)%mod;
printf("%lld",(s+mod)%mod);
return 0;
}
【ABC240Ex】 Sequence of Substrings
题目描述
给定一个长度为 \(n\) 的 \(01\) 串，求最多可以选出多少互不相交的子串，满足这些子串按照原串中的顺序，字典序严格升序，\(1 \le n \le 2.5 \times 10^4\)。
解题思路
我们来想一个 \(n^2logn\) 的做法：将所有子串排个序，按字典序从小到大处理，设 \(f_i\) 表示选择到以 \(i\) 为结尾的子串最多能选择 \(f_i\) 个，处理到子串为 \([l,r]\) ，那么由于已处理的子串字典序都是小于 \([l,r]\) 的，字典序等于的 \([l,r]\) 的子串的 \(r'\) 都大于 \(r\) ，那么我们直接从 \([1,l-1]\) 直接选一个 \(f_i\) 转移就可以了，这个 \(dp\) 可以用树状数组优化。
注意到这个做法超时原因在于子串太多，我们来观察题目考虑省去不必要的子串。
我们可以通过让每个选择的子串长度最小的调整使得第一个选择的子串长度一定为 \(1\) ，第 \(i+1\) 个选择的子串长度最多只比第 \(i\) 个选择的子串的长度大 \(1\) ，所以设答案为 \(ans\) ，选择的子串长度之和最大为 \(\frac{ans(ans+1)}{2} <n\) ，所以 \(ans\le 2 \sqrt{n}\) ，最大子串长度 \(< \sqrt{n}\) 。
这样我们只用处理 \(n\sqrt{n}\) 个子串，时间复杂度 \(O(n\sqrt{n}logn)\) 。
注意排序不能直接排字符串，要把所以字符串丢到字典树上处理。
Code
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
struct datay
{
int l,r,v;
}b[8000005];
int n,maxx,num,num1,num2,to[8000005][2],f[250005],d[8000005];
string a;
vector<datay> t[8000005];
int lowbit(int x){return x&(-x);}
void modify(int x,int v)
{
while(x<=8000000)d[x]=max(d[x],v),x+=lowbit(x);
return;
}
int query(int x)
{
int h=0;
while(x)h=max(h,d[x]),x-=lowbit(x);
return h;
}
void dfs(int x)
{
if(x==0)return;
num2++;
for(int i=0;i<t[x].size();i++)b[++num1]=t[x][i],b[num1].v=num2;
dfs(to[x][0]),dfs(to[x][1]);
return;
}
bool cmp1(datay q,datay w)
{
if(q.v^w.v)return q.v<w.v;
return q.r>w.r;
}
int main()
{
int x;datay q;
scanf("%d",&n),num=1,maxx=sqrt(4*n);cin>>a;
for(int i=0;i<a.size();i++)
{
x=1;
for(int j=i;j<=i+maxx-1&&j<a.size();j++)
{
if(!to[x][a[j]-'0'])to[x][a[j]-'0']=++num;
x=to[x][a[j]-'0'];
q.l=i+1,q.r=j+1,t[x].push_back(q);
}
}
dfs(1);
sort(b+1,b+num1+1,cmp1);
for(int i=1;i<=num1;i++)
{
f[i]=query(b[i].l-1)+1;
modify(b[i].r,f[i]);
}
printf("%d",query(n));
return 0;
}
【Luogu P6383】Resurrection
题目描述
有一棵包含 \(n\) 个节点的树 \(T\)，它的所有边依次编号为 \(1\) 至 \(n-1\)。
保证对于 \(T\) 中任意一个节点 \(u\) ，从 \(u\) 到 \(n\) 号节点的简单路径都不经过任何编号小于 \(u\) 的节点。
按照如下步骤生成一张包含 \(n\) 个节点的无向图 \(G\)：
选取一个 \(1 \sim n-1\) 的排列 \(p\)，然后依次进行 \(n-1\) 次操作。在进行第 \(i\) 次操作时，首先删除树 \(T\) 中编号为 \(p_i\) 的边 \((a,b)\)，然后，记 \(u\) 和 \(v\) 分别为当前树 \(T\) 中与 \(a,b\) 联通的所有点中，编号最大的点，并在图 \(G\) 的 \(u\) 号点和 \(v\) 号点之间连一条边。
求对于给定的树 \(T\)，按上述方式一共可以生成多少种本质不同的图 \(G\)。图 \(G_1\) 和 \(G_2\) 本质不同当且仅当存在 \(u\) 和 \(v\) 满足在 \(G_1\) 中不存在边 \((u,v)\)，而 \(G_2\) 中存在。
因为答案可能很大，你只需要求出答案对 \(998244353\) 取模的值，\(1 \le n \le 3 \times 10^3\)。
解题思路
注意到生成的图 \(G\) 一定为一棵树，我们来考虑这棵树该如何连边。
手玩样例后发现新图 \(G\) 中节点 \(i\) 的父亲一定为原图中节点 \(i\) 的祖先，并且对于一个 \(i\) 的祖先 \(j\) ，\(i\) 在新图的父亲 \(i'\) 的原图深度一定大于 \(j\) 在新图的父亲 \(j'\) （即连边不能交叉）。
我们可以根据这条性质开始树形 \(dp\)，但是正常的树形 \(dp\) 是从儿子子树中统计信息考虑儿子对本节点的影响的，但由于这题祖先新图连边的情况会影响自己，我们考虑父亲对儿子节点的影响。
注意到我们只需要知道祖先中有多少个节点可被连边即可，我们可以设 \(f_{i,j}\) 表示第 \(i\) 个节点它的祖先中有 \(j\) 个节点可被连，那么转移时我们只需要枚举当前节点往深度为 \(x\) 的祖先连边，那么儿子只剩下 \(x+1\) 个祖先可连，即 \(f_{i,j}=\sum_{x=1}^j \prod_{v \in son_i} f_{v,x+1}\)。
很明显可以用前缀和优化到 \(O(n^2)\) 。
还有一种做法，我们可以设 \(f_{i,j}\) 表示做到第 \(i\) 个节点，有 \(j\) 个点连边连向 \(i\) 的方案数，由于可以调换操作顺序，也是做一个类似树形背包的 \(dp\) 就可以了。
Code
#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
int n,deep[3005];
long long f[3005][3005],s=1;
vector<int> a[3005];
void dfs(int x)
{
for(int i=0;i<a[x].size();i++)deep[a[x][i]]=deep[x]+1,dfs(a[x][i]);
for(int i=1;i<=deep[x]+1;i++)
{
f[x][i]=1;
for(int j=0;j<a[x].size();j++)
f[x][i]=(f[x][i]*f[a[x][j]][i+1])%mod;
if(i!=0)f[x][i]=(f[x][i]+f[x][i-1])%mod;
}
return;
}
int main()
{
int x,y;
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
if(x<y)swap(x,y);
a[x].push_back(y);
}
deep[n]=1,dfs(n);
for(int i=0;i<a[n].size();i++)s=(s*f[a[n][i]][1])%mod;
printf("%lld",s);
return 0;
}
【Luogu P7888】 Distinct Subsequences
题目描述
给定一个由小写字符构成的字符串 \(S\)。
令一个字符串的价值为该串的本质不同非空子序列个数，其中子序列可以为整体。
求 \(S\) 所有子序列的价值和。答案对 \(10^9+7\) 取模，\(1\le |S|\le 10^6\)。
解题思路
我们先来考虑如何求出某序列的所有不同子序列。
我们设该序列为 \(a\) ，那么对于 \(a_i\) ，若存在 \(j>i,a_i=a_j\) ，那么以 \(a_i\) 为结尾的子序列的集合是在以 \(a_j\) 为结尾的子序列的集合中的，那我们统计本质不同的子序列只需要考虑对于每一个字符在 \(a\) 中最后一个出现的位置即可。
考虑 \(S\) 所有子序列的价值和，我们考虑 \(S\) 的每一位作为某一个子序列的结尾能产生多少贡献，我们考虑它作为子序列的子序列的前一位是什么，设当前处理到的位置为 \(i\) ，从第 \(j\) 位转移过来，思考转移系数，只有 \([j+1,i-1]\) 内的位置是我们可以决定是否作为子序列，但由于前面的性质，\([j+1,i-1]\) 内的作为子序列的位不能等于 \(a_j\) ，那么有状态转移方程 \(f_i=\sum_{j=1}^{i-1} f_j \times 2^{cnt_{i-1,a_i}-cnt_{j,a_i}}\) ，其中 \(cnt_{i,j}\) 表示区间 \([1,i]\) 不等于 \(a_j\) 的有多少个，答案为 \(\sum_{i=1}^n f_i \times 2^{n-i}\)。
考虑优化，方程可以优化为 \(f_i=2^{cnt_{i-1,a_i}} \times \sum_{j=1}^{i-1} f_j \times 2^{-cnt_{j,a_i}}\) ，这个东西明显可以用前缀和优化，直接优化到 \(O(VN)\) ，其中 \(V\) 为字符集大小。
Code
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
string a;
long long f[1000005],d[26],s,cnt[26][1000005],p2[1000005],inv2[1000005],q;
long long poww(long long x,long long y)
{
if(abs(y)<=1000000)
{
if(y<0)return inv2[-y];
return p2[y];
}
long long h=1;
while(y)
{
if(y&1)h=(h*x)%mod;
x=(x*x)%mod,y>>=1;
}
return h;
}
int main()
{
cin>>a,cnt[a[0]-'a'][0]=p2[0]=inv2[0]=1,q=poww(2,mod-2);
for(int i=1;i<=1000000;i++)p2[i]=p2[i-1]*2%mod,inv2[i]=inv2[i-1]*q%mod;
for(int i=1;i<a.size();i++)
{
cnt[a[i]-'a'][i]=1;
for(int j=0;j<26;j++)cnt[j][i]+=cnt[j][i-1];
}
for(int i=0;i<a.size();i++)
{
f[i]=poww(2,i-cnt[a[i]-'a'][i]+1);
f[i]=(f[i]+d[a[i]-'a']*poww(2,i-cnt[a[i]-'a'][i])%mod)%mod;
for(int j=0;j<26;j++)
d[j]=(d[j]+f[i]*poww(2,cnt[j][i]-i)%mod)%mod;
}
for(int i=a.size()-1;i>=0;i--)s=(s+poww(2,a.size()-1-i)*f[i]%mod)%mod;
printf("%lld",s);
return 0;
}
【AGC030F】 Permutation and Minimum
题目描述
有一个 \(2 N\) 个数的序列 \(A\)，从 \(1\) 到 \(2 N\) 标号。你要把 \(1 \sim 2 N\) 这些数填进去，使它形成一个排列。
但是已经有一些位置强制填了特定的数了，输入时会给出。
最后令长度为 \(N\) 的序列 \(B\) 为：令 \(B_i = \min\{A_{2 i - 1}, A_{2 i}\}\)。
询问所有方案中能得到的不同的 \(B\) 的数量。
- \(1 \le N \le 300\)。
解题思路
我们先考虑全是 \(-1\) 的情况，我们从小到大遍历 \(1\) 到 \(2N\) ，可以做一个很简单的 \(dp\) ：\(f_{i,j}\) 表示做到第 \(i\) 位，前面有 \(j\) 个还未被配对，状态转移方程十分简单，先不用考虑在排列中的相对顺序，最后乘上 \(N!\) 即可。
但是注意到 \(\{1,3\},\{2,4\}\) 与 \(\{1,4\},\{2,3\}\) 会被计算两次，因为我们计算贡献时是后面一个来计算导致前面可能重复，所以我们要从 \(2N\) 遍历到 \(1\) ，以前面一位来计数。
考虑已确定的位置，对于 \(A_{2i-1},A_{2i}\) 都不为 \(-1\) 的对最终答案不会产生任何影响，若 \(A_{2i-1},A_{2i}\) 中只有 \(1\) 位不为 \(-1\) ，那么对于和它配对的那个数它的位置是已经固定的，这会影响状态转移时的转移系数。
所以我们需要分开记录为 \(-1\) 的位和已确定的位，设 \(f_{i,j,k}\) 表示从 \(2N\) 开始处理处理到第 \(i\) 位，其中 \(j\) 个 \(-1\) ，\(u\) 个非 \(-1\) 的还未配对，状态转移时由于我们已经把所有的 \(A_{2i-1} ,A_{2i}\) 都不为 \(-1\) 的位给踢了出去，所以注意不能用一个非 \(-1\) 的去配对一个非 \(-1\) 的，其他随便转移即可，注意由一个非 \(-1\) 转移到另一个 \(-1\) 由于可以任选一位放置，转移要乘系数 \(u\) ，同时最后乘上 \(N!\) 时 \(N\) 是不包含非 \(-1\) 的位的。
时间复杂度 \(O(n^3)\) 。
Code
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
const int mod=1e9+7;
int n,a[605],f[2][605][605],pre[605];
bool v[605];
void add(int &q,int w){q=(q+w>=mod?q+w-mod:q+w);return;}
int main()
{
long long x,y;
scanf("%d",&n),n<<=1;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]!=-1){v[a[i]]=1;pre[a[i]]=i;}
}
f[(n&1)^1][0][0]=1;
for(int i=n;i>=1;i--)
{
x=i&1,y=(x^1);
for(int j=0;j<=n/2;j++)
for(int u=0;u<=n/2;u++)
{
if(v[i]&&a[((pre[i]-1)^1)+1]!=-1){f[x][j][u]=f[y][j][u];continue;}
f[x][j][u]=0;
if(v[i])
{
add(f[x][j][u],f[y][j+1][u]);
if(u>=1)add(f[x][j][u],f[y][j][u-1]);
}
else
{
add(f[x][j][u],int(((long long)(u+1))*f[y][j][u+1]%mod)),add(f[x][j][u],f[y][j+1][u]);
if(j>=1)add(f[x][j][u],f[y][j-1][u]);
}
}
}
x=1;
for(int i=1;i<=n;i+=2)
if(a[i]==-1&&a[i+1]==-1)f[1][0][0]=(x*f[1][0][0]%mod),x++;
printf("%d",f[1][0][0]);
return 0;
}
【AGC004E】 Salvage Robots
题目描述
有一个棋盘，上面要么是空的，要么有一个机器人，要么是一个出口（整个地图只有一个出口）。每次可以命令所有机器人向上下左右中的某个方向移动一格，如果它超出了棋盘的边界就会消失。如果它到了出口的位置就会被你救下（并且从棋盘上消失）。求你能够救下的机器人的最大值，\(H,W \le 100\) 。
解题思路
先转化一下题意，改成只有出口动，机器人不动，如果出口距离机器人的横或纵坐标超出了某个值，该机器人就死了，否则该机器人移动到了出口答案就 \(+1\)。
做 \(dp\) ，设 \(f_{i,j,u,k}\) 为出口到四边最远能到的距离分别为 \(i,j,u,k\) ，转态转移方程有 \(4\) 条，分别往 \(4\) 个方向走，每次转移时只需判断走向另一端时自己这一端有没有出界即可。
关于每次转移增加的值，为一段区间内的机器人个数，用前缀和处理即可，同时需要注意上下或左右的最远边界的到达会影响该区间的左右界，不能直接用 \([i,j]\) 或 \([u,k]\)。
时间复杂度 \(O(n^4)\) 。
Code
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
short f[105][105][105][105],s=0;
int n,m,stx,sty,a[205][205];
string x;
inline int query(int q,int w,int e,int r)
{
if(q<=0||w<=0||e<=0||r<=0||q>n||w>m||e>n||r>m)return 0;
return a[e][r]+a[q-1][w-1]-a[q-1][r]-a[e][w-1];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
cin>>x,x=' '+x;
for(int j=1;j<=m;j++)
{
if(x[j]=='E')stx=i,sty=j;
a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+(x[j]=='o');
}
}
for(int i=0;i<=stx;i++)
for(int j=0;j<=n-stx;j++)
for(int u=0;u<=sty;u++)
for(int k=0;k<=m-sty;k++)f[i][j][u][k]=-10000;
f[0][0][0][0]=0;
for(int i=0;i<=stx-1;i++)
for(int j=0;j<=n-stx;j++)
for(int u=0;u<=sty-1;u++)
for(int k=0;k<=m-sty;k++)
{
if(f[i][j][u][k]<0)continue;
s=max(s,f[i][j][u][k]);
if(i+j+1<=stx-1)f[i+1][j][u][k]=max(f[i+1][j][u][k],short(f[i][j][u][k]+query(stx-i-1,max(sty-u,k+1),stx-i-1,min(m-u,sty+k))));
if(i+j+1<=n-stx)f[i][j+1][u][k]=max(f[i][j+1][u][k],short(f[i][j][u][k]+query(stx+j+1,max(sty-u,k+1),stx+j+1,min(m-u,sty+k))));
if(u+k+1<=sty-1)f[i][j][u+1][k]=max(f[i][j][u+1][k],short(f[i][j][u][k]+query(max(stx-i,j+1),sty-u-1,min(stx+j,n-i),sty-u-1)));
if(u+k+1<=m-sty)f[i][j][u][k+1]=max(f[i][j][u][k+1],short(f[i][j][u][k]+query(max(stx-i,j+1),sty+k+1,min(stx+j,n-i),sty+k+1)));
}
cout<<s;
return 0;
}
【CF398B】 Painting The Wall
题目描述
有一个 \(n \times n\) 的网格，其中 \(m\) 个格子上涂了色。每次随机选择一个格子（有可能是涂过色的格子）涂色，求让网格每一行每一列都至少有一个格子涂了色的操作次数期望，\(1 \le n \le 2000\) 。
解题思路
如果随机选择选择不到涂过色的格子，那么这题很难，但是可选择到，所以 \(dp\) 会简单很多。
期望 \(dp\) 一般都是要倒推的，这道题不倒推不好做，我们考虑倒着来做 \(dp\) 。
我们设 \(f_{i,j}\) 表示还有 \(i\) 行 \(j\) 列未被染色，初始化可以很快计算出 \(f_{i,0}/f_{0,i}\) ，转移从四个方向转移来，方程式很好写，为 \(f_{i,j}=\frac{ij \times f_{i-1,j-1}+i(n-j) \times f_{i-1,j}+(n-i)j \times f_{i,j-1}}{n^2-(n-i)(n-j)}\) 。
时间复杂度 \(O(n^2)\) 。
Code
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
int n,m,v1[2005],v2[2005];
double f[2005][2005];
int main()
{
int x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
v1[x]=1,v2[y]=1;
}
x=y=0;
for(int i=1;i<=n;i++)x+=v1[i],y+=v2[i];
x=n-x,y=n-y;
for(int i=1;i<=x;i++)f[i][0]=f[i-1][0]+double(n)/double(i);
for(int i=1;i<=y;i++)f[0][i]=f[0][i-1]+double(n)/double(i);
for(int i=1;i<=x;i++)
for(int j=1;j<=y;j++)
{
f[i][j]=(n*n+f[i-1][j-1]*i*j+f[i-1][j]*i*(n-j)+f[i][j-1]*(n-i)*j);
f[i][j]/=double(n*n-(n-i)*(n-j));
}
printf("%.9lf",f[x][y]);
return 0;
}
【ARC121F】 Logical Operations on Tree
题目描述
给定一棵树，给每个点填 \(0\) 或 \(1\)，给每条边填 \(\text{AND}\) 或 \(\text{OR}\)，在所有 \(2^{n+n-1}\) 种填法中，计数有多少种满足存在一种缩边的顺序，使得每次把一条边的两个端点缩成一个点，权为原端点与边的运算值，最终点的权为 \(1\)，\(1 \le n \le 10^5\)。
解题思路
我们先来思考对于每个方案应该怎样合并，很明显，先把所有 \(AND\) 边给合并了再合并 \(OR\) 边是最优的。
我们可以把 \(AND\) 边先连在一起看成一个连通块，连通块权值即为内部所有点是否全为 \(1\) ，只要有一个连通块的权值为 \(1\) ，那么这种方案就是有贡献的。
但是统计至少有一个连通块权值为 \(1\) 的状态转移不好推，我们改成所有方案 \(-\) 所有连通块权值都为 \(0\) 的方案数。
前面的预处理即可，后面的我们做一个简单的树形 \(dp\) 即可解决。
时间复杂度 \(O(n)\) 。
Code
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
const long long mod=998244353;
int n,siz[100005];
long long f[100005][3],p[200005];
vector<int> a[100005];
void dfs(int x,int y)
{
siz[x]=1;
f[x][0]=f[x][2]=1;
for(int i=0;i<a[x].size();i++)
{
if(a[x][i]==y)continue;
dfs(a[x][i],x);
f[x][0]=f[x][0]*((f[a[x][i]][0]*2+f[a[x][i]][1]*2+f[a[x][i]][2])%mod)%mod;
f[x][1]=(f[x][1]*((f[a[x][i]][0]*2+f[a[x][i]][1]*2+f[a[x][i]][2])%mod)%mod+f[x][2]*(f[a[x][i]][0]+f[a[x][i]][1])%mod)%mod;
f[x][2]=f[x][2]*((f[a[x][i]][0]+f[a[x][i]][1]+f[a[x][i]][2])%mod)%mod;
siz[x]+=siz[a[x][i]];
}
return;
}
int main()
{
int x,y;
scanf("%d",&n),p[0]=1;
for(int i=1;i<=200000;i++)p[i]=p[i-1]*2%mod;
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
a[x].push_back(y),a[y].push_back(x);
}
dfs(1,0);
printf("%lld",(p[2*n-1]-f[1][0]-f[1][1]+3*mod)%mod);
return 0;
}
【Luogu P2151】 HH去散步
题目描述
HH 有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间内，走过一定的距离。但是同时 HH 又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。又因为 HH 是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多少种散步的方法。
现在给你学校的地图（假设每条路的长度都是一样的都是 \(1\)），问长度为 \(t\)，从给定地点 \(A\) 走到给定地点 \(B\) 共有多少条符合条件的路径，\(1 \le n \le 50,1 \le m \le 60,1 \le t \le 2^{30}\) 。
解题思路
观察数据范围，由于 \(t \le 2^{30}\) 且 \(n,m\) 都极小，很容易想到矩阵加速 \(dp\) 。
先不考虑不能折返的限制，我们只需把连边情况转化成矩阵在做矩阵快速幂即可。
由于不能折返，我们也许还需额外记录边的信息，但是这样绝对会爆。
我们已经记录了边的信息同时记录走的方向，那我们已经知道到了那个节点，那我们就可以不用记录节点信息了，直接预处理出每条边可以到那些边就可以了。
时间复杂度 \(O(m^3logk)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
const long long mod=45989;
struct datay
{
int x,y;
}a[105];
int n,m,k,st,en;
long long b[125][125],h[125][125],d[125][125],s;
int main()
{
int x,y;
scanf("%d%d%d%d%d",&n,&m,&k,&st,&en);
for(int i=1;i<=m;i++)scanf("%d%d",&a[i].x,&a[i].y);
k--;
for(int i=1;i<=m;i++)
{
if(a[i].x==st)d[0][2*i-2]=1;
if(a[i].y==st)d[0][2*i-1]=1;
}
for(int i=1;i<=2*m;i++)
{
x=(i-1)/2+1;
if(!(i&1))swap(a[x].x,a[x].y);
for(int j=1;j<=2*m;j++)
{
if(i==j)continue;
y=(j-1)/2+1;
if(!(j&1))swap(a[y].x,a[y].y);
if(a[x].y==a[y].x)b[i-1][j-1]=1;
if(!(j&1))swap(a[y].x,a[y].y);
}
if(!(i&1))swap(a[x].x,a[x].y);
}
while(k)
{
if(k&1)
{
for(int i=0;i<2*m;i++)
for(int j=0;j<2*m;j++)
{
h[i][j]=0;
for(int u=0;u<2*m;u++)h[i][j]=(h[i][j]+d[i][u]*b[u][j]%mod)%mod;
}
for(int i=0;i<2*m;i++)
for(int j=0;j<2*m;j++)
d[i][j]=h[i][j];
}
k>>=1;
for(int i=0;i<2*m;i++)
for(int j=0;j<2*m;j++)
{
h[i][j]=0;
for(int u=0;u<2*m;u++)h[i][j]=(h[i][j]+b[i][u]*b[u][j]%mod)%mod;
}
for(int i=0;i<2*m;i++)
for(int j=0;j<2*m;j++)
b[i][j]=h[i][j];
}
for(int i=1;i<=2*m;i++)
{
if(!(i&1))swap(a[(i-1)/2+1].x,a[(i-1)/2+1].y);
if(a[(i-1)/2+1].y==en)s=(s+d[0][i-1])%mod;
}
printf("%lld",s);
return 0;
}
【ARC100E】 Or Plus Max
题目描述
给你一个长度为 \(2^n\) 的序列 \(a\)，每个\(1\le K\le 2^n-1\)，找出最大的 \(a_i+a_j\)（\(i \mathbin{\mathrm{or}} j \le K\)，\(0 \le i < j < 2^n\)）并输出。
\(\mathbin{\mathrm{or}}\) 表示按位或运算，\(1 \le n \le 18\)。
解题思路
直接考虑 \(i \mathbin{\mathrm{or}} j \le k\) 会出现 $ i \mathbin{\mathrm{or}} j \notin k$ 的情况不好做，我们考虑求 \(i \mathbin{\mathrm{or}} j =k\) 的在通过前缀和求出答案。
即使这样还是不好做，我们观察到若 \(i \in k,j \in k\) 有 \(i \mathbin{\mathrm{or}} j \le k\) ，那我们可以改成求 \(i \in k,j \in k\) 的 \(a_i+a_j\) 最大值，这样答案一定会贡献到 \(i\mathbin{\mathrm{or}}j\) 。
这个问题就很好做了，若只有 \(i \in k\)，那就是高维前缀和搞完，现在又 \(i \in k,j \in k\) ，那我们分别记录 \(a_i\) 的最大值与 \(a_i+a_j\) 的最大值，继续用高维前缀和即可。
时间复杂度 \(O(2^nn)\) 。
Code
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
int n,a[300005],p,f[300005][2],s;
int main()
{
scanf("%d",&n),p=(1<<n);
for(int i=0;i<p;i++)scanf("%d",&a[i]),f[i][0]=a[i];
for(int i=0;i<n;i++)
for(int j=0;j<p;j++)
if(j&(1<<i))
{
f[j][1]=max(f[j][1],f[j][0]+f[j^(1<<i)][0]);
f[j][0]=max(f[j][0],f[j^(1<<i)][0]);
f[j][1]=max(f[j][1],f[j^(1<<i)][1]);
}
for(int i=1;i<p;i++)s=max(s,f[i][1]),printf("%d\n",s);
return 0;
}
【ARC187C】 1 Loop Bubble Sort
题目描述
对于 \((1, \ldots, N)\) 的排列 \(P=(P_1,...,P_N)\) ，令 \(P'=(P_1',...,P_N')\) 是进行一次以下操作后得到的排列。
- 对于按此顺序排列的 \(i = 1, 2, \ldots, N-1\) ，如果是 \(P_i>P_{i+1}\) ，则交换 \(P_i\) 和 \(P_{i+1}\) 。
给你一个长度为 \(N\) 的序列 \(Q = (Q_1,..., Q_N)\) 。每个 \(Q_i\) 都是 \(-1\) 或一个介于 \(1\) 和 \(N\) 之间的整数。
求在每个 \(i\) 中，如果 \(Q_i \neq -1\) 则 \(Q_i = P'_i\) 的排列 \(P\) 数。
解题思路
题目要求我们做的操作等价于做一次冒泡排序，注意到对于一个数 \(P_i\) ，只有 \(P_{i-1}\) 与 \(P_{i+1}\) 会影响它的位置，同时还有一条性质：对于一个前缀 \([1,i]\) ，若只做完了这段的操作，那么 \(P_i\) 一定是前缀最大值。
那我们就变 \(dp\) 边交换，由于要考虑 \(P_{i+1}\) 对 \(P_i\) 的影响，设 \(dp\) 数组为 \(f_{i,j}\) 表示目前做到第 \(i\) 位且前缀最大值即 \(P_i\) 为 \(j\) ，我们转移时即考虑 \(P_{i+1}\) 能是什么，是否会与 \(P_i\) 交换等。
显然分类讨论，当 \(Q_{i}=-1\) 时，由于 \(P_{i-1}\) 为前 \(i-1\) 个数的最大值，那么 \(P_i>P_{i-1}\) 的方案数即为 \(n-j\) ，转移即为 \(f_{i,j}=\sum_{k=1}^{j-1} f_{i-1,k}\) ，直接做是 \(O(n^3)\) 的，要前缀和优化，当 \(P_i< P_{i-1}\) 时，很明显是由 \(f_{i-1,j}\) 转移到 \(f_{i,j}\) ，我们需要考虑能把多少数可以放交换前的 \(P_i\) 上，设 \(cnt1_i\) 表示前 \(i\) 位的 \(-1\) 个数，\(cnt2_i\) 表示 \(\le i\) 有 \(cnt2_i\) 个 \(-1\) 位，那么可以放 \(cnt2_j-cnt1_{i-1}\) 个数。
再来考虑 \(Q_i \neq -1\) 的情况，当 \(P_{i-1}< P_i\) 时，由于 \(P_{i}=Q_i\) ，那么即 \(f_{i,Q_i}=\sum_{j=1}^{Q_i-1} f_{i-1,j-1}\) ，当 \(P_{i-1}>P_i\) 时，还是从 \(f_{i-1,j}\) 转移到 \(f_{i,j}\) ，只是注意 \(j>Q_i\) 。
时间复杂度 \(O(n^2)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
int n,a[5005],q,v1[5005],v2[5005];
long long f[2][5005],s=0;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]>0)v1[a[i]]=1,v2[i]=1;
}
for(int i=1;i<=n;i++)v1[i]=v1[i-1]+(v1[i]^1),v2[i]=(v2[i]^1)+v2[i-1];
for(int i=1;i<=n;i++)f[1][i]=1;
for(int i=2;i<=n;i++)
{
q=(i&1);
if(a[i-1]==-1)
{
s=0;
for(int j=1;j<=n;j++)
{
f[q][j]=s;
if(v1[j-1]>=v2[i-1])f[q][j]=(f[q][j]+f[q^1][j]*(v1[j-1]-v2[i-2])%mod)%mod;
if(v1[j]-v1[j-1])s=(s+f[q^1][j])%mod;
}
}
else
{
for(int j=1;j<=n;j++)f[q][j]=0;
for(int j=a[i-1]+1;j<=n;j++)f[q][j]=(f[q][j]+f[q^1][j]+f[q^1][a[i-1]])%mod;
}
}
printf("%lld",f[n&1][n]);
return 0;
}
【AGC022E】 Median Replace
题目描述
有个长度为 \(N\)（\(N\) 为奇数）的 \(\texttt{01}\) 串 \(s\)，其中有若干位置是 \(\texttt{?}\)。
一次操作可将 \(3\) 个连续的字符替换成这三个数的中位数。
求有多少将 \(\texttt ?\) 替换成 \(\texttt0\) 或 \(\texttt1\) 的方案使得进行 \(\frac{N-1}{2}\) 次操作后的字符串可以是 \(\texttt1\)，其中 \(1 \le N \le 3 \times 10^5\)。
解题思路
我们从前往后消除，思考最优的消除策略。
当出现 \(000\) 的结构时我们可以直接删成 \(0\)，出现 \(11\) 的结构时我们已经做完了，只需把后面全部消完之后再用 \(11x\) 来消成 \(1\) 。
考虑出现 \(01/10\) 这样的结构时的策略，由于 \(01x/10x\) 的值取决于 \(x\) ，所以 \(01/10\) 是能删就删的，但由于 \(01\) 留下来没有收益，但是 \(10\) 留下来可能凑成 \(1000\) 消成 \(10\) 白消掉了两个 \(0\) ，所以 \(10\) 是需要保留的。
根据这些限制，我们可以做一个线性 \(dp\) ，记录做到第 \(i\) 位，分别保留了空\(,0,00,1,10,100,11\) 这些情况的方案数，转移枚举下一位 \(0/1\) 来看转移到那些状态，最后只有 \(1,11\) 两种情况贡献到答案里。
时间复杂度 \(O(n)\) 。
Code
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
const long long mod=1e9+7;
string a;
long long f[300005][8];
int main()
{
cin>>a,a=' '+a,f[0][0]=1;
for(int i=1;i<a.size();i++)
{
if(a[i]=='0'||a[i]=='?')
{
f[i][1]=(f[i][1]+f[i-1][0]+f[i-1][2])%mod;
f[i][2]=(f[i][2]+f[i-1][1])%mod;
f[i][4]=(f[i][4]+f[i-1][3]+f[i-1][5])%mod;
f[i][5]=(f[i][5]+f[i-1][4])%mod;
f[i][6]=(f[i][6]+f[i-1][6])%mod;
}
if(a[i]=='1'||a[i]=='?')
{
f[i][3]=(f[i][3]+f[i-1][0]+f[i-1][4])%mod;
f[i][0]=(f[i][0]+f[i-1][1])%mod;
f[i][1]=(f[i][1]+f[i-1][2])%mod;
f[i][6]=(f[i][6]+f[i-1][3]+f[i-1][6])%mod;
f[i][4]=(f[i][4]+f[i-1][5])%mod;
}
}
printf("%lld",(f[a.size()-1][3]+f[a.size()-1][6])%mod);
return 0;
}
【ARC186E】 Missing Subsequence
题目描述
给定正整数 \(n, m, k\) 以及一个值域为 \([1, k]\) 的整数序列 \(b_{1 \sim m}\)，请你求出满足以下条件的值域为 \([1, k]\) 的整数序列 \(a_{1 \sim n}\) 的个数：
- 除了序列 \(b\) 以外的其它所有长度为 \(m\)，值域为 \([1, k]\) 的整数序列都是 \(a\) 的（不一定连续的）子序列。
\(1 \le n,m,k \le 400\) 。
解题思路
先考虑如何求出包含所有长度 \(m\) 的子序列的数列个数，我们可以把每个数列划分前缀，每段里面包含 \([1,k]\) 里面的所有数，那么该数列必定包含所有长度为 \(m\) 的子序列，该条件为充要条件。
考虑题目要求，由于 \(b_1\) 后面不能有 \(b_2,...,b_m\) 的子序列，那我们也可以像上面一样转化成划分成子问题，每段表示当段最后一位为 \(b_i\) ，且后面的数列不含 \(b_{i+1},...,b_n\) 的子序列。
思考其它还需满足的条件，发现对于 $x \in[1,k] $ 且 \(x \neq b_i\) ，其后面一定要有 \(b_{i+1},...,b_n\) 的子序列，但同时 \(b_i\) 后面没有，若 \(b_{i+1}=b_i\) ，那么不需要额外处理，只需保证 \(b_i\) 在最后即可，若 \(b_{i+1} \neq b_i\) ，每段倒数第二个出现的数到最后出现的数即 \(b_i\) 之间必出现一次 \(b_{i+1}\) 来保证有 \(b_{i+1},...,b_n\) 的子序列。
那么就可以用 \(dp\) 解决了，设 \(f_{i,j}\) 表示做了 \(i\) 个数同时划分了 \(j\) 段的方案数，那只需枚举上次做到哪并乘上系数就好了。
系数如何求？预处理系数，我们再做一次 \(dp\) ，求出 \(i\) 个数中出现了 \(j\) 的方案数，对于 \(b_{i+1} \neq b_i\) 转移的系数，我们只需枚举最后一个数在哪出现，保证到结尾出现一次 \(b_{i+1}\) 即可。
时间复杂度 \(O(n^3)\) 。
Code
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
const long long mod=998244353;
int n,m,k,t[405];
long long f[405][405],d[405][2],f1[405][405],s;
long long poww(long long x,long long y)
{
long long h=1;
while(y)
{
if(y&1)h=(h*x)%mod;
x=(x*x)%mod,y>>=1;
}
return h;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++)scanf("%d",&t[i]);
f1[0][0]=f[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
f1[i][j]=(f1[i-1][j-1]*j%mod+f1[i-1][j]*j%mod)%mod;
for(int i=k;i<=n;i++)
{
d[i][1]=f1[i-1][k-1];
for(int j=k-1;j<i;j++)d[i+1][0]=(d[i+1][0]+(f1[j-1][k-2]*(k-1)%mod)*(poww(k-1,i-j)-poww(k-2,i-j))%mod+mod)%mod;
}
for(int i=1;i<=n;i++)
for(int j=1;j<m;j++)
for(int u=1;u<=i;u++)
f[i][j]=(f[i][j]+f[u-1][j-1]*d[i-u+1][t[j]==t[j+1]]%mod)%mod;
for(int i=1;i<=n-k+2;i++)s=(f[i-1][m-1]*f1[n-i+1][k-1]%mod+s)%mod;
cout<<s;
return 0;
}
【Luogu P6189】 跑步
题目描述
给出一个数 \(n\) ，求把这个数划分成若干部分的不重集数，\(n \le 10^5\) 。
解题思路
模拟赛时 \(O(n^2)\) 过了，赛后再来补正解。
\(O(n^2)\) 的做法是一个很好想的完全背包，观察数据范围，我们考虑把它优化到 \(O(n\sqrt{n})\) 。
使用根号分治，对于 \(\le \sqrt{n}\) 的数我们直接做完全背包即可，对于 \(> \sqrt{n}\) 的数我们可以换一种 \(dp\) 方式，每次加进集合中一个 \(= \sqrt{n}\) 的数，这样集合中最多只有 \(\sqrt{n}\) 个数，同时我们每次还可以全部数 \(+1\) ，容易发现，所有都有唯一一种映射方式。
那我们只需把这两种 \(dp\) 出来的结果拼在一起就好了，时间复杂度 \(O(n\sqrt{n})\) 。
Code
#include<bits/stdc++.h>
using namespace std;
int n,mod,block,f[100005],dp[351][100005],d[100005],s;
int main()
{
scanf("%d%d",&n,&mod),block=sqrt(n),f[0]=dp[0][0]=1;
for(int i=1;i<block;i++)
for(int j=i;j<=n;j++)f[j]=(f[j]+f[j-i])%mod;
for(int i=0;i<=block+1;i++)
for(int j=0;j<=n;j++)
{
d[j]=(d[j]+dp[i][j])%mod;
if(j+i<=n&&i!=0)dp[i][j+i]=(dp[i][j+i]+dp[i][j])%mod;
if(j+block<=n)dp[i+1][j+block]=(dp[i+1][j+block]+dp[i][j])%mod;
}
for(int i=0;i<=n;i++)s=(s+(long long)(f[i])*d[n-i]%mod)%mod;
cout<<s;
return 0;
}
【Luogu P7962】 方差
题目描述
给定长度为 \(n\) 的非严格递增正整数数列 \(1 \le a_1 \le a_2 \le \cdots \le a_n\)。每次可以进行的操作是：任意选择一个正整数 \(1 < i < n\)，将 \(a_i\) 变为 \(a_{i - 1} + a_{i + 1} - a_i\)。求在若干次操作之后，该数列的方差最小值是多少。请输出最小值乘以 \(n^2\) 的结果。
其中方差的定义为：数列中每个数与平均值的差的平方的平均值。更形式化地说，方差的定义为 \(D = \frac{1}{n} \sum_{i = 1}^{n} {(a_i - \bar a)}^2\)，其中 \(\bar a = \frac{1}{n} \sum_{i = 1}^{n} a_i\)。
解题思路
方差 $D = \frac{1}{n} \sum_{i = 1}^{n} {(a_i - \bar a)}2=\frac{n\sum_{i=1}n a_i^2 -(\sum_{i=1}^n a_i)2}{n2} $ ，所以答案为 \(n\sum_{i=1}^n a_i^2 -(\sum_{i=1}^n a_i)^2\) 。
题目中操作的本质是交换相邻两个数的差分数组，从差分角度考虑合适方差最小，发现当数越密集，即差分呈单谷状分布时，方差最小。
那我们就可以把差分值按顺序放进数组中了，考虑从大到小把差分值放入数组中，但由于需要存储上下分别插到了哪，这个 \(dp\) 方式不可行。
考虑从小到大把差分值放入数组中，那我们每次只需要在原来的基础上放在序列的头或尾即可，设 \(dp\) 数组 \(f_{i,j}\) 表示当前放了 \(i\) 个数和为 \(j\) 平方和最大为多少，那么我们每次就是分放到头或尾两种情况来讨论，设 \(a_n=V\) ，答案为 \(min_{i=1}^{V} n\times f_{n,i}-i^2\) 。
时间复杂度 \(O(nV)\) ，注意此题可以数据点分治。
Code
#include<bits/stdc++.h>
using namespace std;
const long long MAXN=300000;
long long n,a[10005],num,f[2][MAXN+5],x=0,s=1e15;
int main()
{
memset(f,0x3F,sizeof(f));
scanf("%lld",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<n;i++)a[i]=a[i+1]-a[i];
sort(a+1,a+n),f[0][0]=0;
for(int i=1;i<n;i++)
{
if(a[i]==0)continue;
num++;
for(int j=0;j<=MAXN;j++)
{
if(f[(num&1)^1][j]>=1e16)continue;
if(j+x+a[i]<=MAXN)f[num&1][j+x+a[i]]=min(f[num&1][j+x+a[i]],f[(num&1)^1][j]+(x+a[i])*(x+a[i]));
if(j+a[i]*i<=MAXN)f[num&1][j+a[i]*i]=min(f[num&1][j+a[i]*i],f[(num&1)^1][j]+a[i]*a[i]*i+2*j*a[i]);
f[(num&1)^1][j]=2e16;
}
x+=a[i];
}
for(long long i=0;i<=MAXN;i++)
if(f[num&1][i]<1e16)s=min(s,n*f[num&1][i]-i*i);
printf("%lld",s);
return 0;
}
【AGC043D】 Merge Triplets
题目描述
- 给定如下构造生成长度为 \(3N\) 的排列 \(P\) 的方法：
- 先生成一个长度为 \(3N\) 的排列 \(A\)。然后将 \(\forall k \in [0, N-1]\)，\(A_{3k+1},A_{3k+2},A_{3k+3}\) 分成一块。
- 有 \(N\) 个指针，初始指向每个块的第一个数。
- 每次选择所有指针指向的数中最小的数删除，然后放到 \(P\) 的末尾。之后指向被删除的数后移一个位置。若移出块了，则删除这个指针。
- 请你求出，一共能生成长度为 \(3N\) 的排列共多少种。答案可能很大，请求出对 \(M\) 取模的结果。
- \(1 \leq N \leq 2 \times 10^3\)，\(10^8\leq M \leq 10^9+7\)。
解题思路
没有比较好的映射方式连接 \(A\) 与 \(P\) ，考虑最终生成的排列有什么特殊性质。
根据构造方式，我们想到一个特殊性质：连续下降的子串长度最多只有 \(3\) ，因为每块长度最多为 \(3\) ，只能这一块递减使得子串连续下降。
那我们就可以考虑 \(dp\) 了，设 \(f_{i,j}\) 表示做到第 \(i\) 数目前前缀最大值为 \(j\) ，转移我们考虑枚举下降子串长度为 \(1/2/3\) ，从 \(i\) 个数中挑选 \(1/2/3\) 个作为系数。
时间复杂度 \(O(n^2)\) 。
Code
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
long long n,mod,f[6005][9005],s;
int main()
{
scanf("%lld%lld",&n,&mod);
f[0][3000]=1;
for(int i=1;i<=3*n;i++)
for(int j=0;j<=9000;j++)
{
if(j>0)f[i][j]=f[i-1][j-1];
if(j<9000&&i>=2)f[i][j]=(f[i][j]+f[i-2][j+1]*(i-1)%mod)%mod;
if(i>=3)f[i][j]=(f[i][j]+(f[i-3][j]*(i-1)%mod)*(i-2)%mod)%mod;
}
for(int i=3000;i<=9000;i++)s=(s+f[3*n][i])%mod;
printf("%lld",s);
return 0;
}
【AGC035E】 Develop
题目描述
在黑板上写有\(-10^{18}\)到\(10^{18}\)中的所有整数，每次你可以选中一个\([ 1 , N]\)中还在黑板上的整数\(x\)，把它擦去并补写上\(x − 2\) 与 \(x + K\)（如果原来不存在的话）。你可以进行这个操作任意次（可以不进行），求最终黑板上数字的可能状态有多少种，答案对\(M\)取模。
\(1\leq K \leq N \leq 150 , 10^8\leq M\leq 10^9\)
解题思路
因为保留的数的范围为 \([-10^{18},10^{18}]\) ，所以我们考虑删去的数的集合数，由于只可能在 \([1,N]\) 里面删，会好计算很多。
思考什么删去数的集合才是合法的，我们可以将每个节点 \(x\) 向 \(x-2\) 和 \(x+K\) 连边，我们发现，若一个集合中存在一个环，显然是不合法的，删去任一个环上的节点都会导致指向的节点加回来。
考虑 \(K\) 为偶数的情况，那其实我们可以把 \(x\) 分成奇数和偶数来考虑，那么对于每一类，只要不连续删去 \(K/2+1\) 个都是合法的，那么就是简单线性 \(dp\) 了， \(O(n^2)\) 解决即可。
考虑 \(K\) 为奇数的情况，我们还是分成奇数和偶数来考虑，分成两列，\(A\) 列为 \(1,3,5,...\) ，\(B\) 列为 \(2,4,6,...\) ，由于 \(x\) 会向 \(x-2\) 连边，所以每列中每个数都会向上一个连边，同时还有 \(x\) 向 \(x+K\) 连边的情况 ，就是 \(A\) 列中每个数向 \(B\) 列中对应位置后移 \(K/2\) 位连边，\(B\) 列每个数对应 \(A\) 列后移 \(K/2+1\) 为连边，那这样只要满足 \(A\) 列某些连续的位置和 \(B\) 列某些连续的位置中有一个没删即为合法的。
这样转化实在难以 \(dp\) ，我们考虑对齐。将 \(B\) 列整体前移 \(K/2\) 位，那么 \(A\) 列是直接对着 \(B\) 列对应位置连边了，而 \(B\) 列要连 \(A\) 列对应位置后移 \(K-1\) 位，那么一个环即为 \(B\) 列先连续选了一些部分，然后通过重叠部分转移到 \(A\) 列上，同时长度为 \(K+2\) 。
我们 \(AB\) 列一起考虑，分为 \(4\) 种情况：当前对应位置上 \(AB\) 列都删、\(AB\) 列都不删、只有 \(A\) 列删、只有 \(B\) 列删。我们只需统计当前连续选了多少位置以及当前选的位置是那种情况，可以直接做 \(O(n^2)\) 的线性 \(dp\) 了，但是细节很多，不好调。
我们考虑记录删到哪位、当前 \(B\) 列到 \(A\) 列连续删了多少个、当前 \(B\) 列连续删了多少个这三维，那么转移一下就简单很多了，还是分\(4\) 种情况转移 ，保证不会连续选 \(K+2\) 个即可。
时间复杂度 \(O(n^3)\) 。
Code
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
long long n,k,mod,m1,m2,m,f[155][155][155],s,maxx;
long long solve1(long long m)
{
s=0,f[0][0][0]=1;
for(int i=1;i<=m;i++)
{
f[i][0][0]=0;
for(int j=0;j<=k;j++)f[i][0][0]=(f[i][0][0]+f[i-1][j][0])%mod;
for(int j=1;j<=k;j++)f[i][j][0]=f[i-1][j-1][0];
}
for(int i=0;i<=k;i++)s=(s+f[m][i][0])%mod;
return s;
}
void solve3()
{
long long x;
m2=m1=(k-1)/2;
if(n&1)m2++;
m=(n-m1-m2)/2,maxx=k+2;
f[0][0][0]=1;
for(int i=1;i<=m1;i++)
{
for(int j=0;j<maxx;j++)
for(int u=0;u<=maxx;u++)f[i][0][0]=(f[i][0][0]+f[i-1][j][u])%mod;
for(int j=1;j<=maxx;j++)
for(int u=0;u<maxx;u++)f[i][0][j]=(f[i][0][j]+f[i-1][u][j-1])%mod;
for(int j=0;j<maxx;j++)f[i][0][maxx]=(f[i][0][maxx]+f[i-1][j][maxx])%mod;
}
for(int i=m1+1;i<=m1+m;i++)
{
for(int j=0;j<maxx;j++)
for(int u=0;u<=maxx;u++)f[i][0][0]=(f[i][0][0]+f[i-1][j][u])%mod;
for(int j=1;j<=maxx;j++)
for(int u=0;u<maxx;u++)f[i][0][j]=(f[i][0][j]+f[i-1][u][j-1])%mod;
for(int j=0;j<maxx;j++)f[i][0][maxx]=(f[i][0][maxx]+f[i-1][j][maxx])%mod;
for(int j=0;j<=maxx;j++)f[i][0][0]=(f[i][0][0]+f[i-1][0][j])%mod;
for(int j=3;j<maxx;j++)
for(int u=0;u<=maxx;u++)f[i][j][0]=(f[i][j][0]+f[i-1][j-1][u])%mod;
for(int j=0;j<maxx;j++)
for(int u=0;u<maxx;u++)
{
x=max(j+1,u+2);
if(x>=maxx)continue;
f[i][x][u+1]=(f[i][x][u+1]+f[i-1][j][u])%mod;
}
}
for(int i=m1+m+1;i<=m1+m+m2;i++)
{
for(int j=0;j<maxx;j++)
for(int u=0;u<=maxx;u++)f[i][0][0]=(f[i][0][0]+f[i-1][j][u])%mod;
for(int j=0;j<=maxx;j++)f[i][0][0]=(f[i][0][0]+f[i-1][0][j])%mod;
for(int j=3;j<maxx;j++)
for(int u=0;u<=maxx;u++)f[i][j][0]=(f[i][j][0]+f[i-1][j-1][u])%mod;
}
long long s=0;
for(int i=0;i<maxx;i++)
for(int j=0;j<=maxx;j++)s=(s+f[m1+m+m2][i][j])%mod;
cout<<s;
return;
}
int main()
{
scanf("%lld%lld%lld",&n,&k,&mod);
if(!(k&1))k>>=1,printf("%lld",solve1(n/2)*solve1(n-n/2)%mod);
else solve3();
return 0;
}
【ARC112E】 Cigar Box
题目描述
给定序列 \(1,2,\cdots,n\)，要求进行 \(m\) 次操作，将这个序列变为 \(a_1,a_2,\cdots,a_n\)，问有多少种不同的操作方案数？一次操作是指：将排列中的任意一个数移到第一个或移到最后一个。
- \(2\leqslant n\leqslant 3000\)
- \(1\leqslant m\leqslant 3000\)
解题思路
我们考虑随便找出一组合法的操作方案，不考虑操作次数的限制，我们只需按顺序一个一个放好即可。
这个我们一个启发：我们可以把放好的序列看成三部分，前面和后面的部分是按顺序操作过的，只有中间的部分是没操作过的。
那么对于这种划分，只要中间的部分是递增的以及操作过的数不超过 \(m\) 个即可，那我们就可以枚举如何划分出三部分 \([1,l],[l+1,r],[r+1,n]\) 。
我们需要求出一种划分方案的方案数，设前面部分有 \(x\) 个，后面部分有 \(y\) 个，由于有可能有无效的操作，先分配无效操作 \(C_{m}^{x+y} \times 2^{m-x-y}\) ，同时在分配每个操作朝向即 \(C_{x+y}^x\) ，乘起来就是贡献。
时间复杂度 \(O(n^2)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long n,m,s,a[3005],d[3005],C[3005][3005],p[3005],f[3005][3005];
int main()
{
C[0][0]=p[0]=f[0][0]=1;
for(int i=1;i<=3000;i++)
{
p[i]=p[i-1]*2%mod,C[i][0]=1;
for(int j=1;j<=i;j++)
{
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
f[i][j]=(f[i-1][j-1]+f[i-1][j]*j%mod)%mod;
}
}
scanf("%lld%lld",&n,&m),d[n+1]=n+1;
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<=n;i++)
for(d[i]=i;d[i]<n;d[i]++)
if(a[d[i]+1]<a[d[i]])break;
for(int i=0;i<=n;i++)
for(int j=0;j<=n-i;j++)
if(d[i+1]>=n-j&&i+j<=m)s=(s+(p[m-i-j]*C[i+j][i]%mod)*f[m][i+j]%mod)%mod;
printf("%lld",s);
return 0;
}
【AGC013D】 Piling Up
题目描述
一开始有 \(n\) 个颜色为黑白的球，但不知道黑白色分别有多少， \(m\) 次操作，每次先拿出一个球，再放入黑白球各一个，再拿出一个球，最后拿出的球按顺序排列会形成一个颜色序列，求颜色序列有多少种。答案对 \(10^9+7\) 取模。
\(n,m\) 小于等于 \(3000\)。
解题思路
首先，黑白球总数不变，所以只需记录黑球的数量即可。
考虑每种操作的限制，因为放了一组黑白球进去，所以后拿出的球无特殊限制，所有我们只需保证前面拿球时保证存在该颜色的球即可。
那我们就可以直接做 \(dp\) 了，设 \(f_{i,j}\) 表示做了 \(i\) 次操作还有 \(j\) 个黑球的方案数，转移分四种，每种考虑黑球的上界或下界即可。
但是注意还要去重，我们只需保证每个方案在做的过程中出现了黑球 \(/\) 白球个数为 \(0\) 的情况即可，所以我们要再开两维 \(0/1\) 的状态表示黑球是否到过 \(0/n\) 。
时间复杂度 \(O(nm)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long n,m,f[3005][3005][2];
int main()
{
scanf("%lld%lld",&n,&m),f[0][0][1]=1;
for(int i=1;i<=n;i++)f[0][i][0]=1;
for(int i=0;i<m;i++)
{
for(int j=0;j<=n;j++)
{
for(int u=0;u<=1;u++)
{
if(j!=n)f[i+1][j+1][u]=(f[i+1][j+1][u]+f[i][j][u])%mod,f[i+1][j][u]=(f[i+1][j][u]+f[i][j][u])%mod;
if(j>1)f[i+1][j-1][u]=(f[i+1][j-1][u]+f[i][j][u])%mod,f[i+1][j][u]=(f[i+1][j][u]+f[i][j][u])%mod;
else if(j==1)f[i+1][0][1]=(f[i+1][0][1]+f[i][j][u])%mod,f[i+1][1][1]=(f[i+1][1][1]+f[i][j][u])%mod;
}
}
}
long long s=0;
for(int i=0;i<=n;i++)s=(s+f[m][i][1])%mod;
printf("%lld",s);
return 0;
}
【Luogu P3226】 集合选数
题目描述
《集合论与图论》这门课程有一道作业题，要求同学们求出 \(\{ 1, 2, 3, 4, 5 \}\) 的所有满足以下条件的子集：若 \(x\) 在该子集中，则 \(2x\) 和 \(3x\) 不能在该子集中。
同学们不喜欢这种具有枚举性质的题目，于是把它变成了以下问题：对于任意一个正整数 \(n \le 10^5\)，如何求出 \(\{1,2,\ldots ,n\}\) 的满足上述约束条件的子集的个数（只需输出对 \(10^9+1\) 取模的结果），现在这个问题就交给你了。
解题思路
首先，若 \(\frac{y}{x}\) 不为 \(2\) 或 \(3\) 的倍数，\(x\) 不肯能影响到 \(y\) ，所有我们可以把 \([1,n]\) 分成若干集合，使得集合内最小数 \(x\) 能刚好影响完所有其它数。
每个集合内为独立的问题，我们分开考虑，将集合内所有数 \(/x\) ，那么每个数都可以被表示为 \(2^i3^j\) 的形式，把每个数用点的方式表示出来，那么每个点 \((i,j)\) 只能直接影响到 \((i+1,j)\) 和 \((i,j+1)\) 两点。
我们考虑最多有多少行多少列，显然是 \(log\) 形式的，行最多有 \(17\) 行，列最多有 \(10\) 列。
如此小的网格我们很明显可以做状压 \(dp\) ，我们只需记录每行有哪些点被选了且满足相邻两点没同时被选，然后推到下一行即可。
时间复杂度大概是 \(O(n)\) 到 \(O(nlogn)\) 级别的。
Code
#include<bits/stdc++.h>
using namespace std;
long long n,mod,f[25][10005],m,d[25][10005];
bool v[10005];
bool check(long long x)
{
long long y=0;
while(x)
{
if((x&1)&&(y))return false;
y=x&1;
x>>=1;
}
return true;
}
long long solve(long long x)
{
f[0][0]=1,m=0;
for(int i=0;i<=10000;i++)d[0][i]=1;
long long y,q=0,w=(1<<13),e;
while(x<=n)
{
m++,y=x,q=0;
while(y<=n)q++,y*=3;
e=(1<<q);
for(int i=0;i<e;i++)f[m][i]=d[m][i]=0;
for(int i=0;i<e;i++)if(v[i])d[m][i]=f[m][i]=d[m-1][(w-1)^i];
w=e;
for(int i=0;i<q;i++)
for(int j=0;j<e;j++)
if(j&(1<<i))d[m][j]=(d[m][j]+d[m][j^(1<<i)])%mod;
x*=2;
}
long long s=0;
for(int i=0;i<w;i++)s=(s+f[m][i])%mod;
return s;
}
void poi()
{
long long s=1;
scanf("%lld",&n),mod=1e9+1;
for(int i=1;i<=n;i++)
if((i%2!=0)&&(i%3!=0))s=(s*solve(i))%mod;
printf("%lld\n",s);
return;
}
int main()
{
for(int i=0;i<(1<<13);i++)v[i]=check(i);
poi();
return 0;
}
数据结构
【Luogu P10856】 Xor-Forces
题目描述
给定一个长度为 \(n=2^k\) 的数组 \(a\)，下标从 \(0\) 开始，维护 \(m\) 次操作：
- 操作一：给定 \(x\)，设数列 \(a'\) 满足 \(a'_i=a_{i\oplus x}\)，将 \(a\) 修改为 \(a'\)。其中 \(\oplus\) 表示按位异或运算。
- 操作二：给定 \(l,r\)，查询 \(a\) 的下标在 \(l,r\) 之间的子数组有多少颜色段。不保证 \({l\le r}\)，若 \({l > r}\)，请自行交换 \({l,r}\)。
其中，一个极长的所有数都相等的子数组称为一个颜色段。
部分测试点要求强制在线，\(0 \le k \le 18\)。
解题思路
首先有一条极其重要的性质为数组长度为 \(2\) 的整数幂，因为这种题一般都用线段树，所以这是一条很重要的性质。
我们思考 \(a_{i \oplus x}\) 这个操作的性质，对于 \(x\) 的第 \(j\) 位，若其为 \(1\) ，那么 \(i\) 就会异或上 \(2^j\) ，也就是 \(a_i\) 与 \(a_{i \oplus 2^j}\) 发生交换。
我们发现这个交换可以看成线段树上的某些块对换，所以我们可以线段树遍历时，若该位为 \(1\) ，那就换一个方向遍历。
那么就可以进行查询了，修改直接把直接异或之和存下来即可。
最后一个问题：怎么处理改变位置的操作对每个块内部相对位置的影响。
我们可以想到，不改变块内相对位置的位是不用理它的，所以对于一个第 \(i\) 层的块，若一共有 \(k\) 层，那么只用管 \(k-i\) 位。
由于层数越大块数越多，我们可以把会影响块内位置的存下来，即只存前 \(k-i\) 位的，很明显只用存 \(k2^k\) 个块 。
时间复杂度即为 \(O(k2^k)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
struct datay
{
int lc,rc,v;
};
int qwe,n,k,m,v1[1000005],s;
vector<datay> t[2000005];
datay merge(datay x,datay y)
{
datay h;
h.lc=x.lc,h.rc=y.rc;
h.v=(x.v+y.v-(x.rc==y.lc));
return h;
}
void build(int x,int l,int r,int p)
{
if(l==r)
{
datay h;
h.lc=h.rc=v1[l],h.v=1;
t[x].push_back(h);
return;
}
int lc=(x<<1),rc=(x<<1)|1,mid=(l+r)>>1,z=p>>1;
build(lc,l,mid,z),build(rc,mid+1,r,z);
for(int i=0;i<p;i++)
{
if(i&z)t[x].push_back(merge(t[rc][i^z],t[lc][i^z]));
else t[x].push_back(merge(t[lc][i],t[rc][i]));
}
return;
}
datay query(int x,int l,int r,int ql,int qr,int p)
{
if(ql<=l&&r<=qr)return t[x][(p-1)&s];
int lc=(x<<1),rc=(x<<1)|1,mid=(l+r)>>1,z=p>>1;
if(s&z)swap(lc,rc);
if(qr<=mid)return query(lc,l,mid,ql,qr,z);
if(ql>mid)return query(rc,mid+1,r,ql,qr,z);
return merge(query(lc,l,mid,ql,qr,z),query(rc,mid+1,r,ql,qr,z));
}
int main()
{
int lst=0,op,x,y;
scanf("%d%d%d",&qwe,&k,&m);
n=(1<<k);
for(int i=0;i<n;i++)scanf("%d",&v1[i]);
build(1,0,n-1,n);
for(int i=1;i<=m;i++)
{
scanf("%d",&op);
if(op==1)
{
scanf("%d",&x),x^=(lst*qwe);
s^=x;
}
else
{
scanf("%d%d",&x,&y);
x^=(lst*qwe),y^=(lst*qwe);
if(x>y)swap(x,y);
lst=query(1,0,n-1,x,y,n).v;
printf("%d\n",lst);
}
}
return 0;
}
【Luogu P4587】 神秘数
题目描述
一个可重复数字集合 \(S\) 的神秘数定义为最小的不能被 \(S\) 的子集的和表示的正整数。例如 \(S=\{1,1,1,4,13\}\)，有：\(1 = 1\)，\(2 = 1+1\)，\(3 = 1+1+1\)，\(4 = 4\)，\(5 = 4+1\)，\(6 = 4+1+1\)，\(7 = 4+1+1+1\)。
\(8\) 无法表示为集合 \(S\) 的子集的和，故集合 \(S\) 的神秘数为 \(8\)。
现给定长度为 \(n\) 的正整数序列 \(a\)，\(m\) 次询问，每次询问包含两个参数 \(l,r\)，你需要求出由 \(a_l,a_{l+1},\cdots,a_r\) 所组成的可重集合的神秘数，\(1\le n,m\le {10}^5\)，\(\sum a\le {10}^9\)。
解题思路
我们先来分析一个集合 \(S\) 怎样找到神秘数。
对于一个集合 \(S\) ，我们先找集合中是否存在 \(1\) ，若没有直接输出，否则 \(1\) 即为可以构成的，再来找 \(2\) ，若 \(2\) 存在，那么 \(\le 3\) 的数都是可以构成的，再来找 \(4\) ，若 \(4\) 存在，那么 \(\le 7\) 的数都是可以构成的，接着继续找下去 \(\cdots\)
我们发现从小到大遍历一个集合 \(S\) ，不断更新可以构成的区间 \([1,k]\) ，若新加进来的数 \(x \le k+1\) ，就说明了 \([k+1,k+x]\) 能在原来的基础上加上 \(x\) 来构成，加上即可，否则答案就为 \(k +1\) 。
我们开一棵值域线段树用来存储 \(S\) ，按上述流程进行查找，因为每次查找都会翻一倍，所以总共会有 \(logn\) 次查找，总时间复杂度为 \(O(log^2n)\) 。
现在是区间询问，我们只需要开一棵主席树即可，时间复杂度 \(O(nlog^2n)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
struct datay
{
int lc,rc,v;
}f[10000005];
const int maxx=1e9;
int n,m,a[100005],num,v1[100005],root[100005];
int modify(int x,int l,int r,int k,int v)
{
int h=++num;f[h]=f[x];
if(l==r){f[h].v+=v;return h;}
int mid=(l+r)>>1;
if(k<=mid)f[h].lc=modify(f[x].lc,l,mid,k,v);
else f[h].rc=modify(f[x].rc,mid+1,r,k,v);
f[h].v=f[f[h].lc].v+f[f[h].rc].v;
return h;
}
int query(int x,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr)return f[x].v;
int mid=(l+r)>>1,h=0;
if(ql<=mid&&f[x].lc)h+=query(f[x].lc,l,mid,ql,qr);
if(qr>mid&&f[x].rc)h+=query(f[x].rc,mid+1,r,ql,qr);
return h;
}
int solve(int l,int r)
{
if(query(root[r],1,maxx,1,1)-query(root[l-1],1,maxx,1,1)==0)return 1;
int x=1,s=1,y,pre=1;
for(int i=1;i<=n;i++)
{
if(pre>s)break;
y=query(root[r],1,maxx,pre,s)-query(root[l-1],1,maxx,pre,s);
pre=s+1,s+=y;
}
return s;
}
int main()
{
int x=0,y;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)root[i]=modify(root[i-1],1,maxx,a[i],a[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
if(x>y)swap(x,y);
printf("%d\n",solve(x,y));
}
return 0;
}
【ARC187D】 Many Easy Optimizations
题目描述
给出两个长度为 \(n\) 的序列 \(A\) 与 \(B\) ，对于 \(k \in [1,n]\) ，构造一个长度为 \(k\) 的序列 \(C\) 满足 \(C_i =A_i\) 或 \(C_i=B_i\) ，并且 \(C\) 的极差最小，输出这个最小的极差，\(1 \le n\le 5 \times 10^5\) 。
解题思路
钦定 \(A_i \le B_i\) ，若 \(A_i>B_i\) 就交换，考虑 \(O(n^3)\) 的做法，我们对于每次询问，枚举最小值 \(i\) 从 \(1\) 到 \(2k\) ，那么对于 \(j \in [1,k]\) ，若 \(a_j \ge i\) ，那么就将 \(a_j\) 放入序列，否则若 \(b_j \ge i\) ，将 \(b_j\) 放入序列，否则不能取 \(i\) 为最小值，每个最小值 \(O(n)\) 求出最大值，极差即为最大值减去最小值的最小值。
考虑优化，我们每次询问会重复的枚举某个值作为最小值的情况，由于相邻的询问之间只差了一组数，我们考虑这组数对之前枚举的最小值的影响，同时在考虑当前的 \(A_i,B_i\) 作为最小值的情况，时间复杂度 \(O(n^2)\) 。
考虑进一步优化，我们考虑直接枚举以 \(i \in[1,2n]\) 作为最小值，\(v_i\) 为当前以 \(i\) 为最小值能取到的最小最大值，考虑每次加进去一组数对最大值的影响，由于答案求最小，所以最小值一定能取到已有的 \(A_i/B_i\) 上。
每次加进一组数时，最小值为 $ j \in [1,A_i]$ 的最大值 \(v_j\) 都需取 \(max\) 为 \(A_i\) ，同理，最小值为 \(j \in [A_i+1,B_i]\) 的 \(v_j\) 需取 \(max\) 为 \(B_i\) ，而 \(j>B_i\) 的 \(v_j\) 取为 \(inf\) ，那么就可以直接用吉司机线段树了。
继续观察，由于 \(v_j\) 一定单调递增，每次只有一整段会被修改，我们可以用普通线段树做区间赋值与线段树二分操作即可代替吉司机线段树。
时间复杂度 \(O(nlogn)\) 。
Code
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
const int MAXN=(2e9);
struct datay
{
int x,y;
}a[500005];
int n,f[4000005],maxx[4000005],v1[1000005],d[4000005],minn[4000005];
set<int> l1;
map<int,int> l2;
void galaxy(int x,int l,int r,int v){f[x]=v-v1[r],maxx[x]=minn[x]=v,d[x]=v;return;}
void pushdown(int x,int l,int r)
{
if(d[x]==0)return;
int mid=(l+r)>>1,lc=(x<<1),rc=(x<<1)|1;
galaxy(lc,l,mid,d[x]),galaxy(rc,mid+1,r,d[x]),d[x]=0;
return;
}
void build(int x,int l,int r)
{
if(l==r){maxx[x]=minn[x]=v1[l],f[x]=0;return;}
int lc=(x<<1),rc=(x<<1)|1,mid=(l+r)>>1;
build(lc,l,mid),build(rc,mid+1,r),f[x]=0,maxx[x]=max(maxx[rc],maxx[lc]),minn[x]=min(minn[lc],minn[rc]);
return;
}
void modify(int x,int l,int r,int ql,int qr,int v)
{
if(ql<=l&&r<=qr){galaxy(x,l,r,v);return;}
pushdown(x,l,r);
int lc=(x<<1),rc=(x<<1)|1,mid=(l+r)>>1;
if(ql<=mid)modify(lc,l,mid,ql,qr,v);
if(qr>mid)modify(rc,mid+1,r,ql,qr,v);
maxx[x]=max(maxx[lc],maxx[rc]),f[x]=min(f[lc],f[rc]),minn[x]=min(minn[lc],minn[rc]);
return;
}
int query(int x,int l,int r,int k)
{
if(l==r)return l;
pushdown(x,l,r);
int lc=(x<<1),rc=(x<<1)|1,mid=(l+r)>>1;
if(minn[rc]<=k)return query(rc,mid+1,r,k);
return query(lc,l,mid,k);
}
int main()
{
int num=0,x;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i].x),l1.insert(a[i].x);
for(int i=1;i<=n;i++)scanf("%d",&a[i].y),l1.insert(a[i].y);
for(int i=1;i<=n;i++)
if(a[i].x>a[i].y)swap(a[i].x,a[i].y);
for(set<int>::iterator q=l1.begin();q!=l1.end();q++)l2[*q]=++num,v1[num]=*q;
for(int i=1;i<=n;i++)a[i].x=l2[a[i].x],a[i].y=l2[a[i].y];
build(1,1,num);
for(int i=1;i<=n;i++)
{
if(minn[1]<=v1[a[i].x])x=query(1,1,num,v1[a[i].x]),modify(1,1,num,1,min(x,a[i].x),v1[a[i].x]);
x=query(1,1,num,v1[a[i].y]);
if(a[i].x!=a[i].y&&a[i].x+1<=min(a[i].y,x))modify(1,1,num,a[i].x+1,min(a[i].y,x),v1[a[i].y]);
if(a[i].y!=num)modify(1,1,num,a[i].y+1,num,MAXN);
printf("%d\n",f[1]);
}
return 0;
}
【Luogu P6072】 Path
题目描述
给定一棵 \(n\) 个点的无根树，边有边权，你要选择两条简单路径，满足没有重合的点，且边权异或和之和最大，\(1 \le n\le 3 \times 10^4\)。
解题思路
设 \(1\) 为根，我们考虑转化题意：找出一个节点，使它子树内路径边权异或和 \(+\) 子树外路径边权异或和最大，很明显，题目要求与该条件等价。
由于路径边权异或和可以用树上差分转化为求两点异或和最大的问题，求子树两点异或和最大的问题明显用树上启发式合并 \(+\) \(trie\) 树解决，考虑如何解决子树外两点边权异或和最大的问题。
注意到我们可以直接选出树上进行异或操作后最大的两点作为大多数点的答案，只有 \(1-x\) 和 \(1-y\) 这两条链上的点不能这样贡献，由于 \(x\) 的父亲 \(fa_x\) 的子树包含 \(x\) 的子树，对于一条从 \(1\) 到 \(x/y\) 的路径，我们可以从 \(1\) 出发，不断的把不在子树内的节点加入字典树，更新路径上点的答案，这样时间复杂度是 \(O(nlogn)\) 。
总时间复杂度 \(O(nlog^2n)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
int n,f[20000005][2],num,son[30005],root,siz[30005],dfn[30005],out[30005],num1,re[30005],v1[20000005];
vector<int> a[30005],t[30005];
int v[30005],s,p2[105],ans[30005],ans1[30005];
void add(int x)
{
int p=1,q;
for(int i=30;i>=0;i--)
{
if(x&p2[i])q=1;
else q=0;
if(!f[p][q])f[p][q]=++num,f[num][0]=f[num][1]=0,p=num;
else p=f[p][q];
v1[p]++;
}
return;
}
int query(int x)
{
int h=0,p=1,q;
for(int i=30;i>=0;i--)
{
if(x&p2[i])q=1;
else q=0;
if(f[p][q^1]&&v1[f[p][q^1]])h|=p2[i],p=f[p][q^1];
else p=f[p][q];
}
return h;
}
void del(int x)
{
int p=1,q;
for(int i=30;i>=0;i--)
{
if(x&p2[i])q=1;
else q=0;
p=f[p][q],v1[p]--;
}
return;
}
void dfs1(int x,int y)
{
for(int i=0;i<a[x].size();i++)
{
if(a[x][i]==y)continue;
son[a[x][i]]=x,dfs1(a[x][i],x);
}
return;
}
void dfs2(int x,int y,int z)
{
if(!z)
{
s=max(s,query(v[x]));
add(v[x]);
for(int i=0;i<a[x].size();i++)if(a[x][i]!=y)dfs2(a[x][i],x,0);
return;
}
ans[x]=s;
if(x==root)return;
s=max(s,query(v[x]));
add(v[x]);
for(int i=0;i<a[x].size();i++)
{
if(a[x][i]==y||a[x][i]==son[x])continue;
dfs2(a[x][i],x,0);
}
dfs2(son[x],x,1);
return;
}
void dfs3(int x,int y)
{
siz[x]=1;
for(int i=0;i<a[x].size();i++)
{
if(a[x][i]==y)continue;
v[a[x][i]]=v[x]^t[x][i],dfs3(a[x][i],x),siz[x]+=siz[a[x][i]];
}
return;
}
void dfs4(int x,int y)
{
dfn[x]=++num1,re[num1]=x;
for(int i=0;i<a[x].size();i++)
{
if(a[x][i]==y||a[x][i]==son[x])continue;
dfs4(a[x][i],x);
}
if(son[x])dfs4(son[x],x);
out[x]=num1;
return;
}
void dfs5(int x,int y)
{
for(int i=0;i<a[x].size();i++)
{
if(a[x][i]==y||a[x][i]==son[x])continue;
dfs5(a[x][i],x);
}
int s1=s;
if(son[x])
{
dfs5(son[x],x);
for(int i=dfn[x];i<dfn[son[x]];i++)s=max(s,query(v[re[i]])),add(v[re[i]]);
}
else s=max(s,query(v[x])),add(v[x]);
ans1[x]=s;
if(son[y]!=x)
{
s=s1;
for(int i=dfn[x];i<=out[x];i++)del(v[re[i]]);
}
return;
}
int main()
{
int x=1,y=1,z;
scanf("%d",&n),p2[0]=1,s=0,num=1;
for(int i=1;i<=30;i++)p2[i]=p2[i-1]*2;
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
a[x].push_back(y),a[y].push_back(x);
t[x].push_back(z),t[y].push_back(z);
}
dfs3(1,0);
for(int i=1;i<=n;i++)
{
x=query(v[i]);
if(x>s){s=x;y=i;}
add(v[i]);
}
for(int i=1;i<=n;i++)
if((v[i]^v[y])==s){x=i;break;}
for(int i=1;i<=n;i++)ans[i]=s;
f[1][0]=f[1][1]=s=0,num=1,dfs1(x,0);
root=x,dfs2(1,0,1);
f[1][0]=f[1][1]=s=0,num=1,dfs1(y,0);
root=y,dfs2(1,0,1);
f[1][0]=f[1][1]=0,num=1,s=0;
memset(son,0,sizeof(son));
for(int i=1;i<=n;i++)
for(int j=0;j<a[i].size();j++)
if(a[i][j]>i&&siz[son[i]]<siz[a[i][j]])son[i]=a[i][j];
dfs4(1,0);
memset(v1,0,sizeof(v1));
dfs5(1,0),s=0;
for(int i=1;i<=n;i++)
if(i!=1)s=max(s,ans[i]+ans1[i]);
printf("%d",s);
return 0;
}
【Luogu P6864】 记忆
题目描述
有一个括号串 \(S\)，一开始 \(S\) 中只包含一对括号（即初始的 \(S\) 为 ()），接下来有 \(n\) 个操作，操作分为三种：
-
在当前 \(S\) 的末尾加一对括号（即 \(S\) 变为
S()）； -
在当前 \(S\) 的最外面加一对括号（即 \(S\) 变为
(S)）； -
取消第 \(x\) 个操作，即去除第 \(x\) 个操作造成过的一切影响（例如，如果第 \(x\) 个操作也是取消操作，且取消了第 \(y\) 个操作，那么当前操作的实质就是恢复了第 \(y\) 个操作的作用效果）。
每次操作后，你需要输出 \(S\) 的能够括号匹配的非空子串（子串要求连续）个数。
一个括号串能够括号匹配，当且仅当其左右括号数量相等，且任意一个前缀中左括号数量不少于右括号数量，\(1 \le n \le 2 \times 10^5\)。
解题思路
假设没有撤销操作，我们来考虑如何处理。
我们设处理到第 \(i\) 个操作当前答案为 \(f_{i,0}\) ，以当前最后一位结尾的合法子串有 \(f_{i,1}\) 个，若为 \(1\) 操作，那么 \(f_{i,0}=f_{i-1,0} + f_{i-1,1}+1,f_{i,1} =f_{i-1,1}+1\) ，若为 \(2\) 操作，那么 \(f_{i,0}=f_{i-1,0}+1,f_{i,1}=1\) ，答案即为 \(f_{n,0}\) 。
考虑撤销操作，其实每个撤销操作可以看成令某个操作生效\(/\)失效的操作，我们就需要动态维护每个操作是否生效并做 \(dp\) ，因为 \(dp\) 形式为线性 \(dp\) ，我们很容易想到矩阵加速优化 \(dp\) 。
我们只需求出 \(1\) 操作和 \(2\) 操作对应的矩阵丢到一个线段树里，每次单调操作对一个位置的操作是否生效，合并即为矩阵乘法，撤销一个撤销操作看成令一个操作生效即可。
时间复杂度 \(O(nlogn)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
struct datay
{
long long a[3][3];
}f[1000005],v1,v2,c1,c2,q1,w1;
int n,v[1000005],pre[1000005];
datay operator *(const datay &q,const datay &w)
{
datay c;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
c.a[i][j]=0;
for(int u=0;u<3;u++)c.a[i][j]+=q.a[i][u]*w.a[u][j];
}
return c;
}
void build(int x,int l,int r)
{
if(l==r){f[x]=c2;return;}
int mid=(l+r)>>1,lc=(x<<1),rc=(x<<1)|1;
build(lc,l,mid),build(rc,mid+1,r);
f[x]=f[lc]*f[rc];
return;
}
void modify1(int x,int l,int r,int k,int v)
{
if(l==r)
{
if(v==1)f[x]=v1;
else f[x]=v2;
return;
}
int mid=(l+r)>>1,lc=(x<<1),rc=(x<<1)|1;
if(k<=mid)modify1(lc,l,mid,k,v);
else modify1(rc,mid+1,r,k,v);
f[x]=f[lc]*f[rc];
return;
}
void modify2(int x,int l,int r,int k)
{
if(l==r){v[x]^=1;return;}
int mid=(l+r)>>1,lc=(x<<1),rc=(x<<1)|1;
if(k<=mid)modify2(lc,l,mid,k);
else modify2(rc,mid+1,r,k);
q1=(v[lc])?c2:f[lc];
w1=(v[rc])?c2:f[rc];
f[x]=q1*w1;
return;
}
int main()
{
int op,x;
v1.a[0][0]=v1.a[1][0]=v1.a[1][1]=v1.a[2][0]=v1.a[2][1]=v1.a[2][2]=1;
v2.a[0][0]=v2.a[2][0]=v2.a[2][1]=v2.a[2][2]=1;
c1.a[0][0]=c1.a[0][1]=c1.a[0][2]=c2.a[0][0]=c2.a[1][1]=c2.a[2][2]=1;
scanf("%d",&n),build(1,1,n);
for(int i=1;i<=n;i++)
{
scanf("%d",&op);
if(op==1)modify1(1,1,n,i,1);
if(op==2)modify1(1,1,n,i,2);
if(op==3)
{
scanf("%d",&x);
if(pre[x])pre[i]=pre[x],modify2(1,1,n,pre[i]);
else pre[i]=x,modify2(1,1,n,pre[i]);
}
printf("%lld\n",(c1*f[1]).a[0][0]);
}
return 0;
}
【Luogu P3246】 序列
题目描述
给定长度为 $ n $ 的序列：$ a_1, a_2, \cdots , a_n $，记为 $ a[1 \colon n] \(。类似地，\) a[l \colon r] \(（\) 1 \leq l \leq r \leq N\(）是指序列：\) a_{l}, a_{l+1}, \cdots ,a_{r-1}, a_r$。若 \(1\leq l \leq s \leq t \leq r \leq n\)，则称 $ a[s \colon t] $ 是 $ a[l \colon r] $ 的子序列。
现在有 $ q $ 个询问，每个询问给定两个数 $ l $ 和 $ r \(，\) 1 \leq l \leq r \leq n $，求 $ a[l \colon r] $ 的不同子序列的最小值之和，\(1 \le n,q \le 10^5\)。
解题思路
数据范围是可以跑 \(O(n\sqrt{n})\) 的，我们考虑莫队。
由于每个区间的贡献为 \(\sum_{i=l}^r \sum_{j=i}^r (min_{k=i}^j a_k)\) ，若要 \(O(1)\) 转移，我们要实现 \(O(1)\) 求出 \(\sum_{i=l}^r (min_{j=l}^i a_j)\) ，也就是求 \(a_l+min(a_l,a_{l+1})+...+min(a_l,a_{l+1},...,a_{r})\) 。
由于要求区间 \([l,r]\) 的最小值且 \(l\) 不变 \(r\) 递增，我们可以考虑单调栈，求出每一个节点后第一个比它小的位置 \(las_i\) ，注意到我们可以对于 \([1,n-1]\) 的每个节点，我们都可以在 \(i\) 与 \(las_i\) 之间连一条边，这样就构成了一棵森林。
那么从 \(l\) 开始求每个区间的最小值，其实就是 \(l\) 节点往祖先走走到当前节点编号 \(>r\) 为止，这个东西我们可以用树上前缀和来求，即为 \(f_l-f_x\) ，\(f_i\) 表示根到节点 \(i\) 的权值和， 但是现在我们要 \(O(1)\) 求出它最多能走到哪，所以我们需要思考这棵树的性质。
注意到最后经过的节点一定是区间最小值，那我们只需要预处理 \(ST\) 表 \(O(1)\) 求出区间最小值位置即可，求贡献用前缀和，剩下的情况同理。
时间复杂度 \(O(n\sqrt{n})\) 。
Code
#include<bits/stdc++.h>
using namespace std;
struct datay
{
int l,r,p;
long long v;
}t[1000005];
int n,m,block,pre[100005],las[100005],z,f[100005][21],lo[100005],p[21],x;
long long pre_f[100005],las_f[100005],a[100005],s;
stack<int> l1;
bool cmp1(datay q,datay w)
{
if((q.l-1)/block!=(w.l-1)/block)return q.l<w.l;
return q.r<w.r;
}
bool cmp2(datay q,datay w)
{
return q.p<w.p;
}
int query(int l,int r)
{
z=lo[r-l+1];
if(a[f[l][z]]<a[f[r-p[z]+1][z]])return f[l][z];
return f[r-p[z]+1][z];
}
void pre_add(int l,int r)
{
x=query(l,r);
s+=las_f[l]-las_f[x]+a[x]*(r-x+1);
return;
}
void pre_del(int l,int r)
{
x=query(l,r);
s-=las_f[l]-las_f[x]+a[x]*(r-x+1);
return;
}
void las_add(int l,int r)
{
x=query(l,r);
s+=pre_f[r]-pre_f[x]+a[x]*(x-l+1);
return;
}
void las_del(int l,int r)
{
x=query(l,r);
s-=pre_f[r]-pre_f[x]+a[x]*(x-l+1);
return;
}
int main()
{
int l=1,r=0;
p[0]=-(lo[0]=-1);
for(int i=1;i<=20;i++)p[i]=p[i-1]<<1;
for(int i=1;i<=100000;i++)lo[i]=lo[i>>1]+1;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]),f[i][0]=i;
for(int i=1;i<=m;i++)scanf("%d%d",&t[i].l,&t[i].r),t[i].p=i;
for(int i=1;i<=20;i++)
for(int j=1;j+p[i]-1<=n;j++)
{
if(a[f[j][i-1]]<a[f[j+p[i-1]][i-1]])f[j][i]=f[j][i-1];
else f[j][i]=f[j+p[i-1]][i-1];
}
block=sqrt(n);
sort(t+1,t+m+1,cmp1);
for(int i=1;i<=n;i++)
{
while(l1.size()!=0&&a[l1.top()]>=a[i])l1.pop();
if(l1.size()!=0)pre[i]=l1.top();
l1.push(i);
}
while(l1.size()!=0)l1.pop();
for(int i=1;i<=n;i++)pre_f[i]=pre_f[pre[i]]+a[i]*(i-pre[i]);
l1.push(n+1),a[n+1]=-1e9-5;
for(int i=n;i>=1;i--)
{
while(l1.size()!=0&&a[l1.top()]>=a[i])l1.pop();
if(l1.size()!=0)las[i]=l1.top();
l1.push(i);
}
for(int i=n;i>=1;i--)las_f[i]=las_f[las[i]]+a[i]*(las[i]-i);
for(int i=1;i<=m;i++)
{
while(l>t[i].l)l--,pre_add(l,r);
while(r<t[i].r)r++,las_add(l,r);
while(l<t[i].l)pre_del(l,r),l++;
while(r>t[i].r)las_del(l,r),r--;
t[i].v=s;
}
sort(t+1,t+m+1,cmp2);
for(int i=1;i<=m;i++)printf("%lld\n",t[i].v);
return 0;
}
【ARC101F】 Robots and Exits
题目描述
现在有 \(n\) 个机器人和 \(m\) 个出口在一个数轴上，每个机器人和出口都有一个正整数坐标，并且这 \(n+m\) 个坐标都互不相同
现在执行若干次操作，每次操作可以是：
- 将所有机器人的坐标减一
- 将所有机器人的坐标加一
当一个机器人移到出口的的时候他就会消失
操作将进行直到所有机器人消失
两种操作序列不同，当且仅当存在至少一个机器人在两次操作序列进行完成后从不同的出口消失
给出每个机器人和出口的坐标，求有多少种不同的操作序列，输出方案数对 \(10^9+7\) 取模的结果
坐标 \(\leq10^9\)
\(1\leq n,m\leq 10^5\)
解题思路
首先每个机器人只可能从它左边第一个出口和它右边第一个出口出来，具体从哪个出要看向左移动的多还是向右移动的多。
我们可以求出每个机器人距离左边和右边的出口多远，设为 \(x_i\) 和 \(y_i\)，由于所有机器人是一起移动的，每次操作可以看做令所有 \(x_i\) 和 \(y_i\) 之一减 \(1\) ，当 \(x_i/y_i\) 中有一个到 \(0\) ，看做从左边 \(/\) 右边出来。
我们找一种映射方案，把这些机器人都放到坐标轴上，坐标为 \(x_i,y_i\)，那么每次操作都是将所有机器人同时往下 \(/\) 左走 \(1\) ，机器人走到 \(x/y\) 轴就代表从左 \(/\) 右出口出。
由于全部一起操作不好做，我们把机器人看成两条直线，为 \(x=x_i\) 与 \(y=y_i\) ，出口从 \((0,0)\) 出发向，碰到一个机器人的某一条直线就代表该机器人从该出口出去。
还是不好做，我们把机器人的 \(x_i,y_i\) 都减 \(0.5\) ，那么只要出口经过的轨迹在机器人之上，代表该机器人从右出口走了，否则就从左出口走了。
此时问题已经变成了一个二维偏序问题，为了去重，我们只需将轨迹紧贴着那些在它下面的点即可。
那么我们就可以做 \(dp\) 了，设 \(f_i\) 表示处理到 \(i\) 且 \(i\) 在轨迹之上的路线数，那么 \(f_i=\sum_{x_j<x_i,y_j<y_i}f_j\) ，答案即为 \(f_n\) 。
时间复杂度 \(O(nlogn)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
struct datay
{
long long x,y;
}a[500005];
long long n,m,b1[500005],b2[500005],f[500005],d[500005],s=1;
long long lowbit(long long x)
{
return x&(-x);
}
void modify(long long x,long long y)
{
for(int i=x;i<=n;i+=lowbit(i))f[i]=(f[i]+y)%mod;
return;
}
long long query(long long x)
{
long long h=0;
while(x)h=(h+f[x])%mod,x-=lowbit(x);
return h;
}
bool cmp1(datay q,datay w)
{
if(q.x!=w.x)return q.x<w.x;
return q.y>w.y;
}
bool cmp2(datay q,datay w)
{
return q.y<w.y;
}
bool cmp3(datay q,datay w)
{
if(q.x==0||q.y==0)return false;
if(w.x==0||w.y==0)return true;
return false;
}
int main()
{
long long x=0,y=0;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&b1[i]);
for(int i=1;i<=m;i++)scanf("%lld",&b2[i]);
sort(b1+1,b1+n+1),sort(b2+1,b2+m+1);
for(int i=1;i<=n;i++)
{
while(x<m&&b2[x+1]<=b1[i])x++;
if(x==0)a[i].x=0;
else a[i].x=b1[i]-b2[x];
}
x=m+1;
for(int i=n;i>=1;i--)
{
while(x>1&&b2[x-1]>=b1[i])x--;
if(x==m+1)a[i].y=0;
else a[i].y=b2[x]-b1[i];
}
sort(a+1,a+n+1,cmp3);
for(int i=1;i<=n;i++)
if(a[i].x<=0||a[i].y<=0){n=i-1;break;}
sort(a+1,a+n+1,cmp2),x=0;
for(int i=1;i<=n;i++)
{
if(a[i].y!=a[i-1].y)x++;
a[i-1].y=y,y=x;
}
a[n].y=x;
sort(a+1,a+n+1,cmp1);
for(int i=1;i<=n;i++)
{
if(a[i].x==a[i-1].x&&a[i].y==a[i-1].y)continue;
d[i]=query(a[i].y-1)+1;
modify(a[i].y,d[i]);
}
for(int i=1;i<=n;i++)s=(s+d[i])%mod;
cout<<s;
return 0;
}
杂题
【Luogu P10991】 选段排序
题目描述
给定一个长度为 \(n\) 的序列 \(A_i\) 以及两个下标 \(p, q(p < q)\)。你可以选择任意一个区间 \([L, R]\) 并将序列的这个范围内的元素 \(A_L \sim A_R\) 从小到大排序。
求选择一个区间排序后 \(A_q − A_p\) 的值最大可以是多少，\(1 \le n \le 2 \times 10^5,1 \le V \le 10^6\)。
解题思路
这题不好做贪心，我们来猜一下性质。
对于一个区间 \([l,r]\) ，满足 \(l<p\) 且 \(r>q\) ，那么这个区间 \([l,r]\) 肯定是不优的，感性理解即可，证明考虑反证法，发现缩小区间一定会比原来好，矛盾得证。
那对于区间 \([l,r]\) ，若同时包含了 \(p,q\) ，那么 \(l=p\) 或 \(r=q\) 。
对于 \(l>p\) 或 \(r<q\) 的区间，我们发现他们的答案是肯定小于等于 \(l=p+1\) 或 \(r=q-1\) 时的，而 \(l=p+1\) 或 \(r=q-1\) 时答案明显时不会比 \(l=p\) 或 \(r=q\) 时更优的，所以最大值所排的区间定有一端点为 \(p\) 或 \(q\) 。
我们用个数据结构维护即可，可以用优先队列，这里用了线段树，时间复杂度 \(O(nlogn)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
int n,k1,k2,a[200005],f[4000005],s,maxx;
void modify(int x,int l,int r,int k,int v)
{
if(l==r){f[x]+=v;return;}
int lc=(x<<1),rc=(x<<1)|1,mid=(l+r)>>1;
if(k<=mid)modify(lc,l,mid,k,v);
else modify(rc,mid+1,r,k,v);
f[x]=f[lc]+f[rc];
return;
}
int query(int x,int l,int r,int k)
{
if(l==r)return l;
int lc=(x<<1),rc=(x<<1)|1,mid=(l+r)>>1;
if(f[lc]<k)return query(rc,mid+1,r,k-f[lc]);
return query(lc,l,mid,k);
}
int main()
{
scanf("%d%d%d",&n,&k1,&k2);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),maxx=max(maxx,a[i]);
for(int i=k1;i<k2;i++)modify(1,1,maxx,a[i],1);
for(int i=k2;i<=n;i++)
{
modify(1,1,maxx,a[i],1);
s=max(s,query(1,1,maxx,k2-k1+1)-query(1,1,maxx,1));
}
memset(f,0,sizeof(f));
for(int i=k1+1;i<=k2;i++)modify(1,1,maxx,a[i],1);
for(int i=k1;i>=1;i--)
{
modify(1,1,maxx,a[i],1);
s=max(s,query(1,1,maxx,k2-i+1)-query(1,1,maxx,k1-i+1));
}
printf("%d",s);
return 0;
}
【ARC121D】 1 or 2
题目描述
你有 \(n\) 个糖果，第 \(i\) 个糖果的美味值为 \(a_i\)。
你需要吃糖，每次你可以选择吃 \(1\) 个或 \(2\) 个糖，并将你这一次吃的糖的总和写在黑板上。
你需要求出吃完所有糖果的所有可能的情况中，黑板上数字最大值和最小值之差最小是多少，\(1 \le n\le 5000\)。
解题思路
有两个操作不好处理，我们把这两个操作看成一个操作。
我们思考一下，每次只吃一个糖相当于吃了一个糖和吃了一棵为 \(0\) 的糖，这样我们可以将吃 \(1\) 个糖的操作转化为吃 \(2\) 个糖。
考虑每次如果吃两个糖怎样最优，肯定是一头一尾的吃最好。
我们每次枚举有多少颗为 \(0\) 的糖，再遍历一遍即可，时间复杂度 \(O(n^2)\)。
Code
#include<bits/stdc++.h>
using namespace std;
long long n1,n2,n,m,a1[5005],a2[5005],t[10005],maxx,minn,s=2e9;
int main()
{
long long x;
scanf("%lld",&n);
if(n==1){cout<<0;return 0;}
for(int i=1;i<=n;i++)
{
scanf("%lld",&x);
if(x<=0)a1[++n1]=x;
else a2[++n2]=x;
}
sort(a1+1,a1+n1+1);
sort(a2+1,a2+n2+1);
for(int i=((n-1)/2+1)*2;i<=2*n;i+=2)
{
m=0,maxx=-2e9,minn=2e9;
for(int j=1;j<=n1;j++)t[++m]=a1[j];
for(int j=1;j<=i-n;j++)t[++m]=0;
for(int j=1;j<=n2;j++)t[++m]=a2[j];
for(int j=1;j<=m/2;j++)maxx=max(maxx,t[j]+t[m-j+1]),minn=min(minn,t[j]+t[m-j+1]);
s=min(maxx-minn,s);
}
cout<<s;
return 0;
}
【ARC108F】 Paint Tree
题目描述
给定一棵 \(n\) 个节点的树。你需要对每个节点黑白染色。
设 \(x\) 表示白色点之间的最大距离，\(y\) 表示黑色点之间的最大距离，那么定义一种染色的权值为 \(\max(x,y)\)。如果某种颜色没有出现那么对应的 \(x/y\) 就是 \(0\)。
求所有 \(2^n\) 种染色方式的权值和。对 \(10^9+7\) 取模。
\(\texttt{Data Range:} 2\le n\le 2\times 10^5\)。
解题思路
我们分开枚举每一种情况，设 \(g_i\) 为最大距离为 \(i\) 的方案数，那么答案就为 \(\sum_{i=1}^n g_i \times i\) 。
\(g_i\) 明显不好处理，我们用容斥解决 ，设 \(f_i\) 为最大距离小于等于 \(i\) 的方案数，那么 \(g_i=f_i-f_{i-1}\) 。
\(f_i\) 如何求出？我们发现一个性质，对于任意一棵树，其最远距离的一对点之中必有一个为直径的一端。
根据这个性质，那么若当前最远距离为 \(k\) ，那么距离两个直径端点距离都小于等于 \(k\) 的肯定没影响，大于 \(k\) 的只需和离它近的那个直径端点颜色一样即可。
设 \(cnt_i\) 表示距离直径两端都小于等于 \(i\) 的点个数，那么 \(f_i=2^{cnt_i}\) 。
设 \(x,y\) 为直径两端， \(L=max_{i=1}^n min(dis(i,x),dis(i,y))\) ，那么对于 \(i<L\) ，\(f_i=0\) 。
时间复杂度 \(O(nlogn)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
int n,deep[200005],f[200005][21],root,root1,l;
long long d[200005],p2[200005],s;
vector<int> a[200005];
int LCA(int x,int y)
{
if(deep[x]<deep[y])swap(x,y);
for(int i=20;i>=0;i--)x=(deep[f[x][i]]>=deep[y]?f[x][i]:x);
if(x==y)return x;
for(int i=20;i>=0;i--)x=(f[x][i]!=f[y][i])?f[x][i]:x,y=(deep[x]!=deep[y]?f[y][i]:y);
return f[x][0];
}
int dis(int x,int y)
{
return deep[x]+deep[y]-2*deep[LCA(x,y)];
}
void dfs1(int x,int y)
{
deep[x]=deep[y]+1,f[x][0]=y;
if(deep[root]<deep[x])root=x;
for(int i=0;i<a[x].size();i++)
if(a[x][i]!=y)dfs1(a[x][i],x);
return;
}
int main()
{
int x,y;
scanf("%d",&n),p2[0]=1;
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
}
dfs1(1,0),root1=1;
for(int i=1;i<=20;i++)
for(int j=1;j<=n;j++)f[j][i]=f[f[j][i-1]][i-1];
for(int i=1;i<=n;i++)
if(dis(root,root1)<dis(root,i))root1=i;
for(int i=1;i<=n;i++)
{
if(i==root||i==root1)continue;
d[max(dis(root,i),dis(root1,i))]++;
l=max(l,min(dis(root,i),dis(root1,i)));
}
for(int i=1;i<=n;i++)d[i]+=d[i-1];
for(int i=1;i<=n;i++)p2[i]=p2[i-1]*2%mod;
s=(p2[d[l]]*l%mod);
for(int i=l+1;i<=n;i++)s=(s+(p2[d[i]]-p2[d[i-1]])*i%mod)%mod;
printf("%lld",((s+mod)*2+dis(root,root1)*p2[n-1]%mod)%mod);
return 0;
}
【MXOI 11.23 T2】 交换
题目描述
有一个长度为 \(n\) 的整数数组 \(a_{0...n-1}\) 和一个长度为 \(m\) 的操作序列 \((b_0,c_0)...(b_{m-1},c_{m-1})\) 。
你需要执行 \(t\) 次操作，第 \(i\) 次操作（操作从 \(1\) 开始编号）形如：\(swap(a_{(b_{i \% m}+i)\% n},a_{(c_{i \% m}+i)\% n} )\) 。
输出 \(t\) 次操作后的序列。
解题思路
我们先来考虑没有 \(+i\) 该如何做，我们发现，每次都是在重复执行 \(m\) 此操作，我们可以把这 \(m\) 次操作的结果处理出来，同时用快速幂重复处理 \(\frac{k}{m}\) 次，最后把 $k %m $ 个操作再处理一遍，时间复杂度 \(O(nlogk)\) 。
此题每次操作的位置要后移当前操作次数位 ，那么每次执行的操作变不同了，我们考虑在原来的做法上优化。
注意到第二组 \(m\) 个操作相对于第一组 \(m\) 个操作的位置只是后移了 \(m\) 位，那我们可以把一组操作再后移 \(m\) 位看做新的一组操作，这样就可以用快速幂优化了，算完再减回来即可。
时间复杂度 \(O(nlogk)\) 。
Code
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
struct datay
{
long long x,y;
}t[100005];
long long n,m,k,b[100005],f[100005],a[100005],d[100005],i;
int main()
{
long long x,y;
scanf("%lld%lld%lld",&n,&m,&k),x=k/m,y=((k/m)-1)*m;
for(i=0;i<n;i++)scanf("%lld",&b[i]),f[i]=a[i]=i;
for(i=0;i<m;i++)scanf("%lld%lld",&t[i].x,&t[i].y);
for(i=1;i<=m;i++)swap(a[(t[i%m].x+i+y)%n],a[(t[i%m].y+i+y)%n]);
for(i=0;i<n;i++)a[i]=(a[i]+m)%n;
while(x)
{
if(x&1)
{
for(i=0;i<n;i++)d[i]=f[a[i]];
for(i=0;i<n;i++)f[i]=d[i];
}
for(i=0;i<n;i++)d[i]=a[a[i]];
for(i=0;i<n;i++)a[i]=d[i];
x>>=1;
}
for(i=(k/m)*m+1;i<=k;i++)swap(f[(t[i%m].x+i%n)%n],f[(t[i%m].y+i%n)%n]);
for(i=0;i<n;i++)f[i]=(f[i]-((k/m)*m)%n)%n,f[i]=(f[i]+n)%n;
for(i=0;i<n;i++)printf("%lld ",b[f[i]]);
return 0;
}
【Luogu P10833】 下 Niz
题目描述
给定长度为 \(N\) 的序列 \(a\)，求满足以下条件的 \((l,r)\) 对数：
- \(1\le l\le r\le N\)；
- \(a_l,a_{l+1},\cdots,a_{r-1},a_r\) 是 \(1\sim r-l+1\) 的排列。
\(1 \le N \le 10^6\)
解题思路
手玩一些样例后发现答案其实不多，我们考虑找弱化条件来找每一个区间。
我们考虑满足这样条件的区间 \([l,r]\) ：\([l,r]\) 内只包含一个 \(1\) ，并且满足区间长度 \(r-l+1=\) 区间最大值，这是题目要求的弱化条件，满足题目要求的区间一定满足该条件。
由于区间内只能有一个 \(1\) ，我们以 \(1\) 作为划分序列的方式，要求每个区间左右端点 \(l,r\) 必须在相邻的两段中，满足第一个条件。
由于区间长度 \(=\) 区间最大值，确定最大值与一个端点即能确定一个区间，我们可以从一个 \(1\) 开始往左右做单调栈，处理出每一位到 \(1\) 的最大值来确定区间，可以证明这样找出的区间数不超过 \(2N\)。
我们还需检查这些区间是否满足题目要求，用线段树存每个值最后出现的位置，用线段树二分求出区间 \([l,r]\) 的 \(mex\) 值来检验。
时间复杂度 \(O(nlogn)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
struct datay
{
int l,r;
}t[2000005];
int n,a[1000005],pre[1000005],las[1000005],m,s,f[4000005];
vector<int> l1;
stack<int> l;
bool cmp1(datay q,datay w){return q.r<w.r;}
void modify(int x,int l,int r,int k,int v)
{
if(l==r){f[x]=v;return;}
int lc=(x<<1),rc=(x<<1)|1,mid=(l+r)>>1;
if(k<=mid)modify(lc,l,mid,k,v);
else modify(rc,mid+1,r,k,v);
f[x]=min(f[lc],f[rc]);
return;
}
int query(int x,int l,int r,int k)
{
if(l==r)return l-(f[x]<k);
int lc=(x<<1),rc=(x<<1)|1,mid=(l+r)>>1;
if(f[lc]>=k)return query(rc,mid+1,r,k);
return query(lc,l,mid,k);
}
int query1(int x,int l,int r,int k)
{
if(l==r)return f[x];
int mid=(l+r)>>1;
if(k<=mid)return query1((x<<1),l,mid,k);
return query1((x<<1)|1,mid+1,r,k);
}
int main()
{
int x,q,w,y;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]==1)l1.push_back(i);
}
a[0]=a[n+1]=n+2,l.push(0),s=-l1.size();
for(int i=1;i<=n;i++)
{
while(l.size()&&a[l.top()]<=a[i])l.pop();
pre[i]=l.top();
l.push(i);
}
while(l.size())l.pop();
l.push(n+1);
for(int i=n;i>=1;i--)
{
while(l.size()&&a[l.top()]<=a[i])l.pop();
las[i]=l.top();
l.push(i);
}
for(int i=0;i<l1.size();i++)
{
x=l1[i];
if(i!=0)q=l1[i-1];
else q=0;
if(i!=l1.size()-1)w=l1[i+1];
else w=n+1;
while(x>q)
{
y=x,x=pre[x];
for(int j=max(x,q)+1;j<=y;j++)t[++m].l=j,t[m].r=(j+a[y]-1);
}
x=l1[i];
while(x<w)
{
y=x,x=las[x],q=min(x,w);
for(int j=y;j<q;j++)t[++m].l=j-a[y]+1,t[m].r=j;
}
}
sort(t+1,t+m+1,cmp1);
for(int i=1;i<=m;i++)
{
if(t[i].r>n)break;
for(int j=t[i-1].r+1;j<=t[i].r;j++)modify(1,1,n,a[j],j);
if(t[i].l>=1&&query(1,1,n,t[i].l)>=t[i].r-t[i].l+1)s++;
}
printf("%d",s);
return 0;
}
【CF442C】 Artem and Array
题目描述
给定长度为 \(n\) 的数组 \(a\) ，你需要进行 \(n\) 次操作：删去某一元素 \(a_i\) ，并获得 \(\min\{a_{i-1}, a_{i+1}\}\) 的分数。若不存在 \(a_{i-1}\) 或 \(a_{i+1}\)，则此次操作不得分。
请你计算至多能得到多少分。
\(1\leq n \leq 5*10^5\)
\(1 \leq a_i \leq 10^6\)
解题思路
对于三个数 \(a_{i-1},a_i,a_{i+1}\) ，若 \(a_{i-1}>=a_i\) 且 \(a_{i+1}>=a_i\) ，很明显一定先可以先删 \(a_i\) 。
先对一遍数列中的每个数都做一次这个操作，删完后的数列再不断的重复，最后可以发现，若一个数 \(a_i\) 存在 \(j<i,a_j>=a_i\) 且 \(u>i,a_u>=a_i\) ，那么这个数一定会被删掉。
我们可以在每读入一个数就判断 \(V\) 字形结构并删除，那么删完后的数列一定是呈现先递增后递减的结构，此时我们只用从顶点开始贪心从上往下删即可。
时间复杂度 \(O(n)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
long long n,a[5000005],s;
vector<long long> l1;
int main()
{
scanf("%lld",&n);
if(n==1){printf("0");return 0;}
scanf("%lld%lld",&a[1],&a[2]);
for(int i=3;i<=n;i++)
{
scanf("%lld",&a[i]);
while(i>=2&&a[i-2]>=a[i-1]&&a[i-1]<=a[i])s+=min(a[i-2],a[i]),a[i-1]=a[i],n--,i--;
}
sort(a+1,a+n+1);
for(int i=1;i<=n-2;i++)s+=a[i];
cout<<s;
return 0;
}