居然补完了

组合 

import java.util.*;import java.io.*;public class Main   {    public static void main(String[] args)  {        Scanner cin = new Scanner (new BufferedInputStream (System.in));        int n = cin.nextInt ();        int[] col = new int[105];        String str;        long ans = 0;        for (int i=0; i

枚举 

import java.util.*;import java.io.*;public class Main   {    public static void main(String[] args)  {        Scanner cin = new Scanner (new BufferedInputStream (System.in));        int n = cin.nextInt ();        String[] sex = new String[5005];        int[] btime = new int[5005];        int[] etime = new int[5005];        for (int i=0; i
     
      = btime[j] && i <= etime[j]) {                    if (sex[j].charAt (0) == 'M')   male++;                    else    female++;                }            }            if (male < female)  {                if (male * 2 > ans) ans = male * 2;            }            else    {                if (female * 2 > ans)   ans = female * 2;            }        }        System.out.println (ans);    }}
     

DP C - Famil Door and Brackets

题意：n长的字符串有‘（’和‘）’组成，现在已知其中m长的字串，问满足任意前缀字串‘（’数量不小于‘）’数量且最后两者数量相等的原字符串的方案数。

分析：‘（’看作+1，‘（’看作-1。dp[i][j]表示前i个字符，和为j(j >= 0)的方案数，然后枚举m字符串前的字符个数p，那么m后q的个数也知道，根据总和为0可以得到前后组合，这里dp[n-m-i][j+now]用到对称思想。

import java.util.*;import java.io.*;public class Main   {    public static final int MOD = 1000000007;    public static void main(String[] args)  {        Scanner cin = new Scanner (new BufferedInputStream (System.in));        Main ma = new Main ();        int n = cin.nextInt ();        int m = cin.nextInt ();        char[] str = cin.next ().toCharArray ();        long[][] dp = new long[2005][2005];        dp[0][0] = 1;        for (int i=1; i<=n-m; ++i)  {            for (int j=0; j<=i; ++j)    {                if (j > 0)  {                    dp[i][j] = ma.add (dp[i][j], dp[i-1][j-1]);                }                dp[i][j] = ma.add (dp[i][j], dp[i-1][j+1]);            }        }        int mn = 10000000;        int now = 0;        for (int i=0; i
     
      = 0 && j + now <= n - m - i)    {                    ans = ma.add (ans, dp[i][j] * dp[n-m-i][j+now] % MOD);                }            }        }        System.out.println (ans);    }    public long add(long a, long b)  {        a += b;        if (a >= MOD)   a -= MOD;        return a;    }}
     

线段树+DP 

题意：求最大上升序列和

分析：dp[i] 表示前i得到的最大上升序列和，dp[i] = dp[j] + vol[i] (vol[i] > vol[j])。用线段树优化动态统计前rk[i] - 1的最大值即dp[j]，rk[i]是vol[i]离散化后的排名。

#include 
     
      #define lson l, mid, o << 1#define rson mid + 1, r, o << 1 | 1const double PI = acos (-1.0);const int N = 1e5 + 5;struct Segment_Tree {    double v[N<<2], mx[N<<2];    void push_up(int o) {        mx[o] = std::max (mx[o<<1], mx[o<<1|1]);    }    void build(int l, int r, int o) {        if (l == r) {            v[o] = mx[o] = 0;            return ;        }        int mid = l + r >> 1;        build (lson);   build (rson);        push_up (o);    }    void updata(int p, double x, int l, int r, int o)   {        if (l == r && l == p)   {            v[o] = mx[o] = x;            return ;        }        int mid = l + r >> 1;        if (p <= mid)   updata (p, x, lson);        else    updata (p, x, rson);        push_up (o);    }    double query(int ql, int qr, int l, int r, int o)   {        if (ql <= l && r <= qr) {            return mx[o];        }        int mid = l + r >> 1;   double ret = 0;        if (ql <= mid)  ret = std::max (ret, query (ql, qr, lson));        if (qr > mid)   ret = std::max (ret, query (ql, qr, rson));        return ret;    }};double dp[N];int r[N], h[N];double vol[N], V[N];int main(void)  {    int n;  scanf ("%d", &n);    for (int i=0; i
     

LCA + DP + DFS 

题意：加一条边，使形成简单环(无重边)，u和v在其中的方案数

分析：加一条边一定是从u或v引出一条边到w而且w能到另一个点。无重边就是w不能选择u到v路径上的点。

　　dep[u]：根节点1到u的距离　　　sz[u]：u的子树包括u的结点数　　sdown[u]：在u的子树下到u的距离和，树形dp

　　sall[u]：所有点到u的距离和，由sdown[u]得到，也是树形DP

　　一共有3种情况：1.LCA (u, v) == v，除v子树外所有点到v的距离和/点数 + u子树所有点到u的距离 / 点数

　　　　　　　　　　2.LCA (v, u) == u，同1

　　　　　　　　　　3.除1，2的情况，只能在u或v的子树选择一节点才能构成环，u子树所有点到u的距离 / 点数 + v子树所有点到v的距离 / 点数

　　最后还要加上不变的距离 dis (u, v) + 1。学习大牛的代码，获益匪浅

#include 
     
      const int N = 1e5 + 5;const int D = 20;std::vector
      
        G[N];int dep[N], sz[N];long long sdown[N], sall[N];int rt[N][D];int n, m;void DFS(int u, int fa) {       //get rt[v][0], sdown[u] and dep[v]    sdown[u] = 0;   sz[u] = 1;    for (int i=0; i
       
        =0; --i)  {        if (d < (1 << i))   continue;        u = rt[u][i];   d -= (1 << i);    }    return u;}int LCA(int u, int v)   {    if (dep[u] < dep[v])    std::swap (u, v);    for (int i=0; i
        
         > i & 1) {            u = rt[u][i];        }    }    if (u == v) return u;    for (int i=D-1; i>=0; --i)  {        if (rt[u][i] != rt[v][i])   {            u = rt[u][i];            v = rt[v][i];        }    }    return rt[u][0];}int main(void)  {    scanf ("%d%d", &n, &m);    for (int u, v, i=0; i