二维偏序问题

知识讲解  二维偏序模板题。把 (a[i], b[i]) 看成二维平面上的一个红点，(q[i][0], q[i][1]) 看成二维平面上的一个蓝点。我们要对每个蓝点求出它的右上方横纵坐标之和最大的红点。  我们将所有点先按横坐标从大到小排序，然后依此枚举每个点。这样遇到一个蓝点 (x, y)，我们只
算法 刷题 2023年06月11日 700次浏览

进制转换

10进制转为b进制用秦九韶算法可以快速求解：此处 nnn 为 101010 进制n=ak−1∗bk−1+ak−2∗bk−2+ak−3∗bk−3+...+a1∗b1+a0∗b0n = a_{k - 1} * b^{k-1} + a_{k - 2} * b^{k - 2} + a_{k-3} * b^
算法 刷题 2023年04月07日 732次浏览

最短路之分层图

  分层图最短路是指在可以进行分层图的图上解决最短路问题。分层图：可以理解为有多个平行的图。  一般模型是：在一个正常的图上可以进行 k 次决策，对于每次决策，不影响图的结构，只影响目前的状态或代价。一般将决策前的状态和决策后的状态之间连接一条权值为决策代价的边，表示付出该代价后就可以转换状态了。见
算法 刷题 2023年04月05日 727次浏览

对拍模板

需要写三个文件：认为的正解暴力做法测试文件以01背包为例：正解#include <bits/stdc++.h>using namespace std;void create_data(){ofstream fout("in.txt"); int n = 10, m =
算法 2023年04月03日 485次浏览

和式变换技术

放一下引用的大佬博客地址 https://www.eriktse.com/algorithm/1101.html#toc-12
算法 刷题 2023年04月03日 737次浏览

数论分块

数论分块可以在 O(n)O(\sqrt{n})O(n​) 的时间复杂度内计算以下式子：∑1nf(⌊ni⌋){\large \sum_{1}^{n}f(\left \lfloor \frac{n}{i} \right \rfloor)}∑1n​f(⌊in​⌋)
算法 刷题 2023年04月02日 677次浏览

组合数学——康拓展开

今天在洛谷刷数位DP题目的时候碰到了一道数位很长的题目，直接用数位DP的方法难以解决，这里记录一下康拓展开的方式求解。康拓展开基本知识： =====> 传送门板子题链接： P5367 【模板】康托展开AC代码：#include <bits/stdc++.h>using namesp
算法 2023年03月31日 443次浏览

树上分组背包问题

  第一次碰到这种问题，记录一下，后续会慢慢补充题目链接 《P1273 有线电视网》AC代码：#include <bits/stdc++.h>using namespace std;const int N = 3010;int h[N], e[N], w[N], ne[N], idx;i
算法 刷题 2023年03月28日 678次浏览

基环树与拓扑排序技巧

基环树的基本知识： https://www.cnblogs.com/fusiwei/p/13815549.html《参加会议的最多员工数》https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/descrip
算法 刷题 2023年03月27日 503次浏览

最小链覆盖——Dilworth定理，与LIS问题

DilworthDilworthDilworth 定理，一言以蔽之，偏序集能划分成的最少的全序集个数等于最大反链的元素个数。https://blog.csdn.net/qq_43408238/article/details/104542949导弹拦截：https://www.luogu.com.cn
算法 2023年03月20日 473次浏览