Znzryb's Blog
0%

Posted on Edited on

思路讲解

AC代码

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

那么根据我的经验来说，如果说这个东西要求连续性（如距离，字母排列等等），大概率是树上dp，像这种具有超距作用的，那么大概率就是要配合DSU了。

核心代码如下，注意，先计算，后合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
FOR(i,1,N){		// 特判两个点的情况
	for(auto &v:g[i]){
		if(A[v]==A[i]) ++ans;
	}
}
// 生成的这张图相当于其权值都是大于等于key的（至少是相连的图，孤立点我们不知道）
// 这个时候就是要看两个相同的A值点，是不是连接于这个图上面。
// 那么我们发现不用把问题想的非常复杂，只需要考虑key-1（即后面一个k）就行了
// 最重要的是遵循"先计数，后合并"的原则
for(auto it=mp.rbegin();it!=mp.rend();it++){
	// auto& 相当于定义了一个别名
	auto& ls=it->second;ll key=it->first;
	map<ll,ll> cnt;
	// 先计数
	for(auto &u:ls){
		vector<ll> wp;
		for(auto &v:g[u]){
			if(A[v]<=key) continue; 
			wp.pb(find(v));
		}
		wp.resize(unique(all(wp))-wp.begin());
		for(auto &v:wp){
			++cnt[find(v)];
		}
	}
	for(auto &t:cnt){
		ll n=t.second;
		ans+=(n-1+1)*(n-1);	// 2Cn * 2 在n个中选两个，然后由于先选哪个比较重要*2
	}
	// 后合并
	for(auto &u:ls){
		for(auto &v:g[u]){
			if(A[v]<key) continue;
			merge(u,v);
		}
	}
}

那么这种复杂路径问题，点分治也能解决（应该来说更泛用）。

AC代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78161052

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78175127

心路历程（WA，TLE，MLE……）

WA了的点分治代码，过了60%，我认为错误就在这个我的这个点分治统计答案他有点问题，统计到的不一定都经过u，这是违背点分治思想的。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78164958

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78165041

然后改了统计代码以后WA的更多了

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78165092

AI指出了一个不对的地方，现在正确率提升到了84%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 保证计入答案的路径是经过u点的
for(auto &v:g[u]){
	if(vis[v]) continue;	// 你不能就不判断了
	dfs(dfs,v,u,A[u]);
	for(auto &a:wp){
		if(cnt.count(a)){
			ans+=cnt[a];
		}
	}
	for(auto &a:wp){
		++cnt[a];
	}
	wp.clear();
}

Posted on Edited on

思路讲解

差分做法，只要用差分把所有坏区间都标记出来，剩下的就是不可行的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
FOR(i,0,M-2){
	for(auto &p:pos[i+1]){
		auto it=lower_bound(all(pos[i]),p);
		if(it==pos[i].begin()){
			diff[1]+=1;
			// p+1是可行的（至少从这个p看来）
			diff[p+1]-=1;
		}else{
			it--;ll idx=*it;
			diff[idx+1]+=1;
			// p+1是可行的（至少从这个p看来）
			diff[p+1]-=1;
		}
	}
}

AC代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78135312

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

将硬币个数也纳入状态设计当中就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
N=250;
vector dp(N+5,vector<ll>(N+5,0));
dp[0][0]=1;
vector<ll> coin={1,5,10,25,50};
for(auto &c:coin){
	FOR(i,1,N){
		FOR(j,1,100){
			if(i-c<0) break; 
			dp[i][j]+=dp[i-c][j-1];
		}
	}
}

AC代码

https://oj.dhu.edu.cn/#/user/training/382/problems/458?catId=13&continueTrain=yes

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
FOR(i,1,M){
	ll u,v,w;cin>>u>>v>>w;
	E[i]={u,v,w};
	if(w==1){
		merge(u,v);
	}
}
ll VB=0;
FOR(i,1,N){
	if(fa[i]==i) ++VB;	// 黑图联通块数量。
}
ll ans=0,rem=0;
FOR(i,1,M){
	auto [u,v,w]=E[i];
	if(w==0){
		if(find(u)==find(v)){	// 这个白边的两个端点在黑图上是联通的
			++ans;	// 涂这些白边只需要消耗一个，就可以贡献一个答案
		}else{
			++rem;	// 剩余白边
		}
	}
}
ans+=max(0ll,rem-VB+1);

https://gemini.google.com/gem/coding-partner/f12365cf9d028877

好的，我们一起来用中文梳理一下这道题的思路。我会试着一步步引导你，而不是直接告诉你答案。

第一步：思考问题的本质

我们想让操作次数尽可能多。每次操作都需要一个“引子”：一个包含至少一条白边的环。操作完成后，这个环里所有的白边都会变成黑边。

一个很自然的想法是：我们的操作次数，会不会受到白边总数的限制？

是的，每次操作我们至少“消耗”掉了一条白边（它从白色变成了黑色，之后就不能再作为“引子”了）。所以，操作次数的上限，就是初始状态下白边的总数。

那么，是不是每条白边都能贡献一次操作呢？

第二步：寻找最“划算”的操作

为了让操作次数最多，我们应该让每次操作都尽可能“划算”。最划算的操作是什么样的？就是我们只用一条白边作为“引子”，去把一个环染黑。

思考一下，什么样的环正好只有一条白边，其余都是黑边？

… 答案是：当一条白边 (u, v) 的两个端点 u 和 v，已经能通过一条纯黑边路径连接起来时。这时，这条白边和这条纯黑边路径就构成了一个完美的环，里面只有一条白边。

我们可以把所有这种“划算”的白边都找出来。对于每一条这样的白边，我们都可以进行一次独立的操作。

如何找到它们？

我们可以先把图中所有的黑边建成一个图。然后遍历每一条白边 (u, v)，看看在只考虑黑边的前提下，u 和 v 是否已经连通了。如果连通，那这条白边就是一条“划算”的边，可以贡献一次操作。

这个“判断是否连通”的任务，听起来是不是很熟悉？对，这正是并查集 (DSU) 的拿手好戏。

第三步：处理剩下的白边

好，现在我们已经把所有“划算”的白边都用掉了。剩下的白边是什么样的？

它们连接的都是原本在黑边图里不连通的点。我们可以把黑边图中每一个连通块想象成一个“大岛屿”（或者叫“超级节点”）。那么，这些剩下的白边，就成了连接这些岛屿的“桥梁”。

现在，我们的图变成了这个样子：有若干个黑色的岛屿，以及连接它们的白色桥梁。

因为题目保证原图是连通的，所以这些岛屿和桥梁最终也会构成一个连通的结构。

在这个由“岛屿”和“桥梁”组成的新图里，我们还能找到环吗？

当然能！如果这些桥梁的数量足够多，多到在这个新图里形成了环，那我们就可以继续操作。

例如，从岛屿A出发，经过白色桥梁1到达岛屿B，再经过白色桥梁2到达岛屿C，最后经过白色桥梁3又回到了岛屿A。这就构成了一个大环！这个环里的边，要么是白色的桥梁，要么是岛屿内部的黑色路径。它肯定包含白边，所以我们可以对它进行一次操作。

第四步：计算新图里的操作次数

在一个连通图里，有多少“多余”的边可以形成环呢？

有一个经典的图论公式：对于一个有 V 个点、E 条边的连通图，它的“环度”（也就是基本环的数量）是 E - V + 1。这也就是我们能从这个结构中挤出的操作次数。

在我们的“岛屿和桥梁”新图里：

  • V 是多少？就是黑色连通块的数量，我们称之为 $K_B$。

  • E 是多少？就是剩下的白边（桥梁）的数量。

所以，从这些剩下的白边中，我们还能进行 $E_{剩余白边} - K_B + 1$ 次操作。

第五步：整合答案

现在把两部分的操作次数加起来：

总操作数 = (第二步中“划算”的白边数) + (第四步中“桥梁”构成的操作数)

总操作数 = ∣Ws∣+(∣Wd∣−KB+1)|W_s| + (|W_d| - K_B + 1)

（这里 ∣Ws∣|W_s| 是划算的白边数，∣Wd∣|W_d| 是桥梁白边数）

因为白边总数 $|W| = |W_s| + |W_d|$，所以上面这个公式可以简化成一个非常优美的形式：

总操作数 = (总白边数 ∣W∣) - (黑色连通块数 KB) + 1

最终算法

这个最终公式给了我们一个清晰的算法：

  1. 读入 N 和 M。

  2. 初始化一个并查集。

  3. 遍历所有 M 条边：

  • 如果是白边，就把白边计数器 whiteCnt 加一。
  • 如果是黑边，就在并查集中 unite 这条边的两个端点。

  1. 遍历完成后，统计并查集中有多少个独立的集合（也就是有多少个节点的父亲是它自己）。这个数量就是 $K_B$。

  2. 代入公式 whiteCnt - K_B + 1，就是最终答案。

希望这个一步步的解释能帮助你彻底理解这道题的思路！

AC代码

https://codeforces.com/gym/105992/submission/328463103

心路历程（WA，TLE，MLE……）