「BZOJ2744」 HEOI2012 朋友圈 题解
「BZOJ2744」 HEOI2012 朋友圈 题解
问题
原题链接 BZOJ2744
Description
在很久很久以前,曾经有两个国家和睦相处,无忧无虑的生活着。一年一度的评比大会开始了,作为和平的两国,一个朋友圈数量最多的永远都是最值得他人的尊敬,所以现在就是需要你求朋友圈的最大数目。
两个国家看成是AB两国,现在是两个国家的描述:
A国:每个人都有一个友善值,当两个A国人的友善值a、b,如果 axorb≡1(mod2)a xor b \equiv 1 \pmod 2axorb≡1(mod2) ,
那么这两个人都是朋友,否则不是;
B国:每个人都有一个友善值,当两个B国人的友善值a、b,如果 axorb≡0(mod2)a xor b \equiv 0 \pmod 2axorb≡0(mod2) 或者 (aorb)(a or b)(aorb) 化成二进制有奇数个 111 ,那么两个人是朋友,否则不是朋友;
A、B两国之间的人也有可能是朋友,数据中将会给出A、B之间“朋友”的情况。
在AB两国,朋友圈的定义:一个朋友圈集合S,满足 S∈A∪BS \in A \cup ...
「HDU5093」 Battle ships 题解
「HDU5093」 Battle ships 题解
题目
原题链接 HDU5093
Problem Description
Dear contestant, now you are an excellent navy commander, who is responsible of a tough mission currently.
Your fleet unfortunately encountered an enemy fleet near the South Pole where the geographical conditions are negative for both sides. The floating ice and iceberg blocks battleships move which leads to this unexpected engagement highly dangerous, unpredictable and incontrollable.
But, fortunately, as an experienced navy commande ...
「HDU2819」 Swap 题解
「HDU2819」 Swap 题解
题目
原题链接 HDU2819
Problem Description
Given an N*N matrix with each entry equal to 0 or 1. You can swap any two rows or any two columns. Can you find a way to make all the diagonal entries equal to 1?
Input
There are several test cases in the input. The first line of each test case is an integer N (1 <= N <= 100). Then N lines follow, each contains N numbers (0 or 1), separating by space, indicating the N*N matrix.
Output
For each test case, the first line contain the numbe ...
Learn English With HDUOJ
Learn English With HDUOJ
undirected [adj.] 无向的
weighted [adj.] 加权的
denote [v.] 表示
navy [n.] 海军
tough [adj.] 艰难的、坚固的
fleet [n.] 舰队
encounter [v.] 遭遇
embattle [vt.] 布阵
cannon [n.] 大炮
engagement [n.] 交战、约会
arbitrary [adj.] 武断的
iceberg [n.] 冰山
column [n.] 列、柱子
unpredictable [adj.] 不可预测的
represent [v.] 相当于
battlefield [n.] 战场
respectively [adv.] 各自地
iteratively [adv.] 反复地
symbolize [vt.] 象征
哈希(Hash)算法模板
哈希(Hash)算法模板
1234567891011121314151617const ull MOD = 998244353;typedef unsigned long long ull;ull h[MAXN], p[MAXN];inline ull hash(string s) { //求哈希值 static const ull BASE = 131; ull res = 0; int len = s.length(); for(int i = 0; i < len; i++) { p[i] = p[i - 1] * BASE; h[i] = (h[i - 1] * p[i] + ull(s[i])) % MOD; } return h[len - 1];}inline ull sub_hash(int l, int r) { //子串哈希值 return ((h[r] - h[l] * p[r - l + 1]) % MOD + MOD) % MOD;& ...
k条白边最小生成树问题
k条白边最小生成树问题
问题
给定一张图,每条边都有一个权值和颜色,仅为黑色或白色,求一条恰好包含 kkk 条白边的最小生成树。
求解
这个问题与分数规划问题非常类似
给每条白边的权值都增加 CCC ,二分 CCC ,求此时的最小生成树总权值 www ,并求出这个树包含几条白边。
假如包含的白边数 r>kr > kr>k ,则增大 CCC ,否则减小 CCC ,直到 r=kr = kr=k ,则最小生成树的总权值则为 w−k∗Cw - k * Cw−k∗C
分数规划模型学习笔记
分数规划模型学习笔记
问题
给定 nnn 个二元组 (ai,bi)(a_i, b_i)(ai,bi) ,从中选出 kkk 个二元组使得 ΣaiΣbi\frac{\Sigma a_i}{\Sigma b_i}ΣbiΣai 尽可能大,求出最小值。
求解
假设
ΣaiΣbi≥x\frac{\Sigma a_i}{\Sigma b_i} \geq x
ΣbiΣai≥x
则可以将式子变形为
Σai−x⋅Σbi≥0\Sigma a_i - x \cdot \Sigma b_i \geq 0
Σai−x⋅Σbi≥0
对 xxx 进行二分,将 ai−x⋅bia_i - x \cdot b_iai−x⋅bi 从大到小排序,选出前 kkk 个 ,判断式子是否成立,如果成立则增加 xxx ,不成立则减小 xxx ,直至求出最优解。
线段树优化建图笔记
线段树优化建图笔记
问题
给定 nnn 个结点, mmm 组边,第 iii 组边从 $ P_i$ 向 LiL_iLi 到 RiR_iRi 这段点号区间中所有点连一条长度为 ViV_iVi 的边,求最短路。
线段树使用
首先线段树每一个区间节点都向这个节点的子区间节点连一条长度为零的边,叶子结点向这个长度为 111 的区间所表示的点连一条长度为零的边。
如果有一组边为从 333 号点向 [4,8][4, 8][4,8] 这段区间连长度为 vvv 的边,则从 333 号点向区间节点 [4,4][4, 4][4,4] 连一条长度为 vvv 的边,再从 333 这个点向区间节点 [5,8][5, 8][5,8] 连一条长度为 vvv 的边,就完成了连边以及建图。
代码模板
在写了在写了
二分图的最大独立集问题
二分图的最大独立集问题
最大独立集和最大团
一个图中包含尽可能多个互相没有边的点组成的集合就称为这个图的最大独立集。
一个图中包含尽可能多个彼此都有边相连的点组成的集合称为这个图的最大团。
在一个图中的最大独立集等于在这个图的补图中的最大团。
与二分图的关系
不幸的是,在一般的图中,求解最大独立集是一个NP完全问题,但是幸运的是,在二分图中,这是一个可以解的问题,在二分图中,最大独立集中的点数等于所有点数减去匹配的数量,假设这个二分图一共有 nnn 个结点,并且形成了 kkk 个匹配,即说明其中至少 kkk 个形成匹配的结点被删掉之后,这个图中剩下的所有点就彼此都没有边相连了,所以最大独立集的数量为 n−kn - kn−k 。
而如果存在一个图,两边所有的节点都有边相连,并且两边有有几条边彼此相连,这显然是一个二分图的补图,如果要求这个图的最大团,即可以将该问题转化为对补图求最大独立集。
而同理,如果一个题目中涉及最大独立集或者最大团,就可以将该问图与二分图联想。
二分图匹配问题
二分图匹配问题
问题
在一个二分图中,每一个点只能匹配一个点,求这个图中最多能存在多少对匹配上的点。
匈牙利算法
dfs(i) 函数为尝试让 i 进行匹配的函数,如果 i 号点可以进行匹配,则答案 ans++ 。
dfs 函数的原理为:首先对与 i 号点有边的点尝试匹配,如果该点已经被匹配,则尝试让该点匹配的点重新匹配,如果匹配成功,修改该点匹配的点为 i 否则尝试下一个点。
算法代码
12345678910111213141516171819202122int n, m;bool dfs(int i) { for(int j = 1; j <= m; j++) { if(match[i][j] && !use[j]) { use[j] = true; if(!result[j] || dfs(result[j])) { result[j] = i; return true; ...