4 月做题记录

P11355 Teleporters Master

题目大意

dXqwq 和 Haitang 在数轴上的两个不同的点，他们想要见面，但是他们只能通过传送器移动。

有个传送器，第个位于坐标轴位置，频率为。由于某种原因，只有频率的传送器可以使用。

使用一个传送器会将一个人传送到与其坐标对称的点。形式化地说，一个人传送前后的位置与传送器的位置满足。

dXqwq 和 Haitang 会不断同时各自选择一个传送器（不需要相同），进行传送并经历的疲劳值，直到他们抵达同一位置。整个过程的疲劳值为每次经历的疲劳值的最大值。

给定次询问，每次给定一组，求 dXqwq 和 Haitang 见面的总疲劳值的最小值，或报告他们不可能通过这些传送器见面。

，，，，。

解答

首先，假设两个人在位置，选的两个传送器坐标为，那么第一个人的位置就变为了，第二个人的位置就变为了，两个人的距离也就从变为了，也就是相当于是加上了或是减去了。而这道题我们不关心它们的坐标是多少，只关心它们坐标的差值是多少。

而且，容易发现：假设有三个传送器（按照值从小到大排序），那么直接使用传送器肯定不如先使用再使用的。首先，从疲劳值来看肯定是不优的。并且它们的使用效果相等。因为前者是。后者是，然后再使用一轮。这个时候，两个人的距离的差值的变化是相等的。

所以肯定是先把传送器按照排序，然后选择两个传送器就相当于是选传送器。那么我们就可以把问题转化为操作连续区间了。

然后我们发现有解的条件是什么？就是你选一些合法的相邻点二元组，记每一对相邻点的距离为，那么有解的条件就是存在一种合法相邻点二元组集合使这些的是的因数。那么肯定的，当为奇数，无解。

那么我们就可以对于单次询问，先二分答案，设其为。那么先圈定范围，然后的肯定全部选上，因为多选肯定不劣。然后就判定如果全部选上的是否为的因数，若是，则设，否则设，然后当的时候判一下就可以了。单次询问时间复杂度。

这样的话时间复杂度肯定会爆。那么我们改用整体二分。整体二分是什么呢？我们首先把所有修改和询问全部使用一个函数：void solve(int l, int r, vector<Change> chg, vector<Query> qry) 包含起来，然后将 chg 分为和的两个部分，然后执行部分，看 qry 里面哪些符合的。若符合就把它 push 进 lqry 里面，否则 push 进 rqry 部分。然后清除，之后再 solve(l, mid, lchg, lqry), solve(mid+1, r, rchg, rqry)。当时，就直接执行 chg 的修改，不撤回了。然后再查询。这样就可以保证再二分的时候的修改是执行了的。时间复杂度。

但是请注意，当 solve 到一个区间，这个区间的 qry 是空的的话，那么就执行 chg 然后 return。不然会导致你的时间复杂度假！

0403T1 BFES

题目大意

小 T 有一个很有趣的键盘。

小 T 的键盘是专门为输入 T 语言——小 T 自⼰发明的某种语言而设计的。具体而言，T 语言共有个字母，分别用编号表示。此外，T 语言共有个不同的单词，其中第个单词可表示为一个包含个字母的序列，其中相邻两个字母均不相同。

这种键盘有趣之处在于，其输入个字母的部分由两块子键盘（分别用和表示）构成，且提供了对应的个按键用于自行安装。对于这个按键中的每一个，小 T 可以自行选择将其安装在或上（不能不安装，也不能同时安装在两块子键盘上）。为了方便，小 T 希望在输入任意一个单词时，都可以通过交替使用两块子键盘输入（即对于任意单词的任意一对相邻字母，其对应按键不在同一块子键盘）。除此之外，小 T 希望两块子键盘上按键数尽可能接近，即希望最小化按键数之差的绝对值。

解答

首先，我们可以判定是否无解。将每一个单词相邻的字母连边，然后使用 DFS 染色。若存在两个相邻的字母颜色相同，则无解。

然后我们就得到了一群连通块，设每一个连通块的两种颜色之差为。那么问题就转化为：给定一群，将其分配到两个集合内，使这两个集合的之和尽可能接近，即绝对值最小。即拔河问题的升级版。

这是一个非常之非常之经典的问题，但是我还是不会。严重性已经过于大了。

遇到这种问题，很明显的是一个背包，如果暴力 + Bitset 做这种背包的话时间复杂度，无法通过此题。赛时就被卡在了这里。

于是优化算法。这种经典问题可以转化为多重背包。如何转化？

原题中，根据题意，所有的和一定。于是，本质不同的一定只有种。我们可以记录一个数组，表示这个数出现过多少次，所以最多只有个位置有值。然后就可以转化为最多个元素的多重背包。但是一般的多重背包还是做不起。

所以要使用二进制分组优化。

具体地说，假设元素出现过次，那么可以将转化为。在这些里面使用 0-1 背包选可以达到和多重背包一样的效果。例如：

。假如想选，那么选项即可。

然后这样，0-1 背包的项数就从项转化为了项，所以就可以使用的时间复杂度解决这个问题了。

P11111 [ROI2023] 生产计划

题目大意

某个国家准备制定汽车的生产计划。

该国总共有个城市，每个城市中有一个工厂，它们要参与汽车的生产。第个城市的工厂可以雇佣到个人。

一些城市之间通过双向道路相连，且道路网络呈树状结构。因此，如果要从一个城市到另一个城市，在不重复经过同一个城市的情况下，只有一种路径。

生产计划被定义为一个整数序列，其中表示在第个工厂工作的人数，满足。在制定生产计划后，一些工厂将被选为装配工厂，这些工厂负责装配汽车，而其它工厂则负责生产零部件。如果没有两个装配工厂所在的城市被一条道路直接连接，那么这个生产计划就是合理的。在所有可能的合理的计划中，会选择装配工厂的工人总数最大的一个计划。这个数就被称为计划的效率。

你需要确定是否存在效率为的计划。如果存在这样的计划，则可能需要输出这样一个计划。

制定计划的过程包括两个阶段。

在第一阶段，你将获得的值。你需要确定是否存在效率为的计划，如果不存在，输出 -1；如果存在，输出一个非负整数。

对的定义如下：给定三个整数，定义计划的，其中为按位异或。

因为符合要求的计划可能不止一个，所以也有很多种可能，你需要输出其中一种可能的。

在第二阶段，某些计划的可行性将被检查。在每个查询中，你的程序会得到一个整数（）。对于这个查询，如果不能制定效率为的计划，你需要输出 -1；否则，你需要输出个整数（），表示一个制定的计划。这个计划计算出来的值应该等于你先前输出的，效率应该等于。

在程序输出每个之前，无法知道哪些计划会被检查。因此，你需要保证在第一阶段中输出的是正确的。

使用交互形式强制在线。

，且每组数据中检查计划次数的总和不超过，。

解答

这道题其实就是让你选出一棵树的最大权独立集。这个比较的典型，可以使用树形 DP 来做。

考虑，如果给某一个点的点权一直增加，后面会发生什么。这棵树的最大权独立集可能会不变一段时间，之后就会一直。所以，我们肯定可以得到一个结论：

首先将所有点的点权设为，求最大独立集为；然后将所有点的点权设为，求最大独立集为，则当时，则一定有解，否则无解。

因为当我们以某一个顺序，将每一个地方的慢慢加到，再根据上面的答案是连续的，即可以得证。但是我们应该如何确定这个顺序？

因为我们之前是树形 DP，所以考虑再树上的顺序，即 DFN 序。这样也好换根。我们换根 DP 求得，当点全部设为，全部设为的最大权独立集是多少。设其为，这是容易求的。并且，这样也可以求得每一个这种状态的值。

而也是根据序单调不降的，所以可以二分求得哪些 dfn 序的位置取了。然后后面最多一个位置不取，也可以求出。

后面构造也根据这个来构造即可。

CF2086D Even String 最新最热

题目大意

您想构造一个由小写拉丁字母组成的字符串，使得以下条件成立：

对于每一对和这样的索引，这些索引的差都是偶数，即。

构造任何字符串都非常简单，因此我们将得到一个由个数字组成的数组 - 即字符串中每个字母出现的所需次数。因此，对于每一个来说，拉丁字母的第个字母应该正好出现次。

你的任务是计算满足所有这些条件的不同字符串的数量。由于答案可能非常庞大，因此请输出它的模数。

所有数据的。

解答

一道赛时做不出来的数数题。被两千多个人强制【数据删除】了。怎么回事呢？

假如不考虑的限制，该怎么做？

首先，假设有个位置，放置个不同元素的方案数为。其次，放置个相同元素的方案数为。

所以，这种情况的方案数即为：。

然后考虑限制。其实这个限制只是相当于钦定一些拉丁字母选偶数位，其它的选奇数位。那么，对于每一种选择，方案数其实相似，就是，即。

那么我们需要求出有多少种选择符合条件，即一种大小，另一种大小。

唉，这不就是上一道题，0403T1 吗。0-1背包 DP 求得即可。

然后再把和上面的方案数乘起来即可。

void Maisolve(){
    for(int i=1;i<=n;i++) cin>>c[i], sum += c[i];
    dp[0] = 1;
    for(int ct=1;ct<=n;ct++){
        int val = c[ct]; if(val == 0) continue;
        for(int i=sum;i>=0;i--){
            if(i + val <= sum)
                dp[i+val] += dp[i];
        }
    }
    int one = sum/2, another = sum-sum/2;
    mint allinv=1; // use modint template
    for(int i=1;i<=n;i++){
        if(c[i]) allinv *= mint(fact[c[i]]).ksminv();
    }
    mint once = fact[one] * fact[another] * allinv;
    cout<<dp[one] * once<<'\n';
}

P3488 [POI 2009] LYZ-Ice Skates Master

题目大意

滑冰俱乐部初始有号码溜冰鞋各双，已知号脚的人可以穿号码的鞋子。

现在有次操作，每次两个数，表示来了个号脚的人，为负则表示离开。在每次操作之后，你需要判断溜冰鞋是否足够。

解答

首先，最直接的想法就是直接暴力，连边，建二分图。然后当来人走人的时候，就加边删边。很容易的，会 TLE。

先说结论：这道题需要用到霍尔（Hall）定理。

Q：什么是 Hall 定理？

假设你有一个二分图。这个二分图被分成了左、右两部分。

左部分能够被完全匹配的充要条件是，对于所有的，部分向有连边的点数部分的点数。

借用网上的解释，就相当于是一堆男的要和一堆女的匹配，每一个男生都喜欢一些女生。喜欢关系就相当于有连边。

那么，要让那群男的每一个人都可以匹配到自己喜欢的女生，当且仅当随便拎出来一些男生，这些男生喜欢的女生集合的集合大小都要大于这些男生的个数。

那么我们如何将这个定理套到这道题上面呢？取所有集合肯定是不现实的。所以我们要考虑最紧的那个集合。

容易发现，假设你取了集合，肯定是不如取优的。因为这样做就相当于是在不改变对应的下，凭空增加了。这样是更紧的。

所以我们就可以得到，必须。

两边同时减去，可得。

可以发现是定值，所以可以写一个数据结构维护全局最大子段和即可。

P11392 [JOI Open 2019] 三段跳び Master

题目大意

给定数列，次询问，每一次给定一区间，需要选 3 个数，其中，，要求最大化，输出这个值。

。

解答

首先，如果你考虑暴力，假设选了和，那么因为的范围可以得出来是，所以可以完成。

之后，考虑如果你将范围缩小，我们定，发现的范围肯定是不劣的嘛，那么肯定要使比最优。那么我们就得出，最优的一定满足中没有或的数。因为如果有的话就一定可以被换掉。

所以我们可以使用单调栈得出每一个位置的，即左边第一个的数，和，即右边第一个的数。然后最优一定只有和，最多个。

所以我们就可以将这些区间离线，也将询问离线，遍历，每到一个位置就将左端点为的区间更新。怎么更新，又更新什么呢？其实，因为每一个区间的答案是，所以我们可以维护一个区间加、区间查 max 的数据结构，对的位置上一个的 tag。然后询问离线就在只更新的区间后询问一下即可。

CF1056H Detect Robots 3200

题目大意

您成功地在您完全预料到的车站出口附近找到了可怜的阿尔卡季。您把他送上出租车后，突然想到了一个问题。

您所在的城市有个十字路口，连接其中一些十字路口的有几条双向道路。乘坐出租车就是从一个十字路口到另一个十字路口，而不会两次经过同一个十字路口。你有一个司机的乘车记录，现在你想知道这个司机是机器人还是人类。

你认为，如果在每两个十字路口和中，司机从开往时总是选择相同的路径，那么司机就可能是机器人。请注意，这里的和不一定是一段路程的终点，从到的路径也可以不同。相反，如果司机曾经驾驶过从到的两条不同路径，那么他们肯定是人类。

根据道路系统和对所有可乘坐交通工具的描述，判断司机是否可能是机器人。

简要题意：

有一张个点的图，给你条路径，每条路径中每个点最多出现一次，如果存在两个点、，他们在两条不同的路径中均出现，且在两条路径中到之间的点依次有一个点不同，则输出 Human，否则输出 Robot。

数据范围为。

解答

首先，我们考虑暴力可以怎么做。假设我们知道两条路径，都是从。第一条是，另一条是。若，那么就一定是人类。所以可以得出一种暴力做法：暴力枚举，然后对于前面的所有，查询是否有的后面一个不同的。

对于路径长度比较小的可以使用这个暴力做法，所以考虑根号分治。记的路径为短路径，否则为长路径。那么短路径对短路径就可以使用这个暴力方法：存储所有的至下标，然后看是否有两个相同的，不同。

那么长路径对短路径、长路径对长路径怎么做？注意到长路径最多只有个。所以时间复杂度要单次 check 。我们可以沿用上面的思路，设现在枚举的这个路径编号，对于每一个，枚举路径，若枚举到了一个点在路径中出现过，并且这两个点在这两个路径上的后继不同，并且后面出现过相同的点，那么就肯定是人类。「后面出现过相同的点」如何实现？可以在枚举时倒序枚举，然后记录一个当前路径中目前枚举过的点在出现过的最右位置，最初赋为。每一次若出现过就对在路径中的位置取一个。若当前点在中的位置，说明后面有相同的点出现了，就可以判后继是否相同了。

P11160 機械生命体

题目大意

维护一个可重集 ，初始为空。支持如下操作：

1 x，你需要在中加入一个数。
2 x，你需要在中删除一个数。保证此时中存在至少一个。如果存在多个，则仅删除一个。
3 x k v，你需要对中所有满足的增加并对取模。
4 x，你需要求出。保证此时不为空。

其中表示最大的整数，使得是的整数次幂并且整除。代表按位异或。

特殊的，我们在本题定义。

对于所有数据，，，。

解答

因为包含位运算，和加入数删除数操作，所以考虑 Trie。

因为包含操作，所以这次建 Trie 倒着建。即从低位到高位建。

加入数、删除数和查询操作是简单的，考虑第三个操作，第三个操作相当于是把一个子树提取出来，然后重新插到一个地方。所以这个可以使用 Trie 分裂/合并加上 lazytag 实现。

P11343 出租车旅行 Re: Master

题目大意

IOI 国由个城市和连接这些城市的条双向道路组成，任意两个不同的城市都可以通过这些道路互相到达。也就是说，IOI 国的道路网络是一个树结构。

每个城市都有一个编号，从到，其中号城市是 IOI 国的首都。对于每个，第条道路连接号城市和号城市，道路长度为公里。

在 IOI 国，不同城市的出租车费用不同。具体来说，对于每个，从号城市出发的出租车有一个基本费用元和每公里的费用元。这意味着，如果从号城市出发并行驶公里，需要支付元。

小明目前住在首都号城市，他计划乘坐出租车去其他城市旅行。当他到达一个城市时，可以选择继续乘坐当前的出租车，或者换乘该城市出发的出租车。当然，换乘出租车需要支付基本费用，并且每公里的费用也可能不同。请计算从 0 号城市出发到达其他所有城市的最小费用。

对于所有输入数据，满足：

对于所有，
对于所有，
对于所有，
对于所有，

解答

首先，我们考虑什么时候才会换乘。那么肯定是换乘后的比换乘之前的小才去换乘，不然不优。所以可以得到，一段路程的换乘点（包括起点），除了终点，其它的都是递减的。所以可以设计一个基本的 DP 转移：

设表示从出发到的最短距离，那么转移顺序就是按照从大到小排序后的顺序。转移式子可以得出来：

for(int i=1;i<=n;i++){
    int idx = p[i].idx; // 这里 P 序列是按照 B 从大到小排序后的序列
    for(int j=1;j<=n;j++){
        if(b[j] < b[idx])
            dp[j] = min(dp[j], dp[idx] + a[idx] + b[idx] * dis(idx, j)); // dis 使用 DFS + DFN 序求 LCA O(1) 求出
    }
}

最后因为终点不是递减的，所以对于终点还要再转移一次。时间复杂度。那么如何优化这个时间复杂度？

现在需要一个数据结构来优化转移。可以使用点分治思想，建一棵点分树，可以得到即的祖先都是可以被转移的地方。所以对于每一个分治中心（即我们钦定两点经过分治中心），到的代价就是。把前面的看作，后面的看作，就是个一次函数。所以我们可以给点分树上的每一个点开一个动态开点李超树，维护线段最小值。因为在点分树上只有及其祖先才能有可用，所以修改、查询时都暴力跳点分树父亲修改、查询。查询取最小值。

注意因为要加上的最小路径，所以要先给加上查询值，再做修改。最后答案就是对每一个点查一遍就可以了。

P7357 中位数 Master

题目大意

给定一棵以为根的包含个节点的有根树。第个节点有点权。

定义函数表示从到经过的所有节点的点权的可重集的中位数。

请注意，本题中的中位数的定义与数学中的定义略有不同：这里一个长度为的序列的中位数定义为这个序列第小的数。

定义函数表示从到的路径是否完全覆盖了从到的路径。如果完全覆盖，则，否则。

你需要依次处理次操作，按照以下格式给出：

1 u：表示一次操作，需要你将点的点权对异或；

2 u v：表示一次询问，需要你求出。

对于第二类操作，保证每次询问均满足不是的祖先且不是的祖先，且。

你需要对于每个第二类操作，输出对应的值。

对于的数据满足，，保证每次询问均满足不是的祖先且不是的祖先，且。

解答

对于中位数，有一个求中位数使用的非常经典的 Trick：将所有的数新设点权设为 -1，将所有的数设点权设为 1，然后二分答案，当就说明中位数，否则 。

原题面可以被看作在两个子树上面选点，假设选两点，那么设中位数为的值就是（这里的函数指的是从到根的权值之和）。为了让二分时容易查询答案，所以我们建一棵可持久化线段树，版本代表时每一个点的权值。然后因为要使答案最大，所以想要取两棵子树权值最大值，所以我们定义区间值为 dfn 序范围的权值最大值。开始 build 的时候，因为要区间加值，并且后面要区间查，所以要使用标记永久化。

然后查询时的修改操作就看它是怎么修改的。我们设为当前这个点，为原值。那么如果为奇数，相当于是以这棵树为开头的后面所有树区间加，然后以上一颗树为开头的后面所有树区间减。所以只需要对上一颗树区间减即可。为偶数同理。

P12014 牢帽 Master

题目大意

给你一个个点的无向图，图初始没有边。他还有整数和。现在有次操作，操作有四种：

1 x y ：连接之间的边，保证边原先不存在。
2 x y ：删除之间的边，保证边原先存在。
3 x y ：将修改为。
4 x ：设图分为共个连通块，求出。

对于的数据，满足，操作中、操作中均为小于的非负整数。

解答

连边、删边可以使用线段树分治实现。

观察限制里面，若是的倍数，那么，对于一个连通块，会化成的形式。因为是的倍数，所以在意义下，及更高的项可以被忽略不计。只剩下项。因为算答案的时候会涉及到多项式乘法，但是因为只有 4 项，所以可以暴力写。这样是的倍数的情况就解决了。

而如果不是的倍数呢？因为，所以可以将转化为。然后就对于答案开一个大小为 10 的数组。数组内每一个元素开一个项数为 4 的多项式。因为可以被转化为，所以下标为的位置就记录的答案。然后就又可以转化为是的倍数的情况了。

细节比较少，但是注意线段树上的情况要特判！

0418T1 mercury

原题链接：P11519 Telephone Plans Master

题目大意

CCO 国现在由唯一的电话服务商多米通提供服务。CCO 国有个房屋，编号从到。每条电话线连接两栋不同的房屋，所有曾经存在过的电话线都不会形成回路（就像树一样）。

但是每条电话线只能在一段时间内使用。如果在某个时刻，房屋之间存在着由电话线连接的路径，那么这两个房屋就可以互相通话。

个查询，查询格式如下：

1 x y：在房屋和之间添加一条电话线。保证之前没有在和之间添加过电话线。
2 x y：移除房屋和之间存在的电话线。
3 t：计算在最后个查询这一段时间内至少有一个时刻能互相通话的房屋对数。更准确地说，记为第个查询之后 CCO 国的状态，为没有任何查询之前的状态。如果是第个查询，则计算在这个状态中的至少一个状态中能够互相通话的房屋对数。（注意操作和操作也是查询操作！）

部分测试用例会被加密。对于加密的测试用例，参数，和会和上一个类型为的查询的答案进行异或等于（C++ 中的 ^=）操作（如果还没有过类型为的查询，则认为上一个答案为）。

解答

对于第个操作：对于一个加边操作，我们记。（这里的指的是加边之前和的连通块大小）对于一个删边操作，我们记。（这里的指的是删边之后和的连通块大小）

因为所有曾经连的边都不会成环。所以对于一个询问操作，答案即为。现在我们要做的就是维护连通块大小了。

对于加边，就是启发式合并。这个简单。

而对于删边，我们要使用启发式分裂。具体来说，就是对和同时 BFS，其中一个 BFS 完了就退出，然后将先 BFS 完了的那个单独赋一种颜色。注意 BFS 的时候不能一次 BFS 完所有出边，因为这样每次 BFS 的大小会不一样！

P4249 剪刀石头布 Re: Master

题目大意

在一些一对一游戏的比赛（如下棋、乒乓球和羽毛球的单打）中，我们经常会遇到胜过，胜过而又胜过的有趣情况，不妨形象的称之为剪刀石头布情况。有的时候，无聊的人们会津津乐道于统计有多少这样的剪刀石头布情况发生，即有多少对无序三元组，满足其中的一个人在比赛中赢了另一个人，另一个人赢了第三个人而第三个人又胜过了第一个人。注意这里无序的意思是说三元组中元素的顺序并不重要，将、、、、和视为相同的情况。

有个人参加一场这样的游戏的比赛，赛程规定任意两个人之间都要进行一场比赛：这样总共有场比赛。比赛已经进行了一部分，我们想知道在极端情况下，比赛结束后最多会发生多少剪刀石头布情况。即给出已经发生的比赛结果，而你可以任意安排剩下的比赛的结果，以得到尽量多的剪刀石头布情况。

输出剪刀石头布情况的最大值，并且需要构造任意一组可行的方案。

。

解答

发现对于任意一个三元组，成为环的情况就说明三点的入度、出度均为。若不成环，就说明有一个点的入度为，有一个点的出度为。这里为了方便，仅对入度考虑。

那么一个点它对“不成环的三元组个数”的贡献有，就是从它的入边里面随便选两条边然后就构成了一个不成环的三元组。那么整张图的环个数就是。

那么我们可以只看后面那个式子：当增大，那么它的贡献就是原。也就是说它的贡献是一个公差为，首项为的等差数列。

那么我们就可以建模：对于赢了，。对于输了，。而对于不知道结果的，设一虚点，。

然后连汇点：对于每一个点，循环次操作，定义从到，连边。

最后求出最小费用就是后面那一项。然后构造方案就 check 一下虚点连出去的两条边的流量。

AGC034D Manhattan Max Matching Master

题目大意

斯努克正在玩红球和蓝球，他把它们放在一个二维平面上。

首先，他进行了次放置红球的操作。在次操作中，他在坐标处放置了个红球。然后，他又进行了次操作来放置蓝球。在次操作中，他在坐标处放置了个蓝球。放置的红球总数和放置的蓝球总数相等，即。设这个值为。

现在，斯努克将把对红球和蓝球组成一对，这样每个球都正好属于一对。让我们将坐标处的红球和坐标处的蓝球组成的一对的得分定义为。

斯努克想要最大化这对小球的得分之和。请帮助他找出这两对球得分之和的最大值。

解答

对于两个点的曼哈顿距离，可以将其化成。

然后建 4 个虚点，然后跑最大费用最大流就完事了。

P3679 二分毯 Master

题目大意

在二分图中，所有点被划分成了两个不相交的集合和，每条边都恰好连接着某个和某个。一个匹配是一个边集，满足没有任何两条边有相同的端点。我们称一个匹配覆盖了点集当且仅当中的每个点都是中至少一条边的端点。

给定一个二分图，每个点有一个正整数权值。定义一个点集的权值为其中所有点的权值之和。

给定一个参数，请统计有多少点集，满足的权值不小于，且被至少一个匹配覆盖。

，，。

解答

根据广义 Hall 定理，若存在左部点集被一个匹配覆盖，并且存在右部点集被一个匹配覆盖，那么点集一定能被一个匹配覆盖（可以为）。

所以我们可以分别对左、右两点集分开考虑。

先考虑左边的。根据 Hall 定理，一个点集能够有完美匹配的充要条件是，，的邻居个数一定。所以我们可以使用高维前缀和来处理合法性。右边同理。

然后就是点权。因为每一边最多个合法点集，所以先把他们权值求出来，然后排序，最后双指针扫一遍即可。