编号	名称	通过率	通过人数	提交人数
√水题（队友写的		91%	1122	1228
—		57%	68	119
最大子矩阵和		51%	182	353
缩点/二分/数位dp		11%	23	209
凸包		57%	327	567
—		15%	15	95
√找规律		74%	456	609
—		51%	17	33
√线段树		77%	861	1110
最短路		57%	44	77

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
             
            
           
          
         
        
       
      

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
             
            
           
          
         
        
       
      

#include
      
       #include
       
        #include
        
         using namespace std;int p[105];int l[105];struct Node{    int day;    int cost;}node[105];int main(){    int n, m;    while (scanf("%d%d", &n, &m) != EOF)    {        memset(l, 0, sizeof(l));        for (int i = 0; i < n; i++)        {            scanf("%d", &p[i]);        }        int ln,x;        scanf("%d", &ln);        for (int i = 0; i < ln; i++)        {            scanf("%d", &l[i]);        }        sort(l, l + ln);        int now = 0;        int now_node = 0;        for (int i = 0; i < n; i++)        {            if (i == l[now]&&now
        
       
      

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
             
            
           
          
         
        
       
      

#include 
      
       #define mem(a,b) memset((a),(b),sizeof(a))#define MP make_pair#define pb push_back#define fi first#define se second#define sz(x) x.size()using namespace std;typedef long long ll;const int INF=0x3f3f3f3f;const ll LLINF=0x3f3f3f3f3f3f3f3f;const double PI=acos(-1.0);const double eps=1e-8;const int MAX=2e5+10;const ll mod=1e9+7;int sgn(double x){      if(fabs(x)
       
        0?1:-1;  }struct Point{      int id;    double x,y;    Point(){}    Point(double a,double b)    {        x=a;        y=b;    }    void input()    {        scanf("%lf%lf",&x,&y);    }};typedef Point Vector;Vector operator -(Vector a,Vector b){
    return Vector(a.x-b.x,a.y-b.y);}bool operator <(Point a,Point b){
    return a.x
        
         
           graham(vector
          
            p){      int n,m,k,i;    sort(p.begin(),p.end());    p.erase(unique(p.begin(),p.end()),p.end());    n=p.size();    m=0;    vector
           
             res(n+1); for(i=0;i
            
             1&&cross(res[m-1]-res[m-2],p[i]-res[m-2])<=0) m--; res[m++]=p[i]; } k=m; for(i=n-2;i>=0;i--) { while(m>k&&cross(res[m-1]-res[m-2],p[i]-res[m-2])<=0) m--; res[m++]=p[i]; } if(n>1) m--; res.resize(m); return res;}char ans[111];int main(){ int t,n,i; scanf("%d",&t); while(t--) { scanf("%d",&n); vector
             
               v; Point p[111]; for(i=0;i
              
                res=graham(v); mem(ans,0); if(sz(res)==n) { if(n==3) { puts("NO"); continue; } int flag=0; for(i=0;i
              
             
            
           
          
         
        
       
      

#include
      
       #define rep(i,j,k) for((i)=(j);(i)<=(k);++i)#define per(i,j,k) for((i)=(j);(i)>=(k);--i)using namespace std;typedef long long ll;inline void cmin(ll &x,ll y){
    if(y
       
        x)x=y;}const ll N = 1000006;const ll inf = 1LL<<60;bool ok[N]; struct edge{ll v,next,w;}e[N];ll dep[N],last[N],s[N],d[N],fa[N],id1[N],id2[N],K,L,n,i,l,r,u,v,w,cnt,top,stk[N];ll inline read(){    char ch=getchar();ll z=0,f=1;    while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){z=z*10+ch-'0';ch=getchar();}    return z*f;}void add(ll u,ll v,ll w){    e[++cnt]=(edge){v,last[u],w};last[u]=cnt;    e[++cnt]=(edge){u,last[v],w};last[v]=cnt;}void dfs(ll x,ll y,ll &mx){    if(dep[x] > dep[mx]) mx = x; fa[x] = y; ll i;    for(i=last[x];i;i=e[i].next)        if(!ok[e[i].v] && e[i].v!=y){dep[e[i].v] = dep[x] + e[i].w; dfs(e[i].v,x,mx);}}ll getlength(ll root,ll &st,ll &ed,ll &len){    dep[st = root] = 0; dfs(root,0,st); len = dep[st];    dep[ed = st] = 0; dfs(st,0,ed);    return dep[ed];}bool cmp1(ll x,ll y){
    return s[x]+d[x]
        
         K){i=id2[l++]; cmax(mx,s[i]+d[i]);}        if(l>1){            ll mi2=s[id2[1]]-d[id2[1]];            l1=mx+s[top]+L-K;             cmin(r1,mi2+s[j]-d[j]-L+K);            l2=s[top]+L-K-mi2;            cmin(r2,s[j]-d[j]-mx-L+K);        }    }    if(l1>r1) return 0; k = l = top; p = q = 1;    rep(i,2,top)if(s[i]*2>=l1+l2&&s[i]*2<=r1+r2){        while(k>0 && s[i]+s[k]>=l1) --k;        while(l>0 && s[i]+s[l]>r1) --l;        while(p<=top && s[i]-s[p]>=l2) ++p;        while(q<=top && s[i]-s[q]>r2) ++q;        if(max(q,k+1)<=min(p-1,min(l,i-1))) return 1;    }    return 0;}int main(){    int t;    scanf("%d",&t);    while (t--)    {                scanf("%lld",&n);        L=1;        cnt = 0; rep(i,0,n) last[i] = ok[i] = 0;        rep(i,1,n-1){u=read();v=read();add(u,v,1);}        ll st,ed,len,l=-1,r=getlength(1,st,ed,len);        stk[top = ok[ed] = 1] = ed;        for(i=ed;i!=st;i=fa[i]) ok[stk[++top] = fa[i]] = 1;        reverse(stk+1,stk+top+1);        rep(i,1,top) s[i] = dep[stk[i]];        rep(i,1,top) cmax(l,getlength(stk[i],st,ed,d[i])-1);        rep(i,1,top) id1[i] = id2[i] = i;        sort(id1+1,id1+top+1,cmp1);        sort(id2+1,id2+top+1,cmp2);        while(l+1
         
          >1;            if(solve(K)) r=K; else l=K;        }        printf("%lld\n",r);    }    return 0;}
         
        
       
      

import java.io.OutputStream;import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.util.StringTokenizer;import java.math.BigInteger;import java.io.IOException;import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.io.InputStream;/** * Built using CHelper plug-in * Actual solution is at the top */public class Main {    public static void main(String[] args) {        InputStream inputStream = System.in;        OutputStream outputStream = System.out;        InputReader in = new InputReader(inputStream);        PrintWriter out = new PrintWriter(outputStream);        Task2 solver = new Task2();        int testCount = Integer.parseInt(in.next());        for (int i = 1; i <= testCount; i++)            solver.solve(i, in, out);        out.close();    }    static class Task2 {        BigInteger C(int n, int m) {            BigInteger ans = BigInteger.valueOf(1);            for (int i = 1; i <= m; i++) {                ans = ans.multiply(BigInteger.valueOf(n - i + 1));            }            for (int i = 2; i <= m; i++) {                ans = ans.divide(BigInteger.valueOf(i));            }            return ans;        }        public void solve(int testNumber, InputReader in, PrintWriter out) {            int n = in.nextInt();            int[] a = new int[n + 1];            int[] b = new int[n + 1];            for (int i = 1; i <= n; i++) {                a[i] = in.nextInt();                b[a[i]] = i;            }            ArrayList
      
        arr = new ArrayList<>();            int now = 1;            for (int i = 2; i <= n; i++) {                if (a[i - 1] != n && (a[i] == n || b[a[i - 1] + 1] > b[a[i] + 1])) {                    arr.add(now);                    now = 1;                } else {                    now++;                }            }            arr.add(now);            if (arr.size() > 26) {                out.println(0);            } else {                int sz = arr.size();                BigInteger[][] dp = new BigInteger[sz + 1][27];                for (int i = 0; i <= sz; i++) {                    for (int j = 0; j <= 26; j++) {                        dp[i][j] = BigInteger.valueOf(0);                    }                }                dp[0][0] = BigInteger.valueOf(1);                for (int i = 0; i < sz; i++) {                    for (int j = 0; j < 26; j++) {                        for (int k = 1; j + k <= 26; k++) {                            dp[i + 1][j + k] = dp[i + 1][j + k].add(dp[i][j].multiply(C(arr.get(i) + k - 2, k - 1)));                        }                    }                }                // out.println(dp[sz][26]);                BigInteger ans = BigInteger.valueOf(0);                for (int i = 1; i <= 26; i++) {                    ans = ans.add(dp[sz][i]);                }                out.println(ans);            }        }    }    static class InputReader {        public BufferedReader reader;        public StringTokenizer tokenizer;        public InputReader(InputStream stream) {            reader = new BufferedReader(new InputStreamReader(stream), 32768);            tokenizer = null;        }        public String next() {            while (tokenizer == null || !tokenizer.hasMoreTokens()) {                try {                    tokenizer = new StringTokenizer(reader.readLine());                } catch (IOException e) {                    throw new RuntimeException(e);                }            }            return tokenizer.nextToken();        }        public int nextInt() {            return Integer.parseInt(next());        }    }}
      

B：java，26^3 dp，http://blog.csdn.net/skywalkert/article/details/51731556（在 cdoj 上也有一个

C：枚举上下界变成最大子段和，变成 dp[i][0..1]，C 直接卡上下界降维。开个数组记录下压缩这一列的最小值

 我是枚举上下边界然后单调栈 //

 dp[前i列][换了j次][有没有开始选区间]

二维rmq（×）

 你用单调栈就不用rmq了 

。

区间最小值就是

v[u][d][i]=min(v[u][d-1][i],a[d][i])

然后u d不用存 

 就和一般的最大子矩阵和一样做

D：http://uoj.ac/problem/298（UOJ原题）抓一条直径，在上面选两个点连，二分答案之后考察可行性，点对的可行区域是一个菱形交（菱形交是百度之星原题）

（如果原本不能满足条件那么就要走这条新边

E：n<3 直接NO；n=3除了共线都是NO；n>=4 取前四个点 讨论一下就行

G：G 是个 TC 原题改，是数论。把这个图对偶一下，考察有多少个正方形被走过。发现是 (m-1)(n-1)/g^2，每个正方形内部一条对角线被走过，有 g-1 个。

J：J直接建图跑最短路，每条 1 边中间加个虚点拆成两个 0.5 就可以 BFS 了