Technocup 2020 - Elimination Round 3 A. Math Problem 题意：有n个区间，判断被所有区间包括的最小区间的 l-r 的值; 题解：取 “左边界中的最右点，右边界中最左点” 做差 int mixn=0; int maxn=inf; mixn=max(mixn,l); maxn=min(maxn,r); cout<<max(0,mixn-maxn)<<endl;

普通GCD int gcd(int a,int b){ return (b>0)?gcd(b,a%b):a; }

作用 给出一些形如x-y<=b不等式的约束，询问是否满足有解。 参考博客 差分约束系统详解 Note 将约束为标题转换成图论里的最短路径问题 求未知数的最大值，那么按小于等于建图后求最短路 如果求未知数的最小值，那么按小于等于建图后求最长路即可。 代码实现 存储结构 const int maxn=10010; const int inf=0x3f3f3f3f; int n,ml,md; int al[maxn],bl[maxn],dl[maxn];//两点与权值 int ad[maxn],bd[maxn],dd[maxn]; int d[maxn]; 所需函数 Be...

作用 求二分图最大权完美匹配 参考博客 KM算法详解+模板 代码实现 存储结构 const int maxn=310; const int inf=0x3f3f3f3f; int mmp[maxn][maxn]; // 记录每个妹子和每个男生的好感度 bool book_gril[maxn];//标记被匹配过的人 bool book_boy[maxn]; int val_gril[maxn];//权值 int val_boy[maxn]; int match[maxn];//记录匹配到的人 int slack[maxn];//尚需的期望值 所需函数 dfs递归匹配 bool...

作用 寻找二分图最大匹配值 参考博客 趣写算法系列之–匈牙利算法 代码实现 存储结构 const int maxn=1105; bool mp[maxn][maxn];//邻接矩阵存图 bool vis[maxn]; //标记数组 int mark[maxn];//匹配的两个点 所需函数 dfs递归找增广路 bool dfs(int x){ for(int i=0;i<n;i++){ if(mp[x][i]&&!vis[i]){//一次递归中数据仅可被更改一次 vis[i]=true; if(mark[i]==-1||dfs(mar...

二分图定义 顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。 抽象理解：将人群分为男生和女生两部分，一对一的交往 二分图匹配 在二分图的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。 最大匹配：（匈牙利算法） 选择这样的边数最大的子集称为图的最大匹配问题,最大匹配的边数称为最大匹配数。 完全匹配 如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。 最优匹配（KM算法） 最优匹配又称为带权最大匹配，是指在带有权值边的二分图中，求...

1.hash字符串 例题：POJ-1200:http://poj.org/problem?id=1200题意：寻找存在nc个字符的字符串中给定字符串中不同子串数量注：若无特殊规定，则nc应取131或13331以减少冲突算法思想：将字符串拆分成含有n个字符的子串并将其转化为nc进制数。 字符串相同hash值一定相同，反之不成立（所以要减少冲突）代码： #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=1e6+10; cha...