（模板）匈牙利算法 匈牙利算法就是不断找增广路的过程 假期的宿舍 题目概述 每个人只能睡自己的床或者自己直接认识人的床 学校自己的学生一部分回家，一部分留校 一部分外校人来找朋友 能否每个人都有床睡觉 输入格式 第一行一个数 表示数据组数。接下来 组数据，每组数据第一行一个数 表示涉及到的总人数。 接下来一行 个数，第 个数表示第 个人是否是在校学生 ( 表示不是， 表示是)。再接下来一行 个数，第 个数表示第 个人是否回家 ( 表示不回家， 表示回家，注意如果第 个人不是在校学生，那么这个位置上的数是一个随机的数，你应该在读入以后忽略它)。 接下来 行每行 个数...

同余方程 题意描述 求关于 的同余方程的最小正整数解，若无解，输出"-1" 思路 实际上就是求a的逆元 有这样几种方法 费马小定理 解不定方程 欧拉定理 , 那么 一定是a的逆元 但是费马小定理和欧拉定理求出来的不一定是最小的正整数解，所以我们考虑用"解不定方程" 解不定方程 可以转换为 , 求解就好了 但是求出来的只是其中一组解，我们要求出来最小的那一组才行 假设求出来的一组解是， 那通解就是 , 要求最小的, 考虑让,为了方便，让， 那么 代回去，, 发现这个东西不就是 % 吗 代码 #include <bits/stdc++.h> #define endl ...

exgcd 理解 函数的返回值仍然是gcd，整个函数的过程是先向下递归算gcd，回溯的时候把不定方程求解出来了 代码 #include <bits/stdc++.h> int exgcd(int a, int b, int &x, int &y) { if (b == 0) { return x = 1, y = 0, a; } int r = exgcd(b, a % b, x, y); std::tie(x, y) = std::make_tuple(y, x - (a / b) * y); re...

D. Maximize the Root 题意 题目链接 给一棵树，每个点初始权值给定，对每一棵树，根节点每增加1，所有叶子节点减少1，问1号（根节点）最大权值多少 思路 根节点加1，所有叶子节点减少1，那么操作次数就取决于子树中的最小值 那么我们就可以维护子树中的最小值，并且让这个最小值最大 用 表示这棵子树中最小值的最大值，也就是最终要存的答案 用 存子树中的最小值 那么有如下的分类讨论 : < 时 这时操作会使得结果更差，不要 >= 时， 这时最小值变成了mp(s), 可以让他变大，变为 代码 #include <bits/stdc++.h> ...

欧拉函数 欧拉函数求法 暴力求单项的欧拉函数 暴力求单项欧拉函数类似于暴力分解质因数 // 暴力求一项的欧拉函数类似于暴力分解质因数 int single_phi(int n) { int res = 1; for (int i = 2; i <= n / i; i++) { if (n % i == 0) { res *= (i - 1); n /= i; while(n % i == 0) { res...

H 入 题意概括 无向图， 任选一点开始走， 若走到一点时， 就把点的所有邻居都ban掉，问最多走几个点 思路 点数较少，可以暴力搜索 但是要注意的是，用邻接表存图的时候，回溯的时候可能会把不该重置的标记也重置了 什么意思呢？看这个图。 其实也可以不管这个，直接记录访问的次数，起点肯定多访问一次，也就不会在不该置为0的时候置0了 不记录次数的法一 #include <bits/stdc++.h> #define endl '\n' //#define int long long using lli = long long; using ull = unsigned long ...

A. LCT 题意概括 有一棵n个点的树， n - 2条边，每次给出 , , 保证前者为后者的父亲， 再给出一个询问, 保证是根不是儿子，问从开始的最长简单路径的长度。 思路 最长简单路径的长度， 实际上就是以为根的树的高度 我们就可以去维护每颗树的高度， 那应该怎么去维护呢？尤其是合并的时候 看这个 所以还要维护树的深度 那就要用到带权并查集了 代码 #include <bits/stdc++.h> int fa[1000010] = {0}; int dis[1000010] = {0}; // dis[i] i点的深度， 就是i距离fa[i]的距离 int ans[10...

线段树模板 题意概括 实现一棵线段树，有如下操作 1 l r 询问区间[l,r]内的元素和 2 l r 询问区间[l,r]内的元素的平方 和 3 l r x 将区间[l,r]内的每一个元素都乘上x 4 l r x 将区间[l,r]内的每一个元素都加上x 注意 我们可以用面向对象的方法来构建线段树 这道题有两个tag: * 和 +, 对于lazy标记我们可以单独用函数封装 init_lazy(), cal_lazy(), union_lazy(), pushdown() init_lazy() 把*的标记置为1， +的标记置为0 void init_lazy(int root) { ...

D.小红组比赛 题意 n场比赛，每场m道题，每一道题有一个难度分数，每一场选一道题出来组成的难度分数要最接近target,问最小差值是多少 思路 这个问题和背包问题中的装箱问题类似，尽可能把背包装满。数据范围也不大 我们可以用dp[i][x] 表示前i场比赛中获得x分可不可能，也就是开一个bool数组 代码 #include <bits/stdc++.h> // 动态规划 // dp[i][j] 前i场比赛有没有可能获得j分 // 类比装箱问题 int mar[105][25] = {0}; bool dp[105][5005] = {0}; int main() { ...

D. K-th nearest 题意概况 给定N个点a1,a2,a3....an,有Q次询问, 每次询问给定 bi 和 ki, 问所有a点中距离 bi 最近第 ki 个点和 bi 的距离是多少 思路 每次暴力去求显然复杂度会爆的。但是有一个发现：第K近的点，那距离也是第K小的 假如最后的答案是ans, 随便选一个点和bi是第m近，距离为dis,如果 m < k, 那么dis < ans, 如果m > k,那么 dis > ans 所以我们可以二分答案 代码如下 #include <bits/stdc++.h> #define endl '\n'; //...

欸嘿

我来也