题目： 小G有一棵大树  树可以以任意一个结点作为根 memset可以为结构体赋初值 f[i]表示将i点删掉后最大连通块的大小 tot[i]表示以i为根的子树大小 f[i]=max(n-tot[i],max(tot[k]) k是i的儿子include<bits/stdc++.h> using namespace std;int const N=1e3+7;int n,cnt;int head[N];struct node{ int a,next,len;}edge[N<<1];void add(int x,int y,int len){ edge[++cnt].a =y...

1、坐标中两个点的非直线距离为 abs(x_1-x_2)+abs(y_1-y_2) 例题：P1708 天然气井 2、一组点到某条平行x轴直线距离之和最小，那么此条直线的纵坐标为各点的中位数 例题: P1862 输油管道问题 例题题解 3、在平面格子中，可以一行或一列地染色，则其重复染的格子为len1*len2 例题

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)+(s<<3)+(ch^48); s*=f; }}#define ll long l...

01背包：f[j]表示装满j个空间获得的最大价值装箱问题：f[j]表示是否可以装满j个空间 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)+(...

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)+(s<<3)+(ch^48); s=f; }}#define ll long longint n;ll...

次始边界：初始状态的下一个状态 以此题为例： 区间dp： 初始状态：拿完m-1个元素时，剩下最后一个元素，可以是任意一个 次始状态：拿完m-2个元素时，剩下两个元素，可以是任意两个（题目限制只能是连续的两个） 若是线性dp： 初始状态：拿完m-1个元素时，剩下最后一个元素只能是第一个,即a[1] 次始状态：拿完m-2个元素时，次始状态为a[2]斜体部分是废话，不重要，不要看，不舍得删看其初始边界线性dp和区间dp的区别：  线性dp：只能在队尾加元素，状态只能由上一层线性递推* 区间dp：能在队首或队尾加元素，状态是由小区间推到大区间* 此题为例：* 区间dp：拿完m-1个元素时，剩下最后一个...

#include<bits stdc++.h> using namespace std; namespace{ template 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)+(s<<3)+(ch^48); s*=f; } } int n,q; struct L{ int i,j; friend bool oper...

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)+(s<<3)+(ch^48); s*=f; }}int n,m;int a[1005][1005];&...

void floyd(){ for(int k=1;k<=n;++k){ for(int i=1;i<=n;++i){ if(f[i][k]==INF) continue; //剪枝 for(int j=1;j<=n;++j){ if(i!=j&&i!=k&&j!=k){ if(f[i][k]+f[k][j] <= f[i][j]) //松弛 f[i][j]=f[i][k]+f[k][j]; } } } } }

用于带负权边的图不能用于有负权环的图一般题（单源点最短路的题）用dijkstra*时间复杂度 O(KM) //k表示每个点平均入队次数,M表示边数 //出题人卡它很容易，可以把它卡成O(N^2) //不能用于棋盘格子，会被卡爆 *  int dis[N],vis[N]; void spfa(int s){ memeset(dis,0x3f,sizeof(dis)); queue<int>q; q.push(s); dis[s]=0; vis[s]=1;//vis数组表示s点是否在队列q中，而不是表示是否访问过 while(!q.empty()){ int u=q.front();q...

题目：日志统计(AcWing) 解析：本题的尺子长度为时间#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)+(s<<3)+(ch^48); s*=f; ...

题目：旅行（牛客） include<bits/stdc++.h> using namespace std;int t; int const N=1e3+7;int const M=1e3+7;struct L{ int dis,a; friend bool operator<(L a,L b){ //这里的a,b表示在队列里的顺序，即a在b前 return a.dis > b.dis ; //因为堆是优先级小的在前，大的在后，且堆是优先级大的出队，即队尾（top）出队（即小的出列），所以重载时a(前面的)要大于b(后面的)//堆的补充：堆访问到的元素也是优先级大的即to...

//01背包 + 并查集#include<bits/stdc++.h>using namespace std;int const N=1e4+7;//int const M=1e5+7;int t;//int a[i];int f[N];int v[N],w[N];int dp[505];int find(int x){ return f[x]==x ? x : f[x]=find(f[x]);}int main(){ cin >> t; while(t--){ int n,m,c; cin >> n >> m >> c; for(i...

//题目分析：并查集，节点祖先为连续的没有使用的节点，每次使用后的下一个点合并//每个点的祖先是自己，如果自己被使用了，则祖先指向下一个点(即+1)(即合并)#include<bits/stdc++.h>using namespace std;#define _for(n,m,i) for (register int i = (n); i < (m); ++i)#define _rep(n,m,i) for (register int i = (n); i <= (m); ++i)const int N = 2e6+5;int a[N], f[N];int Find(i...