Ghi chú giải bài tập lập trình (Bản 14)

Liên kết cuộc thi

\(\text{By DaiRuiChen007}\)

A. [P11648] 2236 A.D. (4.5)

Liên kết bài toán

Ta thực hiện phân tách từng bit của \(k\), duy trì tập hợp \(S\) động. Mỗi thao tác cập nhật hoặc truy vấn \(w_x=\sum_{y\in S}a_{x\lor y}\).

Sử dụng DSU để quản lý, mỗi nút chỉ có \(k\) tổ tiên thay đổi trọng số đường đi. Với \(\log n\) cạnh nhẹ, số lần sửa đổi và truy vấn \(S\) là \(\mathcal O(n\log n)\).

Thực hiện phân tách từng nửa, khi chèn/xóa, duyệt các bit trước và sau \(\frac k2\) của \(x\lor y\).

Độ phức tạp thời gian \(\mathcal O(n2^{k/2}(k+\log n))\).

Mã nguồn:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5e5+5,MOD=998244353;
int n,m,k,L,R,a[MAXN];
ll h[16],wl[128],wr[256],z[MAXN],f[256][128];
vector <int> G[MAXN];
int maxChild[MAXN],size[MAXN],parent[MAXN],b[MAXN],inTime[MAXN],outTime[MAXN],rank[MAXN],timeCount;
void dfs1(int u,int p) {
	if(p) G[u].erase(find(G[u].begin(),G[u].end(),p));
	parent[u]=p,size[u]=1,inTime[u]=++timeCount,rank[timeCount]=u;
	for(int v:G[u]) {
		dfs1(v,u),size[u]+=size[v];
		if(size[v]>size[maxChild[u]]) maxChild[u]=v;
	}
	outTime[u]=timeCount;
}
int c[MAXN],stack[MAXN],top;
void dfs2(int u) {
	z[u]=h[a[u]];
	for(int v:G[u]) if(v^maxChild[u]) {
		dfs2(v),z[u]=(z[u]+z[v])%MOD,b[v]=1<<a[v];
		for(int i=inTime[v];i<=outTime[v];++i) {
			b[rank[i]]=(i==inTime[v]?0:b[parent[rank[i]]])|1<<a[rank[i]];
			memset(f[b[rank[i]]>>k],0,sizeof(f[0]));
		}
	}
	auto add=[&](int s,int o) {
		int r=s>>k,l=s&L;
		for(int x=0;x<=L;++x) f[r][x]+=o*wl[x|l];
	};
	auto query=[&](int s) {
		int r=s>>k,l=s&L; ll o=0;
		for(int x=0;x<R;++x) o=(o+(f[x][l]%MOD+MOD)*wr[x|r])%MOD;
		return o;
	};
	if(maxChild[u]) {
		dfs2(maxChild[u]),z[u]=(z[u]+z[maxChild[u]])%MOD;
		function<void(int,int)> dfs3=[&](int x,int s) {
			if(s>>a[u]&1) return ;
			if(!c[s]++) stack[++top]=s;
			for(int y:G[x]) dfs3(y,s|1<<a[y]);
		};
		dfs3(maxChild[u],1<<a[maxChild[u]]);
		for(;top;c[stack[top--]]=0) add(stack[top],-c[stack[top]]),add(stack[top]|1<<a[u],c[stack[top]]);
	}
	z[u]=(z[u]+query(1<<a[u]))%MOD,add(1<<a[u],1);
	for(int v:G[u]) if(v^maxChild[u]) {
		for(int i=inTime[v];i<=outTime[v];++i) {
			b[rank[i]]|=1<<a[u];
			if(!c[b[rank[i]]]++) stack[++top]=b[rank[i]];
		}
		for(int i=1;i<=top;++i) z[u]=(z[u]+query(stack[i])*c[stack[i]])%MOD;
		for(;top;c[stack[top--]]=0) add(stack[top],c[stack[top]]);
	}
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m,k=m/2,L=(1<<k)-1,R=1<<(m-k);
	for(int i=0;i<m;++i) cin>>h[i];
	for(int s=0;s<=L;++s) {
		wl[s]=1;
		for(int i=0;i<k;++i) if(s>>i&1) wl[s]=wl[s]*h[i]%MOD;
	}
	for(int s=0;s<R;++s) {
		wr[s]=1;
		for(int i=0;i<m-k;++i) if(s>>i&1) wr[s]=wr[s]*h[i+k]%MOD;
	}
	for(int i=1;i<=n;++i) cin>>a[i],--a[i];
	for(int i=1,u,v;i<n;++i) cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
	dfs1(1,0),dfs2(1);
	for(int i=1;i<=n;++i) cout<<z[i]<<" \n"[i==n];
	return 0;
}

*B. [P14652] Đây là, Hội đồng Dừng Cuối (8)

Liên kết bài toán

Đây là bài toán phân bổ, dễ nghĩ đến mô hình min-cut. Tuy nhiên, min-cut thông thường chỉ có hai trạng thái \(u\in S\) hoặc \(u\in T\).

Cần tách nút thành \(x_u,y_u\) và phân biệt ba trạng thái dựa trên \(x_u,y_u\in S\): A khi \(x_u\in S,y_u\in T\), B khi \(x_u\in T,y_u\in S\), C khi \(x_u,y_u\in S\).

Đối với cạnh loại hai, kết nối hai cặp \((x_u,y_v),(x_v,y_u)\) với trọng số 1. Phân tích các trường hợp chứng minh tính hợp lệ.

Đối với cạnh loại một, thêm 2 vào đáp án và kết nối bốn cặp tương ứng với trọng số 1.

Chứng minh rằng trạng thái \(x_u,y_u\in T\) không tối ưu như chuyển các nút liên thông sang \(x_u,y_u\in S\).

Yêu cầu tìm k min-cut nhỏ nhất theo thứ tự từ điển.

Dựa trên kết luận min-cut, thu gọn mạng còn các thành phần liên thông. Mỗi lần thêm nút vào \(S\), thêm các nút kế tiếp vào \(S\), ngược lại thêm vào \(T\).

Sử dụng bitset để kiểm tra tính可达 giữa các nút trong mạng dư.

Độ phức tạp \(\mathcal O(m\sqrt m+\frac{nm}\omega+(n+m)k)\).

Mã nguồn:

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5,MAXE=1e7+5,inf=1e9,B=4096;
struct Edge { int v,f,e; } G[MAXE];
int S,T,ec=1,hd[MAXN],cur[MAXN],d[MAXN];
void link(int u,int v,int w) {
	G[++ec]={v,w,hd[u]},hd[u]=ec;
	G[++ec]={u,0,hd[v]},hd[v]=ec;
}
bool bfs() {
	memset(d,-1,sizeof(d)),memcpy(cur,hd,sizeof(hd));
	queue <int> Q; d[S]=0,Q.push(S);
	while(Q.size()) {
		int u=Q.front(); Q.pop();
		for(int i=hd[u];i;i=G[i].e) if(G[i].f&&d[G[i].v]<0) d[G[i].v]=d[u]+1,Q.push(G[i].v);
	}
	return ~d[T];
}
int dfs(int u,int f) {
	if(u==T) return f;
	int r=f;
	for(int &i=cur[u];i;i=G[i].e) if(d[G[i].v]==d[u]+1&&G[i].f) {
		int g=dfs(G[i].v,min(G[i].f,r));
		if(!g) d[G[i].v]=-1;
		r-=g,G[i].f-=g,G[i^1].f+=g;
		if(!r) return f;
	}
	return f-r;
}
int n,m1,m2,q,dfn[MAXN],low[MAXN],dcnt,st[MAXN],tp,bl[MAXN],scnt,vis[MAXN];
bool ins[MAXN],ok[MAXN];
vector <int> E[MAXN];
void tarjan(int u) {
	dfn[u]=low[u]=++dcnt,ins[st[++tp]=u]=1;
	for(int i=hd[u];i;i=G[i].e) if(G[i].f) {
		int v=G[i].v;
		if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
		else if(ins[v]) low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]) for(++scnt;ins[u];ins[st[tp--]]=0) bl[st[tp]]=scnt;
}
bitset <B> f[MAXN];
void update(int u,int c) {
	if(~vis[u]) return ;vis[u]=c,st[++tp]=u;
	for(int i=hd[u];i;i=G[i].e) if(bl[u]==bl[G[i].v]||G[i^c].f) update(G[i].v,c);
}
string result;
void solve(int i) {
	if(!q) exit(0);
	if(i>n) return cout<<result<<"\n",--q,void();
	int h=tp;
	auto rollback=[&]() { for(;tp>h;vis[st[tp--]]=-1); };
	if(!ok[i]&&vis[i]!=0&&vis[i+n]!=1) result[i-1]='A',update(i,1),update(i+n,0),solve(i+1),rollback();
	if(!ok[i+n]&&vis[i]!=1&&vis[i+n]!=0) result[i-1]='B',update(i,0),update(i+n,1),solve(i+1),rollback();
	if(vis[i]!=1&&vis[i+n]!=1) result[i-1]='C',update(i,0),update(i+n,0),solve(i+1),rollback();
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m1>>m2>>q,S=2*n+1,T=S+1;
	for(int i=1;i<=n;++i) {
		char type; cin>>type;
		if(type=='A') link(i,T,inf),link(S,i+n,inf);
		if(type=='B') link(S,i,inf),link(i+n,T,inf);
		if(type=='C') link(S,i,inf),link(S,i+n,inf);
	}
	for(int i=1,u,v;i<=m1+m2;++i) {
		cin>>u>>v,link(u+n,v,1),link(u,v+n,1),link(v+n,u,1),link(v,u+n,1);
		if(i<=m1) link(u,v,1),link(u+n,v+n,1),link(v,u,1),link(v+n,u+n,1);
	}
	int residual=2*m1;
	while(bfs()) residual-=dfs(S,inf);
	cout<<residual<<"\n";
	for(int i=1;i<=T;++i) if(!dfn[i]) tarjan(i);
	for(int u=1;u<=T;++u) for(int i=hd[u];i;i=G[i].e) if(G[i].f&&bl[u]!=bl[G[i].v]) E[bl[u]].push_back(bl[G[i].v]);
	for(int l=1,r;l<=2*n;l=r+1) {
		r=min(2*n,l+B-1);
		for(int i=1;i<=scnt;++i) f[i].reset();
		for(int i=l;i<=r;++i) f[bl[i]][i-l]=1;
		for(int u=1;u<=scnt;++u) for(int v:E[u]) f[u]|=f[v];
		for(int i=l;i<=r;++i) ok[i]=f[bl[i> n?i-n:i+n]][i-l];
	}
	memset(vis,-1,sizeof(vis)),update(S,0),update(T,1);
	result=string(n,'A'),solve(1);
	return 0;
}

*C. [P13758] Mùa Hè Kết Thúc (7)

Liên kết bài toán

Từ trường hợp chuỗi, đặc trưng của cây khung nhỏ nhất (MST) là chọn các cạnh tạo thành các đoạn, sau đó nối mỗi đoạn với giá trị nhỏ nhất cộng với \(x=b_0+\min b_i\).

Có thể coi giá trị này là một hàm của \(x\) có dạng bao lồi, gộp các đoạn bằng phép nhân ma trận.

Hiện tại cần hỗ trợ cập nhật \(b\) và duy trì bao lồi động.

Phân khối, mỗi khối xây cây đoạn, duy trì giá trị ma trận tại mỗi vị trí \(x\), nhân các giá trị khối lại.

Độ dài khối \(B\), độ phức tạp cập nhật \(\mathcal O(B)\), truy vấn \(\mathcal O(\frac nB\log B)\). Nút nghẽn cổ chai là tìm nhị phân bao lồi. Có thể sắp xếp và sử dụng con trỏ kép để đạt độ phức tạp tuyến tính khi xử lý ngoại tuyến.

Với cây khung tổng quát, chỉ cần đảm bảo tính liên thông tại mọi bước, nên có thể biến đổi cây thành chuỗi theo thứ tự duyệt DFS.

Độ phức tạp \(\mathcal O(q\sqrt {n\log n})\), cài đặt kỹ lưỡng có thể đạt \(\mathcal O(q\sqrt n)\).

Mã nguồn:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
typedef basic_string<ll> vec;
const int MAXN=2e5+5,B=512;
const ll inf=1e15;
void multiply(const vec&u,const vec&v,ll *w) {
	int i=0,j=0,l=u.size()-1,r=v.size()-1;
	for(w[0]=u[0]+v[0];i<l||j<r;) {
		if(j==r||(i<l&&u[i+1]-u[i]<v[j+1]-v[j])) w[i+j+1]=w[i+j]+u[i+1]-u[i],++i;
		else w[i+j+1]=w[i+j]+v[j+1]-v[j],++j;
	}
}
void combine(const vec&xl,const vec&xr,const vec&yl,const vec&yr,vec&z) {
	static ll x[B+5],y[B+5];
	multiply(xl,xr,x),multiply(yl,yr,y),z.resize(xl.size()+xr.size()-1);
	for(int i=0;i<(int)z.size();++i) z[i]=min(x[i],y[i]);
}
ll query(const vec&x,ll z) {
	int p=0,m=x.size()-1;
	if(m) for(int k=1<<__lg(m);k;k>>=1) if(p+k<=m&&x[p+k-1]-x[p+k]>z) p+=k;
	return x[p]+p*z;
}
vec f[B<<1][2][2];
int _,n,m,q,dsu[MAXN],ed[MAXN],nx[MAXN],id[MAXN],ps[MAXN];
ll a0[MAXN],a[MAXN],b[MAXN],dp[MAXN][2],mn[MAXN],vl[MAXN];
int find(int x) { return x^dsu[x]?dsu[x]=find(dsu[x]):x; }
void initialize(int p,int x) {
	f[p][0][0]={b[x],a[x]};
	f[p][0][1]={a[x]+b[x],inf};
	f[p][1][0]={inf,0};
	f[p][1][1]={b[x],inf};
}
void pushUp(int p) { for(int l:{0,1}) for(int r:{0,1}) combine(f[p<<1][l][0],f[p<<1|1][0][r],f[p<<1][l][1],f[p<<1|1][1][r],f[p][l][r]); }
void build(int l,int r,int p) {
	if(l==r) return initialize(p,l);
	int mid=(l+r)>>1;
	build(l,mid,p<<1),build(mid+1,r,p<<1|1);
	pushUp(p);
}
void update(int x,int l,int r,int p) {
	if(l==r) return initialize(p,l);
	int mid=(l+r)>>1;
	x<=mid?update(x,l,mid,p<<1):update(x,mid+1,r,p<<1|1);
	pushUp(p);
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>_>>n>>m>>q>>a[0],a0[0]=a[0];
	multiset <ll> A;
	for(int i=1;i<=n;++i) cin>>a0[i],A.insert(a0[i]);
	vector <array<ll,3>> E(m);
	for(auto&e:E) cin>>e[1]>>e[2]>>e[0];
	for(int i=1;i<=n;++i) dsu[i]=ed[i]=i,E.push_back({inf,1,i});
	sort(E.begin(),E.end());
	for(auto e:E) {
		int x=find(e[1]),y=find(e[2]);
		if(x!=y) nx[ed[x]]=y,tw[ed[x]]=e[0],dsu[y]=x,ed[x]=ed[y];
	}
	for(int u=find(1),i=1;i<=n;++i,u=nx[u]) id[u]=i,b[i]=tw[u];
	for(int i=1;i<=n;++i) a[id[i]]=a0[i];
	memcpy(a0,a,sizeof(a));
	for(int i=1;i<=q;++i) {
		cin>>ps[i]>>vl[i],ps[i]=id[ps[i]];
		if(ps[i]) A.erase(A.find(a[ps[i]]));
		a[ps[i]]=vl[i];
		if(ps[i]) A.insert(a[ps[i]]);
		mn[i]=*A.begin()+a[0],dp[i][0]=-*A.begin(),dp[i][1]=inf;
	}
	for(int l=1,r;l<=n;l=r+1) {
		memcpy(a,a0,sizeof(a));
		r=min(n,l+B-1),build(l,r,1);
		for(int i=1;i<=q;++i) {
			if(l<=ps[i]&&ps[i]<=r) a[ps[i]]=vl[i],update(ps[i],l,r,1);
			ll z0=min(dp[i][0]+query(f[1][0][0],mn[i]),dp[i][1]+query(f[1][1][0],mn[i]));
			ll z1=min(dp[i][0]+query(f[1][0][1],mn[i]),dp[i][1]+query(f[1][1][1],mn[i]));
			dp[i][0]=z0,dp[i][1]=z1;
		}
	}
	for(int i=1;i<=q;++i) cout<<dp[i][1]<<"\n";
	return 0;
}

*D. [P11066] Thang máy (9)

Liên kết bài toán

Ý tưởng chính là kích hoạt tất cả thang máy theo thứ tự để tự do điều chỉnh từng thang máy.

Kích hoạt từ phải sang trái, mục tiêu luôn nằm bên phải thang máy hiện tại.

Xử lý các điểm \(p_i>i\) trực tiếp. Nếu \(p_i\le i\), di chuyển đến \(i+1\).

Sau đó, từ trái sang phải, di chuyển các điểm \(p_i\le i\) đến vị trí \(p_i\).

Vấn đề là điểm \(p_i=i+1\) sẽ cản trở quá trình di chuyển. Quan sát thấy hoán đổi với bất kỳ điểm nào cũng đảm bảo tính hợp lệ.

Tạo cặp ghép, nếu có điểm \(p_i=i+1\) thì hoán đổi với điểm kia trong cặp. Sử dụng cấu hình cách 2 để ghép.

Do \(m\) hợp lệ, có thể loại bỏ phần tử để \(m\) chẵn, sau đó phân loại theo \(m\bmod 4\) để ghép. Trường hợp đặc biệt \(m=2\) và \(m\bmod 4=2\) xử lý riêng.

Chứng minh số thao tác không vượt quá \(5n\).

Độ phức tạp \(\mathcal O(n)\).

Mã nguồn:

#include<bits/stdc++.h>
using namespace std;
typedef basic_string<int> vec;
const int MAXN=5e4+5;
int n,m,a[MAXN],b[MAXN];
vec solution;
void process(int *positions) {
	int left=0,right=0;
	for(int i=m;i;--i) {
		if(positions[i]>i) solution+=positions[i];
		else solution+=i+1;
		right=max(right,positions[i]-i),left=max(left,i-positions[i]);
	}
	solution+=0;
	for(int i=1;i<=m;++i) if(positions[i]<=i) solution+=positions[i];
	solution+=vec(max(right-1,left+1),0);
}
void solve() {
	solution.clear();
	for(int i=1;i<=m;++i) cin>>a[i],b[i]=i;
	if(m==2) return cout<<(a[1]==1?"0\n\n":"7\n3 3 0 1 0 2 0\n"),void();
	if(m==3) {
		if(a[1]==2||a[2]==3) solution={4,3,3,0,1,0,2,3,0},swap(a[1],a[2]),swap(b[1],b[2]);
	} else {
		for(int i=1,k=m-(m&1);i<=k;i+=4) {
			if(i+5==k) {
				for(int j:{0,1,2}) if(a[i+j]==i+j+1||a[i+j+3]==i+j+4) swap(a[i+j],a[i+j+3]),swap(b[i+j],b[i+j+3]);
				break;
			}
			for(int j:{0,1}) if(a[i+j]==i+j+1||a[i+j+2]==i+j+3) swap(a[i+j],a[i+j+2]),swap(b[i+j],b[i+j+2]);
		}
		process(b);
	}
	process(a),cout<<solution.size()<<"\n";
	for(int x:solution) cout<<x<<" "; cout<<"\n";
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _; cin>>_;
	for(int q,o;_--;) {
		cin>>q>>n>>m>>o;
		while(q--) solve();
	}
	return 0;
}

Thẻ: Data-Structures Algorithms competitive-programming dynamic-programming graph-theory

Đăng vào ngày 1 tháng 6 lúc 14:48

Thành phố Cuồng loạn

Ghi chú giải bài tập lập trình (Bản 14)

A. [P11648] 2236 A.D. (4.5)

*B. [P14652] Đây là, Hội đồng Dừng Cuối (8)

*C. [P13758] Mùa Hè Kết Thúc (7)

*D. [P11066] Thang máy (9)

Thẻ Phổ Biến