11 月杂题
其实大部分都是佳老师图论专题的题，但是万一做了其他题呢？所以还是叫杂题。
CF1163F Indecisive Taxi Fee
题意很友好，需要注意虽然保证 \(1,n\) 连通，但不保证整张图连通。
首先容易发现修改一条边后，只有两种情况：
- 新的最短路包含这条边。
- 新的最短路不包含这条边。
这不是废话吗
容易发现第一种就是起点到一端点的最短路加上边权加上另一端点到终点的最短路，这个很简单，预处理起点和终点的单源最短路即可。
然后第二种情况，这个是个最短路树的常见技巧，即删边最短路。
这个可以参考我的这篇博客。
然后就做完了，复杂度 \(O(m\log m+m\log^2n+q)\)。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=2e5+5,inf=1e18;
i64 n,m,q,ans[N],co[N];
struct edge{
i64 v,w,pos;
};
vector<edge> e[N];
vector<i64> son[N],st[N],ed[N];
struct Node{
i64 dis,u;
bool operator <(const Node &r)const{return dis>r.dis;}
};
i64 vis[N],dis[2][N],ff[N],fp[N];
pii sv[N];
void dijkstra(i64 s,i64 p){
forup(i,1,n){
dis[p][i]=inf;
vis[i]=0;
}
priority_queue<Node> q;
dis[p][s]=0;ff[s]=0;
q.push(Node{0,s});
while(q.size()){
i64 u=q.top().u;q.pop();
if(vis[u]) continue;
vis[u]=1;
for(auto i:e[u]){
i64 v=i.v,w=i.w;
if(dis[p][v]>dis[p][u]+w){
dis[p][v]=dis[p][u]+w;
ff[v]=u;fp[v]=i.pos;
q.push(Node{dis[p][v],v});
}
}
}
}
i64 f[N][19],dpt[N];
void dfs(i64 x,i64 fa){
dpt[x]=dpt[fa]+1;
f[x][0]=fa;
forup(i,1,18){
f[x][i]=f[f[x][i-1]][i-1];
}
for(auto i:son[x]){
dfs(i,x);
}
}
i64 lca(i64 x,i64 y){
if(dpt[x]>dpt[y]) swap(x,y);
for(i64 i=18;i>=0&&dpt[y]>dpt[x];--i){
if(dpt[f[y][i]]>=dpt[x]){
y=f[y][i];
}
}
if(x==y) return x;
for(i64 i=18;i>=0&&f[x][0]!=f[y][0];--i){
if(f[x][i]!=f[y][i]){
x=f[x][i];y=f[y][i];
}
}
return f[x][0];
}
multiset<i64> ss[N];
i64 mp[N];
void merge(i64 u,i64 v){
if(ss[mp[u]].size()<ss[mp[v]].size()) swap(mp[u],mp[v]);
for(auto i:ss[mp[v]]){
ss[mp[u]].insert(i);
}
}
void dfs2(i64 x){
ss[mp[x]].clear();
for(auto i:son[x]){
dfs2(i);
if(ss[mp[i]].size()) ans[fp[i]]=*ss[mp[i]].begin();
merge(x,i);
}
for(auto i:st[x]){
ss[mp[x]].insert(i);
}
for(auto i:ed[x]){
ss[mp[x]].erase(ss[mp[x]].find(i));
}
}
signed main(){
n=read();m=read();q=read();
forup(i,1,m){
ans[i]=inf;
i64 u=read(),v=read(),w=read();
e[u].push_back(edge{v,w,i});
e[v].push_back(edge{u,w,i});
sv[i]=mkp(u,v);
}
dijkstra(1,0);dijkstra(n,1);
forup(i,1,n){
if(ff[i]){
son[ff[i]].push_back(i);
}
}
dfs(n,0);
forup(u,1,n){
if(dis[0][u]==inf) continue;
for(auto i:e[u]){
i64 v=i.v,w=i.w;
if(i.pos==fp[u]||i.pos==fp[v]) continue;
i64 y=lca(u,v);
st[u].push_back(dis[0][u]+w+dis[1][v]);ed[y].push_back(dis[0][u]+w+dis[1][v]);
}
}
forup(i,1,n){
mp[i]=i;
}
dfs2(n);
for(int i=1;i!=n;i=ff[i]){
co[fp[i]]=1;
}
forup(i,1,q){
i64 t=read(),v=read();
if(dis[0][sv[t].fi]==inf){
printf("%lld\n",dis[0][n]);
continue;
}
i64 res=min({ans[t],dis[0][sv[t].fi]+dis[1][sv[t].se]+v,dis[1][sv[t].fi]+dis[0][sv[t].se]+v});
if(!co[t]) res=min(res,dis[0][n]);
printf("%lld\n",res);
}
}
P2619 [国家集训队] Tree I
P5633 最小度限制生成树
容易发现把对应点周围的边涂成白色，其余涂成黑色就是上一道题。
但是有个问题，如何判无解。
其实很简单，容易发现有解的必定是一段连续的区间，因为每次变化只删一条边加一条边，不可能突然多两条白边。判一下 \(k\) 是不是在区间内即可。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
using i64=long long;
using namespace std;
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=5e4+5,M=5e5+5,inf=0x3f3f3f3f;
i64 n,m,s,ned;
struct edge{
i64 u,v,w,c;
}e[M];
i64 fa[N];
i64 getfa(i64 x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
bool cmp(edge a,edge b){
if(a.w!=b.w) return a.w<b.w;
return a.c>b.c;
}
i64 val=0;
bool chk(i64 mm){
forup(i,1,m){
if(e[i].c==0) e[i].w-=mm;
}
sort(e+1,e+m+1,cmp);
forup(i,1,n){
fa[i]=i;
}
val=0;
i64 tmp=0;
forup(i,1,m){
i64 u=e[i].u,v=e[i].v,w=e[i].w,c=e[i].c;
i64 fu=getfa(u),fv=getfa(v);
if(fu==fv) continue;
fa[fu]=fv;
val+=w;
if(c==0) ++tmp;
}
forup(i,1,m){
if(e[i].c==0) e[i].w+=mm;
}
return tmp>ned;
}
signed main(){
n=read();m=read();s=read();ned=read();
i64 cnt=0;
forup(i,1,m){
e[i].u=read();e[i].v=read();e[i].w=read();
if(e[i].u==s||e[i].v==s){
e[i].c=0;++cnt;
}else{
e[i].c=1;
}
}
if(cnt<ned||chk(-30005)){
puts("Impossible");
return 0;
}
i64 ll=-30005,rr=30005,mm,ans=0;
while(ll<rr){
mm=ll+(rr-ll+1)/2;
if(chk(mm)){
rr=mm-1;
}else{
ll=mm;ans=val+mm*ned;
}
}
printf("%lld\n",ans);
}
P4180 [BJWC2010] 严格次小生成树
最小生成树很好求，容易发现任意生成树都能由最小生成树删若干条边加同样多条边得到。
容易证明严格次小生成树能由最小生成树删恰好一条边加恰好一条边得到，考虑如果你删了两条边并且加了两条边，并且两个操作都使总边权改变。若它们在同一个环上等价于删一条加一条，若不在可以考虑去掉去掉其中一个操作，由于原先是最小生成树，只操作一次权值肯定比操作两次小。
那么就可以枚举每一条非树边考虑加上它，然后减去对应环上的边最少让总权值增加多少。因为要严格次小所以还要维护树链上次大值。这个可以树剖或者倍增。
参考代码
///很久以前写的，马蜂和现在可能有些微差别
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
#define mkp(a,b) make_pair((a),(b))
using namespace std;
using i64=long long;
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=1e5+5,M=3e5+5,inf=1e18;
i64 n,m;
struct edge{
i64 v,w;
};
vector<edge> e[N];
struct EDGE{
i64 u,v,w;
bool operator <(const EDGE &r)const{return w>r.w;}
};
priority_queue<EDGE> q;
vector<EDGE> E;
i64 fa[N];
i64 getfa(i64 x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
i64 f[N][20],fmx[N][20],fsec[N][20],dpt[N];
void dfs(i64 x,i64 fa){
f[x][0]=fa;dpt[x]=dpt[fa]+1;
forup(i,1,19){
f[x][i]=f[f[x][i-1]][i-1];
if(fmx[x][i-1]==fmx[f[x][i-1]][i-1]){
fmx[x][i]=fmx[x][i-1];
fsec[x][i]=max(fsec[x][i-1],fsec[f[x][i-1]][i-1]);
}else{
fmx[x][i]=max(fmx[x][i-1],fmx[f[x][i-1]][i-1]);
fsec[x][i]=min(fmx[x][i-1],fmx[f[x][i-1]][i-1]);
}
}
for(auto i:e[x]){
if(i.v==fa) continue;
fmx[i.v][0]=i.w;
dfs(i.v,x);
}
}
struct pii{
i64 mx,sec;
pii(){
mx=-inf;sec=-inf;
}
pii& operator ()(i64 QAQ){
if(QAQ==mx||QAQ==sec) return *this;
if(QAQ>mx){
sec=mx;mx=QAQ;
}else if(QAQ>sec){
sec=QAQ;
}
return *this;
}
};
pii lca(i64 x,i64 y){
pii res;
if(dpt[x]>dpt[y]) swap(x,y);
for(i64 i=19;i>=0&&dpt[y]>dpt[x];i--){
if(dpt[f[y][i]]>=dpt[x]){
res(fmx[y][i])(fsec[y][i]);
y=f[y][i];
}
}
if(x==y) return res;
for(i64 i=19;i>=0&&f[x][0]!=f[y][0];i--){
if(f[x][i]!=f[y][i]){
res(fmx[x][i])(fmx[y][i])(fsec[x][i])(fsec[y][i]);
x=f[x][i];y=f[y][i];
}
}
res(fmx[x][0])(fmx[y][0])(fsec[x][0])(fsec[y][0]);
return res;
}
signed main(){
n=read();m=read();
forup(i,1,m){
i64 u=read(),v=read(),w=read();
q.push(EDGE{u,v,w});
}
forup(i,1,n){
fa[i]=i;
}
i64 ans=0;
while(q.size()){
i64 u=q.top().u,v=q.top().v,w=q.top().w;q.pop();
i64 fu=getfa(u),fv=getfa(v);
if(fu==fv){
E.push_back(EDGE{u,v,w});
continue;
}
fa[fu]=fv;
e[u].push_back(edge{v,w});
e[v].push_back(edge{u,w});
ans+=w;
}
forup(i,1,n){
forup(j,0,19){
fmx[i][j]=fsec[i][j]=-inf;
}
}
dfs(1,0);
i64 res=inf;
for(auto i:E){
i64 u=i.u,v=i.v,w=i.w;
pii get=lca(u,v);
if(get.mx==w){
res=min(res,ans-get.sec+w);
}else{
res=min(res,ans-get.mx+w);
}
}
printf("%lld",res);
}
CF152E Garden
斯坦纳树板题。
首先如果按四联通建图，显然选出来的应该是一棵树（其实因为这道题统计的是点权貌似不按树统计也行，但是按树统计要方便一些），不然可以考虑换成选你选出来的东西的最小生成树。
考虑 DP，设 \(dp_{msk,i}\) 表示考虑一棵以 \(i\) 为根的树，包含 \(msk\) 内的关键点，需要的最小代价。
考虑如何转移，对于第一维就是一个子集枚举，不用担心后效性。但是第二维有后效性，怎么办呢？容易发现这是一个类似于最短路的东西，可以考虑用类似于 Bellman 的算法做。具体来说先枚举第一维做子集枚举，然后对于第二维可以松弛每条边 \(nm\) 次，这样就能保证一个点的最短路传到其余所有点了。由于只统计最小值，必定能找到一个地方没算重，然后就做完了，复杂度 \(O(n^2m^23^k)\)。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=105,inf=0x3f3f3f3f;
int n,m,k,a[N][N],dp[N][N][1<<7|5];
struct Node{
int x,y,msk;
}pre[N][N][1<<7|5];
vector<int> e[N];
int nxt[4][2]={
{0,1},{1,0},{0,-1},{-1,0}
};
int res=-1;
int ans[N][N];
void gans(int x,int y,int msk){
ans[x][y]=1;
if(pre[x][y][msk].x==0) return;
if(pre[x][y][msk].msk==msk){
gans(pre[x][y][msk].x,pre[x][y][msk].y,msk);
}else{
gans(x,y,pre[x][y][msk].msk);
gans(x,y,pre[x][y][msk].msk^msk);
}
}
signed main(){
n=read();m=read();k=read();
mem(dp,0x3f);
forup(i,1,n){
forup(j,1,m){
dp[i][j][0]=0;
a[i][j]=read();
}
}
forup(i,1,k){
int x=read(),y=read();
dp[x][y][1<<(i-1)]=a[x][y];
pre[x][y][1<<(i-1)]=Node{0,0,0};
}
forup(msk,1,(1<<k)-1){
forup(x,1,n){
forup(y,1,m){
for(int s1=(msk-1)&msk;s1;s1=(s1-1)&msk){
int s2=msk^s1;
if(dp[x][y][s1]+dp[x][y][s2]-a[x][y]<dp[x][y][msk]){
dp[x][y][msk]=dp[x][y][s1]+dp[x][y][s2]-a[x][y];
pre[x][y][msk]=Node{x,y,s1};
}
}
}
}
forup(T,1,n*m+10){
forup(x,1,n){
forup(y,1,m){
forup(i,0,3){
int nx=x+nxt[i][0],ny=y+nxt[i][1];
if(nx<0||nx>n||ny<0||ny>m) continue;
if(dp[x][y][msk]+a[nx][ny]<dp[nx][ny][msk]){
dp[nx][ny][msk]=dp[x][y][msk]+a[nx][ny];
pre[nx][ny][msk]=Node{x,y,msk};
}
}
}
}
}
}
Node res=Node{0,0,0};
forup(x,1,n){
forup(y,1,m){
if(res.x==0||dp[x][y][(1<<k)-1]<dp[res.x][res.y][res.msk]){
res=Node{x,y,(1<<k)-1};
}
}
}
printf("%d\n",dp[res.x][res.y][res.msk]);
gans(res.x,res.y,res.msk);
forup(i,1,n){
forup(j,1,m){
putchar(ans[i][j]?'X':'.');
}
puts("");
}
}
CF1697F Too Many Constraints
这个问题乍一看像差分约束（ 其实我按差分约束想了 20min ），后面发现其实更像 k-sat 问题，但 k-sat 是 NPC 问题， 所以我们考虑跳过这道题 。
考虑条件 \(3\)，即 \(a_i+a_j\ge x\)，容易发现这等价于对于每一对 \((p,q)\) 使得 \(p+q=x+1\)，必定有 \(a_i\ge p\) 或者 \(a_j\ge q\)，因为如果 \(a_i<p\) 且 \(a_j<q\) 显然 \(a_i+a_j\le p+q-2\)（因为是整数），对于条件 \(2\) 是类似的。那么这就能转化成一个 2-sat 问题了。
那么考虑对于每个 \(i\) 建 \(k+1\) 个点，其中 \((i,j)\) 表示 \(a_i\ge j\) 是否成立，然后建边是简单的，需要注意 \((i,1)\) 必定取 \(1\)，以及 \((1,k+1)\) 必定取 \(0\)，以及要求序列单调不减，其余略过。
为什么要建 \(k+1\) 个点呢？因为对于一个条件 \(3\)，当 \(a_i\) 取到 \(k\) 的上界时，\(a_j\) 必须大于等于 \(x+1-k\)，这个限制需要用到 \(k+1=0\)。
复杂度 \(O(nk+q)\)。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e4+5,inf=0x3f3f3f3f;
int t,n,m,k;
vector<int> e[N*11*2];
int gnum(int i,int j,int f){
return (i-1)*k+j+f*n*k;
}
int dfn[N*11*2],low[N*11*2],Tm,blg[N*11*2],csc,ist[N*11*2];
stack<int> stk;
void Tarjan(int x){
low[x]=dfn[x]=++Tm;
stk.push(x);ist[x]=1;
for(auto i:e[x]){
if(!dfn[i]){
Tarjan(i);
low[x]=min(low[x],low[i]);
}else if(ist[i]){
low[x]=min(low[x],dfn[i]);
}
}
if(dfn[x]==low[x]){
++csc;
while(stk.top()!=x){
ist[stk.top()]=0;
blg[stk.top()]=csc;
stk.pop();
}
ist[stk.top()]=0;
blg[stk.top()]=csc;
stk.pop();
}
}
void solve(){
n=read();m=read();k=read()+1;
forup(i,1,n*k*2){
e[i].clear();
dfn[i]=low[i]=ist[i]=blg[i]=0;
}
Tm=csc=0;
forup(i,1,n){
forup(j,1,k-1){
e[gnum(i,j+1,1)].push_back(gnum(i,j,1));
e[gnum(i,j,0)].push_back(gnum(i,j+1,0));
}
e[gnum(i,1,0)].push_back(gnum(i,1,1));
e[gnum(i,k,1)].push_back(gnum(i,k,0));
}
forup(i,1,n-1){
forup(j,1,k){
e[gnum(i,j,1)].push_back(gnum(i+1,j,1));
e[gnum(i+1,j,0)].push_back(gnum(i,j,0));
}
}
forup(Case,1,m){
int op=read();
if(op==1){
int p=read(),x=read();
if(x<k){
e[gnum(p,x,1)].push_back(gnum(p,x+1,1));
e[gnum(p,x+1,0)].push_back(gnum(p,x,0));
}else{
e[gnum(p,x,1)].push_back(gnum(p,x,0));
}
}else if(op==2){
int p=read(),q=read(),x=read();
forup(i,1,k){
int j=x+1-i;
if(j<1||j>k) continue;
e[gnum(p,i,1)].push_back(gnum(q,j,0));
e[gnum(q,j,1)].push_back(gnum(p,i,0));
}
}else{
int p=read(),q=read(),x=read();
forup(i,1,k){
int j=x+1-i;
if(j<1||j>k) continue;
e[gnum(p,i,0)].push_back(gnum(q,j,1));
e[gnum(q,j,0)].push_back(gnum(p,i,1));
}
}
}
forup(i,1,n*k*2){
if(!dfn[i]) Tarjan(i);
}
forup(i,1,n){
forup(j,1,k){
if(blg[gnum(i,j,0)]==blg[gnum(i,j,1)]){
puts("-1");
return;
}
}
}
forup(i,1,n){
int ans=0;
while(ans<k&&blg[gnum(i,ans+1,1)]<blg[gnum(i,ans+1,0)]) ++ans;
printf("%d ",ans);
}
puts("");
}
signed main(){
t=read();
while(t--){
solve();
}
}
P3209 [HNOI2010] 平面图判定
首先有一个经典结论，对于任意平面图，有 \(|E|\le 3|V|+6\)。
首先我们知道欧拉公式 \(|V|+|F|-|E|=2\)，然后容易发现一个面附近至少有 \(3\) 条边，一条边附近至多有 \(2\) 个面，即 \(3|F|\le 2|E|\)，然后解个不等式可以得到 \(|E|\le 3|V|+6\)。
那么对于 \(m>3n+6\) 可以直接输出无解，就把边数压到 \(O(n)\) 级别了。
考虑哈密顿回路它自己肯定是能铺成平面图的，铺成一个环即可。那么对于一条不在哈密顿回路上的边，它显然可以放到环内侧或外侧。容易想到有一些边是不能放到同一侧的，即“\(a\) 在内测且 \(b\) 在外侧”和“\(a\) 在外侧且 \(b\) 在内测”至少要成立一个，那么直接对边的内外做 2-sat 即可。
复杂度 \(O(n^2)\)（因为你要 \(m^2\) 地找不能在同一侧的环，但是 \(m\) 是 \(O(n)\) 级别的）。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=205,inf=0x3f3f3f3f;
int t,n,m;
int grp[N][N];
vector<int> e[N*6];
int seq[N],mp[N];
struct Node{
int l,r,pos;
};
vector<Node> vec;
int dfn[N*3*2],low[N*3*2],Tm,blg[N*3*2],csc,ist[N*3*2];
stack<int> stk;
void Tarjan(int x){
low[x]=dfn[x]=++Tm;
stk.push(x);ist[x]=1;
for(auto i:e[x]){
if(!dfn[i]){
Tarjan(i);
low[x]=min(low[x],low[i]);
}else if(ist[i]){
low[x]=min(low[x],dfn[i]);
}
}
if(dfn[x]==low[x]){
++csc;
while(stk.top()!=x){
ist[stk.top()]=0;
blg[stk.top()]=csc;
stk.pop();
}
ist[stk.top()]=0;
blg[stk.top()]=csc;
stk.pop();
}
}
bool solve(){
n=read();m=read();
forup(i,1,n){
forup(j,1,n){
grp[i][j]=0;
}
}
forup(i,1,m){
int u=read(),v=read();
grp[u][v]=grp[v][u]=i;
}
forup(i,1,n){
seq[i]=read();
mp[seq[i]]=i;
}
if(m>n*3-6) return false;
forup(i,1,n-1){
grp[seq[i]][seq[i+1]]=grp[seq[i+1]][seq[i]]=0;
}
grp[seq[n]][seq[1]]=grp[seq[1]][seq[n]]=0;
vec.clear();
forup(i,1,m*2){
e[i].clear();
blg[i]=dfn[i]=ist[i]=low[i]=0;
}
Tm=csc=0;
forup(i,1,n-1){
forup(j,i+1,n){
if(grp[i][j]){
vec.push_back(Node{mp[i],mp[j],grp[i][j]});
}
}
}
int sz=vec.size();
forup(i,0,sz-1){
if(vec[i].l>vec[i].r) swap(vec[i].l,vec[i].r);
}
forup(i,0,sz-2){
forup(j,i+1,sz-1){
if((vec[i].l<vec[j].l&&vec[j].l<vec[i].r&&vec[i].r<vec[j].r)||(vec[j].l<vec[i].l&&vec[i].l<vec[j].r&&vec[j].r<vec[i].r)){
int pi=vec[i].pos,pj=vec[j].pos;
e[pi].push_back(pj+m);
e[pi+m].push_back(pj);
e[pj].push_back(pi+m);
e[pj+m].push_back(pi);
}
}
}
forup(i,1,m*2){
if(!dfn[i]) Tarjan(i);
}
forup(i,1,m){
if(blg[i]==blg[i+m]) return false;
}
return true;
}
signed main(){
t=read();
while(t--){
puts(solve()?"YES":"NO");
}
}
QOJ#5504 Flower Garden
题面太不友好了，这里概括一下：
- 给定 \(n\)，你需要构造一个长为 \(3n\) 的 \(01\) 序列。
- 有 \(m\) 个限制，形如 \(([l_1,r_1],[l_2,r_2])\) 表示 \([l_1,r_1]\) 全为 \(0\) 和 \([l_2,r_2]\) 全为 \(1\) 必须满足一个。
- 要求序列里 \(0,1\) 的数量均必须在 \([n,2n]\) 之间。
- 随便输出一个方案。
容易发现它的限制长得很像 2-sat，考虑先按 2-sat 做。
那么要连的边就是 \(([l_1,r_1],1)\to ([l_2,r_2],1)\) 和 \(([l_2,r_2],0)\to ([l_1,r_1],0)\)。
对于区间连区间，可以考虑线段树优化建图。由于区间连区间是不好做的，可以新建一个点然后两个区间都向这个点连边。
容易发现如果只考虑这些限制，显然是有解的（比如可以全填 \(1\)），因为 \(0,1\) 其实是两张独立的图。这时候可以考虑只建 \(0\) 的图。那么问题就转化成了你有一个 DAG，点权总和为 \(3n\)，然后要选择任意一个拓扑序的前缀，使得选出来的点权总和在 \([n,2n]\) 之间。
首先若所有点点权都在 \([0,n]\) 中，随便找一个拓扑序的前缀即可，因为点权总和不可能从小于 \(n\) 突变到大于 \(2n\)。如果有一个点点权大于 \(2n\)，那显然无解，因为选它也不是不选它也不是。
考虑存在点点权在 \((n,2n]\) 区间中的情况。这个很简单，求出不包含它的最大前缀（算拓扑序时不考虑这个点即可），和包含它的最小前缀（建反图，然后加上所有后继即可），然后你就会做了。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=123456,inf=0x3f3f3f3f;
int n,q,cntn;
struct edge{
int v,nxt;
}e[12345678];
int head[N*9],cnte;
void adde(int u,int v){
e[++cnte]=edge{v,head[u]};head[u]=cnte;
}
int dfn[N*9],low[N*9],Tm,blg[N*9],csc,ist[N*9];
stack<int> stk;
int col[N*9],sz[N*9];
vector<pii> sve;
void Tarjan(int x){
low[x]=dfn[x]=++Tm;
stk.push(x);ist[x]=1;
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
if(!dfn[v]){
Tarjan(v);
low[x]=min(low[x],low[v]);
}else if(ist[v]){
low[x]=min(low[x],dfn[v]);
}
}
if(dfn[x]==low[x]){
++csc;sz[csc]=col[csc]=0;
while(stk.top()!=x){
int u=stk.top();
ist[u]=0;
blg[u]=csc;
if(u<=n*3){
++sz[csc];
}
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
sve.push_back(mkp(u,v));
}
stk.pop();
}
int u=stk.top();
ist[u]=0;
blg[u]=csc;
if(u<=n*3){
++sz[csc];
}
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
sve.push_back(mkp(u,v));
}
stk.pop();
}
}
int newnode(){
++cntn;
head[cntn]=0;
dfn[cntn]=low[cntn]=blg[cntn]=ist[cntn]=0;
return cntn;
}
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
int num[N<<2],tp;
void Build(int l=1,int r=3*n,int id=1){
if(l==r){
num[id]=l;
if(tp==0){
adde(num[id>>1],num[id]);
}else{
adde(num[id],num[id>>1]);
}
return;
}
if(id>1){
num[id]=newnode();
if(tp==0){
adde(num[id>>1],num[id]);
}else{
adde(num[id],num[id>>1]);
}
}
Build(lson);Build(rson);
}
void init(int _tp){
tp=_tp;
num[1]=newnode();
Build();
}
void Link(int L,int R,int X,int l=1,int r=3*n,int id=1){
if(L<=l&&r<=R){
if(tp==0){
adde(X,num[id]);
}else{
adde(num[id],X);
}
return;
}
if(L<=mid) Link(L,R,X,lson);
if(mid< R) Link(L,R,X,rson);
}
};
SegTree t[2];
namespace ANS{
vector<int> e[N*9],re[N*9];
int deg[N*9];
int dfs(int x){
int res=sz[x];
col[x]=1;
for(auto i:re[x]){
if(col[i]) continue;
res+=dfs(i);
}
return res;
}
bool work2(){
fordown(i,csc,1){
if(sz[i]>n){
forup(i,1,csc){
col[i]=0;
}
if(dfs(i)<=n*2){
return true;
}
}
}
return false;
}
void work(){
forup(i,1,csc){
e[i].clear();
re[i].clear();
deg[i]=0;
}
set<pii> ss;
for(auto i:sve){
int u=i.fi,v=i.se;
int fu=blg[u],fv=blg[v];
if(fu==fv||ss.count(mkp(fu,fv))) continue;
ss.insert(mkp(fu,fv));
e[fu].push_back(fv);
re[fv].push_back(fu);
++deg[fv];
}
vector<int> vec,v1;
forup(i,1,csc){
if(deg[i]==0&&sz[i]<=n){
vec.push_back(i);
}
}
vector<int> seq;
while(vec.size()){
v1.clear();
for(auto u:vec){
if(sz[u]!=0) seq.push_back(u);
for(auto v:e[u]){
--deg[v];
if(deg[v]==0&&sz[v]<=n) v1.push_back(v);
}
}
vec=v1;
}
int sum=0;
for(auto i:seq){
sum+=sz[i];
col[i]=1;
if(sum>=n){
break;
}
}
if(sum>=n&&sum<=n*2){
puts("TAK");
}else{
if(work2()){
puts("TAK");
}else{
puts("NIE");
return;
}
}
forup(i,1,n*3){
putchar(col[blg[i]]?'F':'R');
}
puts("");
}
}
void solve(){
n=read();q=read();
cnte=0;cntn=n*3;
forup(i,1,n*3){
head[i]=0;
dfn[i]=low[i]=blg[i]=ist[i]=0;
}
forup(j,0,1){
t[j].init(j);
}
forup(i,1,q){
int l1=read(),r1=read(),l2=read(),r2=read();
int nw=newnode();
t[1].Link(l2,r2,nw);t[0].Link(l1,r1,nw);
}
sve.clear();
Tm=csc=0;
forup(i,1,n*3){
if(!dfn[i]) Tarjan(i);
}
forup(i,1,csc){
if(sz[i]>n*2){
puts("NIE");
return;
}
}
ANS::work();
}
signed main(){
int t=read();
while(t--){
solve();
}
}
P4630 [APIO2018] 铁人两项
容易发现题意等价于对于所有 \((s,f)\)，求出它们间所有路径点集的交的大小总和。
那么容易发现，对于一个点双，若确定了入口和出口，对于其中每个点都能找到一条路径经过它。我们要做的就是统计所有 \((s,f)\) 能经过的点双大小总和。
那么可以直接考虑圆方树，把方点点权赋为点双大小，原点赋为 \(-1\) 即可。
然后统计答案可以计算每个点在多少条路径上出现过，这个很简单。
复杂度 \(O(n)\)。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
using namespace std;
using i64=long long;
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=2e5+5,inf=0x3f3f3f3f;
i64 n,m,w[N],ans=0;
vector<i64> e[N],e2[N];
i64 dfn[N],low[N],Tm,cntn;
stack<i64> stk;
int als;
void Tarjan(i64 x){
dfn[x]=low[x]=++Tm;
stk.push(x);
++als;
for(auto i:e[x]){
if(!dfn[i]){
Tarjan(i);
low[x]=min(low[x],low[i]);
if(low[i]==dfn[x]){
++cntn;
w[cntn]=1;
i64 v=0;
while(v!=i){
v=stk.top();stk.pop();
e2[v].push_back(cntn);
e2[cntn].push_back(v);
++w[cntn];
}
e2[x].push_back(cntn);
e2[cntn].push_back(x);
}
}else{
low[x]=min(low[x],dfn[i]);
}
}
}
i64 sz[N];
void dfs2(i64 x,i64 fa){
sz[x]=(x<=n);
for(auto i:e2[x]){
if(i==fa) continue;
dfs2(i,x);
ans+=2*sz[x]*sz[i]*w[x];
sz[x]+=sz[i];
}
ans+=2*sz[x]*(als-sz[x])*w[x];
}
signed main(){
n=read();m=read();
cntn=n;
forup(i,1,m){
i64 u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
forup(i,1,n){
w[i]=-1;
}
forup(i,1,n){
if(!dfn[i]){
als=0;
Tarjan(i);
stk.pop();
dfs2(i,0);
}
}
printf("%lld\n",ans);
}
CF487E Tourists
同样的，我们只需要考虑维护路径上每个点双的答案即可。
那么对每个方点开 multiset 维护所有儿子的最小值，然后树剖即可。
注意特判如果 \(\mathrm{lca}\) 是个方点还要算上它的父亲的答案。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(register int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(register int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5,inf=0x3f3f3f3f;
int n,m,q,a[N],cntn;
multiset<int> s[N];
namespace T{
vector<int> e[N];
int dpt[N],hig[N],sz[N],son[N],fat[N],f[N];
void dfs(int x,int fa){
sz[x]=1;dpt[x]=dpt[fa]+1;
fat[x]=fa;
for(auto i:e[x]){
if(i==fa) continue;
dfs(i,x);
sz[x]+=sz[i];
if(sz[i]>sz[son[x]]||son[x]==0){
son[x]=i;
}
}
}
int st[N],ed[N],Tm,seq[N];
void dfs(int x,int fa,int hh){
hig[x]=hh;st[x]=++Tm;
if(x>n) s[x].insert(a[son[x]]);
if(son[x]!=0) dfs(son[x],x,hh);
for(auto i:e[x]){
if(i==fa||i==son[x]) continue;
if(x>n){
s[x].insert(a[i]);
}
dfs(i,x,i);
}
ed[x]=Tm;
if(x>n) a[x]=*s[x].begin();
seq[st[x]]=a[x];
}
struct SegmentTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
private:
int querymin[N<<2];
void PushUp(int id){
querymin[id]=min(querymin[id<<1],querymin[id<<1|1]);
}
public:
void Build(int* A,int l=1,int r=cntn,int id=1){
if(l==r){
querymin[id]=A[l];
return;
}
Build(A,lson);
Build(A,rson);
PushUp(id);
}
void Update(int P,int X,int l=1,int r=cntn,int id=1){
if(l==r){
querymin[id]=X;
return;
}
if(P<=mid) Update(P,X,lson);
else Update(P,X,rson);
PushUp(id);
}
int AskMin(int L,int R,int l=1,int r=cntn,int id=1){
if(L<=l&&r<=R){
return querymin[id];
}
int res=inf;
if(L<=mid) res=min(res,AskMin(L,R,lson));
if(mid< R) res=min(res,AskMin(L,R,rson));
return res;
}
}mt;
void NodeUpdate(int P,int X){
if(fat[P]){
s[fat[P]].erase(s[fat[P]].find(a[P]));
s[fat[P]].insert(X);
a[fat[P]]=*s[fat[P]].begin();
mt.Update(st[fat[P]],a[fat[P]]);
}
a[P]=X;
mt.Update(st[P],X);
}
int ChainAsk(int x,int y){
if(hig[x]==hig[y]){
if(dpt[x]>dpt[y]) swap(x,y);
int res=mt.AskMin(st[x],st[y]);
if(x>n&&fat[x]) res=min(res,a[fat[x]]);
return res;
}
if(dpt[hig[x]]<dpt[hig[y]]) swap(x,y);
int res=inf;
res=min(res,mt.AskMin(st[hig[x]],st[x]));
res=min(res,ChainAsk(fat[hig[x]],y));
return res;
}
}
vector<int> e[N];
int dfn[N],low[N],dfc;
int stk[N],top;
void Tarjan(int u){
low[u]=dfn[u]=++dfc;
stk[++top]=u;
for(auto v:e[u]){
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
if(low[v]==dfn[u]){
++cntn;
a[cntn]=inf;
for(int x=0;x!=v;--top){
x=stk[top];
T::e[x].push_back(cntn);
T::e[cntn].push_back(x);
}
T::e[cntn].push_back(u);
T::e[u].push_back(cntn);
}
}else{
low[u]=min(low[u],dfn[v]);
}
}
}
signed main(){
n=read();m=read();q=read();
cntn=n;
forup(i,1,n){
a[i]=read();
}
forup(i,1,m){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
Tarjan(1);
T::dfs(1,0);T::dfs(1,0,1);
T::mt.Build(T::seq);
while(q--){
char op;
scanf(" %1c",&op);
if(op=='C'){
int x=read(),w=read();
T::NodeUpdate(x,w);
}else{
int u=read(),v=read();
printf("%d\n",T::ChainAsk(u,v));
}
}
}
P5471 [NOI2019] 弹跳
第一眼觉得线段树套数优化建图然后跑 dij，结果发现空间要炸。
考虑优化，发现只用开一维线段树，另一维可以用 multiset 维护。然后由于每次 dis 最小的点必定是一整个矩形内的点，优先队列里面可以塞矩形，然后每个点拓展一次就从线段树上删掉即可（赞美 dij）。
复杂度 \(O(n\log^2 n)\)。
参考代码
因为写代码时没想清楚，貌似实现的时候复杂度假到 \(log^3\) 了，但是无所谓。
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=70005,inf=0x3f3f3f3f;
int n,m,w,h,dis[N],x[N],y[N];
struct Node{
int v,l,r,d,u,dis;
bool operator <(const Node &r)const{return dis>r.dis;}
};
priority_queue<Node> q;
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
set<pii> querynode[N<<2];
void Update(int X,int Y,int P,int l=1,int r=w,int id=1){
if(l==r){
querynode[id].insert(mkp(Y,P));
return;
}
if(X<=mid) Update(X,Y,P,lson);
else Update(X,Y,P,rson);
}
void Erase(int X,int Y,int P,int l=1,int r=w,int id=1){
querynode[id].erase(mkp(Y,P));
if(l==r) return;
if(X<=mid) Erase(X,Y,P,lson);
else Erase(X,Y,P,rson);
}
void Build(int l=1,int r=w,int id=1){
if(l==r) return;
Build(lson);Build(rson);
for(auto i:querynode[id<<1]) querynode[id].insert(i);
for(auto i:querynode[id<<1|1]) querynode[id].insert(i);
}
void Modify(int L,int R,int D,int U,int X,int l=1,int r=w,int id=1){
if(querynode[id].empty()) return;
if(L<=l&&r<=R){
#define mit multiset<pii>::iterator
mit st=querynode[id].lower_bound(mkp(D,0)),ed=querynode[id].lower_bound(mkp(U+1,0));
vector<int> er;
for(mit it=st;it!=ed;++it){
int v=it->se;
dis[v]=X;
q.push(Node{v,0,0,0,0,X});
er.push_back(v);
}
#undef mit
for(auto v:er){
Erase(x[v],y[v],v);
}
return;
}
if(L<=mid) Modify(L,R,D,U,X,lson);
if(mid< R) Modify(L,R,D,U,X,rson);
}
#undef mid
#undef lson
#undef rson
};
SegTree mt;
struct edge{
int t,l,r,d,u;
};
vector<edge> e[N];
signed main(){
n=read();m=read();w=read();h=read();
forup(i,1,n){
x[i]=read();y[i]=read();
mt.Update(x[i],y[i],i);
}
mt.Build();
forup(i,1,m){
int p=read(),t=read(),l=read(),r=read(),d=read(),u=read();
e[p].push_back(edge{t,l,r,d,u});
}
mem(dis,0x3f);
dis[1]=0;q.push(Node{1,0,0,0,0,0});
while(q.size()){
if(q.top().v==0){
int l=q.top().l,r=q.top().r,d=q.top().d,u=q.top().u,val=q.top().dis;q.pop();
mt.Modify(l,r,d,u,val);
}else{
int v=q.top().v;q.pop();
for(auto i:e[v]){
int t=i.t,l=i.l,r=i.r,d=i.d,u=i.u;
q.push(Node{0,l,r,d,u,dis[v]+t});
}
}
}
forup(i,2,n){
printf("%d\n",dis[i]);
}
}
P3243 [HNOI2015] 菜肴制作
容易发现从小到大最小化拓扑序中每个数的下标等价于最大反图拓扑序的字典序。
感性理解就是在反图上先把更大的用了更小的就更容易提到前面，严谨证明其实也差不多，可以考虑数学归纳，这里就略过了。
那么求拓扑序时把队列换成优先队列即可。
注意 reverse，复杂度 \(O(n\log n)\)。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e5+5,inf=0x3f3f3f3f;
int n,m,deg[N];
vector<int> e[N];
priority_queue<int> q;
void solve(){
n=read();m=read();
forup(i,1,n){
deg[i]=0;
e[i].clear();
}
forup(i,1,m){
int u=read(),v=read();
e[v].push_back(u);
++deg[u];
}
while(q.size()) q.pop();
forup(i,1,n){
if(!deg[i]) q.push(i);
}
vector<int> seq;
while(q.size()){
int u=q.top();q.pop();
seq.push_back(u);
for(auto v:e[u]){
--deg[v];
if(!deg[v]) q.push(v);
}
}
if((int)seq.size()!=n){
puts("Impossible!");
}else{
reverse(seq.begin(),seq.end());
for(auto i:seq){
printf("%d ",i);
}
puts("");
}
}
signed main(){
int t=read();
while(t--){
solve();
}
}
[ABC237Ex] Hakata
首先有个结论，就是一个字符串本质不同的回文字串数量不超过 \(n\)。
因为考虑你假如在字符串末尾插入一个字符，以它结尾的回文字串中，除去最大的一个，其余都被最大的覆盖了，那肯定在之前出现过。那么每次只会新增一个。
另外容易发现字符串的字串关系是个偏序集，然后我们要求的是最小反链覆盖，直接套 Dilworth 定理，求最小链划分即可。
经典二分图建模，直接 dinic，这一部分复杂度 \(O(n\sqrt{m})\)，然后边数是 \(O(n^2)\) 的，复杂度就是 \(O(n^2)\)。
然后前面求偏序关系直接 \(O(n^3)\) 暴力即可。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=456,inf=0x3f3f3f3f;
int n;
string str;
set<string> mp;
vector<string> vec;
bool chk(int i,int j){
while(i<=j&&str[i]==str[j]){
++i;--j;
}
return i>j;
}
int nxt[N];
bool subseq(int x,int y){
nxt[0]=0;
forup(i,1,(int)vec[y].size()-1){
int j=nxt[i-1];
while(j&&vec[y][i]!=vec[y][j]) j=nxt[j-1];
if(vec[y][i]==vec[y][j]) ++j;
nxt[i]=j;
}
int f=0;
forup(i,0,(int)vec[x].size()-1){
while(f&&vec[x][i]!=vec[y][f]) f=nxt[f-1];
if(vec[x][i]==vec[y][f]) ++f;
if(f==(int)vec[y].size()) return true;
}
return false;
}
struct flow{
struct edge{
int v,rst,nxt;
}e[N*N*2];
int head[N],cur[N],cnte=1,dpt[N],s,t,n;
void adde(int u,int v,int w){
e[++cnte]=edge{v,w,head[u]};head[u]=cnte;
e[++cnte]=edge{u,0,head[v]};head[v]=cnte;
}
bool bfs(){
forup(i,0,n){
cur[i]=head[i];
dpt[i]=-1;
}
queue<int> q;
dpt[s]=0;q.push(s);
while(q.size()){
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(!e[i].rst||dpt[v]!=-1) continue;
dpt[v]=dpt[u]+1;
q.push(v);
}
}
return dpt[t]!=-1;
}
int dfs(int x,int flow){
if(x==t||!flow) return flow;
int res=0;
for(int i=cur[x];i;i=e[i].nxt){
cur[x]=i;int v=e[i].v;
if(dpt[v]==dpt[x]+1){
int gt=dfs(v,min(flow-res,e[i].rst));
if(gt){
e[i].rst-=gt;
e[i^1].rst+=gt;
res+=gt;
if(res==flow) break;
}
}
}
return res;
}
int dinic(){
int ans=0;
while(bfs()){
ans+=dfs(s,inf);
}
return ans;
}
}mf;
signed main(){
cin>>str;
n=str.size();
forup(i,0,n-1){
forup(j,i,n-1){
if(chk(i,j)){
string ss=str.substr(i,j-i+1);
if(!mp.count(ss)){
vec.push_back(ss);
mp.insert(ss);
}
}
}
}
mf.s=vec.size()*2;mf.t=vec.size()*2+1;mf.n=vec.size()*2+1;
forup(i,0,(int)vec.size()-1){
forup(j,0,(int)vec.size()-1){
if(i==j) continue;
if(subseq(i,j)){
mf.adde(i,j+vec.size(),inf);
}
}
}
forup(i,0,(int)vec.size()-1){
mf.adde(mf.s,i,1);
mf.adde(i+vec.size(),mf.t,1);
}
int ans=vec.size()-mf.dinic();
printf("%d\n",ans);
}
P7215 [JOISC2020] 首都
很考验对点分治的理解。
题面不是很友好，所以这里给出形式化题意：
- 给你一棵有 \(N\) 个点的树，每个点有颜色，共有 \(K\) 种颜色。
- 你一次操作可以把所有颜色为 \(a\) 的点涂成颜色为 \(b\) 的点（\(a,b\) 你随意指定）。
- 问至少需要多少次操作才能使某一种颜色的点是一个连通块。
那么容易想到一个初步思路：先枚举最终的颜色 \(c\)，然后随意选一个该颜色的点，考虑把所有不和它连通且颜色为 \(c\) 的点之间的路径全涂成 \(c\)。
具体如何实现，可以考虑一个贪心。先把以你选的点为根求出所有点的父亲，再将所有颜色为 \(c\) 的点压入一个队列，然后每次取出队首元素，若其父亲没涂成 \(c\) 就将对应颜色涂成 \(c\) 并压入队列。这个贪心显然是对的，因为你的每次涂色都是必要的，复杂度 \(O(n)\)。然后加上枚举颜色就是 \(O(nm)\) 的。
考虑优化，容易发现对于选的那个点，我们的算法相当于“寻找一个包含它的连通块，使得它包含一个颜色集合的所有点”，即这是一个对连通块的查找！这种给定点找连通块的问题可以考虑用点分治优化。
具体来说，对于每个分治中心，只考虑完全包含在对应连通块中的颜色，因为如果跨越了连通块，它会在其它分治中心被算到，如果贪心过程中发现没有被该连通块完全包含的直接当成无解即可。然后就做完了，复杂度 \(O(n\log n)\)。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5,inf=0x3f3f3f3f;
int n,m,c[N],ans;
vector<int> e[N],cmeb[N];
int vis[N],sz[N],mx[N],rt,als;
void dfs1(int x,int fa){
sz[x]=1;mx[x]=0;
for(auto i:e[x]){
if(i==fa||vis[i]) continue;
dfs1(i,x);
sz[x]+=sz[i];
if(sz[i]>mx[x]){
mx[x]=sz[i];
}
}
mx[x]=max(mx[x],als-sz[x]);
if(rt==-1||mx[x]<mx[rt]) rt=x;
}
int ccnt[N],ff[N],cvis[N];
set<int> cset;
void dfs2(int x,int fa){
++ccnt[c[x]];ff[x]=fa;
cset.insert(c[x]);
for(auto i:e[x]){
if(i==fa||vis[i]) continue;
dfs2(i,x);
}
}
int work(int x){
cset.clear();
dfs2(x,0);
queue<int> q;
if(ccnt[c[x]]!=(int)cmeb[c[x]].size()){
for(auto i:cset){
cvis[i]=ccnt[i]=0;
}
return m;
}
for(auto i:cmeb[c[x]]) q.push(i);
cvis[c[x]]=1;
int res=0;
while(q.size()){
int u=q.front();q.pop();
if(ff[u]!=0&&!cvis[c[ff[u]]]){
if(ccnt[c[ff[u]]]!=(int)cmeb[c[ff[u]]].size()){
for(auto i:cset){
cvis[i]=ccnt[i]=0;
}
return m;
}
cvis[c[ff[u]]]=1;
++res;
for(auto i:cmeb[c[ff[u]]]) q.push(i);
}
}
for(auto i:cset){
cvis[i]=ccnt[i]=0;
}
return res;
}
void dfz(int x,int ps){
ans=min(ans,work(x));
vis[x]=1;
for(auto i:e[x]){
if(vis[i]) continue;
als=(sz[i]<sz[x]?sz[i]:ps-sz[x]);rt=-1;
dfs1(i,x);
dfz(rt,als);
}
}
signed main(){
n=read();m=read();
ans=m-1;
forup(i,1,n-1){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
forup(i,1,n){
c[i]=read();
cmeb[c[i]].push_back(i);
}
rt=-1;als=n;
dfs1(1,0);
dfz(rt,n);
printf("%d\n",ans);
}
P3623 [APIO2008] 免费道路
很考验对 Kruskal 的理解（感觉佳老师抓的题严格薄纱 匈牙利人（Hungary belonger） 或者 奥运评委（Olympic judge） 抓的啊）。
这道题乍一看很像之前 Tree I 边权全为 \(1\) 的削弱版加上输出方案。但其实容易发现这道题的图像是一条横向的线段，而 wqs 二分多点共线的情况要输出方案是很麻烦的（或许可以考虑给边随机赋权值然后跑 wqs 二分）。
一个简单的想法是先随便加 \(k\) 条不含环的 \(0\) 权边。但是这样可能会让本来有解的判成无解，考虑如何保证有解。
由于 Kruskal 是一个缩点的过程，容易发现把 \(1\) 权边全缩完之后，在剩余的图上跑 Kruskal 就能找到必要的 \(0\) 权边。而只要把这些“必要的边”缩了，其余边必定能连出一棵生成树（除非图不连通）。
那么先跑一遍 Kruskal 找到必要的边，再跑一遍 Kruskal，先加必要的边，再补 \(0\) 权边补到 \(k\) 条，最后再连 \(1\) 权边即可。
复杂度 \(O(m\log m\alpha(n))\)。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e4+5,M=1e5+5,inf=0x3f3f3f3f;
int n,m,t;
struct edge{
int u,v,c;
}e[M];
vector<edge> nec,ans;
int fa[N];
int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
signed main(){
n=read();m=read();t=read();
forup(i,1,m){
e[i].u=read();e[i].v=read();e[i].c=read();
}
sort(e+1,e+m+1,[&](edge a,edge b){
return a.c>b.c;
});
forup(i,1,n) fa[i]=i;
int cnt=0;
for(int i=1;i<=m;++i){
int fu=getfa(e[i].u),fv=getfa(e[i].v);
if(fu==fv) continue;
fa[fu]=fv;
++cnt;
if(!e[i].c){
nec.push_back(e[i]);
}
}
if((int)nec.size()>t||cnt<n-1){
puts("no solution");
return 0;
}
sort(e+1,e+m+1,[&](edge a,edge b){
return a.c<b.c;
});
forup(i,1,n) fa[i]=i;
int cnt0=nec.size();
for(auto i:nec){
fa[getfa(i.u)]=getfa(i.v);
ans.push_back(i);
}
for(int i=1;i<=m;++i){
int fu=getfa(e[i].u),fv=getfa(e[i].v);
if(fu==fv||(cnt0==t&&!e[i].c)) continue;
fa[fu]=fv;
ans.push_back(e[i]);
if(!e[i].c) ++cnt0;
}
if(cnt0!=t){
puts("no solution");
}else{
for(auto i:ans){
printf("%d %d %d\n",i.u,i.v,i.c);
}
}
}
P9726 [EC Final 2022] Magic
容易发现没有被其余操作覆盖的区间端点会产生贡献，那么考虑区间 \(A,B\) 的关系：
- \(A\) 区间完全覆盖 \(B\) 区间：先执行 \(B\) 再执行 \(A\) 必定不劣。
- \(A\cap B=\varnothing\)：两区间显然互不影响。
- \(A\cap B\ne\varnothing\)：不妨设 \(l_a<l_b<r_a<r_b\)，容易发现 \(l_b,r_a\) 只有一个可以产生贡献。
假如把形如“二选一能产生贡献”的两两连边，容易发现这是一个二分图的形式，而每条边的意义是“两端点只有一个能产生贡献”，那么显然贡献最大就是最大独立集，可以用最大流或者匈牙利算法解决。
但是只有答案“小于等于最大独立集”是显然的，考虑证明答案能取到最大独立集。
容易发现无解当且仅当操作顺序构成环，考虑假设存在一个环，环上存在一个 \((l_i,r_i)\) 是 \(r_i\) 产生贡献，考虑一组和它有顺序要求的 \((l_i',r_i')\)，假设 \(l_i<l_i'<r_i<r_i'\)，那么显然是 \(r_i'\) 产生贡献。容易发现环上 \(r_i\) 是递增的，那显然这不是个环。
但是这道题卡空间，可以考虑用 bitset 存邻接矩阵，然后空间就能过了，此时跑 dinic 时间复杂度是 \(O(\frac{n^3\sqrt{n}}{w})\)（还不如匈牙利 \(O(\frac{n^3}{w})\)，但是我不会匈牙利\kk）。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(short i=(s);i<=(e);i++)
#define fordown(i,s,e) for(short i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline short read(){
short x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const short N=5005;
short n,l[N],r[N],col[N<<1];
bitset<N<<1> grp[N<<1];
short dpt[N<<1],cur[N<<1],s,t;
bool bfs(){
forup(i,1,t){
dpt[i]=-1;
cur[i]=grp[i]._Find_first();
}
queue<short> q;
q.push(s);dpt[s]=0;
while(q.size()){
short u=q.front();q.pop();
for(short v=grp[u]._Find_first();v<=t;v=grp[u]._Find_next(v)){
if(dpt[v]!=-1) continue;
dpt[v]=dpt[u]+1;
q.push(v);
}
}
return dpt[t]!=-1;
}
short dfs(short x,short flow){
if(x==t||!flow) return flow;
short res=0;
for(short v=grp[x]._Find_next(cur[x]-1);v<=t;v=grp[x]._Find_next(v)){
cur[x]=v;
if(dpt[v]!=dpt[x]+1) continue;
short gt=dfs(v,min(flow-res,1));
if(gt){
res+=gt;
grp[x][v]=0;
grp[v][x]=1;
if(res==flow) break;
}
}
return res;
}
short dinic(){
short ans=0;
while(bfs()){
ans+=dfs(s,n);
}
return ans;
}
signed main(){
n=read();
forup(i,1,n){
l[i]=read();r[i]=read();
col[l[i]]=0;col[r[i]]=1;
}
s=n*2+1;t=n*2+2;
forup(i,1,n){
forup(j,1,n){
if(j==i) continue;
if(l[i]<l[j]&&l[j]<r[i]&&r[i]<r[j]){
grp[l[j]][r[i]]=1;
}
}
}
forup(i,1,n*2){
if(col[i]==0){
grp[s][i]=1;
}else{
grp[i][t]=1;
}
}
printf("%d\n",n*2-dinic());
}
然后卡空间的另一个办法是可持久化线段树优化建图。这个可以参考我的这篇洛谷题解。
P5025 [SNOI2017] 炸弹
线段树优化建图后跑强连通分量。根据题设容易发现能引爆的区域必定是一个连续的区间，在缩点后反图上跑拓扑序列 DP 维护每个强连通分量能到达的最左和最右即可。复杂度 \(O(n\log n)\)。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=5e5+5,mod=1e9+7;
i64 n,x[N],r[N],deg[N*5];
vector<i64> e[N*5],e2[N*5];
i64 cntn;
vector<pii> sve;
void adde(i64 u,i64 v){
e[u].push_back(v);
sve.push_back(mkp(u,v));
}
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
i64 num[N<<2];
void Build(i64 l=1,i64 r=n,i64 id=1){
if(l==r){
num[id]=l;
return;
}
num[id]=++cntn;
Build(lson);Build(rson);
adde(num[id],num[id<<1]);
adde(num[id],num[id<<1|1]);
}
void Link(i64 L,i64 R,i64 X,i64 l=1,i64 r=n,i64 id=1){
if(L<=x[l]&&x[r]<=R){
adde(X,num[id]);
return;
}
if(L <=x[mid]) Link(L,R,X,lson);
if(x[mid+1]<=R ) Link(L,R,X,rson);
}
}mt;
i64 dfn[N*5],low[N*5],Tm,ist[N*5],blg[N*5],csc,L[N*5],R[N*5];
stack<i64> stk;
void Tarjan(i64 x){
dfn[x]=low[x]=++Tm;
ist[x]=1;stk.push(x);
for(auto i:e[x]){
if(!dfn[i]){
Tarjan(i);
low[x]=min(low[x],low[i]);
}else if(ist[i]){
low[x]=min(low[x],dfn[i]);
}
}
if(low[x]==dfn[x]){
++csc;
L[csc]=n+1;
for(i64 v=0;v!=x;stk.pop()){
v=stk.top();
blg[v]=csc;
if(v<=n){
L[csc]=min(L[csc],v);
R[csc]=max(R[csc],v);
}
ist[v]=0;
}
}
}
signed main(){
n=read();
vector<i64> lsh;
forup(i,1,n){
x[i]=read();r[i]=read();
}
cntn=n;
mt.Build();
forup(i,1,n){
mt.Link(x[i]-r[i],x[i]+r[i],i);
}
forup(i,1,cntn){
if(!dfn[i]){
Tarjan(i);
}
}
set<pii> ss;
for(auto i:sve){
i64 u=blg[i.fi],v=blg[i.se];
if(u==v||ss.count(mkp(u,v))) continue;
ss.insert(mkp(u,v));
e2[v].push_back(u);
++deg[u];
}
queue<i64> q;
forup(i,1,csc){
if(deg[i]==0){
q.push(i);
}
}
while(q.size()){
i64 u=q.front();q.pop();
for(auto i:e2[u]){
--deg[i];
L[i]=min(L[i],L[u]);
R[i]=max(R[i],R[u]);
if(deg[i]==0){
q.push(i);
}
}
}
i64 res=0;
forup(i,1,n){
(res+=1ll*i*(R[blg[i]]-L[blg[i]]+1)%mod)%=mod;
}
printf("%lld\n",res);
}
[AGC056C] 01 Balanced
妙妙题。
首先很自然能想到差分约束。具体来说，就是对前缀和进行差分约束，最开始限制 \(a_i\le a_{i+1},a_{i+1}\le a_i+1\)，然后每个条件用两个 \(\le\) 拼成一个 \(=\) 即可。但这样有个问题，就是要连负权边。不能用 dij 了，而且 \(|V|=10^6,|E|>2|V|\)，不像是 SPFA 能过的样子（据说会被卡五个点），考虑构造出不用连负权边的方案。
首先肯定不能直接用前缀和了，一个想法是把前缀和换成前缀“\(0\) 的个数减去 \(1\) 的个数”，容易发现最小化原序列字典序就是最大化这个序列的字典序，并且由于差分约束本来就是求的字典序最大值，所以还会更方便。然后这样限制就变成了 \(a_i\le a_{i+1}+1,a_{i+1}\le a_i+1\)，每个条件就拼出两值相等即可，然后就做完了。复杂度 \(O(n\log n)\)。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e6+5,inf=0x3f3f3f3f;
int n,m;
struct edge{
int v,w;
};
vector<edge> e[N];
int vis[N],dis[N];
struct Node{
int dis,u;
bool operator <(const Node &r)const{return dis>r.dis;}
};
priority_queue<Node> q;
signed main(){
n=read();m=read();
forup(i,0,n-1){
e[i].push_back(edge{i+1,1});
e[i+1].push_back(edge{i,1});
}
forup(i,1,m){
int l=read(),r=read();
e[l-1].push_back(edge{r,0});
e[r].push_back(edge{l-1,0});
}
mem(dis,0x3f);dis[0]=0;
q.push(Node{0,0});
while(q.size()){
int u=q.top().u;q.pop();
if(vis[u]) continue;
vis[u]=1;
for(auto i:e[u]){
int v=i.v,w=i.w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push(Node{dis[v],v});
}
}
}
forup(i,1,n){
printf("%d",(dis[i]>dis[i-1]?0:1));
}
}
P3953 [NOIP2017 提高组] 逛公园
这道题乍一看很难做，因为长度小于等于 \(D_n+K\) 的路径不一定能由最短路简单变化而来。但是注意到 \(K\le 50\)，所以它是能支持 \(O(NK)\) 之类的做法的。容易想到可能是用 DP 做。
首先不考虑边权为 \(0\) 的边，这道题应该怎么做。
容易发现，若不存在边权为 \(0\) 的边，那么建出最短路 DAG（就是 \(G'=(V,E'),E'=\begin{Bmatrix}(u,v,w)|D_v=D_u+w\end{Bmatrix}\)）后，经过任意边都会使得这条路径大于等于最短路，那么按比最短路大多少 DP 是没有后效性的！容易想到设 \(dp_{u,i}\) 表示从 \(1\) 到 \(u\) 的路径中恰好比最短路 \(D_u\) 大 \(i\) 的有多少条。然后先枚举第二维就没有后效性了。
但是有个问题，即第一维的枚举顺序问题。这个其实也好解决，容易发现经过不在最短路 DAG 上的边必定使得第二维增加，考虑 \(dp_{u,i}\) 经过 \((u,v,w)\) 转移到 \(dp_{v,j}\)，容易发现 \(j=D_u+i+w-D_j\)（最短路三角不等式 \(D_u+w\ge D_j\)，且在最短路 DAG 上取等）。故不在最短路 DAG 上的边没有枚举顺序要求，而最短路 DAG 上的边可以考虑按点的拓扑序枚举点后再枚举出边，这样就能保证每个点从所有前驱转移过来。
然后考虑有 \(0\) 边的情况。容易发现若 \(0\) 边没形成环那么岁月静好，无事发生。但如果 \(0\) 边形成 \(0\) 环，并且恰好存在至少一条经过它到达 \(n\) 的路径长度小于等于 \(D_n+K\)，那么就有无穷多条合法路径了，输出 \(-1\)。
然后反正你都要在最短路 DAG 上跑拓扑了，容易发现这样的 \(0\) 边肯定都在最短路图上，可以直接跑拓扑找到它。
然后注意若经过一个点到达 \(n\) 的路径已经大于 \(D_n+K\) 了，那么显然它和答案完全无关。
参考代码
代码很屎山，因为写到一半发现错了但是不舍得重构。
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e5+5,M=2e5+5,inf=0x3f3f3f3f;
#define ull unsigned long long
#define ui128 __uint128_t
struct Barrett{
ull d;ui128 m;
void init(ull _d){
d=_d,m=(((ui128)(1)<<64)/d);
}
}mod;
int t,n,m,K,p;
ull operator %(int a,Barrett mod){
ull w=(mod.m*a)>>64;w=a-w*mod.d;
if(w>=mod.d)w-=mod.d;return w;
}
struct edge{
int v,w,nxt;
}e[M<<1];
int head[N],head1[N],cnte;
void adde(int u,int v,int w){
e[++cnte]=edge{v,w,head[u]};head[u]=cnte;
e[++cnte]=edge{u,w,head1[v]};head1[v]=cnte;
}
int dp[N][55],vis[N],dis[2][N];
struct Node{
int u,dis;
bool operator <(const Node &r)const{return dis>r.dis;}
};
vector<edge> E[N];
int deg[N];
void solve(){
n=read();m=read();K=read();p=read();
mod.init(p);
mem(head,0);mem(head1,0);
cnte=0;
mem(deg,0);
forup(i,1,n){
forup(j,0,K){
dp[i][j]=0;
}
}
dp[1][0]=1;
forup(i,1,m){
int u=read(),v=read(),w=read();
adde(u,v,w);
}
mem(dis,0x3f);
mem(vis,0);
priority_queue<Node> q;
dis[0][1]=0;q.push(Node{1,0});
while(q.size()){
int u=q.top().u;q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(dis[0][v]>dis[0][u]+w){
dis[0][v]=dis[0][u]+w;
q.push(Node{v,dis[0][v]});
}
}
}
mem(vis,0);
dis[1][n]=0;q.push(Node{n,0});
while(q.size()){
int u=q.top().u;q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head1[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(dis[1][v]>dis[1][u]+w){
dis[1][v]=dis[1][u]+w;
q.push(Node{v,dis[1][v]});
}
}
}
vector<pair<pii,int>> sve;
mem(vis,0);
forup(i,1,n){
if(dis[0][i]+dis[1][i]>dis[0][n]+K){
vis[i]=1;
}
}
forup(x,1,n){
E[x].clear();
if(vis[x]) continue;
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(vis[v]) continue;
if(dis[0][v]==dis[0][x]+w){
E[x].push_back(edge{v,w,0});
++deg[v];
}else{
sve.push_back(mkp(mkp(x,v),w));
}
}
}
vector<int> seq;
queue<int> q1;
forup(i,1,n){
if(deg[i]==0) q1.push(i);
}
while(q1.size()){
int u=q1.front();q1.pop();
seq.push_back(u);
for(auto i:E[u]){
--deg[i.v];
if(deg[i.v]==0){
q1.push(i.v);
}
}
}
if((int)seq.size()<n){
puts("-1");
return;
}
forup(j,0,K){
for(auto u:seq){
for(auto ed:E[u]){
int nw=dis[0][u]+j+ed.w-dis[0][ed.v];
if(nw<=K){
dp[ed.v][nw]=(dp[ed.v][nw]+dp[u][j])%mod;
}
}
}
for(auto i:sve){
int u=i.fi.fi,v=i.fi.se,w=i.se,nw=dis[0][u]+j+w-dis[0][v];
if(nw<=K){
dp[v][nw]=(dp[v][nw]+dp[u][j])%mod;
}
}
}
int ans=0;
forup(i,0,K){
ans=(ans+dp[n][i])%mod;
}
printf("%d\n",ans);
}
signed main(){
t=read();
while(t--){
solve();
}
}
P3658 [USACO17FEB] Why Did the Cow Cross the Road III P
设一个数 \(i\) 在第一个排列中的位置是 \(x_i\)，在第二个排列中是 \(y_i\)。
容易发现要统计的就是这样的数对 \((i,j)\)：
- \(x_i<x_j\)
- \(y_i>y_j\)
- \(|i-j|> K\)。
那么就是个三维偏序，其中第三个条件可以直接简单容斥，用总的减去不要的即可。
/// details | 参考代码 oprn: False type: success
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
using namespace std;
using i64=long long;
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=1e5+5,inf=0x3f3f3f3f;
i64 n,k,ans;
struct Node{
i64 x,y,val;
}s[N];
struct BIT{
i64 c[N];
void upd(i64 x,i64 k){for(;x<=n;x+=x&-x)c[x]+=k;}
i64 sum(i64 x){i64 res=0;for(;x>0;x-=x&-x)res+=c[x];return res;}
i64 query(i64 l,i64 r){return sum(r)-sum(l-1);}
}mt;
void cdq(i64 l,i64 r){
if(l==r) return;
i64 mid=(l+r)>>1;
cdq(l,mid);cdq(mid+1,r);
i64 ll=l;
forup(i,mid+1,r){
while(ll<=mid&&s[ll].y>s[i].y){
mt.upd(s[ll].val,1);
++ll;
}
ans+=(ll-l)-mt.query(max(s[i].val-k,1ll),min(s[i].val+k,n));
}
forup(i,l,ll-1){
mt.upd(s[i].val,-1);
}
inplace_merge(s+l,s+mid+1,s+r+1,[&](Node a,Node b){
return a.y>b.y;
});
}
signed main(){
n=read();k=read();
forup(i,1,n){
i64 a=read();
s[a].x=i;
s[i].val=i;
}
forup(i,1,n){
i64 b=read();
s[b].y=i;
}
sort(s+1,s+n+1,[&](Node a,Node b){
return a.x<b.x;
});
cdq(1,n);
printf("%lld\n",ans);
}
///
P3157 [CQOI2011] 动态逆序对
设某个数的大小为 \(y\)，在排列中的位置为 \(x\)，删除的时间为 \(z\)（若没被删除视作在 \(m\) 时间删除）。
容易发现，对于一个逆序对 \((i,j)\)，若 \(z_i\le z_j\)，就会对 \(z_i\) 之前（包括 \(z_i\)）的答案产生贡献，反之会对 \(z_j\) 之前的答案产生贡献，然后转化成三维偏序就做完了。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
using namespace std;
using i64=long long;
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=1e5+5,inf=0x3f3f3f3f;
i64 n,m,ans[N];
struct Node{
i64 x,y,z;
}s[N];
struct BIT{
i64 c[N];
void upd(i64 x,i64 k){for(;x<=n;x+=x&-x)c[x]+=k;}
i64 sum(i64 x){i64 res=0;for(;x>0;x-=x&-x)res+=c[x];return res;}
}mt;
void cdq(i64 l,i64 r){
if(l==r) return;
i64 mid=(l+r)>>1;
cdq(l,mid);cdq(mid+1,r);
i64 ll=l;
forup(i,mid+1,r){
while(ll<=mid&&s[ll].z>=s[i].z){
mt.upd(s[ll].y,1);
++ll;
}
ans[s[i].z]+=(ll-l)-mt.sum(s[i].y);
}
forup(i,l,ll-1) mt.upd(s[i].y,-1);
ll=mid+1;
forup(i,l,mid){
while(ll<=r&&s[ll].z>s[i].z){
mt.upd(s[ll].y,1);
++ll;
}
ans[s[i].z]+=mt.sum(s[i].y-1);
}
forup(i,mid+1,ll-1) mt.upd(s[i].y,-1);
inplace_merge(s+l,s+mid+1,s+r+1,[&](Node a,Node b){
return a.z>b.z;
});
}
signed main(){
n=read();m=read();
forup(i,1,n){
int y=read();
s[y].x=i;s[y].y=y;
}
forup(i,1,m){
i64 a=read();
s[a].z=i;
}
forup(i,1,n){
if(!s[i].z) s[i].z=m;
}
sort(s+1,s+n+1,[&](Node a,Node b){
return a.x<b.x;
});
cdq(1,n);
fordown(i,m,2){
ans[i-1]+=ans[i];
}
forup(i,1,m){
printf("%lld\n",ans[i]);
}
}