test29

冷飯模擬賽來了。

1-A 地址壓縮 (address.cpp)

#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)

using namespace std;

const int N=105;

int T, n, len, cnt;
char str[N];

void mian() {
	cin >> (str+1), n=strlen(str+1), len=8, cnt=0;
	for(int l=1, r=1; l<=n; l=r+1, r=l) {
		if(str[l]==':') continue;
		while(str[r+1]!=':') ++r;
		--len;
	}
	for(int l=1, r=1; l<=n; l=r+1, r=l) {
		if(str[l]==':') {
			if(str[l+1]==':') {
				while(len--) {
					cout << "0000";
					if(++cnt<8) cout << ':';
				}
			}
			continue;
		}
		while(r<n&&str[r+1]!=':') ++r;
		up(i,1,4-(r-l+1)) cout << "0";
		up(i,l,r) cout << str[i];
		if(++cnt<8) cout << ':';
	}
	cout << '\n';
}

signed main() {
//	freopen("1.txt","r",stdin);
	freopen("address.in","r",stdin); 
	freopen("address.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> T;
	while(T--) mian();
	return 0;
}

1-B 準高速列車 (express.cpp)

因為 \(B\leq C\leq A\)，且高速列車停靠的地方準高速列車一定停靠，走到一個站點 \(x\) 的最優方案一定是盡量走 高速列車->準高速列車->普通列車，我們考慮對于一個高速列車的間隔，怎么設定額外的準高速列車，顯然是設定在第一個不能直接到達的地方是最優的，因為往左會浪費，往右肯定不會更容易滿足，我們枚舉新設定的車車，設在能加最多站的地方即可。

#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)

using namespace std;

const int N=100005;

int n, m, k, a, b, c, T, s[N], p[N], Ans;

signed main() {
//	freopen("1.txt","r",stdin);
	freopen("express.in","r",stdin); 
	freopen("express.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> k >> a >> b >> c >> T;
	up(i,1,m) cin >> s[i], --s[i];
	Ans=(s[m]*b<=T), k-=m;
	up(i,1,m-1) {
		if(s[i]*b>T) { p[i]=s[i+1]; continue; }
		int k=min((T-s[i]*b)/a,s[i+1]-1-s[i]);
		Ans+=(k+1), p[i]=s[i]+k+1;
	}
	while(k--) {
		int j=0, kk=0;
		up(i,1,m-1) {
			if(p[i]>s[i+1]) continue;
			int val=s[i]*b+(p[i]-s[i])*c;
			if(val<=T) {
				int k=min((T-val)/a,s[i+1]-p[i]-1);
				if(k>=kk) j=i, kk=k;
			}
		}
		if(j) Ans+=(kk+1), p[j]+=kk+1;
	}
	cout << Ans-1 << '\n';
	return 0;
}

1-C 通信調度 (dispatch.cpp)

差分、拓展域并查集維護信息，考慮最后的連通塊即可。

#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pb push_back

using namespace std;

const int N=600005, M=19, P=1e9+7;

int n, m, T, dep[N], fa[N][M], dsu[N], d[N], Ans;
vector<int> to[N];

int get(int x) { return x==dsu[x]?x:dsu[x]=get(dsu[x]); }
void merge(int x,int y) { x=get(x), y=get(y), dsu[x]=y; }

void dfs(int x,int fad) {
	dep[x]=dep[fad]+1, fa[x][0]=fad;
	up(i,1,T) fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int y:to[x]) if(y!=fad) dfs(y,x);
}

void solve(int x,int fad) {
	for(int y:to[x]) if(y!=fad) solve(y,x), d[x]+=d[y];
	if(d[x]) merge(x,fad), merge(x+n,fad+n); 
}

int lca(int x,int y) {
	if(dep[x]<dep[y]) swap(x,y);
	dn(i,T,0) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
	if(x==y) return x;
	dn(i,T,0) if(fa[x][i]!=fa[y][i]) x=fa[x][i], y=fa[y][i];
	return fa[x][0];
}

signed main() {
//	freopen("data.txt","r",stdin);
	freopen("dispatch.in","r",stdin); 
	freopen("dispatch.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m, T=log2(n), Ans=1;
	up(i,2,n) {
		int u, v;
		cin >> u >> v;
		to[u].pb(v);
		to[v].pb(u);
	}
	dfs(1,0);
	up(i,1,n) dsu[i]=i, dsu[i+n]=i+n;
	while(m--) {
		int x, y, p, X, Y;
		cin >> x >> y;
		if(fa[x][0]==y||fa[y][0]==x) continue;
		X=x, Y=y, p=lca(x,y);
		dn(i,T,0) if(dep[fa[X][i]]>dep[p]) X=fa[X][i];
		dn(i,T,0) if(dep[fa[Y][i]]>dep[p]) Y=fa[Y][i];
		if(p==x) swap(x,y), swap(X,Y);
		if(p==y) ++d[x], --d[X];
		else {
			++d[x], --d[X], ++d[y], --d[Y];
			merge(X,Y+n), merge(X+n,Y);
		}
	}
	solve(1,0); 
	up(i,1,n) {
		int l=get(i), r=get(i+n);
		if(l==r) { cout << 0 << '\n'; return 0; }
	}
	up(i,1,n) merge(i,i+n);
	merge(1,2);
	up(i,1,(n<<1)) if(dsu[i]==i) Ans=2*Ans%P; 
	cout << Ans << '\n';
	return 0;
}

1-D 包裹運輸 (transport.cpp)

最顯然的貪心是，每次擠了的地方選擇先運輸離得最遠的。但是這個過程也太惡心了根本不知道怎么做，所以我們考慮想辦法更好地刻畫答案，就比如我們想看看一個點的答案能不能通過二元貢獻刻畫，我們發現不能，我們考慮一下能不能刻畫某一條邊的貢獻，有一個比較顯眼的答案下界，考慮會經過此邊的點距 \(d_1,\dots,d_m\) 手玩之后可以發現劃開下界是 \(\max\{d_i+\sum_{j\neq i} [d_j\geq d_i]\}\)，那么我們要動態維護子樹邊集 \(d\) 以及上述答案，可以考慮線段樹合并。下面還要考慮怎么拆環，對于在新樹上會斷成兩段，前鏈 \(d\) 變化、后鏈 \(d\) 是對的，考慮在數前拼湊一個等價的樹，來保證其長度的正確性，然后有些地方少些東西不影響 rmq 所以是對的。

#include<bits/stdc++.h>
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pb push_back

using namespace std;

const int N=400005, M=15000005;

int n, p[N], m, tag[N], L[N], R[N], stamp, dep[N];
int tr[N], Ans, cnt[M], mx[M], tot, ls[M], rs[M], dsu[N];
vector<int> to[N], add[N], del[N];

void dfs(int x) {
	L[x]=++stamp;
	for(int y:to[x]) dep[y]=dep[x]+1, dfs(y);
	R[x]=stamp;
}

void eadd(int u,int v) {
	add[u].pb(dep[u]);
	del[v].pb(dep[u]);
//	cout << "add " << u << " -> " << v << " : " << dep[u] << '\n';
}

inline void tup(int p) {
	cnt[p]=cnt[ls[p]]+cnt[rs[p]];
	mx[p]=max(mx[ls[p]]+cnt[rs[p]],mx[rs[p]]);
}

void merge(int &p,int q,int s=1,int e=2*n) {
	if(!p||!q) { p=p|q; return; }
	if(s==e) { cnt[p]+=cnt[q], mx[p]=cnt[p]?s+cnt[p]:0; return; }
	int mid=(s+e)>>1;
	merge(ls[p],ls[q],s,mid);
	merge(rs[p],rs[q],mid+1,e);
	tup(p); 
} 

void modify(int x,int v,int &p,int s=1,int e=2*n) {
	if(!p) p=++tot;
	if(s==e) { cnt[p]+=v, mx[p]=cnt[p]?s+cnt[p]:0; return; }
	int mid=(s+e)>>1;
	if(x<=mid) modify(x,v,ls[p],s,mid);
	if(x>mid) modify(x,v,rs[p],mid+1,e);
	tup(p);
}

void solve(int x) {
	for(int v:add[x]) modify(v,+1,tr[x]);
	for(int y:to[x]) {
		solve(y);
		merge(tr[x],tr[y]);
	}
	for(int v:del[x]) modify(v,-1,tr[x]);
	Ans=max(Ans,mx[tr[x]]-dep[x]);
//	if(mx[tr[x]]-dep[x]==9) {
//		cout << "fuck " << x << ' ' << mx[tr[x]] << ' ' << -dep[x] << '\n';
//	}
}

int get(int x) { return x==dsu[x]?x:dsu[x]=get(dsu[x]); }

signed main() {
    freopen("transport.in","r",stdin);
    freopen("transport.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	up(i,1,n) dsu[i]=i;
	up(i,1,n) {
		cin >> p[i], p[i+n]=p[i]+n;
		int x=get(i), y=get(p[i]);
		if(x!=y) dsu[x]=y;
	}
	vector<int> Rt;
	up(i,1,n) if(dsu[i]==i) {
		for(int j=i; !tag[j]; j=p[j]) tag[j]=i+n;
		p[i]+=n, p[i+n]=0, Rt.pb(i+n);
//		cout << "w : " << p[i] << '\n'; 
	}
//	cout << "p : "; up(i,1,2*n) cout << p[i] << ' '; cout << '\n'; 
	up(i,1,2*n) if(p[i]) to[p[i]].pb(i);
	for(int u:Rt) dep[u]=1, dfs(u); // cout << "dfs " << u << '\n';
//	up(i,1,2*n) cout << "qwq " << i << ' ' << dep[i] << '\n';
	cin >> m;
	while(m--) { 
		int x, y;
		cin >> x >> y;
		if(get(x)!=get(y)) {
			cout << -1 << '\n';
			exit(0);
		}
		if(tag[y]) {
			if(L[y]<=L[x]&&L[x]<=R[y]) {
				eadd(x,y);
				eadd(x+n,y+n);
			}
			else {
				eadd(x,y+n);
				eadd(x+n,tag[y]);
			}
		}
		else {
			if(L[y]<=L[x]&&L[x]<=R[y]) {
				eadd(x,y);
				eadd(x+n,y+n);
			}
			else {
				cout << -1 << '\n';
				exit(0);
			}
		}
	}
	for(int u:Rt) solve(u);
	cout << Ans << '\n';
	return 0;
}