Znzryb's Blog
0%

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……）

Posted on Edited on

思路讲解

递推公式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
auto dfs=[&](auto&& self,ll u,ll p)->void{
	dp[u][0]=1;		// 每一个人说真话这种情况一定是存在的
	for(auto &v:g[u]){
		if(v==p) continue;
		self(self,v,u);
		vector<ll> tmp(N+5);
		ROF(i,sz[u],0){
			FOR(j,0,sz[v]){
				tmp[i+j]+=dp[u][i]*dp[v][j]%mod;
				tmp[i+j]%=mod;
			}
		}
		dp[u]=tmp;
		sz[u]+=sz[v];
	}
	// dp[u][A[u]-1] 就是如果u说真话，dp[u][A[u]]的值
	// 因为u说真话，那么情况已经定下来了，其余的就是dp[u][A[u]-1]
	dp[u][A[u]]=A[u]?dp[u][A[u]-1]:0;  // 对于任何节点来说，A[u]=0都是悖论
};

AC代码

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

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

Posted on Edited on

思路讲解

gcd(a,b)=gcd(a−b,b)gcd(a, b) = gcd(a-b, b)

gcd(a+bx,a)=gcd(a,b)gcd(a+bx,a)=gcd(a,b)

使用如下构造方法即可。

1
2
3
4
5
6
7
8
9
10
11
12
inline void solve(){
	cin>>N;
	init();
	sieve(N+40*N);
	ll p= *upper_bound(all(primes),N);
	FOR(i,1,N){
		FOR(j,1,N){
			cout<<i*p+j<<" ";
		}
		cout<<"\n";
	}
}

AC代码

https://codeforces.com/gym/105992/my

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

Posted on Edited on

思路讲解

【树上背包【力扣周赛 451】】 https://www.bilibili.com/video/BV1o1jgzJE51/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37

这个视频讲树上背包问题讲的非常透彻，非常好。

这个第一个遍历边就不多说了，第二个循环倒过来是因为滚动数组优化，第三个必须正过来，你可以倒过来试一试，当数据中含有这个需要0元，但是价值不为0的物品时就会出错，这是因为倒过来遍历可能取了这个物品两次，正过来遍历的时候是空的，那么就不存在这个问题了。

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
      
auto dfs=[&](this auto &&self,int u,int p)->void{
    
    for(auto v:g[u]){
        if(v==p) continue;
        self(v,u);
    }
    // memo是暂时不考虑当前节点u而定的
    vector<array<int,3> > memo(budget+5,{0,0,0});
    
     for(auto &v:g[u]){
        for(int i=budget;i>=0;--i){
            for(int j=0;j<=i;++j){  // 必须要正过来循环
                memo[i][1]=max(memo[i][1],memo[i-j][1]+dp[1][v][j]);
                memo[i][2]=max(memo[i][2],memo[i-j][2]+dp[2][v][j]);
            }
        }
    }
    for(int i=budget;i>=0;--i){
        for(int j=1;j<=2;++j){
            int cost=present[u-1]/j;
            dp[j][u][i]=max(dp[j][u][i],memo[i][1]);
            if(i>=cost){
                dp[j][u][i]=max(dp[j][u][i],future[u-1]-cost+memo[i-cost][2]);
            }
        }
    }
};

AC代码

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