1. 进程线程区别 2. 协程 3. 进程通信 4. 僵尸进程 5. 设计一个ID生成器？分布式？ 6. 30分钟LFU算法 🙃

F Fake Maxpooling 题意 规定矩阵对应的值为其下标的 ，求所有 子矩阵最大值之和。 Solution 线性求 + 二维单调队列 线性求 ： for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { if (!g[i][j]) { for (int h = 1; h * i <= n && h * j <= m; h++) { g[h * i][h * j] = h; a[h * i][h * ...

题意 有n种扑克牌，每种有ci个。还有m张王牌。可以代替其中任一张。最多可以造出几个套牌（每副牌只能用一次）。 solution 典型的二分答案，每副牌只能使用一次，所以限制使用的王牌数为 ，每种牌不够 张需要王牌补，计算使用的王牌数为判断是否满足条件即可。 Code #include <bits/stdc++.h> using namespace std; typedef long long ll; ll n, m, a[105]; bool check(ll x) { ll cnt = min(m, x); for (ll i = 1; i <= n; i+...

题意：给定一棵树，从s点开始，每次选择一个没有染色过的点居住，居住后所有相邻的点都会被染色，问最多住几个点？ solution：树形dp，这题和“没有上司的舞会”几乎完全一样， 表示i点住/不住的最大值，，只不过起点必选，所以答案只可能是 ， Code： #include <bits/stdc++.h> using namespace std; const int N = 1e6 + 5; int n, s, idx, h[N], dp[N][2]; struct Node { int to, next; } g[N]; void add(int x, int y) { g...

题意 支队伍一共参加了三场比赛。一支队伍 认为自己比另一支队伍 强当且仅当 在至少一场比赛中比 的排名高。求有多少组 ，使得 自己觉得比 强， 自己也觉得比 强，, 算一组。 solution 若 和 都互相认为更强，那么必定存在两场，一场 强于 ，一场 强于 ，那么就是对于任意两场求逆序数，最后的答案需要除以2，因为如果两队互认为更强，必定存在 有两场更强，或者 有两场更强，那么计算逆序数时就多计算了一次。 Code #include <bits/stdc++.h> using namespace std; typedef long long ll;...

题意 一共有 只牛在花坛旁边，第 头牛每分钟破坏 朵花，把第i头牛带回牛棚需要 这么多时间，每次只能带回一头牛，请问怎样能使得被破坏的花最少。 solution 以小化大，先考虑两头牛，先领 ，损失为：，先领 ，损失为 ，故得到排序条件 ，最后模拟得出答案。 Code #include <bits/stdc++.h> #define x first #define y second #define PI pair<int, int> #define ll long long using namespace std; ll n, sum, res; pair&l...

题意 种面额货币，数量无限，问最多保留几种，使得原来可以组成的仍然可以组成。（） solution 由于大的只会被小的组成，所以先排序，对于存在性问题就显然是完全背包了，dp[i] 表示是否能表示出 价值，得到状态转移方程：，对于已经可以表示出来对 ，已经可以由小的组成，因此不需要在枚举。 Code #include <bits/stdc++.h> using namespace std; int t, n, res, a[105], dp[300005]; int main() { cin >> t; while (t--) { cin >&...

题意 栋建筑，第 栋建筑需要 时间修，截止到 时间，问最多可以修多少建筑。 solution 我们可以类比成写作业，先截止的我们会先做，这是大体的贪心策略。但他并不是最优的，因为可能那一科会花你非常多的时间，够你做更多的科目，得不偿失。因此我们用优先队列维护做过的作业中花费时间最大的那份，当目前要做的作业时间不够的时候，与这个最大值比较看是否花的时间更少，可行的话就把这个塞进去，那个丢出来，这样做了同样多的作业却花了更少的时间，同时维护答案。 Code #include <bits/stdc++.h> #define x first #define y second usi...

题意 给定一个 排列，求长度为奇数子串以 为中位数的子串个数。 solution 由于求的是中位数，所以我们只需要关心这个数和 的大小关系就好了，大于 看作 1，小于 看作 -1，等于 看作 0，问题转化为求包含 0 且和为 0 的子串有多少个。 从 的位置开始遍历，map 统计右边累加的和，然后从左边累加的和中查找对应的相反数个数，累加即可。同时，如果遍历过程中任何一边已经存在和为 0 的情况，也为可行解。 Code #include <bits/stdc++.h> using namespace std; map<int, int> mp; int n...

题意 无向图 个点，每次必须跳两个，至少需要加多少条边可以遍历所有点。 solution 首先，如果图不联通，那么需要加联通分量 - 1 条边使图联通，然后发现一点，只要这个图存在奇数环，就一定能全部走完，不存在的话，随便加一条边生成奇数环即可。 Code #include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5; int n, m, odd, x, y, res, vis[N], color[N]; vector<int> g[N]; void dfs(int u) { for (a...

title: 每日一题：简单瞎搞题 （STL）copyright: truedate: 2020-05-26 17:44:37tags: STLcategory: 每日一题mathjax: true 题意 一共有 个数，第 个数是 可以取 中任意的一个值。设 ，求 种类数。（0 ~ n,l,r ~ 100） Solution 表示前 个数能不能组成 ，可以得到转移方程：，最后统计 层组成的 的数量即可。因为 dp 的值只有 0 和 1 ，因此使用 bitset 优化，把第二维看成二进制位，这样就可以用位移的形式来表示加法运算，得到转移方程：，复杂度 。 Code #incl...

题意 一共12道题，你有 的概率做对第 题，有 的概率抄到左边的，有 的概率抄到右边的，问做对 题的概率是多少。 solution 做对的概率不太好求，可以反过来求做错的概率，即 ，然后 表示前 道题做对 道的概率，设 ，得到状态转移方程： 。 Code #include <bits/stdc++.h> using namespace std; double a[15], b[15], c[15], dp[15][15]; int main() { for (int i = 1; i <= 12; i++) cin >> a[i]; for...

题意 有一颗二叉树，树的每一个节点都有一个值，设他的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。 任一棵子树subtree（也包含tree本身）的加分计算方法如下： subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。 要求输出：（1）tree的最高加分（2）tree的前序遍历 solution 符合条件的二叉树是加分最高的二叉树，它的总分依题意得 总分 = 左子树分数 * 右子...

题意 给定 和 两点的距离和 点的货物数量， 次询问将 所有物品搬到 点的总费用（区间内每个物品各自离 点距离和）。（） soltuion 前缀和维护： 表示每个储物点离原点0的距离， 表示前 个储物点共有多少货物， 表示前 个储物点的所有物品到原点0的和。 ，即 所有物品到原点的距离 - 到 点的距离。 ，即 所有物品从 点到原点的距离 - 从原位置到原点的距离。 处于中间的情况，就是拆解成 两种情况，然后分别带入上面情况即可。 Code #include <bits/stdc++.h> using namespace std; typedef lon...