喜闻乐见的代码背诵环节 – 老虫儿的笔记本

高精度struct BigInt {
const static int mod = 10000;

const static int DLEN = 4;

int a[60000],len;

BigInt() {

memset(a,0,sizeof(a));

len = 1;

}

BigInt(int v) {

memset(a,0,sizeof(a));

len = 0;

do {

a[len++] = v%mod;

v /= mod;

} while(v);

}

BigInt(const char s[]) {

memset(a,0,sizeof(a));

int L = strlen(s);

len = L/DLEN;

if(L%DLEN)len++;

int index = 0;

for(int i = L-1; i >= 0; i -= DLEN) {

int t = 0;

int k = i – DLEN + 1;

if(k < 0)k = 0;

for(int j = k; j <= i; j++)

t = t*10 + s[j] – ‘0’;

a[index++] = t;

}

}

BigInt operator +(const BigInt &b)const {

BigInt res;

res.len = max(len,b.len);

for(int i = 0; i <= res.len; i++)

res.a[i] = 0;

for(int i = 0; i < res.len; i++) {

res.a[i] += ((i < len)?a[i]:0)+((i < b.len)?b.a[i]:0);

res.a[i+1] += res.a[i]/mod;

res.a[i] %= mod;

}

if(res.a[res.len] > 0)res.len++;

return res;

}

BigInt operator *(const BigInt &b)const {

BigInt res;

for(int i = 0; i < len; i++) {

int up = 0;

for(int j = 0; j < b.len; j++) {

int temp = a[i]*b.a[j] + res.a[i+j] + up;

res.a[i+j] = temp%mod;

up = temp/mod;

}

if(up != 0)

res.a[i + b.len] = up;

}

res.len = len + b.len;

while(res.a[res.len – 1] == 0 &&res.len > 1)res.len–;

return res;

}

void output() {

printf(“%d”,a[len-1]);

for(int i = len-2; i >=0 ; i–)

printf(“%04d”,a[i]);

printf(“\n”);

}

};
字符串的处理函数
- 字符串连接函数 strcat() ：
```
strcat(arrayName1, arrayName2);//将2拼1
```
- 字符串复制函数 strcpy():
```
strcpy(arrayName1, arrayName2);
```
- 字符串比较函数 strcmp():
```
strcmp(arrayName1, arrayName2);
```
  - 返回值：若 arrayName1 和 arrayName2 相同，则返回0；若 arrayName1 大于 arrayName2，则返回大于 0 的值；若 arrayName1 小于 arrayName2，则返回小于0 的值。
并查集
- map<int,int>pre,rank;//这里应该用离散化替代的int find(int x){return pre[x]==x?x:pre[x]=find(pre[x]);}
  void join(int x,int y){
  
  int a=find(x);
  
  int b=find(y);
  
  if(rank[a]<rank[b])pre[a]=b;
  
  else if(rank[a]>rank[b])pre[b]=a;
  
  else{
  
  pre[a]=b;
  
  rank[b]++;
  
  }
  
  }
  
  void init(){
  
  rep(i,0,maxn-10)pre[i]=i,rank[i]=1;
  
  }

最小生成树

const int INF=0x3f3f3f3f;
const int MAXN=2018;
bool vis[MAXN];
int lowc[MAXN];
int cost[MAXN][MAXN];
int Prim(int n) { //点是0~n-1
	int ans=0;
	memset(vis,false,sizeof(vis));
	vis[0]=true;
	for(int i=1; ilowc[j]) {
		minc=lowc[j];
		p=j;
	}
	if(minc==INF)return -1;//原图不连通
	ans+=minc;
	vis[p]=true;
	for(int j=0; jcost[p][j])
		lowc[j]=cost[p][j];
}
return ans;
}

k树

/*  * Kruskal算法求MST  */ 
const int MAXN=110;//最大点数 
const int MAXM=10000;//最大边数 
int F[MAXN];//并查集使用 
struct Edge {  int u,v,w; }edge[MAXM];//存储边的信息，包括起点/终点/权值 
int tol;//边数，加边前赋值为0 
void addedge(int u,int v,int w) { 
    edge[tol].u=u;  
    edge[tol].v=v;  
    edge[tol++].w=w; 
} 
bool cmp(Edge a,Edge b) {//排序函数，讲边按照权值从小到大排序  
    return a.w<b.w; 
} 
int find(int x) {
    if(F[x]==-1)return x;  
    else return F[x]=find(F[x]); 
} 
int Kruskal(int n)//传入点数，返回最小生成树的权值，如果不连通返回-1 
{  
    memset(F,-1,sizeof(F));  
    sort(edge,edge+tol,cmp);  
    int cnt=0;//计算加入的边数  
    int ans=0;  
    for(int i=0;i<tol;i++)  {
        int u=edge[i].u;   
        int v=edge[i].v;   
        int w=edge[i].w;   
        int t1=find(u);   
        int t2=find(v);   
        if(t1!=t2)   {    
            ans+=w;    
            F[t1]=t2;    
            cnt++;   
        }   
        if(cnt==n-1)break;  
    }  
    if(cnt<n-1)return -1;//不连通  
    else return ans; 
}

最短路
- 邻接表
  #define MAXM 500010
  
  #define MAXN 10010
  
  #define ANS_MAX 2147483647
  
  struct EDGE {
  
  int next;
  
  int to;
  
  int w;
  
  };
  
  EDGE edge[MAXM];
  
  int n, m;
  
  int head[MAXN];
  
  inline int Read() {
  
  char c;
  
  int ans = 0;
  
  bool Sign = false;
  
  while(!isdigit(c=getchar()) && c != ‘-‘);
  
  if(c == ‘-‘) {
  
  Sign = true;
  
  c = getchar();
  
  }
  
  do {
  
  ans = (ans<<3) + (ans<<1) + (c ^ ‘0’);
  
  } while(isdigit(c=getchar()));
  
  return Sign ? -ans : ans;
  
  }
  
  void Add(int u, int v, int w) {
  
  edge[++cnt].next = head[u];//指向上一个输入的x的边
  
  edge[cnt].to = v;
  
  edge[cnt].w = w;//权值
  
  head[u] = cnt;//记录
  
  }
  
  void read() {
  
  int x, y, w;
  
  n = Read();
  
  m = Read();
  
  for(int i=1; i<=m; i++) {
  
  x = Read();
  
  y = Read();
  
  w = Read();
  
  Add(x, y, w);
  
  }
  
  }
  
  for(int i=head[k]; i!=0; i=edge[i].next) {
  
  int j = edge[i].to;
  
  }
- //dij最短路const int MAXN=1010;
  const int maxn=1e5+10;
  
  struct edge {
  
  int v;
  
  int w;
  
  edge(int _v=0,int _w=0):v(_v),w(_w) {}
  
  } e[2*maxn],E[2*maxn];
  
  int tot=0,Tot=0;
  
  int head[MAXN],Head[MAXN];
  
  int nxt[2*maxn],Nxt[2*maxn];
  
  void addedge(int u,int v,int w) {
  
  e[++tot].v=v;
  
  e[tot].w=w;
  
  nxt[tot]=head[u];
  
  head[u]=tot;
  
  E[++Tot].v=u;
  
  E[Tot].w=w;
  
  Nxt[Tot]=Head[v];
  
  Head[v]=Tot;
  
  }
  
  int f[MAXN];
  
  int vis[MAXN];
  
  int n,m,u,v,w,st,ed,k;
  
  struct node{
  
  int x;
  
  int dist;
  
  node(int _x,int _dist):x(_x),dist(_dist){}
  
  bool operator < (const node &a)const{
  
  return dist>a.dist;
  
  }
  
  };
  
  priority_queue<node>que;
  
  void dijkstra() {
  
  rep(i,1,n)f[i]=INF,vis[i]=0;
  
  while(!que.empty())que.pop();
  
  f[ed]=0;
  
  que.push(node(ed,0));
  
  node tmp(0,0);
  
  while(!que.empty()){
  
  tmp=que.top();
  
  que.pop();
  
  int u=tmp.x;
  
  if(vis[u])continue;
  
  vis[u]=1;
  
  for(int i=Head[u];i;i=Nxt[i]){
  
  int v=E[i].v,w=E[i].w;
  
  if(!vis[v]&&f[v]>f[u]+w){
  
  f[v]=f[u]+w;
  
  que.push(node(v,f[v]));
  
  }
  
  }
  
  }
  
  }
- SPFA
- #include<algorithm>
  
  #include <iostream>
  
  #include <cstdlib>
  
  #include <cstring>
  
  #include <cassert>
  
  #include   <cstdio>
  
  #include   <vector>
  
  #include   <string>
  
  #include    <cmath>
  
  #include    <queue>
  
  #include    <stack>
  
  #include      <set>
  
  #include
  
  <map>
  
  using namespace std;
  
  #define P(init,b,c) make_pair(init,make_pair(b,c))
  
  #define rep(i,init,n) for (int i=init;i<=n;i++) #define per(i,init,n) for (int i=n;i>=init;i--)
  
  #define pb push_back
  
  #define mp make_pair
  
  #define all(x) (x).begin(),(x).end()
  
  #define fi first
  
  #define se second
  
  #define SZ(x) ((int)(x).size())
  
  typedef pair<int,pair<int,int> >pii;
  
  typedef long long ll;
  
  const ll mod = 1000000007;
  
  ll gcd(ll init, ll b) { return b ? gcd(b, init%b) : init; }
  
  const int MAXN=1e5+5;
  
  const int INF=0x3f3f3f3f;
  
  struct Edge
  
  {
  
  int v;
  
  int cost;
  
  Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
  
  };
  
  vector<Edge>E[MAXN];
  
  void addedge(int u,int v,int w)
  
  {
  
  E[u].push_back(Edge(v,w));
  
  }
  
  bool vis[MAXN];//在队列标志
  
  int cnt[MAXN];//每个点的入队列次数
  
  int dist[MAXN];
  
  void SPFA(int start,int n)
  
  {
  
      memset(vis,false,sizeof(vis));
  
      for(int i=1;i<=n;i++) dist[i]=INF;
  
      vis[start]=true;
  
      dist[start]=0;
  
      queue<int>que;
  
      while(!que.empty()) que.pop();
  
      que.push(start);
  
      memset(cnt,0,sizeof(cnt));
  
      cnt[start]=1;
  
      while(!que.empty())
  
      {
  
          int u=que.front();
  
          que.pop();
  
          vis[u]=false;
  
          for(int i=0;i<E[u].size();i++) { int v=E[u][i].v; if(dist[v]>dist[u]+E[u][i].cost)
  
              {
  
                  dist[v]=dist[u]+E[u][i].cost;
  
                  if(!vis[v]&&++cnt[v]<=n)
  
                  {
  
                      vis[v]=true;
  
                      que.push(v);
  
                  }
  
              }
  
          }
  
      }
  
  }
- FLOYDfor(int k = 1; k <= n; k++)
  for(int i = 1; i <= n; i++)
  
  for(int j = 1; j <= n; j++)
  
  if(d[i][j] < INF&&d[k][j] < INF)
  
  d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
- dfs求割点
- #include<algorithm>
  
  #include <iostream>
  
  #include   <fstream>
  
  #include <cstdlib>
  
  #include <cstring>
  
  #include <cassert>
  
  #include   <cstdio>
  
  #include   <vector>
  
  #include   <string>
  
  #include    <cmath>
  
  #include    <queue>
  
  #include    <stack>
  
  #include      <set>
  
  #include      <map>
  
  using namespace std;
  
  #define P(a,b,c) make_pair(a,make_pair(b,c))
  
  #define rep(i,a,n) for (int i=a;i<=n;i++)
  
  #define per(i,a,n) for (int i=n;i>=a;i--)
  
  #define CLR(vis) memset(vis,0,sizeof(vis))
  
  #define MST(vis,pos) memset(vis,pos,sizeof(vis))
  
  #define pb push_back
  
  #define mp make_pair
  
  #define all(x) (x).begin(),(x).end()
  
  #define fi first
  
  #define se second
  
  #define SZ(x) ((int)(x).size())
  
  typedef pair<int,pair<int,int> >pii;
  
  typedef long long ll;
  
  typedef unsigned long long ull;
  
  const ll mod = 1000000007;
  
  const int INF = 0x3f3f3f3f;
  
  ll gcd(ll a, ll b) {
  
      return b ? gcd(b, a%b) : a;
  
  }
  
  template<class T>inline void gmax(T &A, T B) {
  
      (A<B)&&(A=B);//if(B>A)A=B;
  
  }
  
  template<class T>inline void gmin(T &A, T B) {
  
      (A>B)&&(A=B);//if(B<A)A=B;
  
  }
  
  template <class T>
  
  inline bool scan(T &ret) {
  
      char c;
  
      int sgn;
  
      if(c=getchar(),c==EOF) return 0; //EOF
  
      while(c!='-'&&(c<'0'||c>'9')) c=getchar();
  
      sgn=(c=='-')?-1:1;
  
      ret=(c=='-')?0:(c-'0');
  
      while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
  
      ret*=sgn;
  
      return 1;
  
  }
  
  inline void outt(int x) {
  
      if(x>9) outt(x/10);
  
      putchar(x%10+'0');
  
  }
  
  const int maxn=1e6+10;
  
  struct Edge{
  
      int v;
  
      int w;
  
  }edge[maxn*2];
  
  int nxt[maxn];
  
  int head[maxn];
  
  int tot=0;
  
  void addedge(int u,int v,int w){
  
      edge[++tot].v=v;
  
      edge[tot].w=w;
  
      nxt[tot]=head[u];
  
      head[u]=tot;
  
  }
  
  int cnt[maxn];
  
  int road[maxn];
  
  bool vis[maxn];
  
  int st,ed;
  
  void dfs(int u,int step){
  
      road[step]=u;
  
      if(u==ed){
  
          rep(i,1,step){
  
              cnt[road[i]]++;
  
          }
  
          return ;
  
      }
  
      vis[u]=1;
  
      for(int i=head[u];i;i=nxt[i]){
  
          if(!vis[edge[i].v]){
  
              dfs(edge[i].v,step+1);
  
          }
  
      }
  
      vis[u]=0;
  
  }
  
  int main(){
  
      int n,m;
  
      cin>>n>>m;
  
      while(m--){
  
          int u,v;
  
          cin>>u>>v;
  
          addedge(u,v,1);
  
          addedge(v,u,1);
  
      }
  
      cin>>st>>ed;
  
      dfs(st,1);
  
      if(cnt[ed]==0){
  
          puts("-1");
  
          return 0;
  
      }
  
      tot=0;
  
      rep(i,1,n){
  
          if(cnt[i]==cnt[ed]&&i!=ed&&i!=st){
  
              tot++;
  
          }
  
      }
  
      cout<<tot<<endl;
  
      return 0;
  
  }
- 拓扑排序
  - 无向有环图中找环(将deg为0的判定改为deg=1)
  - #include<cstdio>
    
    #include<queue>
    
    #include<cstring>
    
    using namespace std;
    
    const int N=2e6+10;
    
    queue<int>q;
    
    int head[N],tot,n,m,deg[N],tps[N],tp;
    
    struct Edge {
    
        int v,nx;
    
    } e[N];
    
    inline void addedge(int u,int v) {
    
        e[tot].v=v;
    
        e[tot].nx=head[u];
    
        head[u]=tot++;
    
        deg[v]++;
    
    }
    
    void toposort() {
    
        for(int i=1; i<=n; i++)if(deg[i]==1)q.push(i);
    
        while(!q.empty()) {
    
            int u=q.front();
    
            q.pop();
    
            tps[++tp]=u;
    
            for(int i=head[u]; ~i; i=e[i].nx) {
    
                int v=e[i].v;
    
                if(--deg[v]==1)q.push(v);
    
            }
    
        }
    
    }
    
    int main() {
    
        memset(head,-1,sizeof(head));
    
        scanf("%d",&n);
    
        int u,v;
    
        for(int i=1; i<=n; i++)scanf("%d%d",&u,&v),addedge(u,v),addedge(v,u);
    
        toposort();
    
        for(int i=1; i<=n; i++) {
    
            if(deg[i]>1)printf("%d ", i);
    
        }
    
        return 0;
    
    }
- 树的直径：离根节点最远的点为端点的最长路径(两次dfs)
- #include <bits/stdc++.h>
  
  using namespace std;
  
  #define INF 10000000000
  
  vector <int > G[1000005];
  
  vector<int > E[1000005];
  
  bool vis[1000005];
  
  int d[1000005];
  
  void init() {
  
      memset(vis, 0, sizeof(vis));
  
  }
  
  void dfs(int u) {
  
      vis[u] = 1;
  
      int size = G[u].size();     //与顶点u相连的点数
  
  
  
      for (int i = 0; i<size; i++) {           //对与顶点u相连的点数进行扫描
  
          int v = G[u][i];
  
          if (!vis[v]) {
  
              d[v] = d[u] + E[u][i];
  
              dfs(v);
  
          }
  
      }
  
  }
  
  int main() {
  
      int n;
  
      cin >> n;
  
      int u, v, w;
  
      for (int i = 0; i<n-1; i++) {        //建立树过程
  
          scanf("%d%d%d",&u,&v,&w);
  
          G[u-1].push_back(v-1);              //顶点两边都要记录
  
          E[u-1].push_back(w);
  
          G[v-1].push_back(u-1);
  
          E[v-1].push_back(w);
  
      }
  
  
  
      init();
  
      for (int i = 0; i<n; i++)    d[i] = (i == 0?0:INF);
  
      dfs(0);
  
      int start = 0;
  
      int max = -1;
  
      for (int i = 0; i<n; i++) {
  
          if (d[i] > max && d[i] != INF) {
  
              max = d[i];
  
              start = i;
  
          }
  
      }
  
  
  
      init();
  
      for (int i = 0; i<n; i++)    d[i] = (i == start?0:INF);
  
      dfs(start);
  
      int ans = -1;
  
      for (int i = 0; i<n; i++) {
  
          if (d[i] > ans && d[i] != INF) {
  
              ans = d[i];
  
          }
  
      }
  
  
  
      //ans = 10*ans + ans*(ans+1)/2;
  
      cout << ans << endl;                    //ans 即为直径
  
      return 0;
  
  }
- DAG上的单源最短路（可解负权）+超级源点+超级汇点
- #include<stdio.h>
  
  #include<string.h>
  
  #include<iostream>
  
  #include<queue>
  
  #define inf 0x3f3f3f3f
  
  using namespace std;
  
  typedef long long LL;
  
  int n,m;
  
  int tol,cnt,head[100010]; //链式前向星
  
  //w记录点权，chu记录点的出度，ru记录点的入度，que记录拓扑序列
  
  int w[100010],chu[100010],ru[100010],que[100010];
  
  //dis记录点到源点的最大距离
  
  LL dis[100010];
  
  queue<int> Q;
  
  struct node
  
  { //链式前向星
  
      int w,to,next; //分别为边权、终点和以u为起点的下一条边在的位置
  
  } edge[2000010];
  
  void init()
  
  { //初始化函数
  
      tol=0;
  
      memset(head,-1,sizeof(head));
  
      memset(chu,0,sizeof(chu));
  
      memset(ru,0,sizeof(ru));
  
  }
  
  void add(int u,int v,int w)
  
  { //加边函数
  
      edge[tol].w=w;
  
      edge[tol].to=v;
  
      edge[tol].next=head[u];
  
      head[u]=tol++;
  
  }
  
  void tuopu()
  
  { //获得拓扑排序
  
      int i,j,top;
  
      cnt=0;
  
      dis[0]=0;
  
      Q.push(0); //0点入队
  
      for(i=1;i<=n+1;i++) dis[i]=-inf; //初始化最长距离为最小值
  
      while(!Q.empty())
  
      { //只有减边的点才有可能入度为0
  
          top=Q.front();
  
          Q.pop();
  
          que[cnt++]=top; //保存拓扑序列
  
          ru[top]--;      //当前节点入度-1
  
          for(j=head[top];j!=-1;j=edge[j].next)
  
          { //遍历与top相连的节点
  
              ru[edge[j].to]--; //入度-1
  
              if(ru[edge[j].to]==0) Q.push(edge[j].to); //如果入度为0则入队
  
          }
  
      }
  
  }
  
  void solve()
  
  {
  
      int i,j,v;
  
      for(i=0;i<cnt;i++) //依照拓扑序列处理
  
          for(j=head[que[i]];j!=-1;j=edge[j].next)
  
          { //遍历i的相邻节点
  
              v=edge[j].to;
  
              if(dis[v]<dis[que[i]]+edge[j].w) //更新距离
  
                  dis[v]=dis[que[i]]+edge[j].w;
  
          }
  
      printf("%lld\n",dis[n+1]);
  
  }
  
  int main()
  
  {
  
      int i,j,u,v;
  
      while(~scanf("%d%d",&n,&m))
  
      { //点数和边数
  
          init();
  
          for(i=1;i<=n;i++) scanf("%d",&w[i]); //输入点权
  
          for(i=0;i<m;i++)
  
          {
  
              scanf("%d%d",&u,&v);
  
              add(u,v,w[v]);
  
              chu[u]++;
  
              ru[v]++;
  
          }
  
          for(i=1;i<=n;i++)
  
          {
  
              if(ru[i]==0)
  
              { //在0点和入度为0的点之间加边
  
                  add(0,i,w[i]);
  
                  ru[i]++;
  
              }
  
              if(chu[i]==0)
  
              { //在出度为0的点和点n+1之间加边
  
                  add(i,n+1,0);
  
                  ru[n+1]++;
  
              }
  
          }
  
          tuopu();
  
          solve();
  
      }
  
      return 0;
  
  }
- TSP：
  - bfs找到任意两个有效点（o、*为有效点）之间的最短距离。
  - dfs求所有点走完后的最短距离。
基础算法
- 位运算
- 补码
  - 32位无符号整数int：直接把这32位编码看作32位二进制数N
  - 32位有符号整数int：
    - 以最高位位符号位，0表示非负数，1表示负数。
    - 对于最高位为0的每种编码C，直接看作32位二进制数S。
    - 定义该编码按位取反后得到的编码~C表示的数值为-1-S。
    - 可以发现在补码下每个数值都有唯一的表示方式，并且任意两个数值做加减法运算，都等价于在32位补码下做最高位不进位的二进制加减法运算。
    - 发生溢出时，32位无符号整数自动对2^32取模。
- 移位运算
  - 左移：1<<n=2的n次方， n<<1=2n
  - 算术右移n>>1=n/2.0 (向下取整，高位以符号位填充)
  - 逻辑右移（高位以0填充）
- 二进制状态压缩
  - 取出整数n在二进制表示下的第k位 (n>>k)&1
  - 取出整数n在二进制表示下的第0~k-1位（后k位） n&((1<<k)-1）
  - 把整数n在二进制表示下的第k位取反 n xor (1<<k)
  - 对整数n在二进制表示下的第k位赋值为1 n|(1<<k)
  - 对整数n在二进制表示下的第k位赋值位0 n&(~(1<<k))
- 成对变换
  - 对于非负整数n：
    - n为偶数：n xor 1等于n+1
    - n为奇数：n xor 1等于n-1
- lobit运算：
  - - lowbit(n)第一位非负整数n在二进制表示下“最低为的1及后面所有的0”构成的数值。例如n=10的二进制数表示为1010，则lowbit（n）=10
    - 推导lowbit公式：n取反加一再或上n —》 lowbot(n)=n&(~n+1)=n&(-n)
    - 配合hash表找出整数二进制下所有是1的位
      - 不断令n=n-lowbit(n)直到n为0,记录其中剪掉的数并对其取对数即可
      - C++数学库比较渣，所以我们选择用hash方法代替log运算,建立一个数组H，令 $H[2^{k}]=k$
      - const MAXN=1 << 20;//其实是一个标记数组
        
        int H[MAXN+1];
        
        for(int i=0; i<=20; i++) H[1 << i]=i;
        
        while(cin>>n){
        
            while(n>0){
        
                cout<<H[n & -n]<<' ';
        
                n-=n & -n;
        
            }
        
            cout<<endl;
        
        }
    - 稍微复杂但更高效的方法是建立一个长度为37的数组H，令 $H[2^{k} mod 37]=k$ ,这里有一个小技巧，所有在0~35之间的整数k，2的k次方mod37互不相等，且恰好取编1~36
    - int H[37];
      
      for(int i=0;i<36;i++) H[(1ll << i) % 37]=i;
      
      while(cin>>n){
      
          while(n>0){
      
              cout<< H[(n & -n) %37] <<' ';
      
              n -= n & -n;
      
          }
      
          cout<<endl;
- 二分//>=x中最小的一个
  while(l<r){
  
  int mid=(l+r)>>2;
  
  if(a[mid]>=x)r=mid;else l=mid+1;
  
  }
  
  return a[l];
  
  //<=x中最大的一个
  
  while(l<r){
  
  int mid=(l+r+1)>>2;
  
  if(a[mid]<=x)l=mid;r=mid-1;
  
  }
  
  return a[l];
- 快排
  - const int MAXN = 1e6+10;
    
    int a[MAXN];
    
    void quick_sort(int l,int r) {
    
        if(r=<l)return ;
    
        int i=l,j=r,temp=a[l];
    
        while(i!=j) {
    
            while(i<j&&a[j]>=temp)j--;//注意=情况一定要排除，否则有可能出现无限循环
    
            while(i<j&&a[i]<=temp)i++;
    
            if(i<j) {
    
                a[i]^=a[j];
    
                a[j]^=a[i];
    
                a[i]^=a[j];
    
            }
    
        }
    
        a[l]=a[i];
    
        a[i]=temp;
    
        quick_sort(l,i-1);
    
        quick_sort(i+1,r);
    
    }
  - 寻找第k大
  - void quick_sort(int l,int r,int k) {
    if(r<=l)return ;
    int i=l,j=r,temp=a[l];
    while(i!=j) {
    while(i<j&&a[j]>=temp)j–;//注意=情况一定要排除，否则有可能出现无限循环
    while(i<j&&a[i]<=temp)i++;
    if(i<j) {
    a[i]^=a[j];
    a[j]^=a[i];
    a[i]^=a[j];
    }
    }
    a[l]=a[i];
    a[i]=temp;
    if(k<i)quick_sort(l,i-1,k);
    if(k>i)quick_sort(i+1,r,k);
    }
- /*
  * 将一个数组中的两个相邻有序区间合并成一个
  *
  * 参数说明：
  * a — 包含两个有序区间的数组
  * start — 第1个有序区间的起始地址。
  * mid — 第1个有序区间的结束地址。也是第2个有序区间的起始地址。
  * end — 第2个有序区间的结束地址。
  */
  void merge(int a[], int start, int mid, int end)
  {
  int *tmp = (int *)malloc((end-start+1)*sizeof(int)); // tmp是汇总2个有序区的临时区域
  int i = start; // 第1个有序区的索引
  int j = mid + 1; // 第2个有序区的索引
  int k = 0; // 临时区域的索引while(i <= mid && j <= end)
  {
  if (a[i] <= a[j])
  tmp[k++] = a[i++];
  else
  tmp[k++] = a[j++];
  }
  
  while(i <= mid)
  tmp[k++] = a[i++];
  
  while(j <= end)
  tmp[k++] = a[j++];
  
  // 将排序后的元素，全部都整合到数组a中。
  for (i = 0; i < k; i++)
  a[start + i] = tmp[i];
  
  free(tmp);
  }
  
  /*
  * 归并排序(从上往下)
  *
  * 参数说明：
  * a — 待排序的数组
  * start — 数组的起始地址
  * endi — 数组的结束地址
  */
  void merge_sort_up2down(int a[], int start, int end)
  {
  if(a==NULL || start >= end)
  return ;
  
  int mid = (end + start)/2;
  merge_sort_up2down(a, start, mid); // 递归排序a[start…mid]
  merge_sort_up2down(a, mid+1, end); // 递归排序a[mid+1…end]
  
  // a[start…mid] 和 a[mid…end]是两个有序空间，
  // 将它们排序成一个有序空间a[start…end]
  merge(a, start, mid, end);
  }
- ST
- void ST_prework()
  
  {
  
  for(int i=1;i<=n;i++)f[i][0]=a[i],f2[i][0]=a[i];
  
  int t=log(n)/log(2)+1;
  
  for(int j=1;j<t;j++)
  
  for(int i=1;i<=n-(1<<j)+1;i++){
  
  f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
  
  f2[i][j]=min(f2[i][j-1],f2[i+(1<<(j-1))][j-1]);
  
  }
  
  }
  
  int ST_query(int l,int r)
  
  {
  
  int k=log(r-l+1)/log(2);
  
  return max(f[l][k],f[r-(1<<k)+1][k])-min(f2[l][k],f2[r-(1<<k)+1][k]);
  
  }
- 进制转化
  - ```
  printf("%05o\n",35);    //按八进制格式输出，保留5位高位补零
  printf("%03d\n",35);    //按十进制格式输出，保留3位高位补零
  printf("%05x\n",35);    //按十六进制格式输出，保留5位高位补零
```
- ```
cout << "35的8进制:" << std::oct << 35<< endl;  
cout << "35的10进制" << std::dec << 35 << endl;  
cout << "35的16进制:" << std::hex << 35 << endl;  
cout << "35的2进制: " << bitset<8>(35) << endl;      //<8>：表示保留8位输
```
  - long int strtol(const char *nptr, char **endptr, int base)格式：base是要转化的数的进制，非法字符会赋值给endptr，nptr是要转化的字符，
  - 1）itoa（）函数（可以将一个10进制数转换为任意的2-36进制字符串）:函数原型：char*itoa(int value,char*string,int radix);
    格式：itoa(num, str, 2); num是一个int型的，是要转化的10进制数，str是转化结果，后面的值为目标进制。
数学
- 快速幂
- const int mode=9901;
  
  long long Mode(long long a, long long b)
  
  {
  
      long long sum = 1;
  
      while (b) {
  
          if (b & 1) {
  
              sum = (sum * a) % mode;
  
              b--;
  
          }
  
          b /= 2;
  
          a = a * a % mode;
  
      }
  
      return sum;
  
  }
- 质因数分解
- const int maxn=10;
  
  int fac[10000];
  
  int fre[10000];
  
  const int mode=9901;
  
  int work_quality_factor(int n)
  
  {
  
      int res,temp,i;
  
      res=0;
  
      temp=n;
  
      for(i=2;i*i<=temp;i++)
  
          if(temp%i==0)
  
          {
  
              fac[res]=i;
  
              fre[res]=0;
  
              while(temp%i==0)
  
              {
  
                  temp=temp/i;
  
                  fre[res]++;
  
              }
  
              res++;
  
          }
  
      if(temp>1)
  
      {
  
          fac[res]=temp;
  
          fre[res++]=1;
  
      }
  
      return res;
  
  }
- 费马平方和定理：费马平方和定理的表述是：奇素数能表示为两个平方数之和的充分必要条件是该素数被4除余1。
- bitset素数表
  const int maxn = 1e8+1e8+1e8;
  
  bitset<maxn> p;
  
  int
  
  main(void) {
  
        int L, R;
  
        scanf("%d %d\n", &L, &R);
  
      p.set();
  
      for (int i = 3; i*i <= R; i+=2) if (p[i]) for (int j = i*i; j <= R; j+=2*i) p[j] = false;
  
      int ans = 0;
  
      for (int i = 5; i <= R; i+=4) if (p[i] && i >= L) ans++;
  
      ans += (L <= 2 && R >= 2) ? 1 : 0;
  
      printf("%d\n", ans);
  
      return 0;
  
  }
- 求N的正约数集合——试除法：
  const int MAXN=1e6+10;int factor[1600],m=0;
  
  for(int i=1; i*i<=n; i++) {
  
  if(n%i==0) {
  
  factor[++m]=i;
  
  if(i!=n/i)factor[++m]=n/i;
  
  }
  
  }
- 求1~N所有正约数集合vector[500010]
  for(int i=1;i<=n;i++)
  
  {
  
  forj=1;j<=n/i;j++)
  
  factor[i*j].push_back(i);
  
  }
- 欧拉函数：//在线试除
  ll euler(int n){
  
  int p=n;
  
  for(int i=2;i<=sqrt(n);i++){//2开始 //玄学问题，用i*i作为判断条件过不了 if(n%i==0){ p=p/i*(i-1); while(n%i==0)n/=i; } } if(n>1){
  
  p=p/n*(n-1);
  
  }
  
  return p;
  
  }
  
  //离线Eratoshenes筛
  
  void euler(int n){
  
  rep(i,2,n)phi[i]=i;
  
  rep(i,2,n)
  
  if(phi[i]==i)
  
  for(int j=i;j<=n;j+=i)
  
  phi[j]=phi[j]/i*(i-1);
  
  }
  
  //O(nlogn)
  
  //线性筛
  
  int prime[1000045],cnt;
  
  int phi[1000045];
  
  bool vis[1000045];
  
  il void shai()
  
  {
  
  for(int i=2;i<=1000045;i++)
  
  {
  
  if(!vis[i])//su shu
  
  {
  
  prime[++cnt]=i;
  
  phi[i]=i-1;//xing zhi 1
  
  }
  
  for(int j=1;j<=cnt;j++)
  
  {
  
  if(i*prime[j]>100000)
  
  break;
  
  vis[i*prime[j]]=1;
  
  if(i%prime[j]==0)
  
  {
  
  phi[i*prime[j]]=prime[j]*phi[i];//xing zhi 3
  
  break;
  
  }
  
  else
  
  phi[i*prime[j]]=(prime[j]-1)*phi[i];//xing zhi 4
  
  }
  
  }
- 性质1：对于所有n>1，1~n中与n互质得数得和为n*phi(n)/2性质2：若a，b互质，则phi(ab)=phi(a)phi(b)
  积性函数：a，b互质，f(a,b)=f(a)*f(b)
  
  性质3：若f是积性函数,,则
  
  性质4：若di|n,则F(n)=f(d1)+f(d2)+f(d3)+…+f(dk)也是积性函数
  
  性质5：gcd是积性函数,欧拉函数是积性函数
  
  性质6：n，m互质，gcd(i,n*m)=gcd(i,n)*gcd(i,m)
  
  性质7：n的所有因子di的phi(di)的累加和为n
  
  性质8：p为质数，若p|n且p|n^2，则phi(n)=phi(n/p)*p
  
  性质9：p为质数，若p|n且！P|N^2，则phi(n)=phi(n/p)*(p-1)
  
  性质10：p为素数，a为整数，phi(p^a)=p^a-p^(a-1)
- 拓展欧几里得ll a,b,x,y;
  ll exgcd(ll a,ll b,ll&x,ll &y){
  
  if(!b){
  
  x=1,y=0;
  
  return a;
  
  }
  
  long long d=exgcd(b,a%b,x,y);
  
  ll z=x;x=y;y=z-y*(a/b);
  
  return d;
  
  }
  
  int main(){
  
  cin>>a>>b;
  
  exgcd(a,b,x,y);
  
  cout<<(x%b+b)%b<<endl;
  
  }
- 组合数直接求解C_{n}^{m}的组合数，不需要进行取模运算。
  
  为了避免中间结果的溢出，仅使用一个简单的方法：n! / m! =（m+1）*（m+2）*……(n-1)* n;
  
  long long C(int n,int m)
  
  {
  
  if(m<n-m)
  
  m=n-m;
  
  long long ans=1;
  
  for(int i=m+1;i<=n;i++)
  
  ans*=i;
  
  for(int i=1;i<=n-m;i++)
  
  ans/=i;
  
  return ans;
  
  }
- 求解C_{n}^{m}组合数对 p取模的结果。
  1. 0≤m≤n≤1000，1≤p≤1e9，直接求
  void Com(int n,int p){
  
  C[0][0]=1;
  
  for(int i=1;i<=1000;++i){
  
  for(int j=0;j<=i;++i){
  
  if(j==0||j==i) C[i][j]=1%p;
  
  else C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;
  
  }
  
  }
  
  }
- 0≤m≤n≤1e18， 1≤p≤1e6，用卢卡斯定理
  LL f[N]; //N为组合数的底数的范围
  
  void init(int p){
  
  f[0] = 1;
  
  for(int i = 1; i <= p; ++i)
  
  f[i] = f[i-1] * i % p;
  
  }
  
  LL pow_mod(LL a, LL x, int p){
  
  LL ret = 1;
  
  a %= p;
  
  while(x){
  
  if(x & 1){
  
  ret = ret * a % p;
  
  –x;
  
  }
  
  else{
  
  a = a * a % p;
  
  x >>= 1;
  
  }
  
  }
  
  return ret;
  
  }
  
  LL Lucas(LL n, LL k, int p){
  
  LL ret = 1;
  
  while(n && k){
  
  LL nn = n % p, kk = k % p;
  
  if(nn < kk) return 0;
  
  ret = ret * f[nn] * pow_mod(f[kk] * f[nn – kk] % p, p – 2, p) % p;
  
  n /= p;
  
  k /= p;
  
  }
  
  return ret;
  
  }
- 0≤n≤1e18，0≤m≤1e6，1≤p≤1e9，用卢卡斯定理
  LL quick_mod(LL a, LL b)
  
  {
  
  LL ans = 1;
  
  a %= p;
  
  while(b)
  
  {
  
  if(b & 1)
  
  {
  
  ans = ans * a % p;
  
  b–;
  
  }
  
  b >>= 1;
  
  a = a * a % p;
  
  }
  
  return ans;
  
  }
  
  LL C(LL n, LL m)
  
  {
  
  if(m > n) return 0;
  
  LL ans = 1;
  
  for(int i=1; i<=m; i++)
  
  {
  
  LL a = (n + i – m) % p;
  
  LL b = i % p;
  
  ans = ans * (a * quick_mod(b, p-2) % p) % p;
  
  }
  
  return ans;
  
  }
  
  LL Lucas(LL n, LL m)
  
  {
  
  if(m == 0) return 1;
  
  return C(n % p, m % p) * Lucas(n / p, m / p) % p;
  
  }
- 杨辉三角for(int i=2;i<=maxn;i++)
  for(int j=2;j<i;j++)
  
  c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
- 利用乘法逆元ll inv(ll a){
  return a==1?1:(ll)(p-p/a)*inv(p%a)%p;
  
  }
  
  ll C(ll n,ll m){
  
  if(m<0||n<m)return 0;
  
  if(m>n-m)m=n-m;
  
  ll up=1,down=1;
  
  rep(i,0,m-1){
  
  up=up*(n-i)%p;
  
  down=down*(i+1)%p;
  
  }
  
  return up*inv(down)%p}
数据结构
- const int maxn = 1e6+10;
  
  int c[maxn];
  
  int a[maxn];
  
  int n;
  
  int ask(int x) {
  
      int ans=0;
  
      for(; x ; x -= x&-x)ans+=c[x];
  
      return ans;
  
  }
  
  void add(int x,int y) {
  
      for(; x<=n; x+= x&-x)c[x]+=y;
  
  }
  
  string cmd;
  
  int main() {
  
      int t;
  
      scan_d(t);
  
      rep(w,1,t) {
  
          printf("Case %d:\n", w);
  
          scan_d(n);
  
          CLR(c);
  
          rep(i,1,n)scan_d(a[i]),add(i,a[i]);
  
          while(cin>>cmd) {
  
              int x,y;
  
              if(cmd[0]=='E')break;
  
              else {
  
                  scan_d(x);
  
                  scan_d(y);
  
                  if(cmd[0]=='A') {
  
                      add(x,y);
  
                  } else if(cmd[0]=='S') {
  
                      add(x,-y);
  
                  } else {
  
                      printf("%d\n", ask(y)-ask(x-1));
  
                  }
  
              }
  
          }
  
      }
  
      return 0;
  
  }
- multiset::iterator it;
  it=s.lower_bound(x);
  *it;
  it=s.find(x);
  s.erase(*it);
  s.erase(s.find(it));
- 字典树
  - const int MAXN = 1e6+10;
    
    int trew[maxn][26],tot=1;
    
    bool end[maxn];
    
    char s[maxn];
    
    void insert(char *str){
    
        int len = strlen(str), p=1;
    
        for(int k=0;k<len;k++){
    
            int ch=str[k]-'a';
    
            if(trie[p][ch]==0)trie[p][ch]=++tot;
    
            p=trie[p][ch];
    
        }
    
        end[p]=true;
    
    }
    
    bool search(char *str){
    
        int len=strlen(str),p=1;
    
        for(int i=0;i<len;i++){
    
            int ch=str[i]-'a';
    
            if(trie[p][ch]==0)return false;
    
            p=trie[p][ch];
    
        }
    
        return end[p];
    
    }
- 线段树
- const int maxn = 1e6+10;
  
  struct SegmentTree {
  
      int l,r;
  
      long long sum, add;
  
  #define l(x) tree[x].l
  
  #define r(x) tree[x].r
  
  #define sum(x) tree[x].sum
  
  #define add(x) tree[x].add
  
  } tree[1000010*4];
  
  int a[1000010],n,m;
  
  void build(int p,int l,int r) {
  
      l(p)=l,r(p)=r;
  
      add(p)=0;//注意初始化位置
  
      if(l==r) {
  
          sum(p)=a[l];
  
          return ;
  
      }
  
      int mid=(l+r)/2;//只有这里的一半是直接用传入的l，r，但实际上这里的l，r就是下面的p.l,p.r
  
      build(p*2,l,mid);
  
      build(p*2+1,mid+1,r);
  
      sum(p)=sum(p*2)+sum(p*2+1);
  
  }
  
  //延迟标记代表：该节点已经被修改，但子节点尚未被更新
  
  void spread(int p) {
  
      if(add(p)) {
  
          sum(p*2) = add(p)*(r(p*2)-l(p*2)+1); //更新左子节点信息
  
          sum(p*2+1) = add(p)*(r(p*2+1)-l(p*2+1)+1);//更新右子节点信息
  
          add(p*2) = add(p); //给左子节点打延迟标记
  
          add(p*2+1) = add(p);
  
          add(p) = 0;//清楚p节点的标记
  
      }
  
  }
  
  void change(int p,int l,int r,int d) {
  
      if(l<=l(p) && r>=r(p)) { //完成覆盖
  
          sum(p)=(long long)d*(r(p)-l(p)+1);//更新节点信息
  
          add(p)=d;//给节点打延迟标记
  
          return ;
  
      }
  
      spread(p); //下传延迟标记
  
      int mid=(l(p)+r(p))/2; //这里的中间是当前节点的中间（或者说是偏左的中间）位置
  
      if(l<=mid)change(p*2,l,r,d);
  
      if(r>mid)change(p*2+1,l,r,d);//注意这里不是非此即彼的关系
  
      sum(p)=sum(p*2)+sum(p*2+1);
  
  }
  
  long long ask(int p,int l,int r) {
  
      if(l<=l(p) && r>=r(p))return sum(p);
  
      spread(p);
  
      int mid=(l(p)+r(p))/2;
  
      long long val=0;
  
      if(l <= mid) val+=ask(p*2,l,r);//注意！这里对中间元素进行比较的是l不是tree[p].l
  
      if(r > mid) val+=ask(p*2+1,l,r);
  
      return val;
  
  }
  
  char cmd[10];
  
  int main() {
  
      int t;
  
      cin>>t;
  
      rep(l,1,t) {
  
          int n,m;
  
          scan_d(n),scan_d(m);
  
          rep(i,1,n)a[i]=1;
  
          build(1,1,n);
  
          while(m--) {
  
              int l,r,d;
  
              scan_d(l);
  
              scan_d(r);
  
              scan_d(d);
  
              change(1,l,r,d);
  
          }
  
          printf("Case %d: The total value of the hook is %d.\n",l,ask(1,1,n));
  
      }
  
      return 0;
  
  }
- kmp
- ```
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
using namespace std;

const int N = 1000002;
int nextt[N];
int ex[N];
char S[N],T[N];
//vector<int>S,T;
int slen, tlen;

void getNext()
{
    int j, k;
    j = 0; k = -1; nextt[0] = -1;
    while(j < tlen)
        if(k == -1 || T[j] == T[k])
            nextt[++j] = ++k;
        else
            k = nextt[k];

}
/*
返回模式串T在主串S中首次出现的位置
返回的位置是从0开始的。
*/
char s1[N],s2[N];
void EXKMP()
{
    int i = 0, j, po, len = strlen(s1), l2 = strlen(s2);
    getNext();//计算子串的next数组，先改动T为s1，tlen为strlen(s1);
    while(s1[i] == s2[i] && i < l2 && i < len) //计算ex[0]
        i++;
    ex[0] = i;
    po = 0; //初始化po的位置
    for(i = 1; i < len; i++)
    {
        if(nextt[i - po] + i < ex[po] + po) //第一种情况，直接可以得到ex[i]的值
            ex[i] = nextt[i - po];
        else//第二种情况，要继续匹配才能得到ex[i]的值
        {
            j = ex[po] + po - i;
            if(j < 0)j = 0; //如果i>ex[po]+po则要从头开始匹配
            while(i + j < len && j < l2 && s1[j + i] == s2[j]) //计算ex[i]
                j++;
            ex[i] = j;
            po = i; //更新po的位置
        }
    }
}
int KMP_Index(){//拓展KMP，求s1以i开始的后缀串与s2的最长前缀串长度
	int i = 0, j = 0,ans=0;//ans=-1;//只计算一次位置时调用
	getNext();
	while(i < slen){ 
		if(j == -1 || S[i] == T[j]){ 
			i++; j++;
		}else 
			j = nextt[j]; 
		if(j == tlen){ 
			//ans++,j=0;//语句1 
			//ans++,j=nextt[j];//语句2 
			//ans=i-j+1;break;//语句3 
		} 
	}
	return ans; 
}

int main()
{
    
    int TT;
    int i, cc;
    while(1)
    {
    	scanf("%s", S);
    	scanf("%s", T);
        slen = strlen(S);
        tlen = strlen(T);
        cout<<KMP_Index()<<endl;
    }
```
- void getNext(){
  int j, k;
  
  j = 0; k = -1; nextt[0] = -1;
  
  while(j < tlen)
  
  if(k == -1 || T[j] == T[k])
  
  nextt[++j] = ++k;
  
  else
  
  k = nextt[k];
  
  }
  
  int KMP_Index() {
  
  int i = 0, j = 0,ans=0;//ans=-1;
  
  getNext();
  
  while(i < slen) {
  
  if(j == -1 || S[i] == T[j]) {
  
  i++;
  
  j++;
  
  } else j = nextt[j];
  
  if(j == tlen) {
  
  //ans++,j=0; //语句1
  
  //ans++,j=nextt[j]; //语句2
  
  //ans=i-j+1;break; //语句3
  
  }
  
  }
  
  return ans;
  
  }
  
  //对于这段代码，若求第一次出现位次，将ans置为-1（为了区分第0位与无），打开语句3；
  
  //求可部分重叠KMP则打开语句2；
  
  //求不可重叠KMP则打开语句1.
- 用kmp求next数组的方法求当i==n时出前后缀相同的串最大长度。
  循环节的长度l=n-next[n];
邻接表
#define MAXM 500010

#define MAXN 10010

#define ANS_MAX 2147483647

struct EDGE {

int next;

int to;

int w;

};

EDGE edge[MAXM];

int n, m;

int head[MAXN];

inline int Read() {

char c;

int ans = 0;

bool Sign = false;

while(!isdigit(c=getchar()) && c != ‘-‘);

if(c == ‘-‘) {

Sign = true;

c = getchar();

}

do {

ans = (ans<<3) + (ans<<1) + (c ^ ‘0’);

} while(isdigit(c=getchar()));

return Sign ? -ans : ans;

}

void Add(int u, int v, int w) {

edge[++cnt].next = head[u];//指向上一个输入的x的边

edge[cnt].to = v;

edge[cnt].w = w;//权值

head[u] = cnt;//记录

}

void read() {

int x, y, w;

n = Read();

m = Read();

for(int i=1; i<=m; i++) {

x = Read();

y = Read();

w = Read();

Add(x, y, w);

}

}

for(int i=head[k]; i!=0; i=edge[i].next) {

int j = edge[i].to;

}
//1.用数组离散for(int i=1;i<=n;i++){
cin>>a[i].val;

a[i].id = i;

}

sort(a+1,a+1+n);

for(int i=1;i<=n;i++)

b[a[i].id] = i;     //将a[i]数组映射成更小的值,b[i]就是a[i]对应的rank值

//2.用STL+二分离散化

for(int i=1;i<=n;i++){

cin>>a[i];

b[i] = a[i];

}

sort(b+1,b+1+n);

int len = unique(b+1,b+1+n)-b-1;   //len就是去重之后的数组长度,unique用法可以去网上看看，用法简单

for(int i=1;i<=n;i++)

a[i] = lower_bound(b+1,b+1+len,a[i])-b;   //a[i]就是直接离散化出来的数组
DP
- 背包//求最大值需满足满条件时则设f[i]为-INF,f[0]为0
  //否则f[i]=0
  
  //求最小值设f[i]为INF,f[0]=0(不分正负)
  
  //完全背包
  
  for(int i=1; i<=n; i++) {
  
  for(int j=cost[i]; j<=C; i++) {
  
  f[j]=max(f[j-cost[i]]+w[i],f[j]);
  
  }
  
  }
  
  //0-1背包
  
  for(int i=1; i<=n; i++) {
  
  for(int j=C; j>=cost[i]; j–) {
  
  f[j]=max(f[j-cost[i]]+w[i],f[j]);
  
  }
  
  }
  
  //多重背包
  
  for(int i=1; i<=n; i++) {
  
  for(int j=sum; j>=0; j–) {
  
  for(int k=0; k<=c[i]; k++) {
  
  if(k*a[i]>j)break;
  
  f[j]=max(f[j],f[j-k*a[i]]+k*w[i]);
  
  }
  
  }
  
  }
  
  //多重背包二进制优化
  
  vector<int>V;
  
  vector<int>W;
  
  for (int i = 0; i < n; ++i) {
  
  scanf(“%d%d”,&m,&x,&w);
  
  for (int j = 1; j <= m; j<<=1) {//二进制优化
  
  V.push_back(j*x);
  
  W.push_back(j*w);
  
  m-=j;
  
  }
  
  if(m>0) V.push_back(m*x),w.push_back(m*w);//！！！别忘了剩余的数
  
  }
  
  for (int i = 0; i < V.size(); i++) {
  
  for (int j = C; j >=V[i] ; –j) {
  
  dp[j]=max(dp[j-V[i]]+W[i],dp[j]);
  
  }
  
  }
- //分组背包
- f[0]=0;
  
  for(int i=1;i<=n;i++)
  
      for(int j=m;j>=0;j--)
  
          for(int k=1;k<=num[i];k++)
  
              if(j>=cost[i][k])
  
                  f[j] = max(f[j], f[j-cost[i][k]] + w[i][k]);
- LCS
- string a,b;
  
  int c[3][maxn]; //记录子序列的长度最大值   此处用到了滚动数组　如果开串c[h][h]会超内存(MLE)，或改为 short int c[H][H]
  
  
  
  void LCS(int m,int n){//求出最长公共子序列的长度
  
  
  
      for(int i=0;i<=2;i++){
  
         c[i][0]=0;
  
      }
  
  
  
      for(int j=0;j<=n;j++){
  
         c[0][j]=0;
  
      }
  
  
  
      for(int i=1;i<=m;i++){
  
          for(int j=1;j<=n;j++){
  
              if(a[i]==b[j])
  
                  c[i%2][j]=c[(i-1)%2][j-1]+1;
  
              else{
  
                  c[i%2][j]=max(c[(i-1)%2][j],c[i%2][j-1]);
  
              }
  
          }
  
      }
  
  }
- ```
int lcs(String str1, String str2) {  
    int len1 = str1.length();  
    int len2 = str2.length();  
    int c[][] = new int[len1+1][len2+1];  
    for (int i = 0; i <= len1; i++) {  
        for( int j = 0; j <= len2; j++) {  
            if(i == 0 || j == 0) {  
                c[i][j] = 0;  
            } else if (str1.charAt(i-1) == str2.charAt(j-1)) {  
                c[i][j] = c[i-1][j-1] + 1;  
            } else {  
                c[i][j] = max(c[i - 1][j], c[i][j - 1]);  
            }  
        }  
    }  
    return c[len1][len2];  
}
```
- LIS
- rep(i,1,n){
  
          f[i]=1;
  
          rep(j,1,i-1){
  
              if(a[j]<a[i])f[i]=max(f[i],f[j]+1);
  
          }
  
          ans=max(f[i],ans);
  
      }
- ```
int low[maxn],a[maxn];
int n,ans;
int binary_search(int *a,int r,int x)
//二分查找，返回a数组中第一个>=x的位置 
{
    int l=1,mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(a[mid]<=x)
            l=mid+1;
        else 
            r=mid-1;
    }
    return l;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) 
    {
        scanf("%d",&a[i]); 
        low[i]=INF;//由于low中存的是最小值，所以low初始化为INF 
    }
    low[1]=a[1]; 
    ans=1;//初始时LIS长度为1 
    for(int i=2;i<=n;i++)
    {
        if(a[i]>=low[ans])//若a[i]>=low[ans]，直接把a[i]接到后面 
            low[++ans]=a[i];
        else //否则，找到low中第一个>=a[i]的位置low[j]，用a[i]更新low[j] 
            low[binary_search(low,ans,a[i])]=a[i];
    }
    printf("%d\n",ans);//输出答案 
    return 0;
}
```
- 最大不重叠自片段
  - rep(i,1,m){
    
                maxx=-INF;
    
                rep(j,i,n){
    
                    dp[j]=max(dp[j-1]+a[j],ma[j-1]+a[j]);
    
                    ma[j-1]=maxx;//后一次记前一次，最后的j对应的值不记录，因为原来k的范围就是从i-1~j-1
    
                    maxx=max(maxx,dp[j]);//两个作用，一是保存前一次j的最大值，二是保存最后一次i中的最大值
    
        //          ma[j]=maxx;这样做会导致前一次的值被覆盖
    
                }
    
            }
- LCIS
- int lengthOfLCIS(int *a, int n, int *b, int m) {int ans = 0;
  int dp[505][505] = {0};
  
  for (int i = 0 ; i < n ; ++i) {
  
  int max_dp = 0;
  
  for (int j = 0 ; j < m ; ++j) {
  
  dp[i + 1][j + 1] = dp[i][j + 1];
  
  if (a[i] > b[j] && max_dp < dp[i + 1][j + 1]) max_dp = dp[i + 1][j + 1];
  
  if (a[i] == b[j]) {
  
  dp[i + 1][j + 1] = max_dp + 1;
  
  }
  
  ans = max(ans, dp[i + 1][j + 1]);
  
  }
  
  }
  
  return ans;
  
  }

发表评论 取消回复

发表评论取消回复