首页 > 其他分享 >启发式合并小记

启发式合并小记

时间:2024-03-14 20:27:03浏览次数:23  
标签:pr cnt int auto 合并 mp 启发式 include 小记

适用范围

当题目中查询有关子树中的问题,而往往涉及类似莫队中每种值出现个数这类比较难用线段树快速维护的时候,我们可以考虑用启发式合并。

过程

启发式合并其实是优雅的暴力,具体思路就是:统计 \(u\) 子树的答案,我们先把 \(u\) 除了重儿子之外的所有儿子的答案统计了,然后再统计重儿子,但是对于重儿子我们不要清空贡献,最后再把轻儿子的贡献加上即可。

这个时间复杂度是 \(O(n \log n)\) 的。

模板题

CF600E Lomsat gelral

这里给一下代码。

点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 5;
int n, m, c[MAXN] = {0};
vector<int> e[MAXN];
int cnt[MAXN] = {0}, maxCnt = 0;
long long sum[MAXN] = {0};
inline void add(int x) {
    sum[cnt[c[x]]] -= c[x];
    if (cnt[c[x]] == maxCnt)
        maxCnt++;
    cnt[c[x]]++;
    sum[cnt[c[x]]] += c[x];
}
inline void del(int x) {
    sum[cnt[c[x]]] -= c[x];
    if (cnt[c[x]] == maxCnt && sum[cnt[c[x]]] == 0)
        maxCnt--;
    cnt[c[x]]--;
    sum[cnt[c[x]]] += c[x];
}
int sz[MAXN] = {0}, chd[MAXN] = {0};
inline int srh(int x, int pr) {
    sz[x] = 1, chd[x] = -1;
    for (auto i: e[x])
        if (i != pr) {
            sz[x] += srh(i, x);
            if (chd[x] == -1 || sz[chd[x]] < sz[i])
                chd[x] = i;
        }
    return sz[x];
}
inline void insert(int x, int pr) {
    add(x);
    for (auto i: e[x])
        if (i != pr)
            insert(i, x);
}
inline void erase(int x, int pr) {
    del(x);
    for (auto i: e[x])
        if (i != pr)
            erase(i, x);
}
long long ans[MAXN] = {0};
inline void dfs(int x, int pr, bool flg) {
    for (auto i: e[x])
        if (i != pr && i != chd[x])
            dfs(i, x, true);
    if (chd[x] != -1)
        dfs(chd[x], x, false);

    for (auto i: e[x])
        if (i != pr && i != chd[x])
            insert(i, x);
    add(x);
    ans[x] = sum[maxCnt];
    if (flg) {
        for (auto i: e[x])
            if (i != pr)
                erase(i, x);
        del(x);
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &c[i]);
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d%d", &u, &v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    srh(1, 1);
    dfs(1, 1, true);
    for (int i = 1; i <= n; i++)
        printf("%lld ", ans[i]);
    return 0;
}
CF375D Tree and Queries

与上道题类似,离线统计即可。

CF1824C LuoTianyi and XOR-Tree

好题。

我们先观察性质,不难发现,答案的上界是叶子个数,因为我们可以通过改变所有叶子的权值使其满足异或和等于 \(0\)。

我们进一步发现,最终状态下,每个节点的子树中所有叶子节点到这个节点的异或值都是相同的,因为祖先这一段是公共的。

我们这样就可以考虑从下往上递归解决,我们先把所有子节点内部贪心地调整成一样的,然后再看如何调整这些子节点的值使得异或和一样。

显然,我们贪心地希望只保留出现次数最多的异或和,其它都调整为这个。

但是一个子树内部可能有很多种情况,异或和不唯一。但是,我们可以断言,再最少调整次数下,这些可能的值构成一个集合 \(M\),且 \(M\) 的大小不会超过子树大小。

所以我们只用求出所有 \(M\) 的并集然后求一下众数即可。这个就可以用启发式合并很轻松地解决了。

最后判断一下最终的集合中有没有 \(0\),来判断要不要将答案加 \(1\)。所以,这道题其实最终异或为 \(0\) 并不是必须的。

点击查看代码
#include <iostream>
#include <cstdio>
#include <map> 
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;

int n;
int a[N] = {0};
vector<int> e[N];

map<int, int> mp[N], t;
int ans = 0;
void dfs(int x, int pr) {
	if ((int)e[x].size() == 1 && pr > 0) {
		mp[x][a[x]] = 1;
		return;
	}
	int mxCnt = 1, tot = 0;
	for (auto i: e[x])
		if (i != pr) {
			a[i] ^= a[x];
			dfs(i, x);
			if (mp[i].size() > mp[x].size())
				swap(mp[i], mp[x]);
			for (auto j: mp[i]) {
				mp[x][j.first] += j.second;
				mxCnt = max(mxCnt, mp[x][j.first]);
			}
			++tot;
		}
	if (mxCnt > 1) {
		t.clear();
		for (auto i: mp[x])
			if (i.second == mxCnt)
				t[i.first] = 1;
		swap(t, mp[x]);
	}
	ans += tot - mxCnt;
}
 
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) 
		cin >> a[i];
	for (int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1, 0);
	cout << ans + (mp[1][0] != 0 ? 0 : 1) << endl;
	return 0;
}
CF1709E XOR Tree

好题。

我们依然需要观察性质,令 \(d_u\) 表示 \(u\) 到根节点的异或和,则 \(P(u,v) = d_u \oplus d_v \oplus d_{\operatorname{lca}(u,v)}\),我们要求任意路径不为 \(0\)。

对于树上问题,依然考虑从子树出发,我们发现:如果可以更改 \(a_u\),则我们可以保证子树内不存在任何一条经过 \(u\) 的路径使得异或和不为 \(0\)。我们可以使的 \(a_u\) 有一个很高很高的位为 \(1\),这样根据上面的式子,这一位消不掉。

所以我们可以从下往上地贪心,每次判断需不需要改 \(u\),我们将子树中还没改的儿子节点的所有节点的 \(d_u\) 的集合拎出来,如果存在一对值异或和为 \(a_u\),说明 \(a_u\) 必须被更改,否则不用。这个过程可以用启发式合并解决。

点击查看代码
#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5;

int n, a[N] = {0};
vector<int> e[N];
set<int> s[N];
int ans = 0;

void dfs(int x, int pr, int dth) {
	for (auto i: e[x])
		if (i != pr) 
			dfs(i, x, (dth ^ a[i]));
	bool flg = false;
	s[x].insert(dth);
	for (auto i: e[x])
		if (i != pr && !flg) {
			if (s[i].size() > s[x].size())
				swap(s[i], s[x]);
			for (auto j: s[i])
				if (s[x].find((j ^ a[x])) != s[x].end()) 
					flg = true;
			for (auto j: s[i]) 
				s[x].insert(j);
		}
	if (flg)
		ans++, s[x].clear();
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1, 0, a[1]);
	cout << ans << endl;
	return 0; 
} 

标签:pr,cnt,int,auto,合并,mp,启发式,include,小记
From: https://www.cnblogs.com/rlc202204/p/18073832

相关文章

  • day-19 合并后数组中的最大元素
    思路:从后向前遍历数组,用tans记录每一种可能的最大值,ans为实际最大值。注意:若ans==0,返回nums[0]要用longcodeclassSolution{publiclongmaxArrayValue(int[]nums){longans=0;longtans=0;booleanflag=true;for(in......
  • leetcode.21 合并两个有序链表
     21.合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  示例1:输入:l1=[1,2,4],l2=[1,3,4]输出:[1,1,2,3,4,4]示例2:输入:l1=[],l2=[]输出:[]示例3:输入:l1=[],l2=[0]输......
  • 数据结构——循环链表,双向链表,线性表和有序表的合并详解
    目录1.循环链表1.带尾指针循环链表的合并 代码示例:2.双向链表代码示例:  1.双向链表的插入​代码示例:2.双向链表的删除代码示例:3.单链表,循环链表,双向链表时间效率的比较4.顺序表和链表的比较 5.存储密度6.线性表的应用 1.线性表的合并​代码示例:2.有序表......
  • 617. 合并二叉树c
    /***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*/structTreeNode*mergeTrees(structTreeNode*root1,structTreeNode*root2){if(!root1&&!roo......
  • leetcode: 2789. 合并数组中的最大元素
    给你一个下标从 0 开始、由正整数组成的数组 nums 。你可以在数组上执行下述操作 任意 次:选中一个同时满足 0<=i<nums.length-1 和 nums[i]<=nums[i+1] 的整数 i 。将元素 nums[i+1] 替换为 nums[i]+nums[i+1] ,并从数组中删除元素 nums[i] ......
  • 2024/3/11打卡管道(14届蓝桥杯省赛)——二分+区间合并
    目录题目思路代码题目有一根长度为 len的横向的管道,该管道按照单位长度分为 len 段,每一段的中央有一个可开关的阀门和一个检测水流的传感器。一开始管道是空的,位于 Li 的阀门会在  时刻打开,并不断让水流入管道。对于位于  的阀门,它流入的水在 时刻会使得......
  • 洛谷 P4173 残缺的字符串 卡常小记
    首先,使用匹配函数\(P(x_i,x_j)=x_ix_j-x_i^2[j\neq0]\)。容易发现,当存在\(i\neqj\)时,\(x_ix_j\)的系数只会增加,因此根据Schwartz-Zippel引理,随机一组\(x_{1\sim26}\)对应a~z即可。然后,对于NTT的过程,有两个卡常的点:一是点积reverse后转卷积的过程是舍......
  • 88. 合并两个有序数组c
    还有什么比刷简单题更爽的。intcmp(constvoid*a,constvoid*b){return*(int*)a-*(int*)b;}voidmerge(int*nums1,intnums1Size,intm,int*nums2,intnums2Size,intn){for(inti=m;i<nums1Size;i++){nums1[i]=nums2[i-m];}qsort(......
  • 插头 dp 小记
    这里默认各位都会轮廓线dp。引入Luogu5074EattheTrees题意:给出\(n\timesm\)的方格,有些格子不能铺线,其它格子必须铺,可以形成多个闭合回路。问有多少种铺法?\(2\len,m\le12\)考虑如果每个格子和相邻格子(包括边缘)的衔接都合法,最终一定能形成若干个闭合回路,因此我们只......
  • 【算法】【线性表】【链表】合并 K 个升序链表
    1 题目给你一个链表数组,每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中,返回合并后的链表。示例1:输入:lists=[[1,4,5],[1,3,4],[2,6]]输出:[1,1,2,3,4,4,5,6]解释:链表数组如下:[1->4->5,1->3->4,2->6]将它们合并到一个有序链表中得到。1-......