我的ACM代码库

常用易忘

ACM常见博弈论

---

头文件声明

#include <iostream> 
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef  vector<int> vi;
typedef  long long ll;
typedef  unsigned long long  ull; 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
const int N = 1e7+5;

int main()
{
    return 0;   
} 

数据类型范围

unsigned   int   0～4294967295   
int   2147483648～2147483647 
unsigned long 0～4294967295
long   2147483648～2147483647
long long的最大值：9223372036854775807
long long的最小值：-9223372036854775808
unsigned long long的最大值：18446744073709551615

__int64的最大值：9223372036854775807
__int64的最小值：-9223372036854775808
unsigned __int64的最大值：18446744073709551615

cin cout 速度慢问题

	ios::sync_with_stdio(false);
	用"\n"不用endl

欧拉筛法

for(int i = 2;i < 50005;i++){
 		if(a[i]) b[ci++] = i;
 		for(int j = 0;j < ci&&b[j]*i<50005;j++){
 			a[b[j]*i] = 0;
 			if(i%b[j] == 0) break;
 		}
 	}//欧拉筛法，不要太大，大于sqrt（x）后面的就没意义了，反而会是这道题超时

快速幂

LL quick_pow(LL a,LL b)
{
    LL res = 1;
    while(b)
    {
        if(b%2 != 0) res *= a;
        a *= a;
        b /= 2;
    }
    return res;
}

辗转相除法gcd和lcm

 int gcd(int a,int b){
     if(a%b == 0) return b;
     else return gcd(b,a%b);
 }

int gcd(int a,int b)///最大公因数，测试数据1e8，没有C++自带的__gcd(,)函数快
{
    return (a%b==0)?b:gcd(b,a%b);
}
int lcm(int a,int b)///最小公倍数
{
    return (a*b/gcd(a,b));
}
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<gcd(a,b)<<endl<<lcm(a,b)<<endl;
}

二进制枚举

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < (1<<n); i++) //从0～2^n-1个状态
    {
        for(int j = 0; j < n; j++) //遍历二进制的每一位
        {
            if(i & (1 << j))//判断二进制第j位是否存在
            {
                printf("%d ",j);//如果存在输出第j个元素
            }
        }
        printf("\n");
    }
    return 0;
}

二分

    int search(int array[], int n, int v)
    {
    int left, right, middle;
    left = 0, right = n - 1;  
    while (left <= right)
    {
        middle = (left + right) >>1;
        if (array[middle] > v)
        {
        
            right = middle - 1;
        }
        else if (array[middle] < v)
        {
            left = middle + 1;
        }
        else
        {
            return middle;
        }
    }
    return -1;
    }

kmp多串匹配模板

#include <bits/stdc++.h>
using namespace std;
char w[10000+10],t[1000000+10];
int next1[10000+10],ans;
void getnext(){
 int wlen = strlen(w);

 int j = 0,k = -1;
 next1[0] = -1;
 
 while(j < wlen){
     if(k == -1 || w[k] == w[j]){
         ++k;
         ++j;
         next1[j] = k;
     }
     else{
         k = next1[k];
     }
 }

 /* for(int i = 0;i <= wlen;i++){ */
 /*     printf("%d ",next1[i]); */
 /* } */
}

void kmp(){
 int wlen = strlen(w);
 int tlen = strlen(t);
 getnext();

 int i = 0,j = 0;
 while(j < tlen){
     if(i == -1 || w[i] == t[j]){
         i++;
         j++;

         if(i == wlen){
             ans++;
             i = next1[i];
         }
     }
     else{
         i = next1[i];
     }
 }
}
int main(){
 
 int xx;
 scanf("%d\n",&xx);
 while(xx--){
     memset(w,0,sizeof(w));
     memset(t,0,sizeof(t));
     scanf("%s",w);
     scanf("%s",t);
     
     ans = 0;
     kmp();
     printf("%d\n",ans);
     
 }
 return 0;
}

KMP最小循环节、循环周期：
https://blog.csdn.net/hao_zong_yin/article/details/77455285
定理：假设S的长度为len，则S存在最小循环节，循环节的长度L为len-next[len]，子串为S[0…len-next[len]-1]。

（1）如果len可以被len - next[len]整除，则表明字符串S可以完全由循环节循环组成，循环周期T=len/L。

（2）如果不能，说明还需要再添加几个字母才能补全。需要补的个数是循环个数L-len%L=L-(len-L)%L=L-next[len]%L，L=len-next[len]。

字符串哈希

p1220
#include<iostream>
#include<cstring>
using namespace std;
const int MaxNum = 20000000;
char ch[MaxNum];
bool lage[MaxNum];                                //用于标记是否为相同的子串
int hashArray[256];                                //存储n个字母转换成整数之后再转换成nc进制的数

int main() {
 int n, nc;
 while (cin >> n >> nc >> ch) {
     int k = 0;
     int len = strlen(ch);                    //注意此处
     for (int i = 0; i < len; i++) {
         if (hashArray[ch[i]] == 0) {
             hashArray[ch[i]] = k++;            //给nc个字母编号，如hashArray['a']=1
         }
     }
     int ans = 0;                            //记录不同子串的种数
     for (int i = 0; i <= len - n; i++) {
         int sum = 0;
         for (int j = i; j < i + n; j++) {
             sum = sum * nc + hashArray[ch[j]];//将hashArray[]的nc进制数转换成一个十进制的整数sum
         }
         if (!lage[sum]) {                    //未出现过为false
             ans++;
             lage[sum] = true;                //出现过的为true
         }
     }
     cout << ans << endl;
 }
 return 0;
}

树状数组

int lowbit(int x){
 return x&(-x);
}

int update(int p,int x){    
 while(p <= 100010){//数字n
     bit[p] = bit[p] + x;
     p = p + lowbit(p);
 }
}

int query(int p){
 int ans = 0;
 while(0 < p){
     ans = ans + bit[p];
     p = p - lowbit(p);
 }
 return ans;
}

矩阵快速幂hdu1005 & LightOJ - 1070

hud1005
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
struct node{
 ull x[2][2];
};
const int mod = 7;
node mux(node a,node b){
 
 node t;
 memset(t.x,0,sizeof(t.x));
 for(int i = 0;i < 2;i++)
     for(int j = 0;j < 2;j++)
         for(int k = 0;k < 2;k++){
             t.x[i][j] = (t.x[i][j]%mod + (a.x[i][k]*b.x[k][j])%mod)%mod;
         }

 return t;

}

node quick(ull n,node a){

 node t;
 memset(t.x,0,sizeof(t));

 t.x[0][0] = t.x[1][1] = 1;
 t.x[0][1] = t.x[1][0] = 0;
 while(n){
     if(n&1)
         t = mux(t,a);
     a = mux(a,a);
     n=n>>1;
 }
 return t;
}


int main(){

 ull a,b,n;
 while(cin>>a>>b>>n){
     if(a == 0 && b == 0 && n == 0){
         exit(0);
     }

     if(n == 1 || n == 2){
         cout<<1<<"\n";
         continue;
     }
     
     node a1;
     a1.x[0][0] = a;
     a1.x[0][1] = 1;
     a1.x[1][0] = b;
     a1.x[1][1] = 0;
     node ans = quick(n-2,a1);

     cout<<(ans.x[0][0] + ans.x[1][0])%mod<<"\n";

 }

 return 0;
}

LightOJ - 1070 
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long llu;
typedef unsigned int uint;

struct node{
 llu s[2][2]; 
};

node mut(node a,node b){

 node c;
 memset(c.s,0,sizeof(c.s));
 for(int i = 0;i < 2;i++)
     for(int j = 0;j < 2;j++)
         for(int k = 0;k < 2;k++)
             c.s[i][j] = c.s[i][j]+ b.s[k][j]*a.s[i][k];
 return c;
             
}

node quick(llu n,node p){

 node q;
 memset(q.s,0,sizeof(q.s));
 
 q.s[0][1] = q.s[1][0] = 0;
 q.s[1][1] = q.s[0][0] = 1;

 while(n){
     if(n&1)
         q = mut(p,q);
     p = mut(p,p);
     n = n/2;
 }

 return q;
}
int main(){
 
 llu t,cnt = 1;
 llu x,y,z;
 cin>>t;
 while(t--){
     cin>>x>>y>>z;
     

     if(z == 1){
         cout<<"Case "<<cnt++<<": "<<x<<"\n";
         continue;    
     }
     else if(z == 2){
         cout<<"Case "<<cnt++<<": "<<x*x-2*y<<"\n";
         continue;    
         
     }
     else if(z == 0){
         cout<<"Case "<<cnt++<<": "<<2<<"\n";
         continue;    
     }
     else{
         node a1,b1;
         a1.s[0][0] = x;
         a1.s[1][0] = x*x-2*y;
         a1.s[1][1] = 0;
         a1.s[0][1] = 0;

         b1.s[0][0] = x;
         b1.s[1][0] = -1*y;
         b1.s[0][1] = 1;
         b1.s[1][1] = 0;

         node ans = quick(z-2,b1);

         cout<<"Case "<<cnt++<<": "<<a1.s[1][0]*ans.s[0][0] + a1.s[0][0]*ans.s[1][0]<<"\n";
     }
 }
 return 0;
}

spfa hdu1874

#include <bits/stdc++.h>
using namespace std;
int dist[210],vis[210],cnt[210];//vis在对列的标志 cnt每个点的如队列次数
const int inf = 0x3f3f3f3f;
struct edge{
 int v;
 int cost;
 edge(int _v = 0,int _cost=0):v(_v),cost(_cost){};
};

vector<edge>e[210];

void addedge(int u,int v,int w)
{
 e[u].push_back(edge(v,w));
}

bool spfa(int start,int n)
{
 memset(vis,0,sizeof(vis));
 for(int i = 0;i < n;i++)
     dist[i] = inf;
 vis[start] = 1;
 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] = 0;

     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]){
                 vis[v] = 1;
                 que.push(v);
                 if(++cnt[v] > n)
                     return false;
                 //cnt[i]为入队列次数，用来判定是否存在负环回路
             }
         }
     }
 }
 return true;
}
int main(){

 int n,m;
 while(~scanf("%d%d",&n,&m))
 {
     for(int i = 0;i < n;i++)
         e[i].clear();
     int a,b,x;
     for(int i = 0;i < m;i++){
         scanf("%d%d%d",&a,&b,&x);
         addedge(a,b,x);
         addedge(b,a,x);
     }

     int start,end;
     scanf("%d%d",&start,&end);
     spfa(start,n);
     if(dist[end] == inf)
         printf("-1\n");
     else
         printf("%d\n",dist[end]);
 }
 return 0;
}

地杰斯特拉 p3371

#include <bits/stdc++.h>
using namespace std;
const int inf = 2147483647;
const int maxn = 100010;
struct qnode
{
 int v,c;
 qnode(int _v = 0,int _c = 0):v(_v),c(_c){}
 bool operator < (const qnode& a) const
 {
     return c > a.c;
 }
};

struct edge{
 int v,cost;
 edge(int _v = 0,int _cost = 0):v(_v),cost(_cost){}
};

vector <edge> e[maxn];
bool vis[maxn];
int dist[maxn];
//点的编号从1开始
//

void disa(int n,int start)
{
 memset(vis,0,sizeof(vis));
 for(int i = 1;i <= n;i++)
     dist[i] = inf;
 priority_queue<qnode>que;
 while(!que.empty())
     que.pop();
 dist[start] = 0;
 que.push(qnode(start,0));
 
 qnode tmp;

 while(!que.empty())
 {
     tmp = que.top();
     que.pop();
     int u = tmp.v;
     if(vis[u])
         continue;
     vis[u] = 1;

     for(int i = 0;i < e[u].size();i++)
     {
         int v = e[tmp.v][i].v;
         int cost = e[u][i].cost;
         if(!vis[v]&&dist[v] > dist[u]+cost)
         {
             dist[v] = dist[u] + cost;
             que.push(qnode(v,dist[v]));
         }
     }
 }
}
void addedge(int u,int v,int w)
{
 e[u].push_back(edge(v,w));
}

int main(){
 int n,m,s,v1,v2,w;
 scanf("%d%d%d",&n,&m,&s);
 for(int i = 0;i < m;i++)
 {
     scanf("%d%d%d",&v1,&v2,&w);
     addedge(v1,v2,w);
     /* addedge(v2,v1,w); */
 }
 disa(n,s);
 for(int i = 1;i <= n;i++)
     printf("%d ",dist[i]);
 putchar('\n');
 return 0;
}

二分图匹配hdu2063

#include <bits/stdc++.h>
using namespace std;
const int maxn = 510;
typedef long long ll;
vector<int>q[maxn];
int match[maxn],book[maxn];
int dfs(int u)
{
    for(size_t i = 0;i < q[u].size();i++)
    {
        int t = q[u][i];
        if(book[t] == 0)
        {
            book[t] = 1;
            if(match[t] == 0 || dfs(match[t]))
            {
                match[t] = u;
                return 1;
            }
        }
    }
    return 0;
}
int main(){

    int k,n,m,a,b,sum = 0;
    while(scanf("%d",&k)&&k){
        for(int i = 0;i < maxn;i++)
            q[i].clear();
        memset(book,0,sizeof(book));
        memset(match,0,sizeof(match));

        scanf("%d%d",&n,&m);
        for(int i = 0;i < k;i++)
        {
            scanf("%d%d",&a,&b);
            q[a].push_back(b);
        }
        
        for(int i = 0;i <= n;i++)
            match[i] = 0;

        for(int i = 1;i <= n;i++)
        {
            memset(book,0,sizeof(book));
            if(dfs(i))
                sum++;
        }
        printf("%d\n",sum);
    }
    return 0;
}

P1435 lcs滚动数组优化

#include<bits/stdc++.h>
using namespace std;
int dp[2][5001];
char str1[5001],str2[5001];
int main()
{
    int n;
    scanf("%s",str1+1);
    n = strlen(str1+1);
    for(int i = 1; i <= n; i++)
        str2[i] = str1[n-i+1];       
    for(int i = 1; i<=n; i++)
        for(int j = 1; j <= n; j++)
            if(str1[i] == str2[j])
                dp[i&1][j] = dp[i-1 & 1][j-1] + 1;
            else
                dp[i&1][j] = max(dp[i-1 & 1][j], dp[i & 1][j-1]);  
    printf("%d\n", n-dp[n&1][n]);                         
    return 0;                                        
}

lis升序降序 lower_bound使用

//luogu p1020
#include <bits/stdc++.h>
using namespace std;
int a[1000005],b[1000005],c[1000005];
int main(){
    int n = 0;
    while(scanf("%d",&a[n])&&a[n]!=0)
    {
        n++;
    }
    int cont = 0,cnt = 0;
    b[0] = a[0];
    c[0] = a[0];
    for(int i = 1;i < n;i++)
    {
        if(a[i] <= b[cnt])
        {
            b[++cnt] = a[i];
        }
        else
        {
            int wei = upper_bound(b,b+cnt,a[i],greater<int>()) - b;
            b[wei] = a[i];
        }

        if(a[i] > c[cont])
        {
            c[++cont] = a[i];
        }
        else
        {
            int wei = lower_bound(c,c+cont,a[i]) - c;
            c[wei] = a[i];
        }
    }
    printf("\n%d\n%d",cnt+1,cont+1);
    return 0;
}

//hdu5532
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <functional>
using namespace std;
int a[100000+10];
int a1[100000+10];
int b1[100000+10];

int main(){

    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        int cnt1 = 0,cnt2 = 0;

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

        scanf("%d",&n);
        for(int i = 0;i < n;i++)
        {
            scanf("%d",&a[i]);
        }

        a1[0] = a[0];
        b1[0] = a[0];

        for(int i = 1;i < n;i++)
        {
            if(a1[cnt1]<=a[i]){

                a1[++cnt1] = a[i];
            }
            else{
                int y = upper_bound(a1,a1+cnt1,a[i]) - a1;
                a1[y] = a[i];
            }

            if(b1[cnt2]>=a[i]){
                b1[++cnt2] = a[i];
            }
            else{
                int y = upper_bound(b1,b1+cnt2,a[i],greater<int>()) - b1;
                b1[y] = a[i];
            }

        }
        if(cnt1+1 >= n-1 || cnt2+1 >= n-1){
            printf("YES\n");
        }
        else{
            printf("NO\n");
        }
    }
    return 0;
}

离散化

    cin>>n;

    int co[1000];
    for(int i=0;i<n;i++){
        cin>>co[i];
    }
    sort(co,co+n);
    int size=unique(co,co+n)-co;//去重函数，将重复的都移到后边，然后用size截掉，相同元素仅保留一个， 
                                //如果不需要去重则删掉这一句。size为离散化后元素个数 
    for(int i=0;i<n;i++)
        arr[i]=lower_bound(co,co+size,arr[i])-co + 1;//arr存放了排序后，第i个数字新的编号。

凸包poj3348

#include <iostream>
#include <algorithm>
using namespace std;
struct Point{
    int x,y;
    Point(){}    //构造函数
    Point(int xx,int yy){
        x = xx;
        y = yy;
    }
    Point operator - (const Point a)const{
        return Point(x-a.x,y-a.y);
    }
    double operator ^(const Point &b)const{
        return x*b.y - y*b.x;    
    }

}p[11000],ch[11000];    //元序列和凸包序列

bool cmp(Point a,Point b){     //点排序
    if(a.x == b.x)  return a.y < b.y;
    return a.x < b.x; 
}

double det (Point a, Point b) {    //返回叉乘的摸  亦可以用重载*的方法
    return a.x * b.y - a.y * b.x;
}

int ConvexHull ( Point * p,int n, Point * ch ){    //构造凸包
    sort(p,p+n,cmp); 
    int m=0;
    for (int i=0;i<n;i++){
        while (m >1&& det(ch[m -1] - ch[m -2] ,    //回溯
                          p[i]-ch[m -2]) <=0) m --;
        ch[m++]= p[i];
    }
    int k=m;
    for (int i=n-2;i >=0;i--){
        while (m>k && det(ch[m -1] - ch[m -2] ,
                          p[i]-ch[m -2]) <=0) m --;
        ch[m++]= p[i];
    }
    if(n > 1)
        m--;

    return m;
}

int main(){
    int n,m,ans;
    double area = 0;
    cin>>n;
    for(int i = 0;i < n;i++){
        cin>>p[i].x>>p[i].y;
    }
    m = ConvexHull(p,n,ch);
    for(int i= 2;i < m;i++){
        area += (ch[i]-ch[0])^(ch[i-1]-ch[0]);
    }
    area/=2;
    if(area <= 0)
        area = -area;
    ans = area/50;
    cout<<ans<<"\n";

    return 0;
}

凸包求边长（注意n为2的时候会计算两边，应该除与2）hdu1392

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps = 1e-8;
const double inf = 1e20;
const double pi = acos( - 1.0);
const int maxp = 1010;
//Compares a double to zero
int sgn(double x){
    if(fabs(x) < eps)return 0;
    if(x < 0)return - 1;
    else return 1;
}
//square of a double
inline double sqr(double x){return x*x;}
struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y){
        x = _x;
        y = _y;
    }
    void input(){
        scanf("%lf%lf",&x,&y);
    }
    void output(){
        printf("%.2f␣%.2f\n",x,y);
    }
    bool operator == (Point b)const{
        return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
    }
    bool operator < (Point b)const{
        return sgn(x - b.x)== 0?sgn(y - b.y)<0:x<b.x;
    }
    Point operator - (const Point &b)const{
        return Point(x - b.x,y - b.y);
    }
    //叉积
    double operator ^(const Point &b)const{
        return x*b.y - y*b.x;
    }
    //点积
    double operator *(const Point &b)const{
        return x*b.x + y*b.y;
    }
    //返回长度
    double len(){
        return hypot(x,y);//库函数
    }
    //返回长度的平方
    double len2(){
        return x*x + y*y;
    }
    //返回两点的距离
    double distance(Point p){
        return hypot(x - p.x,y - p.y);
    }
    Point operator +(const Point &b)const{
        return Point(x+b.x,y+b.y);
    }
    Point operator *(const double &k)const{
        return Point(x*k,y*k);
    }
    Point operator /(const double &k)const{
        return Point(x/k,y/k);
    }
    //计算 pa 和 pb 的夹角
    //就是求这个点看 a,b 所成的夹角
    //测试 LightOJ1203
    double rad(Point a,Point b){
        Point p = *this;
        return fabs(atan2( fabs((a - p)^(b - p)),(a - p)*(b - p) ));
    }
    //化为长度为 r 的向量
    Point trunc(double r){
        double l = len();
        if(!sgn(l))return *this;
        r /= l;
        return Point(x*r,y*r);
    }
    //逆时针旋转 90 度
    Point rotleft(){
        return Point( - y,x);
    }
    //顺时针旋转 90 度
    Point rotright(){
        return Point(y, - x);
    }
    //绕着 p 点逆时针旋转 angle
    Point rotate(Point p,double angle){
        Point v = (*this) - p;
        double c = cos(angle), s = sin(angle);
        return Point(p.x + v.x*c - v.y*s,p.y + v.x*s + v.y*c);
    }
};

struct Line{
    Point s,e;
    Line(){}
    Line(Point _s,Point _e){
        s = _s;
        e = _e;
    }
    bool operator ==(Line v){
        return (s == v.s)&&(e == v.e);
    }
    //根据一个点和倾斜角 angle 确定直线,0<=angle<pi
    Line(Point p,double angle){
        s = p;
        if(sgn(angle - pi/2) == 0){
            e = (s + Point(0,1));
        }
        else{
            e = (s + Point(1,tan(angle)));
        }
    }
    //ax+by+c=0
    Line(double a,double b,double c){
        if(sgn(a) == 0){
            s = Point(0, - c/b);
            e = Point(1, - c/b);
        }
        else if(sgn(b) == 0){
            s = Point( - c/a,0);
            e = Point( - c/a,1);
        }
        else{
            s = Point(0, - c/b);
            e = Point(1,( - c - a)/b);
        }
    }
    void input(){
        s.input();
        e.input();
    }
    void adjust(){
        if(e < s)swap(s,e);
    }
    //求线段长度
    double length(){
        return s.distance(e);
    }
    //返回直线倾斜角 0<=angle<pi
    double angle(){
        double k = atan2(e.y - s.y,e.x - s.x);
        if(sgn(k) < 0)k += pi;
        if(sgn(k - pi) == 0)k-=pi;
        return k;
    }
    //点和直线关系
    //1 在左侧
    //2 在右侧
    //3 在直线上
    int relation(Point p){
        int c = sgn((p - s)^(e - s));
        if(c < 0)return 1;
        else if(c > 0)return 2;
        else return 3;
    }
    // 点在线段上的判断
    bool pointonseg(Point p){
        return sgn((p - s)^(e - s)) == 0 && sgn((p - s)*(p - e)) <= 0;
    }
    //两向量平行 (对应直线平行或重合)
    bool parallel(Line v){
        return sgn((e - s)^(v.e - v.s)) == 0;
    }
    //两线段相交判断
    //2 规范相交
    //1 非规范相交
    //0 不相交
    int segcrossseg(Line v){
        int d1 = sgn((e - s)^(v.s - s));
        int d2 = sgn((e - s)^(v.e - s));
        int d3 = sgn((v.e - v.s)^(s - v.s));
        int d4 = sgn((v.e - v.s)^(e - v.s));
        if( (d1^d2)== - 2 && (d3^d4)== - 2 )return 2;
        return (d1==0 && sgn((v.s - s)*(v.s - e))<=0) ||
            (d2==0 && sgn((v.e - s)*(v.e - e))<=0) ||
            (d3==0 && sgn((s - v.s)*(s - v.e))<=0) ||
            (d4==0 && sgn((e - v.s)*(e - v.e))<=0);
    }
    //直线和线段相交判断
    //-*this line -v seg
    //2 规范相交
    //1 非规范相交
    //0 不相交
    int linecrossseg(Line v){
        int d1 = sgn((e - s)^(v.s - s));
        int d2 = sgn((e - s)^(v.e - s));
        if((d1^d2)== - 2) return 2;
        return (d1==0||d2==0);
    }
    //两直线关系
    //0 平行
    //1 重合
    //2 相交
    int linecrossline(Line v){
        if((*this).parallel(v))
            return v.relation(s)==3;
        return 2;
    }
    //求两直线的交点
    //要保证两直线不平行或重合
    Point crosspoint(Line v){
        double a1 = (v.e - v.s)^(s - v.s);
        double a2 = (v.e - v.s)^(e - v.s);
        return Point((s.x*a2 - e.x*a1)/(a2 - a1),(s.y*a2 - e.y*a1)/(a2 - a1));
    }
    //点到直线的距离
    double dispointtoline(Point p){
        return fabs((p - s)^(e - s))/length();
    }
    //点到线段的距离
    double dispointtoseg(Point p){
        if(sgn((p - s)*(e - s))<0 || sgn((p - e)*(s - e))<0)
            return min(p.distance(s),p.distance(e));
        return dispointtoline(p);
    }
    //返回线段到线段的距离
    //前提是两线段不相交,相交距离就是 0 了
    double dissegtoseg(Line v){
        return min(min(dispointtoseg(v.s),dispointtoseg(v.e)),min(v.dispointtoseg(s),v.dispointtoseg(e)));
    }
    //返回点 p 在直线上的投影
    Point lineprog(Point p){
        return s + ( ((e - s)*((e - s)*(p - s)))/((e - s).len2()) );
    }
    //返回点 p 关于直线的对称点
    Point symmetrypoint(Point p){
        Point q = lineprog(p);
        return Point(2*q.x - p.x,2*q.y - p.y);
    }
};
struct polygon{
    int n;
    Point p[maxp];
    Line l[maxp];
    void input(int _n){
        n = _n;
        for(int i = 0;i < n;i++)
            p[i].input();
    }
    void add(Point q){
        p[n++] = q;
    }
    void getline(){
        for(int i = 0;i < n;i++){
            l[i] = Line(p[i],p[(i+1)%n]);
        }
    }
    struct cmp{
        Point p;
        cmp(const Point &p0){p = p0;}
        bool operator()(const Point &aa,const Point &bb){
            Point a = aa, b = bb;
            int d = sgn((a - p)^(b - p));
            if(d == 0){
                return sgn(a.distance(p) - b.distance(p)) < 0;
            }
            return d > 0;
        }
    };
    //进行极角排序
    //首先需要找到最左下角的点
    //需要重载号好 Point 的 < 操作符 (min 函数要用)
    void norm(){
        Point mi = p[0];
        for(int i = 1;i < n;i++)mi = min(mi,p[i]);
        sort(p,p+n,cmp(mi));
    }
    //得到凸包
    //得到的凸包里面的点编号是 0 ∼ n-1 的
    //两种凸包的方法
    //注意如果有影响,要特判下所有点共点,或者共线的特殊情况
    //测试 LightOJ1203 LightOJ1239
    void getconvex(polygon &convex){
        sort(p,p+n);
        convex.n = n;
        for(int i = 0;i < min(n,2);i++){
            convex.p[i] = p[i];
        }
        if(convex.n == 2 && (convex.p[0] == convex.p[1]))convex.n-- ;//特判
        if(n <= 2)return;
        int &top = convex.n;
        top = 1;
        for(int i = 2;i < n;i++){
            while(top && sgn((convex.p[top] - p[i])^(convex.p[top - 1] - p[i])) <= 0)
                top--;
            convex.p[++top] = p[i];
        }
        int temp = top;
        convex.p[++top] = p[n - 2];
        for(int i = n - 3;i >= 0;i -- ){
            while(top != temp && sgn((convex.p[top] - p[i])^(convex.p[top - 1] - p[i])) <= 0)
                top--;
            convex.p[++top] = p[i];
        }
        if(convex.n == 2 && (convex.p[0] == convex.p[1]))convex.n-- ;//特判
        convex.norm();//原来得到的是顺时针的点,排序后逆时针
    }
    //得到周长
    double getcircumference(){
        double sum = 0;
        for(int i = 0;i < n;i++){
            sum += p[i].distance(p[(i+1)%n]);
        }
        return sum;
    }
};
int main(){
    int n;
    while(scanf("%d",&n)!=EOF&&n){
        polygon q1,q2;
        q1.input(n);
        q1.getconvex(q2);
        double ans = q2.getcircumference();
        if(n==2){
            printf("%.2f\n",ans/2);
        }
        else{
            printf("%.2f\n",ans);
        }
    }
    return 0;
}

POJ 1410判断是否线段和矩阵相交和线段是否在矩阵中

　判断线段、折线、多边形是否在矩形中：

　　因为矩形是个凸集，所以只要判断所有端点是否都在矩形中就可以了。

//kuangbin老模板
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <string>
#include <math.h>

using namespace std;

const double eps = 1e-6;
int sgn(double x)
{
    if(fabs(x) < eps)return 0;
    if(x < 0)return -1;
    else return 1;
}
struct Point
{
    double x,y;
    Point(){}
    Point(double _x,double _y)
    {
        x = _x;y = _y;
    }
    Point operator -(const Point &b)const
    {
        return Point(x - b.x,y - b.y);
    }
    //叉积
    double operator ^(const Point &b)const
    {
        return x*b.y - y*b.x;
    }
    //点积
    double operator *(const Point &b)const
    {
        return x*b.x + y*b.y;
    }
    //绕原点旋转角度B（弧度值），后x,y的变化
    void transXY(double B)
    {
        double tx = x,ty = y;
        x = tx*cos(B) - ty*sin(B);
        y = tx*sin(B) + ty*cos(B);
    }
};
struct Line
{
    Point s,e;
    Line(){}
    Line(Point _s,Point _e)
    {
        s = _s;e = _e;
    }
    //两直线相交求交点
    //第一个值为0表示直线重合，为1表示平行，为0表示相交,为2是相交
    //只有第一个值为2时，交点才有意义
    pair<int,Point> operator &(const Line &b)const
    {
        Point res = s;
        if(sgn((s-e)^(b.s-b.e)) == 0)
        {
            if(sgn((s-b.e)^(b.s-b.e)) == 0)
                return make_pair(0,res);//重合
            else return make_pair(1,res);//平行
        }
        double t = ((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));
        res.x += (e.x-s.x)*t;
        res.y += (e.y-s.y)*t;
        return make_pair(2,res);
    }
};

//判断线段相交
bool inter(Line l1,Line l2)
{
    return
    max(l1.s.x,l1.e.x) >= min(l2.s.x,l2.e.x) &&
    max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x) &&
    max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) &&
    max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y) &&
    sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e)) <= 0 &&
    sgn((l1.s-l2.e)^(l2.s-l2.e))*sgn((l1.e-l2.e)^(l2.s-l2.e)) <= 0;
}

//判断点在线段上
//判断点在线段上
bool OnSeg(Point P,Line L)
{
    return
    sgn((L.s-P)^(L.e-P)) == 0 &&
    sgn((P.x - L.s.x) * (P.x - L.e.x)) <= 0 &&
    sgn((P.y - L.s.y) * (P.y - L.e.y)) <= 0;
}
//判断点在凸多边形内
//点形成一个凸包，而且按逆时针排序（如果是顺时针把里面的<0改为>0）
//点的编号:0~n-1
//返回值：
//-1:点在凸多边形外
//0:点在凸多边形边界上
//1:点在凸多边形内
int inConvexPoly(Point a,Point p[],int n)
{
    for(int i = 0;i < n;i++)
    {
        if(sgn((p[i]-a)^(p[(i+1)%n]-a)) < 0)return -1;
        else if(OnSeg(a,Line(p[i],p[(i+1)%n])))return 0;
    }
    return 1;
}
//判断点在任意多边形内
//射线法，poly[]的顶点数要大于等于3,点的编号0~n-1
//返回值
//-1:点在凸多边形外
//0:点在凸多边形边界上
//1:点在凸多边形内
int inPoly(Point p,Point poly[],int n)
{
    int cnt;
    Line ray,side;
    cnt = 0;
    ray.s = p;
    ray.e.y = p.y;
    ray.e.x = -100000000000.0;//-INF,注意取值防止越界

    for(int i = 0;i < n;i++)
    {
        side.s = poly[i];
        side.e = poly[(i+1)%n];

        if(OnSeg(p,side))return 0;

        //如果平行轴则不考虑
        if(sgn(side.s.y - side.e.y) == 0)
            continue;

        if(OnSeg(side.s,ray))
        {
            if(sgn(side.s.y - side.e.y) > 0)cnt++;
        }
        else if(OnSeg(side.e,ray))
        {
            if(sgn(side.e.y - side.s.y) > 0)cnt++;
        }
        else if(inter(ray,side))
            cnt++;
    }
    if(cnt % 2 == 1)return 1;
    else return -1;
}
int main()
{
    int T;
    double x1,y1,x2,y2;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
        Line line = Line(Point(x1,y1),Point(x2,y2));
        scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
        if(x1 > x2)swap(x1,x2);
        if(y1 > y2)swap(y1,y2);
        Point p[10];
        p[0] = Point(x1,y1);
        p[1] = Point(x2,y1);
        p[2] = Point(x2,y2);
        p[3] = Point(x1,y2);
        if(inter(line,Line(p[0],p[1])))
        {
            printf("T\n");
            continue;
        }
        if(inter(line,Line(p[1],p[2])))
        {
            printf("T\n");
            continue;
        }
        if(inter(line,Line(p[2],p[3])))
        {
            printf("T\n");
            continue;
        }
        if(inter(line,Line(p[3],p[0])))
        {
            printf("T\n");
            continue;
        }
        if(inConvexPoly(line.s,p,4) >= 0 || inConvexPoly(line.e,p,4) >= 0)
        {
            printf("T\n");
            continue;
        }
        printf("F\n");
    }
    return 0;
}

//新kuangbin
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
const double eps = 1E-8;
const double pi = acos(-1.0);

int sgn(double x){
    if(fabs(x) < eps)return 0;
    if(x < 0)return - 1;
    else return 1;
}

struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y){
        x = _x;
        y = _y;
    }
    bool operator == (Point b)const{
        return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
    }
    Point operator -(const Point &b)const{
        return Point(x - b.x,y - b.y);
    }
    Point operator +(const Point &b)const{
        return Point(x+b.x,y+b.y);
    }
    double operator ^(const Point &b)const{
        return x*b.y - y*b.x;
    }

    //点积
    double operator *(const Point &b)const{
        return x*b.x + y*b.y;
    }
    void input(){
        scanf("%lf%lf",&x,&y);
    }
    void output(){
        printf("%.2f %.2f\n",x,y);
    }
};

struct Line{
    Point s,e;
    Line(){}
    Line(Point _s,Point _e){
        s = _s;
        e = _e;
    }
    bool operator ==(Line v){
        return (s == v.s)&&(e == v.e);
    }
    //根据一个点和倾斜角 angle 确定直线,0<=angle<pi
    Line(Point p,double angle){
        s = p;
        if(sgn(angle - pi/2) == 0){
            e = (s + Point(0,1));
        }
        else{
            e = (s + Point(1,tan(angle)));
        }
    }
    //ax+by+c=0
    Line(double a,double b,double c){
        if(sgn(a) == 0){
            s = Point(0, - c/b);
            e = Point(1, - c/b);
        }
        else if(sgn(b) == 0){
            s = Point( - c/a,0);
            e = Point( - c/a,1);
        }
        else{
            s = Point(0, - c/b);
            e = Point(1,( - c - a)/b);
        }
    }

    bool parallel(Line v){
        return sgn((e - s)^(v.e - v.s)) == 0;
    }
    int relation(Point p){
        int c = sgn((p - s)^(e - s));
        if(c < 0)return 1;
        else if(c > 0)return 2;
        else return 3;
    }

    int linecrossseg(Line v){
        int d1 = sgn((e - s)^(v.s - s));
        int d2 = sgn((e - s)^(v.e - s));
        if((d1^d2)== - 2) return 2;
        return (d1==0||d2==0);
    }

    int linecrossline(Line v){
        if((*this).parallel(v))
            return v.relation(s)==3;
        return 2;
    }

    Point crosspoint(Line v){
        double a1 = (v.e - v.s)^(s - v.s);
        double a2 = (v.e - v.s)^(e - v.s);
        return Point((s.x*a2 - e.x*a1)/(a2 - a1),(s.y*a2 - e.y*a1)/(a2 - a1));
    }
    int segcrossseg(Line v){
        int d1 = sgn((e - s)^(v.s - s));
        int d2 = sgn((e - s)^(v.e - s));
        int d3 = sgn((v.e - v.s)^(s - v.s));
        int d4 = sgn((v.e - v.s)^(e - v.s));
        if( (d1^d2)== - 2 && (d3^d4)== - 2 )return 2;
        return (d1==0 && sgn((v.s - s)*(v.s - e))<=0) ||
            (d2==0 && sgn((v.e - s)*(v.e - e))<=0) ||
            (d3==0 && sgn((s - v.s)*(s - v.e))<=0) ||
            (d4==0 && sgn((e - v.s)*(e - v.e))<=0);
    }
};

//判断点在线段上
//判断点在线段上
bool OnSeg(Point P,Line L)
{
    return
    sgn((L.s-P)^(L.e-P)) == 0 &&
    sgn((P.x - L.s.x) * (P.x - L.e.x)) <= 0 &&
    sgn((P.y - L.s.y) * (P.y - L.e.y)) <= 0;
}

//判断点在凸多边形内
//点形成一个凸包，而且按逆时针排序（如果是顺时针把里面的<0改为>0）
//点的编号:0~n-1
//返回值：
//-1:点在凸多边形外
//0:点在凸多边形边界上
//1:点在凸多边形内
int inConvexPoly(Point a,Point p[],int n)
{
    for(int i = 0;i < n;i++)
    {
        if(sgn((p[i]-a)^(p[(i+1)%n]-a)) < 0)return -1;
        else if(OnSeg(a,Line(p[i],p[(i+1)%n])))return 0;
    }
    return 1;
}
int main(){
    int t;
    double x1,y1,x2,y2;
    scanf("%d",&t);
    while(t--){
        int xx,yy;
        scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
        xx = x1;
        yy = y1;
        Line line = Line(Point(x1,y1),Point(x2,y2));
        scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
        if(x1 > x2)swap(x1,x2);
        if(y1 > y2)swap(y1,y2);
        Point p[10];
        p[0] = Point(x1,y1);
        p[1] = Point(x2,y1);
        p[2] = Point(x2,y2);
        p[3] = Point(x1,y2);

        Line a = Line(p[0],p[1]);
        Line b = Line(p[0],p[3]);
        Line c = Line(p[1],p[2]);
        Line d = Line(p[2],p[3]);

        if(line.segcrossseg(a) || line.segcrossseg(b) || line.segcrossseg(c) || line.segcrossseg(d)){
            printf("T\n");
        }
        else{
            if(inConvexPoly(line.s,p,4) >= 0 || inConvexPoly(line.e,p,4) >= 0){
                printf("T\n");
            }
            else{
                printf("F\n");
            }
        }
    }
    return 0;
}

直线与线段相交 POJ - 3304

如果说线段们的投影有公共点的话，那么可以说是过线段的两个端点做垂线以后得到的新线段有公共点，
这些线段如果有公共点，那么可以过这个（或者这些）公共点做条垂线（相当于把投影还原），那么这条
（或者这些）直线必然穿过所有线段，反之亦然。

所以说我们就可以去找这样一条直线，那么怎么找呢？如果说这条直线穿过了所有的线段的中间（即不经过端点），
那么我们可以把它往下移一点点，使得直线经过一个端点，然而只过一个端点我们还是不会做，那么我们可以旋转一
下，让这条线过两个端点，那么问题就十分简单了，判断这条直线是否穿过所有线段即可。

原文链接：https://blog.csdn.net/sdsy191553/article/details/83067586

#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
const double eps = 1E-8;
const double pi = acos(-1.0);
int n = 0;
int sgn(double x){
    if(fabs(x) < eps)return 0;
    if(x < 0)return - 1;
    else return 1;
}

struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y){
        x = _x;
        y = _y;
    }
    bool operator == (Point b)const{
        return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
    }
    Point operator - (const Point &b)const{
        return Point(x - b.x,y - b.y);
    }
    Point operator +(const Point &b)const{
        return Point(x+b.x,y+b.y);
    }
    double operator ^(const Point &b)const{
        return x*b.y - y*b.x;
    }
    void input(){
        scanf("%lf%lf",&x,&y);
    }
    void output(){
        printf("%.2f %.2f\n",x,y);
    }
}p[10005];

struct Line{
    Point s,e;
    Line(){}
    Line(Point _s,Point _e){
        s = _s;
        e = _e;
    }
    bool operator ==(Line v){
        return (s == v.s)&&(e == v.e);
    }
    //根据一个点和倾斜角 angle 确定直线,0<=angle<pi
    Line(Point p,double angle){
        s = p;
        if(sgn(angle - pi/2) == 0){
            e = (s + Point(0,1));
        }
        else{
            e = (s + Point(1,tan(angle)));
        }
    }
    //ax+by+c=0
    Line(double a,double b,double c){
        if(sgn(a) == 0){
            s = Point(0, - c/b);
            e = Point(1, - c/b);
        }
        else if(sgn(b) == 0){
            s = Point( - c/a,0);
            e = Point( - c/a,1);
        }
        else{
            s = Point(0, - c/b);
            e = Point(1,( - c - a)/b);
        }
    }

    bool parallel(Line v){
        return sgn((e - s)^(v.e - v.s)) == 0;
    }
    int relation(Point p){
        int c = sgn((p - s)^(e - s));
        if(c < 0)return 1;
        else if(c > 0)return 2;
        else return 3;
    }

    int linecrossseg(Line v){
        int d1 = sgn((e - s)^(v.s - s));
        int d2 = sgn((e - s)^(v.e - s));
        if((d1^d2)== - 2) return 2;
        return (d1==0||d2==0);
    }

    int linecrossline(Line v){
        if((*this).parallel(v))
            return v.relation(s)==3;
        return 2;
    }

    Point crosspoint(Line v){
        double a1 = (v.e - v.s)^(s - v.s);
        double a2 = (v.e - v.s)^(e - v.s);
        return Point((s.x*a2 - e.x*a1)/(a2 - a1),(s.y*a2 - e.y*a1)/(a2 - a1));
    }
};

bool judge(Line a){

    for(int i = 0;i < n;i+=2){
        if(a.linecrossseg(Line(p[i],p[i+1]))==0)
            return 0;
    }
    return 1;

}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        n= n*2;

        for(int i = 0;i < n;i++){
            p[i].input();
        }
        bool flag = 0;
        for(int i = 0;i < n;i++){
            for(int j = i+1;j < n;j++){
                if(p[i] == p[j])continue;
                Line a(p[i],p[j]);
                if(judge(a)) flag = 1;
            }
        }
        if(flag==0){
            printf("No!\n");
        }
        else if(flag==1){
            printf("Yes!\n");
        }
    }
    return 0;
}

p3805马拉车算法

#include <bits/stdc++.h>
using namespace std;
char a[11000000+100],b[11000000*2+200];
int mp[11000000*2+200];
int main(){
    scanf("%s",a);
    int len = strlen(a),cnt = 1;
    b[0] = '$';
    b[cnt++]='#';
    
    for(int i = 0;i < len;i++){
        b[cnt++] = a[i];
        b[cnt++] = '#';
    }
    b[cnt] = '0';

    int mx = 0,id = 0;
    for(int i = 0;i < cnt;i++){
        if(mx > i){
            mp[i] = min(mp[2*id-i],mx-i);
        }
        else{
            mp[i] = 1;
        }
        while(b[i+mp[i]] == b[i-mp[i]])
            mp[i]++;
        if(i+mp[i]>mx){
            mx = i+ mp[i];
            id = i;
        }
    }

    printf("%d\n",*max_element(mp+1,mp+cnt)-1);
    return 0;
}

poj1962带权并查集

#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 200010;
int d[N],F[N];
void init(int x)
{
    for(int i =0;i<=x;i++)
    {
        F[i] = i;
        d[i]=0;
    }
}
int findset(int x)
{
    if(F[x]!=x)
    {
        int root = findset(F[x]);
        d[x] = d[x]+d[F[x]];
        return F[x] = root;
    }
    else return x;
}
int main()
{
    int T;
    char s[10];
    scanf("%d",&T);
    while(T--)
    {
        int n,u,v;
        scanf("%d",&n);
        init(n);
        while(scanf("%s",s) && s[0]!='O')
        {
            if(s[0] == 'E')
            {
                scanf("%d",&u);
                findset(u);
                printf("%d\n",d[u]);
            }
            else
            {
                scanf("%d%d",&u,&v);
                F[u] = v;
                d[u] = abs(u-v)%1000;      
            }
        }
    }
    return 0;
}

RMQ求静态区间最大最小值poj3264

#include<iostream>
#include<cstring>
#include<cstdio>
#include<climits>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN = 50010;
int dp[MAXN][20];
int dpm[MAXN][20];
int mm[MAXN];
int b[MAXN];
//初始化 RMQ, b 数组下标从 1 开始,从 0 开始简单修改
void initRMQ(int n,int b[]){
    mm[0] = - 1;
    for(int i = 1; i <= n;i++){
        mm[i] = ((i&(i - 1)) == 0)?mm[i - 1]+1:mm[i - 1];
        dp[i][0] = b[i];
        dpm[i][0] = b[i];
    }
    for(int j = 1; j <= mm[n];j++)
        for(int i = 1;i + (1<<j) - 1 <= n;i++)
        {
            dp[i][j] = max(dp[i][j - 1],dp[i+(1<<(j - 1))][j - 1]);
            dpm[i][j] = min(dpm[i][j - 1],dpm[i+(1<<(j - 1))][j - 1]);
        }
}
//查询最大值
inline int rmq(int x,int y){
    int k = mm[y - x+1];
    return max(dp[x][k],dp[y - (1<<k)+1][k]);
}
inline int riq(int x,int y){
    int k = mm[y - x+1];
    return min(dpm[x][k],dpm[y - (1<<k)+1][k]);
}
int main(){
    int n,q,x,y;
    scanf("%d%d",&n,&q);
    for(int i = 1;i <= n;i++)
        scanf("%d",&b[i]);
    initRMQ(n,b);
    for(int i = 0;i < q;i++){
        scanf("%d%d",&x,&y);
        printf("%d\n",rmq(x,y)-riq(x,y));
    }
        return 0;
}

线段树动态求最大最小值模板hdu1754（注意输入Q和A时会出现吃回车问题，用getchar(),或者全程用cin，cout）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<utility>
#include<set>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#define maxn 200005
#define INF 0x3f3f3f3f
#define LL long long
#define ULL unsigned long long
#define E 1e-8
#define mod 1000000007
#define P pair<int,int>
#define MID(l,r) (l+(r-l)/2)
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
using namespace std;
 
int a[maxn];
int ans_min,ans_max,ans_sum;
struct node{
    int l,r;
    int maxx,minx,sum;
}tree[maxn<<2];
void build(int o,int l,int r)
{
    tree[o].l = l;
    tree[o].r = r;
    if(l == r){
        tree[o].maxx = tree[o].minx = tree[o].sum = a[l];
        return ;
    }
    int m = MID(l,r);
    int  lc = lson(o),rc = rson(o);
    build(lc,l,m);
    build(rc,m+1,r);
    tree[o].maxx = max(tree[lc].maxx, tree[rc].maxx);
    tree[o].minx = min(tree[lc].minx, tree[rc].minx);
    tree[o].sum = tree[lc].sum + tree[rc].sum;
}
void update(int o,int p,int v)
{
    if(tree[o].l == tree[o].r){
        tree[o].maxx = v;  //视情况而定
        tree[o].minx = v;
        tree[o].sum = v;
        return ;
    }
    int m = MID(tree[o].l,tree[o].r);
    int lc = lson(o),rc = rson(o);
    if(p<=m) update(lc,p,v);
    else update(rc,p,v);
    tree[o].maxx = max(tree[lc].maxx, tree[rc].maxx);
    tree[o].minx = min(tree[lc].minx, tree[rc].minx);
    tree[o].sum = tree[lc].sum + tree[rc].sum;
}
void query_init()//查询前，将全局变量初始化
{
    ans_max = -INF;
    ans_min = INF;
    ans_sum = 0;
}
void query(int o,int l,int r)
{
    if(tree[o].l == l && tree[o].r == r){
        ans_max = max(ans_max, tree[o].maxx);
        ans_min = min(ans_min, tree[o].minx);
        ans_sum += tree[o].sum;
        return;
    }
    int m = MID(tree[o].l,tree[o].r);
    int lc = lson(o),rc = rson(o);
    if(r<=m) query(lc,l,r);
    else if(l>m) query(rc,l,r);
    else{
        query(lc,l,m);
        query(rc,m+1,r);
    }
}
int main()
{
    int n,m,x,y;
    char c;
    while(scanf("%d %d",&n,&m)!=EOF){
        for(int i=1;i<=n;++i){
            scanf("%d",&a[i]);
        }
        build(1,1,n);
        while(m--){
            cin>>c>>x>>y;
            if(c == 'Q'){
                query_init();
                query(1,x,y);
                printf("%d\n",ans_max);
            }
            else{
                update(1,x,y);
            }
        }
    }
    return 0;
}

线段树求最大最小值p1198（注意输入Q和A时会出现吃回车问题，用getchar(),或者全程用cin，cout）

#include<iostream>
#include<algorithm>
#define maxn 200010
#define INF 0x3f3f3f3f
#define lint long long
#define P pair<int,int>
#define MID(l,r) (l+(r-l)/2)
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
using namespace std;

lint a[maxn];
lint ans_min,ans_max,ans_sum;
struct node{
    lint l,r;
    lint maxx,minx,sum;
}tree[maxn<<2];
void build(lint o,lint l,lint r)
{
    tree[o].l = l;
    tree[o].r = r;
    if(l == r){
        tree[o].maxx = tree[o].minx = tree[o].sum = a[l];
        return ;
    }
    lint m = MID(l,r);
    lint lc = lson(o),rc = rson(o);
    build(lc,l,m);
    build(rc,m+1,r);
    tree[o].maxx = max(tree[lc].maxx, tree[rc].maxx);
    tree[o].minx = min(tree[lc].minx, tree[rc].minx);
    tree[o].sum = tree[lc].sum + tree[rc].sum;
}
void update(lint o,lint p,lint v)
{
    if(tree[o].l == tree[o].r){
        tree[o].maxx = v;  //视情况而定
        tree[o].minx = v;
        tree[o].sum = v;
        return ;
    }
    lint m = MID(tree[o].l,tree[o].r);
    lint lc = lson(o),rc = rson(o);
    if(p<=m) update(lc,p,v);
    else update(rc,p,v);
    tree[o].maxx = max(tree[lc].maxx, tree[rc].maxx);
    tree[o].minx = min(tree[lc].minx, tree[rc].minx);
    tree[o].sum = tree[lc].sum + tree[rc].sum;
}
void query_init()//查询前，将全局变量初始化
{
    ans_max = -INF;
    ans_min = INF;
    ans_sum = 0;
}
void query(lint o,lint l,lint r)
{
    if(tree[o].l == l && tree[o].r == r){
        ans_max = max(ans_max, tree[o].maxx);
        ans_min = min(ans_min, tree[o].minx);
        ans_sum += tree[o].sum;
        return;
    }
    lint m = MID(tree[o].l,tree[o].r);
    lint lc = lson(o),rc = rson(o);
    if(r<=m) query(lc,l,r);
    else if(l>m) query(rc,l,r);
    else{
        query(lc,l,m);
        query(rc,m+1,r);
    }
}
int main()
{
    int n,m,x;
    cin>>n>>m;
    build(1,1,200010);
    int len = 0,t = 0;
    while(n--){
        char c;
        cin>>c>>x;
        if(c == 'Q'){
            query_init();
            query(1,len-x+1,len);
            printf("%lld\n",ans_max);
            t = ans_max;

        }
        else{
            x=(x+t)%m;
            /* printf("\n\n%d %d %d %d %d\n\n",x,t,(x+t)%m,m,x+t); */
            len++;
            update(1,len,x);
        }
    }
    return 0;
}

线段树模板P3372

#include <bits/stdc++.h>
using namespace std;
struct node
{
    long long sum,l,r,tag;
}t[400010];
long long num[100010];

/* 建树操作 */
void build(int p,int l,int r)
{
    t[p].l=l;
    t[p].r=r;
    if(l==r)
    {
        t[p].sum=num[l];
        return ;
    }
    int mid=(l+r)/2;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    t[p].sum=t[2*p].sum+t[2*p+1].sum;
}
/* 懒标记（区间求和） */
void lazy(int p)
{
    if(t[p].tag)
    {
        t[2*p].sum+=t[p].tag*(t[p*2].r-t[p*2].l+1);
        t[2*p+1].sum+=t[p].tag*(t[p*2+1].r-t[p*2+1].l+1);
        t[2*p].tag+=t[p].tag;
        t[2*p+1].tag+=t[p].tag;
        t[p].tag=0;
    }
}

/* 区间修改（加/减） */
void change1(int p,int x,int y,int z)
{
    if(t[p].l>=x&&t[p].r<=y)
    {
        t[p].sum+=1LL*z*(t[p].r-t[p].l+1);
        t[p].tag+=z;
        return ;
    }
    int mid=(t[p].l+t[p].r)/2;
    lazy(p);
    if(x<=mid)
    {
        change1(p*2,x,y,z);
    }
    if(y>mid)
    {
        change1(p*2+1,x,y,z);
    }
    t[p].sum=t[2*p].sum+t[p*2+1].sum;
    return ;
}

/* 区间求和 */
long long sum(int p,int x,int y)
{
    if(t[p].l>=x&&t[p].r<=y)
    {
        return t[p].sum;
    }
    int mid=(t[p].l+t[p].r)/2;
    long long ans=0;
    lazy(p);
    if(x<=mid)
    {
        ans+=sum(p*2,x,y);
    }
    if(mid<y)
    {
        ans+=sum(p*2+1,x,y);
    }
    return ans;
}

/* 单点查询 */
long long single_sum(int p,int x)
{
    {
        if(t[p].l==t[p].r&&t[p].l==x)
        {
            return t[p].sum;
        }
        int mid=(t[p].l+t[p].r)/2;
        lazy(p);
        long long ans=0;
        if(mid>=x)
        {
            ans+=single_sum(2*p,x);
        }
        if(mid<x)
        {
            ans+=single_sum(2*p+1,x);
        }
        return ans;
    }
}

/* 单点修改（加/减） */
void single_change (int p,int x,int z)
{
    if(t[p].l==t[p].r&&t[p].l==x)
    {
        t[p].sum+=z;
        return ;
    }
    int mid=(t[p].l+t[p].r)/2;
    if(mid>=x)
    {
        single_change(2*p,x,z);
    }
    if(mid<x)
    {
        single_change(2*p+1,x,z);
    }
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
}

/* 区间修改（更改数值） */
/* void lazy(int p) */
/* { */
/*     if(t[p].tag) */
/*     { */
/*         t[2*p].sum=t[p].tag*(t[p*2].r-t[p*2].l+1);//少了一个+号 */
/*         t[2*p+1].sum=t[p].tag*(t[p*2+1].r-t[p*2+1].l+1);//少了一个+号 */
/*         t[2*p].tag=t[p].tag; */
/*         t[2*p+1].tag=t[p].tag; */
/*         t[p].tag=0; */
/*     } */
/* } */
/* void change(int p,int x,int y,int z) */
/* { */
/*     if(t[p].l>=x&&t[p].r<=y) */
/*     { */
/*         t[p].sum=1LL*z*(t[p].r-t[p].l+1);//少了一个+号 */
/*         t[p].tag=z; */
/*         return ; */
/*     } */
/*     int mid=(t[p].l+t[p].r)/2; */
/*     lazy(p); */
/*     if(x<=mid) */
/*     { */
/*         change(p*2,x,y,z); */
/*     } */
/*     if(y>mid) */
/*     { */
/*         change(p*2+1,x,y,z); */
/*     } */
/*     t[p].sum=t[2*p].sum+t[p*2+1].sum; */
/*     return ; */
/* } */

//最大最小是另一张表
/* const int maxn = 200000+200; */
/* struct node */
/* { */
/*     int l,r,maxx,minn; */
/* }t[maxn<<2]; */
/* int num[maxn]; */
/* void build(int p,int l,int r) */
/* { */
/*     t[p].l=l; */
/*     t[p].r=r; */
/*     if(l==r) */
/*     { */
/*         t[p].maxx=num[l]; */
/*         t[p].minn=num[l]; */
/*         return ; */
/*     } */
/*     int mid=(l+r)>>1; */
/*     build(p<<1,l,mid); */
/*     build(p<<1|1,mid+1,r); */
/*     t[p].maxx=max(t[p<<1].maxx,t[p<<1|1].maxx); */
    /* t[p].minn=min(t[p<<1].minn,t[p<<1|1].minn); */
/* } */
/* 区间最大值，最小值 */
/* int search_max(int pos,int x,int y) */
/* { */
/*     if(x<=t[pos].l&&y>=t[pos].r) */
/*     { */
/*         return t[pos].maxx; */
/*     } */
/*     int ans=-1; */
/*     int mid=(t[pos].l+t[pos].r)>>1; */
/*     if(x<=mid) ans=max(ans,search_max(pos<<1,x,y)); */
/*     if(y>mid) ans=max(ans,search_max(pos<<1|1,x,y)); */
/*     return ans; */
/* } */
/* int search_min(int pos,int x,int y) */
/* { */
/*     if(x<=t[pos].l&&y>=t[pos].r) */
/*     { */
/*         return t[pos].minn; */
/*     } */
/*     int ans=10000000+1; */
/*     int mid=(t[pos].l+t[pos].r)>>1; */
/*     if(x<=mid) ans=min(ans,search_min(pos<<1,x,y)); */
/*     if(y>mid) ans=min(ans,search_min(pos<<1|1,x,y)); */
/*     return ans; */
/* } */


int main(){

    int n,m;
    scanf("%d%d",&n,&m);

    for(int i = 1;i <= n;i++){
        scanf("%lld",&num[i]);
    }
    build(1,1,n);

    int x,y,z;
    for(int i = 0;i < m;i++){
        scanf("%d",&x);
        if(x == 2){
            scanf("%d%d",&y,&z);
            printf("%lld\n",sum(1,y,z));
        }
        else{
            scanf("%d%d%d",&x,&y,&z);
            change1(1,x,y,z);
        }
    }
    return 0;
}

tarjan求强连通分量及缩点模板poj1236

///POJ1236
///时间复杂度也是O(N+M)
#include <stdio.h>
#include <string.h>
#include <vector>
#include <stack>
#include <iostream>
#define repu(i,a,b) for(int i=a;i<b;i++)
using namespace std;
#define N 105            /// 题目中可能的最大点数
stack<int>sta;            /// 存储已遍历的结点
vector<int>gra[N];        /// 邻接表表示图
int dfn[N];        /// 深度优先搜索访问次序
int low[N];        /// 能追溯到的最早的次序
int InStack[N];
/// 检查是否在栈中(2：在栈中，1：已访问，且不在栈中，0：不在)
vector<int> Component[N]; /// 获得强连通分量结果
int InComponent[N];          /// 记录每个点在第几号强连通分量里
int Index,ComponentNumber;/// 索引号，强连通分量个数
int n, m;          /// 点数，边数
int d[N][N],chu[N],ru[N];

void init()///清空容器，数组
{
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(chu, 0, sizeof(chu));
    memset(ru, 0, sizeof(ru));
    memset(InStack, 0, sizeof(InStack));
    Index = ComponentNumber = 0;
    for (int i = 1; i <= n; ++ i)
    {
        gra[i].clear();
        Component[i].clear();
    }
    repu(i,1,n+1)
    repu(j,1,n+1)
    d[i][j] = 0;
    while(!sta.empty())
        sta.pop();
}
void tarjan(int u)
{
    InStack[u] = 2;
    low[u] = dfn[u] = ++ Index;
    sta.push(u);///寻找u所在的强连通分量
    for (int i = 0; i < gra[u].size(); ++ i)
    {
        int t = gra[u][i];
        if (dfn[t] == 0)///不在的继续递归
        {
            tarjan(t);///递归到头了就
            low[u] = min(low[u], low[t]);
        }
        else if (InStack[t] == 2)///在栈里
        {
            low[u] = min(low[u], dfn[t]);
        }
    }
    if(low[u] == dfn[u])///sta出栈就是一个强连通分量的
    {
        ++ComponentNumber;///强连通分量个数
        while (!sta.empty())
        {
            int j = sta.top();
            sta.pop();
            InStack[j] = 1;///已访问但不在栈中
            Component[ComponentNumber].push_back(j);
            ///用vector存储第ComponentNumber个强连通分量
            InComponent[j]=ComponentNumber;
            ///记录每个点在第几号强连通分量里
            if (j == u)
                break;
        }
    }
}
void input()
{
    repu(i,1,n+1)
    {
        while(scanf("%d",&m) &&m)
            d[i][m] = 1,gra[i].push_back(m);///有向图才有强连通分量
    }
}

void solve(void)
{
    for(int i=1; i<=n; i++)
        if(!dfn[i])
            tarjan(i);
    if(ComponentNumber == 1)
    {
        printf("1\n0\n");
        return;
    }
    ///缩点
    for(int i=1; i<=ComponentNumber; i++)
    {
        for(int j = 0; j < Component[i].size(); j++)
        {
            for(int k = 1; k<=n; k++)
            {
                if(d[k][Component[i][j]] && k != Component[i][j])
                {
                    int s = InComponent[k];
                    int t = InComponent[Component[i][j]];
                    if(s!=t)
                    {
                        chu[s]++;
                        ru[t]++;
                    }
                }
            }
        }
    }
    int sum = 0,num = 0;
    for(int i=1; i<=ComponentNumber; i++)
    {
        if(!chu[i])
            sum++;
        if(!ru[i])
            num++;
    }
    printf("%d\n%d\n",num,max(sum,num));
}

int main()
{
    while(~scanf("%d",&n))
    {
        init();
        input();
        solve();
        /*每一个强连通分量的具体数字
        for(int i = 1; i <= ComponentNumber; i++)
        {
            for(int j = 0; j < Component[i].size(); j++)
                if(!j)
                    cout << Component[i][j];
                else
                    cout <<"-->"<< Component[i][j];
            cout<<endl;
        }
        */
    }
    return 0;
}

tarjan求强连通分量及缩点模板poj2186

#include <stdio.h>
#include <string.h>
#include <vector>
#include <stack>
#include <iostream>
#define repu(i,a,b) for(int i=a;i<b;i++)
using namespace std;
#define N 10005            /// 题目中可能的最大点数
stack<int>sta;            /// 存储已遍历的结点
vector<int>gra[N];        /// 邻接表表示图
int dfn[N];        /// 深度优先搜索访问次序
int low[N];        /// 能追溯到的最早的次序
int InStack[N];  // 检查是否在栈中(2：在栈中，1：已访问，且不在栈中，0：不在)
/* vector<int> Component[N]; /// 获得强连通分量结果 */
int InComponent[N];          /// 记录每个点在第几号强连通分量里
int Index,ComponentNumber;/// 索引号，强连通分量个数
int n,m;          // 点数，边数
int chu[N];         //出度
/* int ru[N];           //入度 */
int num[N]; //各个强连通分量包含点的个数,数组编号 1 ∼ scc
void init() //清空容器，数组
{
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(chu, 0, sizeof(chu));
    memset(InStack, 0, sizeof(InStack));
    Index = ComponentNumber = 0;
    for (int i = 1; i <= n; ++ i)
    {
        gra[i].clear();
        /* Component[i].clear(); */
    }
    while(!sta.empty())
        sta.pop();
}
void tarjan(int u)
{
    InStack[u] = 2;
    low[u] = dfn[u] = ++ Index;
    sta.push(u);///寻找u所在的强连通分量
    for (int i = 0; i < gra[u].size(); ++ i)
    {
        int t = gra[u][i];
        if (dfn[t] == 0)///不在的继续递归
        {
            tarjan(t);///递归到头了就
            low[u] = min(low[u], low[t]);
        }
        else if (InStack[t] == 2)///在栈里
        {
            low[u] = min(low[u], dfn[t]);
        }
    }
    if(low[u] == dfn[u])///sta出栈就是一个强连通分量的
    {
        ++ComponentNumber;///强连通分量个数
        while (!sta.empty())
        {
            int j = sta.top();
            sta.pop();
            InStack[j] = 1;///已访问但不在栈中
            /* Component[ComponentNumber].push_back(j); */
            ///用vector存储第ComponentNumber个强连通分量
            InComponent[j]=ComponentNumber;
            ///记录每个点在第几号强连通分量里
            num[ComponentNumber]++;
            if (j == u)
                break;
        }
    }
}
void input()
{
    int x,y;
    scanf("%d%d",&n,&m);
    repu(i,1,m+1)
    {
        scanf("%d%d",&x,&y);        
        gra[x].push_back(y);///有向图才有强连通分量
    }
}

void solve()
{
    for(int i=1; i<=n; i++)
        if(!dfn[i])
            tarjan(i);
    ///缩点
    
    for(int i = 1;i <= n;i++){
        for(size_t j = 0;j < gra[i].size();j++){
            if(InComponent[i] != InComponent[gra[i][j]]){
                chu[InComponent[i]]++;//求出度
                ru[InComponent[gra[i][j]]]++;//求入度
                //Component[InComponent[gra[i][j]]].push_back(InComponent[i]); //缩点建图
            }
        }
    }
    int ans = 0,sum = 0;
    for(int i=1; i<=ComponentNumber; i++)
    {
        if(!chu[i])
        {
            sum++;
            ans = i;
        }
    }

    if(sum == 1){
        sum = 0;
        for(int i = 1;i <= n;i++){
            if(InComponent[i]==ans){
                sum++;
            }
        }
        printf("%d\n",sum);
    }
    else{
        printf("0\n");
    }
}

int main()
{
    init();
    input();
    solve();
    return 0;
}

P2746 tarjan缩点求入度出度，注意特判强连通分量只有1时的情况

#include <stdio.h>
#include <string.h>
#include <vector>
#include <stack>
#include <iostream>
#define repu(i,a,b) for(int i=a;i<b;i++)
using namespace std;
#define N 505            /// 题目中可能的最大点数
stack<int>sta;            /// 存储已遍历的结点
vector<int>gra[N];        /// 邻接表表示图
int dfn[N];        /// 深度优先搜索访问次序
int low[N];        /// 能追溯到的最早的次序
int InStack[N];  // 检查是否在栈中(2：在栈中，1：已访问，且不在栈中，0：不在)
/* vector<int> Component[N]; /// 获得强连通分量结果 */
int InComponent[N];          /// 记录每个点在第几号强连通分量里
int Index,ComponentNumber;/// 索引号，强连通分量个数
int n,m;          // 点数，边数
int chu[N];         //出度
int ru[N];           //入度
int num[N]; //各个强连通分量包含点的个数,数组编号 1 ∼ scc
void init() //清空容器，数组
{
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(chu, 0, sizeof(chu));
    memset(InStack, 0, sizeof(InStack));
    Index = ComponentNumber = 0;
    for (int i = 1; i <= n; ++ i)
    {
        gra[i].clear();
        /* Component[i].clear(); */
    }
    while(!sta.empty())
        sta.pop();
}
void tarjan(int u)
{
    InStack[u] = 2;
    low[u] = dfn[u] = ++ Index;
    sta.push(u);///寻找u所在的强连通分量
    for (int i = 0; i < gra[u].size(); ++ i)
    {
        int t = gra[u][i];
        if (dfn[t] == 0)///不在的继续递归
        {
            tarjan(t);///递归到头了就
            low[u] = min(low[u], low[t]);
        }
        else if (InStack[t] == 2)///在栈里
        {
            low[u] = min(low[u], dfn[t]);
        }
    }
    if(low[u] == dfn[u])///sta出栈就是一个强连通分量的
    {
        ++ComponentNumber;///强连通分量个数
        while (!sta.empty())
        {
            int j = sta.top();
            sta.pop();
            InStack[j] = 1;///已访问但不在栈中
            /* Component[ComponentNumber].push_back(j); */
            ///用vector存储第ComponentNumber个强连通分量
            InComponent[j]=ComponentNumber;
            ///记录每个点在第几号强连通分量里
            num[ComponentNumber]++;
            if (j == u)
                break;
        }
    }
}
void input()
{
    int x;
    scanf("%d",&n);

    repu(i,1,n+1)
    {
        while(scanf("%d",&x)&&x){
            gra[i].push_back(x);///有向图才有强连通分量
        }        
    }
}

void solve()
{
    for(int i=1; i<=n; i++)
        if(!dfn[i])
            tarjan(i);
    ///缩点
    
    for(int i = 1;i <= n;i++){
        for(size_t j = 0;j < gra[i].size();j++){
            if(InComponent[i] != InComponent[gra[i][j]]){
                chu[InComponent[i]]++;//求出度
                ru[InComponent[gra[i][j]]]++;//求入度
                //Component[InComponent[gra[i][j]]].push_back(InComponent[i]); //缩点建图
            }
        }
    }
    int ans = 0,sum = 0;
    for(int i=1; i<=ComponentNumber; i++)
    {
        if(!chu[i])
        {
            sum++;
        }
        if(!ru[i])
        {
            ans++;
        }
    }
    
    if(ComponentNumber == 1){
        printf("1\n0\n");
    }
    else
        printf("%d\n%d\n",ans,max(sum,ans));
    /* if(sum == 1){ */
    /*     sum = 0; */
    /*     for(int i = 1;i <= n;i++){ */
    /*         if(InComponent[i]==ans){ */
    /*             sum++; */
    /*         } */
    /*     } */
    /*     printf("%d\n",sum); */
    /* } */
    /* else{ */
    /*     printf("0\n"); */
    /* } */
}

int main()
{
    init();
    input();
    solve();
    return 0;
}

tarjan求强连通分量并缩点建图+dag有向无环图的dp问题去求解最大值 p3387

#include <stdio.h>
#include <string.h>
#include <vector>
#include <stack>
#include <iostream>
#define repu(i,a,b) for(int i=a;i<b;i++)
using namespace std;
#define N 10005            /// 题目中可能的最大点数
stack<int>sta;            /// 存储已遍历的结点
vector<int>gra[N];        /// 邻接表表示图
int dfn[N];        /// 深度优先搜索访问次序
int low[N];        /// 能追溯到的最早的次序
int InStack[N];  // 检查是否在栈中(2：在栈中，1：已访问，且不在栈中，0：不在)
vector<int> Component[N]; /// 获得强连通分量结果
int InComponent[N];          /// 记录每个点在第几号强连通分量里
int Index,ComponentNumber;/// 索引号，强连通分量个数
int n,m;          // 点数，边数
int chu[N];         //出度
int dianquan[N];   //初始点权
int dianquan2[N];   //缩点后点权
int dp[N];          //dag问题dp
int vis[N];
int ru[N];           //入度
int num[N]; //各个强连通分量包含点的个数,数组编号 1 ∼ scc
void init() //清空容器，数组
{

    memset(dp, 0, sizeof(dp));
    memset(vis, 0, sizeof(vis));
    memset(dianquan2, 0, sizeof(dianquan2));
    memset(dianquan ,0, sizeof(dianquan));
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(chu, 0, sizeof(chu));
    memset(InStack, 0, sizeof(InStack));
    Index = ComponentNumber = 0;
    for (int i = 1; i <= n; ++ i)
    {
        gra[i].clear();
        Component[i].clear();
    }
    while(!sta.empty())
        sta.pop();
}
void tarjan(int u)
{
    InStack[u] = 2;
    low[u] = dfn[u] = ++ Index;
    sta.push(u);///寻找u所在的强连通分量
    for (size_t i = 0; i < gra[u].size(); ++ i)
    {
        int t = gra[u][i];
        if (dfn[t] == 0)///不在的继续递归
        {
            tarjan(t);///递归到头了就
            low[u] = min(low[u], low[t]);
        }
        else if (InStack[t] == 2)///在栈里
        {
            low[u] = min(low[u], dfn[t]);
        }
    }
    if(low[u] == dfn[u])///sta出栈就是一个强连通分量的
    {
        ++ComponentNumber;///强连通分量个数
        while (!sta.empty())
        {
            int j = sta.top();
            sta.pop();
            InStack[j] = 1;///已访问但不在栈中
            /* Component[ComponentNumber].push_back(j); */
            ///用vector存储第ComponentNumber个强连通分量
            InComponent[j]=ComponentNumber;
            dianquan2[ComponentNumber]+=dianquan[j];
            ///记录每个点在第几号强连通分量里
            num[ComponentNumber]++;
            if (j == u)
                break;
        }
    }
}
void input()
{
    int x,y;
    scanf("%d%d",&n,&m);

    repu(i,1,n+1)
    {
        scanf("%d",&dianquan[i]);
    }

    repu(i,1,m+1)
    {
        scanf("%d%d",&x,&y);        
        gra[x].push_back(y);///有向图才有强连通分量
    }
}

int dfs(int u){

    if(dp[u]){
        return dp[u];
    }
    else{
        dp[u] = dianquan2[u];
        for(size_t i = 0;i < Component[u].size();i++){
            int y = Component[u][i];
            dp[u] = max(dp[u],dfs(y)+dianquan2[u]);
        }
        return dp[u];
    }
}
void solve()
{
    for(int i=1; i<=n; i++)
        if(!dfn[i])
            tarjan(i);
    //缩点
    for(int i = 1;i <= n;i++){
        for(size_t j = 0;j < gra[i].size();j++){
            if(InComponent[i] != InComponent[gra[i][j]]){
                //chu[InComponent[i]]++;//求出度
                //ru[InComponent[gra[i][j]]]++;//求入度
                Component[InComponent[gra[i][j]]].push_back(InComponent[i]); //缩点建图
            }
        }
    }
    int aans = 0;
    for(int i = 1;i <= ComponentNumber;i++){
        memset(dp,0,sizeof(dp));
        aans = max(dfs(i),aans);
        /* printf("%d ",dianquan2[i]); */
    }
    printf("%d\n",aans);
}

int main()
{
    init();
    input();
    solve();
    return 0;
}

p1656 tarjan求割边加排序

#include<cstdio> 
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

vector<pair<int,int>>bridge;
vector<int> g[10010];
int dfn[10010],low[10010];
int deep,root,n,m,ans;
bool cmp(pair<int,int> a,pair<int,int> b){
    if(a.first == b.first)
        return a.second < b.second;
    else
        return a.first < b.first;
}
int tarjan(int u,int fa)
{
    int lowu;
    lowu=dfn[u]=++deep;
    int sz=g[u].size();
    for(int i=0;i<sz;i++)
    {
        int v=g[u][i];
        if(!dfn[v])
        {
            int lowv=tarjan(v,u);
            lowu=min(lowu,lowv);
            if(lowv>dfn[u])
            {
                int from,to;
                from=u;
                to=v;
                if(from>to)
                {
                    swap(from,to);
                }
                bridge.push_back(make_pair(from,to));
            }
        }
        else
        {
            if(v!=fa&&dfn[v]<dfn[u])
            {
                lowu=min(lowu,dfn[v]);
            }
        } 
    }
    low[u]=lowu;
    return lowu;
} 

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int from,to;
        scanf("%d%d",&from,&to);
        g[from].push_back(to);
        g[to].push_back(from);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        {
            root=i;
            tarjan(i,-1);
        }
    }
    sort(bridge.begin(),bridge.end(),cmp);
    for(int i=0;i<bridge.size();i++)
    {
        printf("%d %d\n",bridge[i].first,bridge[i].second);
    }
}

p3388 tarjan求割点

#include<cstdio> 
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
vector<int> g[20010];
int dfn[20010],low[20010],iscut[20010],son[20010];
int deep,root,n,m,ans;
int tarjan(int u,int fa)
{
    int child=0,lowu;
    lowu=dfn[u]=++deep;
    int sz=g[u].size();
    for(int i=0;i<sz;i++)
    {
        int v=g[u][i];
        if(!dfn[v])
        {
            child++;
            int lowv=tarjan(v,u);
            lowu=min(lowu,lowv);
            if(lowv>dfn[u])
            {
                iscut[u]=1;
            }
        }
        else
        {
            if(v!=fa&&dfn[v]<dfn[u])
            {
                lowu=min(lowu,dfn[v]);
            }
        } 
    }
    if(fa<0&&child==1)
    {
        iscut[u]=false;
    }
    low[u]=lowu;
    return lowu;
} 

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int from,to;
        scanf("%d%d",&from,&to);
        g[from].push_back(to);
        g[to].push_back(from);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            root=i;
            tarjan(i,-1);
        }
    }
    for(int i=1;i<=n;i++){
        if(iscut[i]){
            ans++;
        }
    }
    printf("%d\n",ans);
    for(int i=1;i<=n;i++){
        if(iscut[i]){
            printf("%d ",i);
        }
    }
}

HDU - 1712分组背包

#include <bits/stdc++.h>
using namespace std;
long long dp[110];
long long f[110][110];
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)){
        memset(dp,0,sizeof(dp));
        memset(f,0,sizeof(f));
        if(n==0 && m==0)
            break;
        else{
            for(int i = 1;i <= n;i++){
                for(int j = 1;j <= m;j++){
                    scanf("%lld",&f[i][j]);
                }
            }

            for(int i = 1;i <= n;i++){
                for(int j = m;j > 0;j--){
                    for(int k = 1;k <= m;k++){
                        if(j>=k)
                            dp[j] = max(dp[j],dp[j-k]+f[i][k]);
                    }
                }
            }
            printf("%lld\n",dp[m]);
        }
    }

    return 0;
}

hdu2126 dp求最大方案个数

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
int dp[510],g[510],w[510];
int main(){
    int t,n,m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i = 1;i <= n;i++){
            scanf("%d",&w[i]);
        }
        for(int i = 1;i <= m;i++){
            g[i] = 0,dp[i] = -99999999;
        }
        g[0] = 1;
        dp[0] = 0;
        

        for(int i = 1;i <= n;i++){
            for(int j = m;j >= w[i];j--){
                int t = max(dp[j],dp[j-w[i]]+1);
                int s = 0;

                if(t == dp[j]) s += g[j];
                if(t == dp[j-w[i]]+1) s += g[j-w[i]];
                dp[j] = t;
                g[j] = s;
            }
        }

        int maxw = -1;
        for(int i = 0;i <= m;i++) maxw = max(maxw,dp[i]);
        int res = 0;
        for(int i = 0;i <= m;i++){
            /* printf("%d %d\n",g[i],dp[i]); */
            if(maxw == dp[i])
            {
                res += g[i];
            }
        }
        if(maxw == 0){
            printf("Sorry, you can't buy anything.\n");
        }
        else
            printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n",res,maxw);
    }

    return 0;
}