堆 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 //heap template<typename T,bool comp(const T& a,const T& b)> struct HEAP { T ary[maxnode]; int f; HEAP(){f=0;} bool empty(){return f==0;} void push(const T& w) { ary[++f]=w; for(int k=f;k!=1&&comp(ary[k],ary[k/2]);k/=2) { Swap(ary[k],ary[k/2]); } } T top(){return ary[1];} T pop() { T tmp=ary[1]; ary[1]=ary[f--]; for(int k=1,son=k*2;son<=f;k=son,son=k*2) { if(son+1<=f&&comp(ary[son+1],ary[son])) ++son; if(comp(ary[son],ary[k])) Swap(ary[k],ary[son]); else break; } return tmp; } };

链表 普通双向链表 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 //list const int maxnode=10003; template<typename T> struct LIST { int pre[maxnode],nxt[maxnode]; T ary[maxnode]; int f; int endd; LIST() { f=0; endd=maxnode-1; nxt[0]=endd; } void clear() { f=0; endd=maxnode-1; nxt[0]=endd; } void insert(int k,const T& w)//insert in front of k { ary[++f]=w; int pree=pre[k],nxtt=k; pre[nxtt]=nxt[pree]=f; nxt[f]=nxtt; pre[f]=pree; } void del(int k) { int pree=pre[k],nxtt=nxt[k]; pre[nxtt]=pree; nxt[pree]=nxtt; } int begin() { return nxt[0]; } int end() { return endd; } }; 支持内存回收的双向链表 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

最短路算法 Floyd SPFA 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 #include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std; const int maxn=103; const int maxm=23; const int maxe=maxm*maxm*2; const int INF=2e9; int n,m,k,e,x,y,z,d,p,a,b; int tot,point[maxm],nxt[maxe],v[maxe],c[maxe]; int dis[maxm]; bool vis[maxm],flag[maxm]; queue <int> q; inline void addedge(int x,int y,int z) { ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=z; ++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; c[tot]=z; } inline int spfa() { memset(dis,0x7f,sizeof(dis)); dis[1]=0; memset(vis,0,sizeof(vis)); vis[1]=true; while (!q.empty()) q.pop(); q.push(1); while (!q.empty()) { int now=q.front(); q.pop(); vis[now]=false; for (int i=point[now]; i; i=nxt[i]) if (dis[v[i]]>dis[now]+c[i]&&!flag[v[i]]) { dis[v[i]]=dis[now]+c[i]; if (!vis[v[i]]) { vis[v[i]]=true; q.push(v[i]); } } } return dis[m];

NOIP2016提高组 解题报告 Day1 玩具谜题 【题目描述】略。 思路分析 ​ 首先我们容易想到的是把圈拉开成链，也就是将小人按照输入的顺序存储在数组中。 为了代码书写的方便，我们为小人定义一个结构体。 1 2 3 4 5 struct MAN { int face; char job[]; } 其中face是面向的方向，job[]是最后用来输出的职业。 那么我们如何实现不同方向的数呢

动态规划——悬线法 例题：USACO 6.1.2 rectbarn 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 /* ID:du331691 PROG:rectbarn LANG:C++ */ #include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; template<typename T> void read(T& w) { char r; for(r=getchar();r<48||r>57;r=getchar()); for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48; } template<typename T> T Min(const T& a,const T& b){return

最小表示法 例题：luogu1709（USACO5.5.2） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 /* ID:du331691 PROG:hidden LANG:C++ */ #include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cctype> using namespace std; const int maxn=100003*2; int n; char s[maxn]; void input() { scanf("%d",&n); for(int i=0;i<n;++i) { char r; do{r=getchar();} while(!islower(r)); s[i]=s[i+n]=r; } } int ans; void solve() { int i=0,j=1; while(j<=n) { bool ok=true; for(int k=0;k<=n-1&&ok;++k) { if(s[i+k]!=s[j+k]) { ok=false; if(s[i+k]>s[j+k]) i=i+k+1; else j=j+k+1; } } if(ok) {

扫描线 矩形周长并 例题：USACO5.5.1picture 分两次水平和竖直的扫描，以从左往右扫为例 首先对于所有竖直边按从左到右排序， 再将所有边的上坐标，下坐标离散化(tox[],toy[]) 用线段树动态维护当前的线段长度，Ans表示总答案 过程中有用到栈的思想（但并不用打出来） 也就是对于每一个有边的小区

网络流 最大流 这里参考了hzwer（%%%）的模板。 luogu3376 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 #include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> using namespace std; template<typename T>

NOIP2012提高组 解题报告 这些代码是两年前冲刺NOIP时写下的，现在AFO的我已经来不及写详细的解题报告了，所以这里仅仅给出代码和简解。 PS:真的想要我写解题报告可以留言。 Day1 维热纳尔密码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 /* vi */ #include<iostream> #include<cstring> #include<cstdio>

NOIP2014 提高组 解题报告 Day1 生活大爆炸版石头剪刀布 思路分析 这是一道模拟题，可以为每一个出拳设一个编号，然后预处理一个二维数组来表示某个出拳对另一个出拳的胜负情况，也可以直接记为得分。 本来看这个题目还觉得一时想不到什么较好的方法，但是看一下数据范围，maxn=200，所以直接暴力累加每一场的胜负得分即可。 实现代