相等放并查集里，不等直接判断#include<bits/stdc++.h>usingnamespacestd;#definexfirst#defineysecondtypedefpair<int,int>PII;typedeflonglongll;typedefunsignedlonglongull;typedefunsignedintuint;typedefvector<string>VS;typedefv

算法1(离散化+并查集)没想到的点：由于数据范围很大1e9,因此需要采用离散化，从而降低时间复杂度主要思想1.约束条件有相等/不相等，不难发现，相等的约束条件是属于一个集合的--因此需要用到并查集思想我们按照e的大小进行排序，从而完成先处理e=1的所有情况3.并查集：初始化：一

题意给定一个字符串\(s\)和整数\(k\)。求：1.k叉哈夫曼树的带权路径之和；2.求合法的哈夫曼树中，最小的高度是多少。思路按照普通二叉哈夫曼树对其进行编码，将其转化为\(k\)叉哈夫曼树。编码有可能出现合并到根节点的时候不足\(k\)个结点，这会造成结果不优，所以我们可以补

思路：注意到对于每个数，其\(>19\)的质因数最多只有\(1\)个，称为大质数；对于\(\le19\)的质因数有\(8\)个，称为小质数。设第\(i\)个数的小质数集合为\(h_i\)。那么考虑对于所有数按照大质数从小到大排序，那么对于大质数相同的一段，只能放在两个集合中的一个。考虑状态压缩

P2150[NOI2015]寿司晚宴Statement给定\(n-1\)个数分别为\(2\simn\)，从中选出交集为空的两个集合\(A,B\)（集合的并集不必须为\(\{2,\dots,n\}\)，且集合可为空）使得不存在\(a\inA,b\inB\)满足\((a,b)\ne1\)（即任意两个数均互质），将方案数对\(p\)取模后输出。\(2\len\le

原题链接题解1.该题等价于构建一颗k叉树，每个叶子节点都有一个权值\(leaf_i\)，树的权值为\(\sum_{1}^{n}leaf_i\)，在使树的权值尽可能小的情况下，使最深的叶子节点的深度也尽可能小，即使数的高度尽可能小这个叫做哈夫曼树2.构建过程如下：每次从队列中取出\(k\)个节点，然后把他

原题链接：https://www.luogu.com.cn/problem/P1955题意解读：要判断约数条件是否可以同时满足，主要是要判断不相等的情况。解题思路：对于相等的条件，直接进行集合合并即可；对于不相等的条件，判断两者是否属于同一个集合，如果形成矛盾，则条件不能成立。由于i，j的范围至10^9，定义并查集如果

题意简述定义后缀\(p,q\)是\(r\)相似的当且仅当\(\forall1\lei\ler,s_{p+i-1}=s_{q+i-1}\)。对于每一个\(0\ler<n\)，求出：有多少对\(r\)相似的后缀。每个后缀有权值\(a_i\)，求在所有\(r\)相似的后缀对\((p,q)\)中\(a_p\cdota_q\)的最大值。若不存在则答案为

独立过了一道NOI的题，开心~我的做法是后缀数组+单调栈+st表，并没有用到并查集点击查看代码#include<bits/stdc++.h>usingnamespacestd;strings;intsa[300005],rk[20][300005],r[300005],n,w,h[300005],p[25],z[300005],st0[20][300005],st1[20][300005],f[600005];lo

P2178[NOI2015]品酒大会题解纪念一下第一道完全自己想出来的紫NOI题。思路由于r相似有单调性的性质，题目中也提示了这一点，考虑按\(height_i\)从大到小把所有相邻的\(sa\)数组内两个后缀合并，用并查集维护，发现第一问的答案就是\[\sum_{i是并查集的根}\binom{size_i}{2}

P2150[NOI2015]寿司晚宴翻译一下，题目其实就是给你\(2-n\)这些数，从其中选出两个集合（可以为空），求使两个集合中的数两两互质的方案数。那么就相当于说两个集合中的数的质因数的集合不能有重合。先看前\(\%30\)的数据，\(n<=30\)，里面的质因数不多，考虑状压\(DP\)。我们不妨设\(DP[i]

P1955[NOI2015]程序自动分析基本思路考虑到了不等号的不可传递性，所以决定只开相等的并查集。然后突发奇想，觉得可以在找父亲的过程中判断是不是冲突。然而这样就不能路径压缩，显然超时。并且，根本没看清楚数据范围，实际上这题的数很大，裸开数组会爆炸。这是一开始的代码#inclu

写了两天。。。就是说，状态压缩DP可以不用显示写出考虑到第i个数，直接每次考虑加入一个数会对当前状态造成的影响即可。这道题发现了大质因数只有1个之后，就需要考虑有相同的大质因数之间的转移，和大质因数不同的之间的转移。然后会发现没有大质因数的数需要特殊处理……然后就好

这么一想我好像破掉了两个flag。。。一个是Ag的flag……(Wc、Ctsc、Apio都是Ag另一个是二试被翻的flag……(NOIP，省选，Ctsc，各种二试被####DAY-1报到日从长春坐一晚上火车到北京然后坐高铁到杭州。。。一下车一股热气真爽~下了车看到好多人……黄学长居然和我们一趟线？黄学长：

题目链接洛谷LOJ题目分析哈夫曼编码模板题。使用k进制，即编码时将k个点合并为一个。最后要求的就是哈夫曼编码的长度，以及哈夫曼树最深的节点的深度。注意最后合并的时候可能会出现不满一层的情况，所以要在刚开始补成能恰好合并的哈夫曼树。最后剩下一个节点，即需要合并掉

[NOI2015]程序自动分析题目简述输入的第一行包含一个正整数\(t\)，表示需要判定的问题个数。注意这些问题之间是相互独立的。对于每个问题，包含若干行：第一行包含一个正

题目链接：​​传送门​​太难了太难了题意就是问有多少种分案把一个到的排列分配为两组并使组间元素两两互质首先我们只需要考虑根号内的质因子对答案的影响，因为根号外的因

树剖模板题，要求的操作时候区间平推，区间和查询。这还不简单?我会珂朵莉树！然而我打了珂线段树：直接一发A掉。#include<cstdio>#include<algorithm>#include<cmath>#def