Znzryb's Blog
0%

Posted on Edited on

思路讲解

https://chatgpt.com/share/68c0ff99-20d0-8013-b16a-26d60768748a

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
// 我们会发现，能否通过前K关（构造出K前缀），和这个顺序是没有关系的
// 我们直接看前 K 个物品是否可以凑出一个和
// vector<vii> dp(SZ(ls)+5,vii(N+5));
vii dp(N+5);
ll sum=0;
ll ans=0;
// 滚动数组优化，第i层哪些值是可以达到的
dp[0]=true;
FOR(i,1,desti){
	ll w=ls[i];
	sum+=w;
	// 滚动数组反向遍历
	ROF(j,N-w,0){
		dp[w+j]|=dp[j];
	}
	FOR(a,0,N){
		if(dp[a]){
			ll b=sum-a;
			if((a<=K && b<=N-K) || (b<=K && a<=N-K) ){
				ans=i;
				break;
			}
		}
	}
	if(ans!=i){
		break;
	}
}

AC代码

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

Posted on Edited on

思路讲解

注意，不能直接跑分层图，会TLE。

那怎么办呢？可以用传送门，先确定一些种子节点，再跑多源最短路。

一个比较重要的剪枝其实在这里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
FOR(j, 1, N) {
	Dis[i][j] = Dis[i - 1][j];
}
priority_queue < DIS > pq;
FOR(u, 1, N) {
	for (auto &v : jie[u]) {
		Dis[i][u] = min(Dis[i - 1][v], Dis[i][u]);
	}
}
FOR(u, 1, N) {
	// 超了，或者和原来一样，就不要了
	if (Dis[i][u] != Dis[i - 1][u]) {
		pq.push({Dis[i][u], u});
	}
}

AC代码

914ms，在dij中算跑的很快的。

https://qoj.ac/submission/1310755

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

Posted on Edited on

思路讲解

不难想到，其实这个区间长度比较大的自由度
区间长度小的自由度比较小

因为咒语之间的顺序不重要，那么肯定是要排序的。
我们不妨用右端点排序。

那么我们发现，只要两个块颜色不同，且两个块中有一个未经过染色
（即保留着自己初始的独特颜色）
那么就是有一个贡献。

可以使用 dsu on next 进行下一个未涂色点的查询。

https://chatgpt.com/share/68bfb91c-7cf0-8013-8e65-7615f4bf510f

核心贪心代码

1
2
3
4
5
6
7
8
9
10
ll ans=N;
for (auto&[r, vec] : g) {
	for(auto l:vec){
		ll x=find(l);  // 第一个未被涂色的点
		if(x<r){
			fa[x]=x+1;
			--ans;	
		}
	}	
}

AC代码

https://qoj.ac/submission/1307214

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

Posted on Edited on

思路讲解

还是比较简单，比较容易想到的。

AC代码

https://vjudge.net/solution/63500041

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

Posted on Edited on

思路讲解

参考代码

https://qoj.ac/submission/1298127

okay，我们来看一下，其实还是比较难的，没那么简单。

一开始我们想的是一个贪心，但是没那么贪，毕竟过的人比较少，说明大概率就是dp。

或者说容易想到，将一张图分为若干单调链一定是对的，但是怎么分那？这个就需要树上dp。

首先我们发现这个树上dp需要的是整体的值，但是我们计算的时候又需要的是单块的值，这个整体与局部的矛盾怎么解决那？那么dp计算肯定是我们优先考虑的，于是我们将局部的也并入dp。

1
2
3
// dp[i][0] 表示闭合收益 dp[i][1]表示上交最小链收益 
// dp[i][2] 表示上交最大链收益
arr3 dp[MAXN];

具体代码看我注释吧。

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
// dp[i][0] 表示闭合收益 dp[i][1]表示上交最小链收益 dp[i][2] 表示上交最大链收益
arr3 dp[MAXN];
void dfs(int u, int fa) {
	ll a = A[u];
	// 0 - closed with single point
	// 1 - chain with minimum
	// 2 - chain with maximum
	// 3 - closed with two merged link
	array<ll, 4> e = {0, -a, a, -INF};
	for (auto &v : g[u]) {
		if (v == fa) continue;
		dfs(v, u);
		//         上交最大链 与 最小链端
		e[3] = max({A[u] < A[v] ? e[1] + dp[v][2] : -INF,
		            //    最大链端    与  上交最小链
		            A[u] > A[v] ? e[2] + dp[v][1] : -INF,
		            e[3] + dp[v][0]
		           });
		// e[2] 可以怎么样拼出来那？
		// 是不是我可以将 u 这个点作为单个点
		// 向其上交这个最大值，相当于这个点作为一个单链
		// 那么 就是 e[2] + dp[v][0]
		// 你如果要和下面的块融合，那么就是dp[v][2]
		// 当然我们还要考虑一下就是和别的分支的融合，那么就是e[0]+dp[v][2]。
		e[2] = max(e[2] + dp[v][0],
				   A[u]<A[v]?e[0] + dp[v][2]:-INF
		          );
		e[1] = max(e[1] + dp[v][0]
				   , (A[u]>A[v]?e[0]+dp[v][1]:-INF)
				   );
		e[0] += dp[v][0];
	}
	dp[u][0]=max(e[3],e[0]);
	dp[u][1]=e[1];
	dp[u][2]=e[2];
}

AC代码

https://qoj.ac/submission/1303005

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