Znzryb's Blog
0%

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

Posted on Edited on

思路讲解

https://usaco.guide/plat/sweep-line?lang=cpp

主要参考了上面的题解。

这个分治法也比较玄学，就是先按照 x 排序，然后开始分治，从一对开始，逐渐变成两对，四对，八对，。。。

那么我们怎么样把两边的结果合并起来呢？这个就是分治的难点。

就是两边得到的答案，我们选一个较小值，然后把两边至少 x 满足这个值的点加入进来。

即

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ret=dfs(l,mid);
ret=min(ret,dfs(mid+1,r));
Real x=A[mid+1].x;
vector<Point> wp;
ROF(i,mid,l){
    Real d=abs(A[i].x-x);
    if(d*d<ret.d){
        wp.EB(A[i]);
    }else{
        break;
    }
}
FOR(i,mid+1,r){
    Real d=abs(A[i].x-x);
    if(d*d<ret.d){
        wp.EB(A[i]);
    }else{
        break;
    }
}

然后得到了 wp 数组，将其按照 y 排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Best mindis(vector<Point> &a,Best res){
    sort(all(a),[&](Point a,Point b){
        return a.y<b.y;
    });
    FOR(i,1,SZ(a)-1){  // 选一个点
		    // 向后扫描
        ROF(j,i-1,0){
            Point p=a[i],q=a[j];
            // 如果这个点的 y 已经不符合要求了，就直接开摆，后面的点y肯定更离谱
            if((p.y-q.y)*(p.y-q.y)>res.d){
                break;
            }
            Point v=p-q;
            res=min(res,{dot(v, v),p,q});
        }
    }
    return res;
}
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
struct Best{
    Real d;
    Point a,b;
    bool operator<(const Best &o)const{
        return d<o.d;
    }
};
Best mindis(vector<Point> &a,Best res){
    sort(all(a),[&](Point a,Point b){
        return a.y<b.y;
    });
    FOR(i,1,SZ(a)-1){
        ROF(j,i-1,0){
            Point p=a[i],q=a[j];
            if((p.y-q.y)*(p.y-q.y)>res.d){
                break;
            }
            Point v=p-q;
            res=min(res,{dot(v, v),p,q});
        }
    }
    return res;
}

Best dfs(int l,int r){
    if(l>=r) return {(ld)INF,A[l],A[l]}; 
    if(r-l==1){
        Point v=A[r]-A[l];
        return {dot(v,v),A[l],A[r]};
    }
    Best ret;
    int mid=r+l>>1;
    ret=dfs(l,mid);
    ret=min(ret,dfs(mid+1,r));
    Real x=A[mid+1].x;
    vector<Point> wp;
    ROF(i,mid,l){
        Real d=abs(A[i].x-x);
        if(d*d<ret.d){
            wp.EB(A[i]);
        }else{
            break;
        }
    }
    FOR(i,mid+1,r){
        Real d=abs(A[i].x-x);
        if(d*d<ret.d){
            wp.EB(A[i]);
        }else{
            break;
        }
    }
    return mindis(wp,ret);
}

AC代码

https://vjudge.net/solution/63334518

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

Posted on Edited on

思路讲解

AC代码

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