题目： 输油管道问题(洛谷) 这道题是简单的中位数，经典的输油管道问题 此题是中位线到各个点的距离之和最短 #include<bits/stdc++.h> using namespace std; int const N=1e4+7; struct L{ int x,y; friend bool operator<(L a,L b){ return a.y < b.y ; } }a[N]; int n,ans; int main(){ cin >> n; for(int i=1;i<=n;++i){ cin &gt...

题目：P3366 【模板】最小生成树题目： P4779 【模板】单源最短路径（标准版） 最小生成树： 边权之和最小 每次加入（染）最短的边 优先队列放的是边长（即边权）（以该点为终点的边的边长） 最短路： 从原点到任意一点的距离最小 每次加入（染）离原点最短的边 优先队列放的是原点到该点的距离以下是最小生成树（prim)#include<bits/stdc++.h>using namespace std;#define ll long longint const N=5e3+7;int const M=2e5+7;int cnt,a...

E、矩阵 #include<bits/stdc++.h> using namespace std; #define ll long long ll f[1017][1017]; //f[i][j]表示第一行i个数，第二行j个数的方案数 int main(){ f[0][0]=1; for(int i=1;i<=1010;++i){ for(int j=0;j<=i;++j){ //因为第一行一定先放，所以 j<=i //未操作时的f[i][j]表示 第（第一行i个数，第二行j个数）时的数 if(i-...

#include<bits/stdc++.h> using namespace std; int n; map<string,string>mp; //第一个为关键字，第二个为键值 int main(){ cin >> n; for(int i=1;i<=n;++i){ string str1,str2; cin >> str1 >> str2; if(mp.find(str1)==mp.end()){ mp[str2]=str1; ...

参考博客 #include<bits/stdc++.h> using namespace std; int k,len; string str; int main(){ cin >> str; cin >> k; len=str.size(); while(k){ for(int i=0;i<len&&k;++i){ if(str[i]>str[i+1]){ for(int j=i;j<len;++j){ str[j...

参考博客 #include<bits/stdc++.h> using namespace std; int n,m; int const N=1e5+7; list<int>s; list<int>::iterator pos[N]; //用find会超时，所以用数组记录位置 int vis[N]; int main(){ cin >> n; s.push_back(1); pos[1]=s.begin(); for(int i=2;i<=n;++i){ int k,p; ...

//考验心境的时候到了 //和人比惨，痛苦减半 #include<bits/stdc++.h> using namespace std; namespace{ template<typename T> inline void read(T &s){ T f=1;s=0;char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) s=(s<<1)+...

dilworth定理：最长链长度=最小反链覆盖数 （默认反链尽可能长 ）最长反链长度=最小链覆盖数 （默认链尽可能长 ） 链指任意两个元素可比较反链任意两个元素不可比较 解释：离散数学中有一个知识点叫作二元关系，所谓二元关系通俗的理解就是某一个元素有两个键值，用以下的代码来简单的理解一下 struct node{ int a,b; }; bool operator<(node n1,node n2){ return n1.a < n2.a && n1.b < n2.b; }在以上例子中，只有一个对象的a,b均小于另一个对象，两者才可比。...

题目： P1006 传纸条 这题虽然跟方格取数很像，但是这题要求两个人的路径严格不相交减了两条枝，复杂度已经够优秀了 include<bits/stdc++.h> using namespace std;#define low(x) x&(-x)#define ll long longint m,n;int mp[55][55];int f[55][55][55][55];int main(){ cin >> n >> m; for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j...

题目： P3368 【模板】树状数组 2 #include<bits/stdc++.h> using namespace std; #define low(x) x&(-x) #define ll long long int const N=5e5+7; int n,m; ll a[N]; void add(int pos,int val){ for(;pos<=n;pos+=low(pos)){ a[pos]+=val; } } ll ask(int x){ ll z=0; for(;x;x-=low(x)){ ...

参考博客题目： P3374 【模板】树状数组 1 lowbit：二进制最低位1的大小，也是其能管辖到的数的范围 树状数组记得开long long 单次操作的时间复杂度是O(lgn) 只需开N的空间 比线段树的常数小 按值建树（ add(a[i],1) ）：ask可以求比当前数小（或大）的数的数量 按位置建树（ add(pos,1) ）：ask可以求当前点左（或右）边的点数 树状数组：求前面或后面有多少个数 求某区间特定性质点的数量 可用于单点修改，区间查询 区间修改，单点查询等等// #include<bits/stdc++.h> using na...

题目： 二叉苹果树 f[x][j]表示以x为根的树保留j条边（除x外j个结点）得到的最多苹果数f[x][j]=max(f[x][i],f[x][k]+f[u][j-k-1]+w;u是x的儿子 此题是树上背包（多叉树），树上背包可以看成二叉树的合并，将左边的森林（可以为空）看成左子树，将右边依次枚举的单边看成右子树其过程看成左子树不停向右拓展即合并右子树 #include<bits/stdc++.h> using namespace std; int const INF=0x3f3f3f3f; int const N=1e2+7; int n,cnt; int head[N]; s...

题目： CellPhoneNetwork 最小支配集：一个点可以覆盖其周围所有的点包括自己 f[i][0]被其儿子覆盖 f[i][1]被自己覆盖 f[i][2]被其父亲覆盖 设j为i的儿子 f[i][0]= min(f[j][0],f[j][1])+tmp; //tmp表示维护至少有一个儿子覆盖的最小差值 f[i][1]= min(f[j][0],f[j][1],f[j][2])+1; f[i][2]= min(f[j][0],f[j][1]); 注意：根没有父亲，所以不能被父亲覆盖 #include<bits/stdc++.h> using namespace std; int...

最小点覆盖：一条边至少要选一个点 这题测评姬的编译器只能选c++,不能选c++11和c++14,很古老，不能用万能头，不能用string 注意这题有0号结点，所以（前向星和平常不一样的地方（以后就用下面这种，防止0号结点））： 1、for(int i=head[x];i!=-1;i=edge[i].next) 2、memset(edge,-1,sizeof(edge)); //3、memset(head,-1,sizeof(head)); //这个不需要转移方程：f[x][0]= f[i][1];f[x][1...