19-大数据一班-杨文冠

题解

学习(23) 未归档(1) 练习(1)

/ 注册

全部文章 / 题解（共137篇）

L. Square 来自专栏

思路：为了保证为平方数，如果的某个质因数的个数为奇数个，那么的该质因数个数也应该是奇数个，依次类推，那么所有中出现过的质因数在每个中出现的次数要么都是奇数个要么都是偶数个，取代价最小的。 MyCode: #include <bits/stdc++.h> typedef long long...

2021-05-19

3 809

月出皎兮，佼人僚兮。来自专栏

如果颜色最多个数大于其它颜色之和，可以匹配的对数就是其它颜色之和，即其它颜色的都和颜色最多的两两匹配反之，每个颜色都能找到匹配，因为其它颜色匹配后，剩下的只要不断拿出两个去拆已经匹配了的一对，一定能用完。 MyCode: #include<bits/stdc++.h> using nam...

树上启发式合并

2021-05-13

0 673

【模板】最大流加强版 / 预流推进来自专栏

给定 n 个点，m 条有向边，给定每条边的容量，求从点 s 到点 t 的最大流。 DinicDinicDinic算法复杂度上界为n2mn^2mn2m，可以优化到nmlogCnmlogCnmlogC ，CCC是最大的流量，代补。 HLPPHLPPHLPP算法复杂度上界为n2mn^2 \sqrt{m} ...

HLPP 最大流

2021-05-09

2 781

Nastia Plays with a Tree 来自专栏

1 7 1 4 6 5 6 3 1 2 1 6 1 7思路：先以为根画出上面的图。节点度为，有两个度为的叶子节点，我们可以知道，如果将边断开，然后再将其中的一个叶子和树上度为的叶子相连（比如连），此时是最优的，因为这样不必在断开后还需要断开的一个叶子。所以我们的策略是：如果某个点只有一条链，不操作...

树思维

2021-05-08

2 679

Nastia and a Hidden Permutation 来自专栏

坑：又是一种可以搞死面向案例编程的选手的恶心案例，仗着数组是自己隐藏的，自己是知道答案的，于是就假装问几下然后就输出答案。这题别看样例！光这几个问答根本确定不了排列。思路：通过一定能找出的位置，如果那么，如果，那么找到之后就可以通过来得到的值。 MyCode: #include<bits/...

交互思维

2021-05-08

2 654

K取方格数来自专栏

拆点后入点和出点两条（容量，边权）为的边求解最大流需要寻找所以一条增广路，为了费用之和最小，可以改用spfa寻找一条单位费用之和最小的增广路，每次在残余网络中跑最长路，直到找到最大流。这题不要求最大流，所以如果残余网络中得不到费用后可以直接退出。 MyCode: #include <bits/...

费用流网络流

2021-05-07

1 566

F2. Guess the K-th Zero (Hard version) 来自专栏

方法一：记忆化二分，有这么两种二分：、第一种和线段树的所有区间重叠，的子区间都是，如果开个桶去记忆化，需要查次，但可以知道的是被遍历的区间远小于这么多，所以可以去记忆化。方法二：将扩大到的幂次，然后预处理的幂次的下标的值（即对原数组分块）。然后每次二分答案在那个块里面（已经预处理，不需要询问测评姬...

二分记忆化二分

2021-05-07

1 823

Cable TV Network 来自专栏

思路：无向图不连通则必有两个点不连通，枚举两个点，求在剩下的个节点中最少去掉多少个点，可以使和不连通，在每次枚举的结果中取最小值就是这题的答案。拆点的两种方式：1.入点和出点分别是和，需要知道有多少个点2.入点和出点分别是和点的出边到的入边的最小割就是需要去掉的点，枚举完后把反向边的容量加回去就可...

最大流网络流最小割

2021-05-05

1 677

舞动的夜晚来自专栏

思路：用网络流跑二分图的最大匹配，先将H公司第个人的编号变为，然后表示公司和公司的两个人有关系,待匹配。残余网络中非匹配边为从左部到右部的有向边，的边权为，匹配边为从右部到左部的有向边，边权为。非匹配边：，表示边的容量匹配边：因为要求不可行的边的数量，即不是可行边和必须边的边；先跑一遍最大匹配最大匹...

最大流

2021-05-05

1 495

XOR

题意：组数据，每组数据输入一个，接着输入个数，表示一个数组，然后一个，表示组询问，接着输入个整数，对每次询问输出它的异或第小值。思路：高斯消元后的线性基是一个对角矩阵，有一个非行就表示有多少个数成功插入，同时异或谁就相当于加上谁，这和二进制的位权刚好想对应，大的向量对应高位权，小的向量对应低位权。...

线性基 XOR 高斯消元

2021-05-04

2 662