专栏文章

0604

CCap1taL
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip4zc2m
此快照首次捕获于
2025/12/03 06:15
3 个月前
此快照最后确认于
2025/12/03 06:15
3 个月前
查看原文

CF1566F

数轴， nn 个点， mm 个线段。可花费 1 的代价挪动一个点。一个线段被标记，当且仅当存在一个点经过了这条线段。求标记所有线段的最小代价。
n,m≤2×105n,m \leq 2\times 10^5

思考

初始情况下内部含有点的线段都没用了，因此所有的线段现在与初始点无交。
如果线段 A 包含线段 B，那么 A 是无用的。
如果两个点的行动轨迹出现了交叉那么一定不优。因此每个点的移动范围就是包含它初始位置的一小段区间。
一个点要么向左挪动要么向右挪动。假设最终的移动范围区间是 [l,r][l,r] ，初始位置为 ii ，那么代价一定为 r−l+min⁡(i−l,r−i)r-l+\min(i-l,r-i) 。现在要决定的问题就是每个点的这个区间是什么。
尝试依次枚举每个点先向左还是先向右。失败
考虑到两个点区间之间的空隙不会产生贡献，相当于被 "节省" 了。猜测可以先贪心选择空隙最大的部分。发现可以进一步调整，失败。

题解

尝试枚举每个点的方向进行 DP 实则是可行的。
会觉得 fi,0/1f_{i,0/1} 无法转移的原因是，转移时可以向左侧枚举线段，但这个状态没记录向右走到哪，没法算答案。一个解决方案是把向右的位置开进状态里，即 fi,0/1,jf_{i,0/1,j} 表示了 ii 最右抵达 jj 这个线段左侧，即可转移。状态数均摊下来是线性的，但转移复杂度是平方的，应该可以使用数据结构优化。
更好的办法是拆开计算。
转移时我们枚举一个 i−1i-1 和 ii 之间的线段，并枚举 i−1i-1 是向左还是向右。那么我们可以把 i−1i-1 右侧的部分交由 fif_i 计算。本质上来说，状态的定义改变了，变为 fi,0/1f_{i,0/1} 表示考虑了前 ii 个点，第 ii 个点先向左 / 右，且不考虑 ii 右侧移动代价的最小代价。
能这样做是因为， jj 的维度对于转移时，贡献了一个与 fif_i 无关的量。既然它只与 i,ji,j 下标有关，而与 ii 的决策无关，把它开成维度就是没有意义且浪费的。
别急着丢掉一个 DP
CPP
int n,m;
LL a[MAXN];
class Range{
public:
	LL l,r;

	bool operator < (const Range& x)const{
		if(r==x.r)	return l>x.l;
		return r>x.r;
	}
};
vector<Range> ls[MAXN];
void solve(bool SPE){ 
	n=RIN,m=RIN;
	foru(i,1,n){
		a[i]=RIN;
	}
	sort(a+1,a+1+n);
	
	foru(i,0,n){
		ls[i].clear();
	}

	static set<pair<LL,int>> st;
	st.clear();
	st+=mkp(LLONG_MIN,0);
	st+=mkp(LLONG_MAX,n+1);
	foru(i,1,n){
		st+=mkp(a[i],i);
	}
	foru(i,1,m){
		int l=RIN,r=RIN;
		auto it=st.lower_bound(mkp(l,0));
		if(it->fi<=r){
			//useless segment
			continue;
		}
		ls[prev(it)->se]+=Range{l,r};
	}

	static LL f[MAXN][2];
	foru(i,0,n+1){
		f[i][0]=f[i][1]=0;
	}

	// init f[1];
	{
		int L=a[1];
		for(auto [l,r]:ls[0]){
			chkmin(L,r);
		}
		f[1][0]=2*(a[1]-L);
		f[1][1]=(a[1]-L);
	}

	foru(i,2,n){
		//enum segments between i-1 and i
		sort(All(ls[i-1]));

		f[i][0]=f[i][1]=LLONG_MAX;

		static vector<LL> pre;
		pre.clear();
		pre.resize(ls[i-1].size()+1,a[i-1]);
		for(int j=ls[i-1].size()-1;j>=0;j--){
			pre[j]=max(pre[j+1],(LL)ls[i-1][j].l);
		}

		size_t ptr=0;
		for(size_t j=0;j<ls[i-1].size();j++){
			LL L=ls[i-1][j].r;
			LL R=a[i-1];
			while(ptr<ls[i-1].size() && ls[i-1][ptr].r==L)	ptr++;
			// for(size_t k=j+1;k<ls[i-1].size();k++){
			// 	if(ls[i-1][k].r!=L){
			// 		chkmax(R,ls[i-1][k].l);
			// 		// chkmax(R,pre[k]);
			// 		// break;
			// 	}
			// }
			chkmax(R,pre[ptr]);
			LL v0=f[i-1][0]+(R-a[i-1]);
			LL v1=f[i-1][1]+(R-a[i-1])*2;
			chkmin(f[i][0],min(v0,v1)+(a[i]-L)*2);
			chkmin(f[i][1],min(v0,v1)+(a[i]-L));
		}

		LL v0=f[i-1][0]+(pre[0]-a[i-1]);
		LL v1=f[i-1][1]+(pre[0]-a[i-1])*2;
		chkmin(f[i][0],min(v0,v1));
		chkmin(f[i][1],min(v0,v1));
	}

	LL ans=LLONG_MAX;
	
	LL R=a[n];
	for(auto [l,r]:ls[n]){
		chkmax(R,l);
	}

	ans=min(f[n][0]+(R-a[n]),f[n][1]+(R-a[n])*2);

	cout<<ans<<'\n';

	// exit(0);
	return ;
}

P8179

有 nn 套轮胎，滴叉需要用这些轮胎跑 mm 圈。
使用第 ii 套轮胎跑的第 jj 圈（对每套轮胎单独计数）需要 ai+bi(j−1)2a_i+b_i(j-1)^2 秒。在本题中，你不需要担心爆胎，安全车，红旗或者不同的比赛策略。
滴叉需要进入维修站来更换轮胎，所消耗的时间为 tt 秒。特别地，滴叉使用的第一套轮胎不需要进站更换。
为了帮助滴叉拿下 WDC，你需要最小化总时间，总时间等于每圈的时间之和加上进站所花费的时间。
1≤n,bi≤5001\leq n,b_i\leq 500 ， 0≤t≤5000\leq t\leq 500 ， 1≤m≤2×1051\leq m\leq 2 \times 10^5 ， 1≤ai≤1091\leq a_i\leq 10^9 。

思考

DP，决策单调性可以做到 O(nmlog⁡m)O(nm\log m)
转移里的平方和公式很烦
(j−k−1)(j−k)(2j−2k−1)(j-k-1)(j-k)(2j-2k-1)\\
拆开肯定会有 jkjk 的项。得在线性时间维护
继续找性质？

题解

应该从 t=0t=0 的地方入手。
t=0t=0 意味着换轮胎无消耗。又因为轮胎随使用的每圈开销是单调递增的，可以直接用一个堆贪心。 O(mlog⁡m)O(m\log m)
考虑 t≠0t\neq 0 的情况。首先容易发现一旦用一个轮胎就一定连续区间使用。切换到别的轮胎再切换回来完全不优。
因此可以直接把 tt "加给" 每个轮胎的第一圈开销。现在不存在 tt 了。
但此时发现无法贪心，因为轮胎的开销不是单调递增的了。
但每个轮胎除第一圈以外的部分依然是单调递增的，且注意到 tt 很小，这很奇怪，按理说 tt 如果不用被算进复杂度里，是没道理这么小的，正如 ai,bi≤109a_i,b_i\le 10^9 。
在非单调时，我们有 DP 做法，复杂度较高。在单调时，我们有贪心做法，复杂度较低。
尝试把二者拼起来。我们需要给轮胎划的使用分成两个阶段。第一阶段不单调，第二阶段单调。我们将在第一阶段使用 DP 决策，第二阶段使用贪心决策，最后枚举第一阶段使用的轮胎总数，把二者拼起来。
如果只关注单调性，我们甚至可以只把第一个轮胎分为第一阶段。
但分阶段会带来问题。
假设对于某个轮胎，我们把它的前 xx 圈划分为第一阶段，那么在拼答案的时候，就不可避免的可能会存在这种情况：第一阶段并没有取满 [1,x][1,x] 的所有圈。
这种情况显然是非法的。我们希望这种情况能被自动地排除掉，希望对于每个非法情况，一定存在一个合法情况比这个非法情况更优。
我们尝试对于每个非法情况构造对应的更优合法情况。一个很无脑的做法是，把贪心部分选的轮胎往前推，补充到 [1,x][1,x] 中。
如果我们的确在第一阶段选了第 11 圈，那么这个操作是没问题的，一定会得到更优的合法解。但如果第一圈没有被选择，那我们就无法分析二者的优劣。拼答案的时候，我们无法钦定是否选第一圈，没法做。
考虑为什么无法分析二者优劣。本质上是因为 ai+ta_i+t 有可能比贪心部分的开销大，导致推过去反而更劣。
那么答案呼之欲出了，我们只需要排除掉这种情况即可。
即，我们希望贪心部分的开销全部比 ai+ta_i+t 更大。
ai+t≤ai+bi(x−1)2a_i+t\le a_i+b_i(x-1)^2
发现这个题非常厉害地保证了 ** bi>0b_i>0 ** 。因此可以得到 x≥t+1x\ge \sqrt{t}+1 。于是我们只需要把前 t+1\sqrt{t}+1 圈分为第一阶段做 DP 即可。分析一下复杂度为 O(n2t+mlog⁡m)O(n^2t+m\log m) 。使用决策单调性优化可以做到 O(n2tlog⁡t+mlog⁡m)O(n^2\sqrt{t}\log{\sqrt{t}}+m\log m) 。前者即可轻松通过。
观察诡异的数据范围
CPP
int n,m,t;
class Item{
public:
	LL a,b;
}a[505];

LL f[505][505*30];

LL calc(LL n){
	return n*(n+1)*(2*n+1)/6ll;
}

void solve(bool SPE){ 
	n=RIN,m=RIN,t=RIN;

	foru(i,1,n){
		a[i]={RIN,RIN};
	}
	
	int P=ceil(sqrt(t))+5;

	f[0][0]=0;
	foru(i,1,n*P){
		f[0][i]=1e18;
	}

	// cerr<<a[2].a<<endl;
	foru(i,1,n){
		foru(j,1,n*P){
			f[i][j]=f[i-1][j];
			foru(k,1,min(j,P)){
				if(f[i-1][j-k]==1e18)	continue;
				// cerr<<i<<' '<<j<<' '<<k<<endl;
				// if(i==2 && j==4 && k==3){
				// 	cerr<<' '<<a[2].a<<endl;
				// }
				chkmin(f[i][j],f[i-1][j-k]+t+a[i].a*k+a[i].b*calc(k-1));
			}
		}
	}
	// exit(0);
	// cout<<f[2][4]-t<<endl;
	// exit(0);
	static priority_queue<pair<i128,int>,vector<pair<i128,int>>,greater<pair<i128,int>>> q;
	static int cur[505];
	foru(i,1,n){
		cur[i]=P+1;
		q.push(mkp(a[i].a+a[i].b*P*P,i));
	}
	static i128 g[MAXN];
	g[0]=0;
	foru(i,1,m){
		g[i]=g[i-1];
		auto [v,id]=q.top();
		q.pop();
		g[i]+=v;
		cur[id]++;
		q.push(mkp(a[id].a+(i128)a[id].b*(cur[id]-1)*(cur[id]-1),id));
	}

	// cout<<P<<endl;

	i128 ans=i128(1e15)*i128(1e15);
	foru(i,0,min(n*P,m)){
		chkmin(ans,f[n][i]-t+g[m-i]);
	}
	cout<<ans;

	return ;
}

CF1592F1

给定一个 nn 行 mm 列的目标矩阵，矩阵元素只有 W 或 B ，并且你有一个初始矩阵，元素全为 W 。
现在你可以矩阵实施以下操作：
  1. 使用一块钱，选定一个包含 (1,1)(1,1) 的子矩阵，把矩阵中的元素全部反转（ W 变 B ， B 变 W ）。
  2. 使用两块钱，选定一个包含 (n,1)(n,1) 的子矩阵，把矩阵中的元素全部反转。
  3. 使用四块钱，选定一个包含 (1,m)(1,m) 的子矩阵，把矩阵中的元素全部反转。
  4. 使用三块钱，选定一个包含 (n,m)(n,m) 的子矩阵，把矩阵中的元素全部反转。
现在需要你求出把初始矩阵变为目标矩阵最少需要几块钱。

思考

23操作都是无用的，可以用1操作代替不劣
如果只有 1 操作，代价是确定性的，从右下角开始计算即可
考虑用 4 操作去替换 1 操作
只有一种情况可能被替换？
用一次 4？
并非，但答案差得并不多
可以用1个4替换4个1
可以用2个4替换7个1
不好操作

题解

刚才分析的 2个4 替换 7个1 实则分析有误。并且暴力代码写错了，如果写对的话应该可以注意到只会用一次 4。
对矩阵做一步神秘转化
si,j=ai,j⊕ai+1,j⊕ai,j+1⊕ai+1,j+1s_{i,j}=a_{i,j}\oplus a_{i+1,j} \oplus a_{i,j+1} \oplus a_{i+1,j+1}
首先，原矩阵变为全 0 等价于这个矩阵变为全 0。并且注意到这样变形之后，操作一变成了只反转 si,js_{i,j} ，操作四变成了反转 si−1,j−1,si−1,m,sn,j−1,sn,ms_{i-1,j-1},s_{i-1,m},s_{n,j-1},s_{n,m} 四个格子。
这样一来就变得非常简单了。注意到作两次操作四是不优的，因为 sn,ms_{n,m} 被反转两次，一共只操作了 66 个格子，不优于操作一。因此我们只会使用一次操作四。
正常反转之后处理操作四即可。
如果一个过程难以刻画，尝试把他转化成更简单的过程，同时与原先等价
CPP
int n,m;
int a[505][505];
bitset<505> b[505];
void solve(bool SPE){ 
	n=RIN,m=RIN;
	foru(i,1,n){
		foru(j,1,m){
			a[i][j]=RCIN=='B';
		}
	}
	
	foru(i,1,n){
		foru(j,1,m){
			a[i][j]^=a[i+1][j]^a[i][j+1]^a[i+1][j+1];
		}
	}

	int ans=0;

	foru(i,1,n){
		foru(j,1,m){
			ans+=a[i][j];
		}
	}

	foru(i,1,n-1){
		foru(j,1,m-1){
			if(a[i][j] && a[n][j] && a[i][m] && a[n][m]){
				ans--;
				goto fd;
			}
		}
	}

	fd:

	cout<<ans;
	return ;
}

CF1592F2

给定一个 nn 行 mm 列的目标矩阵，矩阵元素只有 W 或 B ，并且你有一个初始矩阵，元素全为 W 。
现在你可以矩阵实施以下操作：
使用一块钱，选定一个包含 (1,1)(1,1) 的子矩阵，把矩阵中的元素全部反转（ W 变 B ， B 变 W ）。
使用三块钱，选定一个包含 (n,1)(n,1) 的子矩阵，把矩阵中的元素全部反转。
使用四块钱，选定一个包含 (1,m)(1,m) 的子矩阵，把矩阵中的元素全部反转。
使用两块钱，选定一个包含 (n,m)(n,m) 的子矩阵，把矩阵中的元素全部反转。
现在需要你求出把初始矩阵变为目标矩阵最少需要几块钱。

思考

这次 2 3 操作似乎还是来搞笑的，忽略他
有了刚才的构造，现在变成一块钱反转某个，或两块钱反转一个矩形的四角
这次不是只用一个四了。
如果把 si,j=1s_{i,j}=1 的 ii 和 jj 连边，似乎变成了一个二分图匹配问题

Accept

对了，确实是一个二分图问题，连边后直接求最大匹配，讨论一下 sn,ms_{n,m} 的奇偶性即可
CPP
int n,m;
int a[505][505];
bitset<505> b[505];
void solve(bool SPE){ 
	n=RIN,m=RIN;
	foru(i,1,n){
		foru(j,1,m){
			a[i][j]=RCIN=='B';
		}
	}
	
	foru(i,1,n){
		foru(j,1,m){
			a[i][j]^=a[i+1][j]^a[i][j+1]^a[i+1][j+1];
		}
	}
	
	static vector<int> e[505];
	foru(i,1,n-1){
		if(a[i][m]!=1)	continue;
		foru(j,1,m-1){
			if(a[n][j]!=1)	continue;
			if(a[i][j]){
				e[i]+=j;
			}
		}
	}

	int ver=0;
	static int vis[505];
	static int nto[505];
	static int mto[505];
	int cnt=0;

	auto dfs=[&ver](auto dfs,int u)->bool{
		for(auto v:e[u]){
			if(vis[v]==ver)	continue;
			vis[v]=ver;
			if(mto[v]==0 || dfs(dfs,mto[v])){
				nto[u]=v;
				mto[v]=u;
				return true;
			}
		}
		return false;
	};
	foru(i,1,n){
		if(nto[i]!=0)	continue;
		ver++;
		if(dfs(dfs,i)){
			cnt++;
		}
	}


	int ans=0;

	foru(i,1,n){
		foru(j,1,m){
			ans+=a[i][j];
		}
	}
	ans-=a[n][m];

	ans-=cnt;

	if((cnt&1)!=a[n][m])	ans++;

	cout<<ans;

	return ;
}

P7390

你要帮 djy 造一棵树，满足以下条件：
  • 由 nn 个点组成。
  • ii 号点的度数为 aia_i 。
定义一条边 (i,j)(i,j) 的价值为 bi×bjb_i\times b_j ，你要在满足上述两个条件下，使所有边的价值和最大。
保证存在这样的树。
对于 100%100\% 的数据， 2≤n≤1072\le n\le10^7 ， 1≤ai≤n1\le a_i\le n ， 1≤bi≤5×1051\le b_i\le5\times10^5 ， type∈{0,1}type\in\{0,1\} ， 0≤seed<2310\le seed<2^{31} 。

思考

感觉可能需要进行调整，来减少可能的策略连接方法
考虑一个一个加入点，当前的策略只与每个点的剩余度数有关，与连接方式无关。
如果有 a≥b≥c≥da\ge b\ge c\ge d ，那么 ab+cd≥ac+bdab+cd\ge ac+bd 。证明显然。
所以可能大的尽量与大的连接是好的？
考虑排序后从大到小加入点，直接优先与还有度数的最大点连接，有无 hack？
还得考虑 1 度点。直接分两个序列双指针插入。
炸了，答案偏小。

题解

刚才的判断是对的，尽量让大的与大的连是完全没问题的，问题在于构造方式出现问题。原来那样构造，在当前联通块只剩下 11 度的时候，强行钦定其与下一个非叶点连边，而这是不对的，在这个情况下，这个联通块与别的所有叶子是等价的，必须从所有"叶子" 里挑一个与下个非叶点连边。
因此在每个联通块尝试拓展时判断，如果这个联通块变成叶子了就不与下个非叶点连边，而是加入叶子的数据结构。
一开始的叶子是单调递减的，随着算法进行新增的叶子也是单调递减的，使用两个队列维护即可做到线性，避免使用优先队列。
CPP
int n;
class Node{
public:
	int a,b;
}a[10000005],lf[10000005];
int rf[10000005];
int N,M;
unsigned seed;
unsigned rnd(unsigned x){
	x^=x<<13;
	x^=x>>17;
	x^=x<<5;
	return x;
}
int rad(int x,int y){
	seed=rnd(seed);
	return seed%(y-x+1)+x;
}
void init_data(){
	cin>>seed;
	for(int i=1;i<=n;i++)
		a[i].a=1,a[i].b=rad(1,500000);
	for(int i=1;i<=n-2;i++)
		a[rad(1,n)].a++;
}



void solve(bool SPE){ 
	int type=RIN;
	n=RIN;
	if(type==0){
		foru(i,1,n){
			a[i].a=RIN;
		}
		foru(i,1,n){
			a[i].b=RIN;
		}
	}else{
		init_data();
	}

	sort(a+1,a+1+n,[](const Node& x,const Node& y)->bool{
		return x.b>y.b;
	});


	class LEAF{
	public:
		queue<int> q;
		queue<int> qn;
		void pushsrc(int x){
			q.push(x);
		}
		void push(int x){
			qn.push(x);
		}
		bool empty(){
			return q.empty() && qn.empty();
		}
		int get(){
			if(q.empty())	return qn.front();
			if(qn.empty())	return q.front();
			if(q.front()>qn.front()){
				return q.front();
			}else{
				return qn.front();
			}
		}
		void pop(){
			if(q.empty()){
				qn.pop();
				return ;
			}
			if(qn.empty()){
				q.pop();
				return ;
			}
			if(q.front()>qn.front()){
				q.pop();
			}else{
				qn.pop();
			}
		}
		int size(){
			return q.size()+qn.size();
		}
	}leaf;

	foru(i,1,n){
		if(a[i].a==1){
			leaf.pushsrc(a[i].b);
			// rf[++M]=a[i].b;
		}else{
			lf[++N]=a[i];
		}
	}

	LL ans=0;
	
	int l=1;
	// int ptr=0;

	foru(r,1,N){
		// cerr<<"r "<<r<<endl;
		auto check=[&]()->bool{
			return l==r && lf[l].a==1;
		};
		auto us=[&]()->void{
			lf[l].a--;
			if(lf[l].a==0)	l++;
		};
		while(!check() && !leaf.empty() && (r==N || leaf.get()>lf[r+1].b)){
			// cerr<<lf[l].b<<' '<<leaf.get()<<endl;
			ans+=(LL)lf[l].b*leaf.get();
			leaf.pop();
			us();
		}
		if(r==N){
			ast(check());
		}
		if(!check()){
			// cerr<<lf[l].b<<'~'<<lf[r+1].b<<endl;
			ans+=(LL)lf[l].b*lf[r+1].b;
			us();
			lf[r+1].a--;
		}else{
			leaf.push(lf[l].b);
			l=r+1;
		}
	}

	ast(leaf.size()==2);
	LL V=leaf.get();
	leaf.pop();
	ans+=leaf.get()*V;

	// foru(i,1,n){
	// 	cerr<<a[i].a<<' '<<a[i].b<<endl;
	// }

	cout<<ans;

	return ;
}

CF1870E

给你一个序列 aa ，让你选出一些不交的子段，使得它们的 MEX 的异或和最大。
1≤n≤5000，0≤ai≤n1\le n\le 5000，0\le a_i\le n

思考

能否直接 DP。 fi,jf_{i,j} 表示钦定 ii 属于最后一个子段，考虑了前 ii 个元素，最大的答案。转移枚举最后一个序列长度：
fi,j←⋁k=1i⋁p=0i−kfp,j⊕mex⁡(i−k+1,i)f_{i,j}\leftarrow \bigvee_{k=1}^i\bigvee_{p=0}^{i-k}f_{p,j\oplus \operatorname{mex}(i-k+1,i)}
下标同时与 i,j,ki,j,k 有关，难以优化，应该寻找性质。
有用的区间并不多？对于每个 mex 的"极紧"区间是有限的
有效区间数量应该是
∑i因为加入 ai 导致 mex⁡ 发生改变的区间数量\sum_i因为加入\ a_i\ 导致\ \operatorname{mex}\ 发生改变的区间数量
直接做一下看看
去掉所有被支配的区间

Accept

去掉就过了。
形式化地，一个区间 [l,r][l,r] 是有效转移区间，当且仅当不存在一个 [l′,r′]∈[l,r]\and[l′,r′]≠[l,r][l',r']\in[l,r]\and[l',r']\neq[l,r] ，满足 mex⁡(l,r)=mex⁡(l′,r′)\operatorname{mex}(l,r)=\operatorname{mex}(l',r') 。
可以证明，这样的区间个数为 O(n)O(n) 。
令每个有效区间在较大的端点一侧被统计。显然一个有效区间的端点不可能相等，除了 [i,i][i,i] 这样的区间。不过它们本来就只有 nn 个。
考虑以 ii 为左端点的有效区间个数，根据刚才的统计原则，所有符合要求的有效区间的右端点都应该小于 aia_i 。因此显然这些有效区间的 mex⁡\operatorname{mex} 不可能大于 ai+1a_i+1 。而 mex⁡\operatorname{mex} 也不可能小于 aia_i ，因为这意味着 aia_i 是无用的，应该被踢出区间。综上，符合要求的有效区间的 mex⁡\operatorname{mex} 一定为 ai+1a_i+1 。显然这样的区间有且仅有一个。
以 ii 为右端点的分析同理。于是总有效转移数量就是 O(n)O(n) 的了。
CPP
int n;
int a[5005];

int fa[5005],sz[5005];
int find(int x){
	// cerr<<x<<' '<<fa[x]endl;
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void Union(int x,int y){
	x=find(x),y=find(y);
	if(x==y)	return ;
	fa[x]=y;
	sz[y]+=sz[x];
}

void solve(bool SPE){ 
	n=RIN;

	foru(i,1,n){
		a[i]=RIN;
	}

	static int mex[5005][5005];
	foru(i,1,n){
		foru(j,0,n+1){
			fa[j]=j;
			sz[j]=1;
		}
		for(int l=i;l>=1;l--){
			Union(a[l],a[l]+1);
			mex[l][i]=sz[find(0)]-1;
			// cerr<<l<<' '<<i<<' '<<mex[l][i]<<endl;
		}
	}

	static int lf[5005][5005];
	foru(i,0,n){
		foru(j,0,n){
			lf[i][j]=0;
		}
	}

	static bitset<9000> f[5005];

	f[0].reset();
	f[0][0]=1;

	foru(i,1,n){
		f[i]=f[i-1];
		ford(l,i,1){
			if(l<i && mex[l][i]==mex[l+1][i])	continue;
			lf[i][mex[l][i]]=l;
			if(lf[i-1][mex[l][i]]==l)	continue;
			// cerr<<'	'<<l<<' '<<i<<' '<<mex[l][i]<<endl;
			for(int j=f[l-1]._Find_first();j<=8192;j=f[l-1]._Find_next(j)){
				// cerr<<
				f[i][j^mex[l][i]]=1;
			}
		}
	}

	int ans=0;
	foru(i,0,8192){
		if(f[n][i]){
			ans=i;
		}
	}

	cout<<ans<<'\n';

	return ;
}

agc012_e

在数轴上有 NN 个绿洲。从左边数第 ii 个绿洲的坐标是 xix _ i 。
骆驼希望访问所有这些绿洲。最初，他背上驼峰的容积为 VV 。当驼峰的容积为 vv 时，最多可以存储体积为 vv 的水。水只在绿洲处供给。他可以在一个绿洲获得尽可能多的水，并且同一个绿洲可以使用任意次数。
骆驼可以通过步行或跳跃在数轴上移动：
  • 步行距离为 dd 需要从驼峰消耗体积为 dd 的水。无法进行导致存储水量为负的步行。
  • 令 vv 为当前存储的水量。当 v>0v\gt 0 时，骆驼可以跳到他选择的数轴上的任意点。此举之后，驼峰的容量变为 v/2v/2 (向下取整到最接近的整数)，存储的水量变为 00 。
对于每个绿洲，确定是否可以从该绿洲出发访问所有绿洲。
  • 2≤N,V≤2×1052 \le N,V \le 2 \times 10^5
  • −109≤x1<x2<...<xN≤109-10^9 \le x_1 \lt x_2 \lt ... \lt x_N \le 10^9
  • VV and xix_i are all integers.

思考

对于当前所处的绿洲，肯定利用 VV 全部走完邻近的所有绿洲，直到撞上一个长度超过 VV 的间隔。
跳跃后也会走完 "一个联通块"
注意到这些联通块构成了一个树形结构状物。每层拥有相同的 VV ，树高是 log⁡V\log V 的。
在高层（ VV 较大）断开的间隙，底层也会断开。
最高层的每个块可以独立做。
每个询问于是形如，钦定最高层的一段必选，是否存在一个在下层每层选出一个联通块的方案，使得他们能拼出整个序列。
或许可以枚举最高层的段，用前后的答案拼起来。需要解决的是，对于一个前缀，在每层（除去最高层）选一个联通块，能否拼出整个前缀。
似乎不可行，不能保证前后层数无交。
削弱询问，考虑任意起点怎么做。
可以枚举最高层选哪个，然后转变为了一个子问题。
但这个子问题需要排除掉最高层选的这个范围。重新计算的复杂度应该是不可接受的，但前后拼接似乎也很困难。
前后拼接应该是不可行的，因为下面每层都会受到这次决策的影响？
考虑能否转化这个过程，例如合并，分裂层联通块。似乎不行。

题解

看似不能状压，恰恰相反，就得状压
觉得不能状压是因为试图做形如 fi,sf_{i,s} 这样的 DP，表示某种意义的前缀能否用集合 ss 完全覆盖，用前后缀拼起来得到答案。这样第二维度是 O(V)O(V) 的，第一维度似乎也不小直接爆炸，而且根本没法转移。
然而这个 DP 蠢的没边了。这是个可行性 DP，考虑对于相同的 ss ，一定有一个前缀 ff 为 11 ，后缀为 00 。我们只需要那个分界线的位置，不需要具体记录每个位置是 00 还是 11 。是这个可二分的性质让我们可以省去第一维度。
哪怕在类序列上状压 DP，也有可能只以集合作为下标
观察 DP 的信息，和我们使用的信息。如果使用的信息小，DP 的信息多，且 DP 的信息具有某种性质，可以压缩 DP，使得对于状态空间的划分更少。
对于此题，DP 维护了一大堆 0 1，但具有前缀 11 后缀 00 的性质。因此只维护一个分界点，而不是维护所有 01 是正确的。
于是用脚做就行了。

CF1984F

两只饥饿的小熊猫奥斯卡和露拉，有一棵具有 nn 个节点的树 TT 。他们愿意对整棵树 TT 执行以下洗牌过程，仅一次。通过这个洗牌过程，他们将从旧树的节点创建一棵新树。
  1. 从原始树 TT 中选择任意节点 VV 。创建一棵以 VV 为根的新树 T2T_2 。
  2. 从 TT 中移除 VV ，使得原始树分裂成一个或多个子树（如果 VV 是 TT 中唯一的节点，则为零个子树）。
  3. 对每个子树使用相同的过程进行洗牌（再次选择任意节点作为根），然后将所有洗牌后的子树的根连接回 VV ，完成构建 T2T_2 。
之后，奥斯卡和露拉留下一棵新树 T2T_2 。他们只能吃叶子，非常饥饿，请找出仅一次洗牌过程中可以创建的所有树中叶子的最大数量。
注意，叶子是所有度为 11 的节点。因此，如果根节点只有一个子节点，则根节点可以被视为叶子。
n≤2×105n\le 2\times 10^5

思考

提根很抽象。
提联通块的过程相当于，给连接点度数减一，再把新根度数加一。
要最大化度数为一的数量。
于是可以这样转化这个过程：
对于一个联通块
  • 选一个初始点，把它的度数加一，把它周围的、联通块内的点的度数减一
  • 对于每个裂出来的联通块，做相同算法
最后枚举一个全局的根，它的度数不加一，对他的每个子树都做上面的算法，最后就能得到每个点的度数，而不需要真的旋转树结构
这个过程是可打乱顺序来 DP 的。
考虑每一条边 (u,v)(u,v)，我们知道 u,vu,v 都会被操作，但只有操作更晚的那个才会被度数减一。
换言之，对于每条边，我们只关心二者的相对操作早晚，据此就能知道 −1-1 的走向。这相当于给无向边定向。同时容易构造一个具体的操作序列，对于定向后的有向图拓扑排序即可。
设 fi,0/1f_{i,0/1} 表示只考虑 ii 所在的子树，ii 和它的父亲哪个操作更早，能得到的度数为 11 的节点的最多数量。答案可以换根 DP 计算。
考虑如何转移，发现也是简单的。uu 想要变成度数为 11，必须所有与之相连的边都向它贡献 −1-1，转移固定。如果 uu 不想变成叶子，则取每个孩子的 max⁡(fv,0,fv,1)\max(f_{v,0},f_{v,1}) 即可。总复杂度 O(n)O(n)。

Accept

过了，这思路对的不能再对了，满昏😋️
CPP
int n;
vector<int> e[MAXN];
void solve(bool SPE){ 
    n=RIN;
    foru(i,1,n){
        e[i].clear();
    }
    foru(i,1,n-1){
        int u=RIN,v=RIN;
        e[u]+=v;
        e[v]+=u;
    }

    static int f[MAXN][2];
	static int fa[MAXN];

    auto dfs=[](auto dfs,int u,int fath)->void {
		fa[u]=fath;
        for(auto v:e[u]){
            if(v==fa[u])	continue;
			dfs(dfs,v,u);
        }
		
		f[u][0]=1;
		f[u][1]=0;
		for(auto v:e[u]){
			if(v==fa[u])	continue;
			f[u][0]+=f[v][1];
			f[u][1]+=max(f[v][0],f[v][1]);
		}
		chkmax(f[u][0],f[u][1]);
    };

	dfs(dfs,1,0);

	int ans=0;

	auto calc=[&ans](auto calc,int u,array<int,2> F)->void {
		int sum=F[0];
		for(auto v:e[u]){
			if(v==fa[u])	continue;
			sum+=f[v][0];
		}
		chkmax(ans,sum+((int)e[u].size()==1));

		// if(u==3){
		// 	cerr<<F[0]<<' '<<F[1]<<endl;
		// }

		array<int,2> g{1,0};
		g[0]+=F[1];
		g[1]+=max(F[0],F[1]);

		for(auto v:e[u]){
			if(v==fa[u])	continue;
			g[0]+=f[v][1];
			g[1]+=max(f[v][0],f[v][1]);
		}

		for(auto v:e[u]){
			if(v==fa[u])	continue;
			calc(calc,v,array<int,2>{max(g[0]-f[v][1],g[1]-max(f[v][0],f[v][1])),g[1]-max(f[v][0],f[v][1])});
		}
	};

	// cerr<<f[2][1]<<endl;

	calc(calc,1,array<int,2>{0,0});

	cout<<ans<<'\n';

	// exit(0);

	return ;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...