Link 我们要求fT=∑S∈T[S为独立集]f_T=\sum\limits_{S\in T}[S为独立集]fT​=S∈T∑​[S为独立集] 考虑集合TTT的最低位二进制位代表的集合是yyy(这个点设为uuu),其他二进制位代表的是xxx 那么T=x+yT=x+yT=x+y 显然,若SSS集合中不包含集合yyy(点uuu),方案数为fxf_xfx​ SSS集合中不包含集合xxx,方案数为fy=1f_y=1fy​=1 若SSS中包含集合yyy且包含集合xxx中的部分点 需要满足包含的集合xxx中那些点不与点uuu有边 这个简单,我们令二进制数valuval_uvalu​表示哪些点与uuu有边 那...

LINK 有点像背包,但是又不完全是 原因在于使用的物品有限制,使得物品的使用次序是未知的 这样显然无法扫一遍做背包 如果按照排序也是不对的,限制大的不一定先使用 若使用变为,这样中间错过了许多小型优惠劵,可能先使用中间的才更优 于是想到按照排序,直接做背包即可. 这样选择物品的顺序满足 如果只选择优惠券中的一个,那么顺序是无所谓的,背包会考虑到 如果需要同时选择物品,那么按照的顺序一定是可行的 反证法 设按照的顺序选可行得到 按照顺序选优惠券不可行得到 我们得到,也就是 而因为,移项得到 显然矛盾,证毕,不存在这种情况. 也就是说,按照这种方式排序不会错,直接做背包即可 #include &...

LINK 作为题的受害者忍不住来写一发题解... 其实就是个简单的模拟,但是数组用混了就非常脑瘫 对n个询问按时间戳排序,并设置一个存机器缓存的特征 是结构体,包含这个缓存的特征类型和优先级,重载<为优先级更小的 优先级使用变量维护,每次加入新的特征类型把即可(后来的优先级一定更大) 那么处理第i个询问的时候,先把所有不符合的时间戳抹去(因为时间戳递增,所以可以用队列维护) 若set中有,就抹去原来的特征类型,把优先级修改为最高,再插入 若set中没有,就一直抹去直到元素个数<m,此时添加 注意 有时候队列中的元素会提前被弹出窗口,此时需要标记一下 遇到被标记的说明已经被抹掉了...

LINK 比较明显的点分治问题,考虑如何计算通过点的路径贡献 获得从出发的所有路径,显然经过的所有路径都是由出发的两条路径拼接而来 每条路径存成一个,第一关键字为最大值,第二关键词为最小值 现在就是一个简单的二维偏序问题 一下那么每个位置的最大值一定比前面大 然后使用动态开点权值线段树，最小值为下标,维护每个位置的数量和权值和即可 比如对于第条路径,最大权值为,最小权值为,考虑和前条路径合并的贡献 在线段树上查询一下权值为的个数和权值和即可 当作为路径中最小值时,答案是 当其他路径作为最小值时,答案是 动态开点权值线段树常数略大,需要写成类型的版本 也可以写离散化的树状数组,就不需要卡常数 实...

LINK 随机数据下,时间复杂度应该是碾压哈希的hhh 大小写是不重要的,因为第一步总是会把大写改成小写 所以我们可以暂时把字符集的大小都变成小写去匹配 然后拿样例来说 iherehtolleh 我们匹配这个,其实可以把这个串反过来 hellotherehi 然后匹配这个玩意,最后把答案倒过来就好了 这个串匹配的结果就是 我们定义为匹配是否有可能 假如暴力枚举个字符复杂度上天 不妨对这个串建立自动机,暴力跳转移 #include <bits/stdc++.h> using namespace std; const int maxn = 1e6+10; string s[maxn];...

考虑先求出最大公约数大于的子序列个数 显然,我们可以枚举这个最大公约数 我们预处理一个表示有个数字含有约数 然后我们去枚举子序列的最大公约数来计算答案 我们定义表示最大公约数是倍数的方案数 怎么求最大公约数是的方案数呢?? 我们定义表示最大公约数是的方案数 那么 预处理数组的复杂度,直接质因子分解的话是 采用调和级数的处理方式复杂度是 转移数组是调和级数的复杂度 #include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 3e5+10; const int mod = 1...

我们每次操作区间 对差分数组而言,相当于是而 又因为,所以 操作简化为以下两种 当 ,因为可以操作区间 当 而,因为可以操作区间 那么是不是倒序扫描差分数组一遍就好了....但是一直

不会写...看的题解,wsfw 物品的两个属性不太好弄 假如暴力设计状态,就是定义表示在中且的状态是否存在 暴力枚举的话复杂度上天 换种思路 考虑到最后的合法方案是 也就是 不妨给所有扩大到,这样一来我们只需要关注当前选择两种属性的偏移量 如果偏移量为零,那么达到目的 因为 所以偏移量不会超过这么多,再算上个物品 实现复杂度和空间复杂度最坏是 定义为前个物品的偏移量为时最大的 问题得到解 注意一下这个背包的物品由于有正数有负数,所以不能只开一维 (假如只开一维,需要分物品价值正数和负数分两次转移) #include <bits/stdc++.h> using namespace s...

传送门 每个人做第一题需要事件,做第二题需要的事件 每个人都要和其他个人组成一组队伍做一次题,你能选择的就是谁做第一题谁做第二题。 但是现在有对关系起了冲突,不能组队 求能组队的最小花费时间总和. 考虑和 花费是 两种选择方式的费用差是 也就是 当说明的方式比较好(因为差是正数) 当说明的方式比较好(因为差是负数) 那我们按照来排个序 对于第个人来说 个人由于比较小,所以都是贡献出来 个人由于比较大,所以都是贡献说来 如此一来,计算一个数值的前缀和就可以轻松求解 至于对关系,直接暴力减去就好了。 #include <bits/stdc++.h> using namespace ...

传送门 如果想到了的话,这题就不难了。 首先解决一个简单的问题,如何求出串有多少不同的子序列 定义为以的长度为的子序列个数 ,意思是选或者不选都是一种选择 但是有重复,考虑且时 形成的子序列后面接上或者接上是等价的 所以真正的转移方程是 也就是找到最近的一个满足条件的,然后去掉的方案数 那么这题就简单了.. 这样处理出数组去贪心即可得到解 #include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 109; int n,k,pre[maxn],f[maxn][maxn],a...

传送门 也就是每一位二进制只能放在这个数中的某一个上面 每位数字不能超过,我们发现这非常像数位的过程 现在简化一下问题 求的对数满足且 很明显这就是一个数位,表示 枚举到二进制第位,卡不卡上界,卡不卡上界 然后只需要暴力考虑当前位二进制填还是填 填的话填在还是填在,然后更新上下界范围即可。 回到这个问题 发现完全就是一样的问题,只不过变成了个数 当然你也可以去转移 不过这里用二进制压缩一下状态会更好看 #include <bits/stdc++.h> using namespace std; #define int long long const int mod = 1e9+7;...

传送门 最小化 同时增大亮度是没有意义的,可以转化为增大一个数组的亮度,设增大了数组亮度 假设增加的亮度一定,变化的就只有最后一项,也就是最大化 但是每一种对齐方式都需要计算形如 的式子 这部分已经是的了 但是如果把数组复制一份在最后面是一个长度的序列 把数组反转,做卷积得到的项中有 模拟一下的情况 数组和卷积 #include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 2e6+10; const int mod = 998244353,G=3,Gi=(mod+1)/...

A.校园活动 因为如果能够进行分组，那么每个组的总熟悉度是相同的 所以枚举最左边的组的总熟悉度的所有可能进行验证，特判所有都为0的情况。 #include <bits/stdc++.h> typedef long long ll; using namespace std; int n; int sum[1005]; string s; int solve() { if(sum[n]==0) return n; for(int i=1;i<n&&sum[n]-sum[i];i++) { int tmp=su...

传送门 找到个互不相等的 使得且 注意你构造的 我是废物^ _ ^ 既然不限制,那么令 要大于原数组的一半 不妨先满足数组,挑选最大的个下标 那么如何调整让数组也满足条件? 是不是选择最大的的下标会比较好呢?但是如果相应的非常小呢?无法抉择,抛弃这种想法... 至此,废物的思想停止了 正文,上面都是废话 一共有组数据,先按照为关键字排序 然后可以直接选前个元素,这样对最优秀,但是肯定会因此不满足 然后发现可以转化为:选择的数字比没选的数字大即可 因为需要选一半的数字,那就两个两个来考虑 一组,一组...每组选择值较大的,这样就可以满足 但是不一定可以满足...但是如果我们一开始把排序后位置选...