算法筆記【持續(xù)更新】

[TOC]

貪心

AcWing122.糖果傳遞^[1]

有n個小朋友坐成一圈，每人有a[i]個糖果。每人只能給左右兩人傳遞糖果庆聘。每人每次傳遞一個糖果代價為1。求使所有人獲得均等糖果的最小代價勺卢。

AC代碼：

#include<bits/stdc++.h>
using namespace std ;
typedef long long LL ;

const int N = 1E6 +10  ;
int n  ; 
int a[N] ;
LL c[N] ;

int main()
{
    cin >> n ;
    LL sum = 0; // 轉(zhuǎn)化成區(qū)間不等式的形式
    for(int i = 1; i <= n ; i ++ ) scanf("%d",&a[i]) , sum += a[i]; 
    LL avg = sum / n ;
    for(int i = n ; i > 1 ; i --  ) c[i] = c[i+1] + avg - a[i] ;
    c[1] = 0 ;
    sort(c+1 , c + n + 1 ) ;
    
    LL res = 0 ; // core code
    for(int i = 1 ; i <= n ; i ++ )  res += abs(c[i] - c[(n + 1 )/2]) ;
    cout << res << endl;

    return 0 ;
}

絕對值不等式解題策略

化為區(qū)間不等式的形式伙判。比較考驗(yàn)數(shù)學(xué)能力。

通過核心代碼求解

for(int i = 1 ; i <= n ; i ++ )  res +=  abs(c[i] - c[(n + 1 )/2]);

Acwing112 .雷達(dá)設(shè)備^[2]

假設(shè)海岸是一條無限長的直線黑忱，陸地位于海岸的一側(cè)宴抚，海洋位于另外一側(cè)。

每個小島都位于海洋一側(cè)的某個點(diǎn)上甫煞。

雷達(dá)裝置均位于海岸線上菇曲，且雷達(dá)的監(jiān)測范圍為d，當(dāng)小島與某雷達(dá)的距離不超過d時抚吠，該小島可以被雷達(dá)覆蓋常潮。

我們使用笛卡爾坐標(biāo)系，定義海岸線為x軸楷力，海的一側(cè)在x軸上方喊式，陸地一側(cè)在x軸下方孵户。

現(xiàn)在給出每個小島的具體坐標(biāo)以及雷達(dá)的檢測范圍，請你求出能夠使所有小島都被雷達(dá)覆蓋所需的最小雷達(dá)數(shù)目岔留。

#include<bits/stdc++.h>
using namespace std ;
const int N = 1010 ;
int n , d ;
struct Segment
{
    double l , r ;
    bool operator<(const Segment & s)const 
    {
        return r < s.r ;
    }
}seg[N] ;

int res = 0 ;
double aim = -1e20 ;

int main() 
{
    cin >> n >> d ;
    for(int i  = 0 ; i < n ; i ++ ) 
    {
        int x , y ;
        cin >> x >>y ;
        if(y > d) 
        {
            puts("-1") ; 
            goto Exit;
        }
        else 
        {
            double len = sqrt(d*d - y*y) ;
            seg[i] = {x - len , x + len } ;
        }
    }

    sort(seg , seg +n ) ;


    for(int i = 0 ; i < n ; i ++ ) 
    {
        if(aim < seg[i].l)
        {
            res ++ ;
            aim = seg[i].r ;
        }
    }
    cout << res << endl;

    Exit:
    return 0 ;
}

關(guān)于goto語句的使用說明：==當(dāng)出現(xiàn)goto跳過某些變量的初始化的時候夏哭，編譯器不允許通過。==務(wù)必小心献联。

區(qū)間貪心策略

首先把問題轉(zhuǎn)化成區(qū)間貪心竖配。（數(shù)據(jù)區(qū)間化，假設(shè)這里通過結(jié)構(gòu)體存儲）
將區(qū)間按照右端點(diǎn)排序里逆。選取aim為0xcfcfcfcf
遍歷每一個區(qū)間进胯。
- 如果當(dāng)前區(qū)間左端點(diǎn)大于aim，則aim更新當(dāng)前區(qū)間右端點(diǎn)运悲，res++
- 否則龄减，繼續(xù)遍歷下一區(qū)間
得到答案

付賬問題^[3]

幾個人一起出去吃飯是常有的事。

但在結(jié)帳的時候班眯，常常會出現(xiàn)一些爭執(zhí)。

現(xiàn)在有 n 個人出去吃飯烁巫，他們總共消費(fèi)了 SS 元署隘。

其中第 $i$ 個人帶了 $a_i$ 元。

幸運(yùn)的是亚隙，所有人帶的錢的總數(shù)是足夠付賬的磁餐，但現(xiàn)在問題來了：每個人分別要出多少錢呢？

為了公平起見阿弃，我們希望在總付錢量恰好為 SS 的前提下诊霹，最后每個人付的錢的標(biāo)準(zhǔn)差最小。

這里我們約定渣淳，每個人支付的錢數(shù)可以是任意非負(fù)實(shí)數(shù)脾还，即可以不是 1 分錢的整數(shù)倍。

你需要輸出最小的標(biāo)準(zhǔn)差是多少入愧。

p1.png

#include<bits/stdc++.h>
using namespace std ;
const int N = 5e5+10 ;
int n;
long double S ; 
int a[N] ;
int main()
{
    cin >>n >> S; 
    for(int i = 0; i < n ; i ++ ) 
    {
        scanf("%d",&a[i]) ;
    }
    sort(a,a+n) ;
    long double avg = S/n , res = 0 ;
    for(int i = 0 ; i < n ; i ++ ) 
    {
        long double cur = S/ (n -i) ;
        if(cur > a[i]) cur = a[i] ;
        res +=  (cur -avg)*(cur -avg) ;
        S -= cur ;
    }
    printf("%.4llf" ,sqrt(res / n ) ) ;
    return 0 ;
}

思路：按照==均攤==為標(biāo)準(zhǔn)鄙漏。 $cur$ 值動態(tài)更新。

cur為當(dāng)前需付金錢下棺蛛，每個人應(yīng)該付多少錢怔蚌。如果當(dāng)前人的錢a[i]不足cur，則此人的錢全部拿出旁赊，也就是a[i]桦踊；如果當(dāng)前人的錢a[i]大于cur，那么此人就優(yōu)先按照cur付錢终畅。

下一輪循環(huán)cur更新籍胯■伲可見，如果上一個人帶的錢小于上一輪的cur,那么當(dāng)前輪的cur數(shù)值一定會提高芒炼。

如果上一個人帶的錢大于等于cur瘫怜，那么當(dāng)前輪的cur還是上一輪的cur。

圖論

Dijkstra

思想：劃出兩個集合本刽，一個是存放已經(jīng)更新并且不再更新的結(jié)點(diǎn)的集合鲸湃，另一邊是沒有更新距離的結(jié)點(diǎn)的集合。每次從未更新的選出一個 $dist$ 最小的結(jié)點(diǎn)子寓，把它放進(jìn)第一個集合里去暗挑，然后對利用它對每一個未更新的結(jié)點(diǎn)更新，重復(fù)執(zhí)行斜友。
特點(diǎn)：使用堆進(jìn)行存儲pair炸裆，其中pair用來記錄dist和ver

int dijkstra()
{
    priority_queue<PII,vector<PII> , greater<PII>> heap ;
    heap.push({0,1}) ;  // 第一個是dist
    while(heap.size() )
    {
        auto t = heap.top() ;
        heap.pop() ;
        
        int ver = t.second , d = t.first ;    
        if(st[ver]) continue ;
        st[ver] = 1 ;
        
        
        for(int i = h[ver] ; ~i ; i = ne[i] ) 
        {
            int j = e[i] ;
            if(dist[j] >d + w[i]) 
            {
                dist[j] = d + w[i] ;
                heap.push({dist[j],j}) ;
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1 ;
    return dist[n] ;
}

SPFA

思想：當(dāng)前結(jié)點(diǎn) $v$ 入隊(duì)，計算其鄰居的最短距離鲜屏； $v$ 出隊(duì)烹看，把其==鄰居有狀態(tài)更新的結(jié)點(diǎn)==入隊(duì) ；重復(fù)執(zhí)行洛史。值得注意的是惯殊，之前已經(jīng)入過隊(duì)的結(jié)點(diǎn)也可能再入隊(duì)。
特點(diǎn)：使用普通隊(duì)列也殖，并且隊(duì)列存儲的是結(jié)點(diǎn)編號土思。

int spfa()
{
    queue<int> q ;
    q.push(1) ;
    st[1] = 1 ;
    while(q.size()) 
    {
        auto t = q.front() ;
        q.pop();
        st[t] = 0 ; // 和dijkstra不同的地方， st數(shù)組記錄：在隊(duì)列的結(jié)點(diǎn)編號忆嗜。所以出隊(duì)即可置零
        
        for(int i = h[t] ; ~i ; i = ne[i]) 
        {
            int j = e[i] ;
            if(dist[j] > dist[t] + w[i]) 
            {
                dist[j] = dist[t] + w[i]  ;
                if(!st[j])  // 不在隊(duì)列里面己儒，才加入隊(duì)列
                {
                    q.push(j) ;
                    st[j] = 1 ;
                }
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1 ;
    return dist[n] ;
}

搜索

偏移量不用過多思考，只是1,-1每兩個單位向后順移即可捆毫。

三維迷宮BFS

你現(xiàn)在被困在一個三維地牢中闪湾，需要找到最快脫離的出路！

地牢由若干個單位立方體組成冻璃，其中部分不含巖石障礙可以直接通過响谓，部分包含巖石障礙無法通過。

向北省艳，向南娘纷，向東，向西跋炕，向上或向下移動一個單元距離均需要一分鐘赖晶。

你不能沿對角線移動，迷宮邊界都是堅硬的巖石，你不能走出邊界范圍遏插。

請問捂贿，你有可能逃脫嗎？

如果可以胳嘲，需要多長時間厂僧？

每組數(shù)據(jù)第一行包含三個整數(shù) L,R,CL,R,C 分別表示地牢層數(shù)，以及每一層地牢的行數(shù)和列數(shù)了牛。

接下來是 LL 個 RR 行 CC 列的字符矩陣颜屠，用來表示每一層地牢的具體狀況。

每個字符用來描述一個地牢單元的具體狀況鹰祸。

其中, 充滿巖石障礙的單元格用”#”表示甫窟，不含障礙的空單元格用”.”表示，你的起始位置用”S”表示蛙婴，終點(diǎn)用”E”表示粗井。

每一個字符矩陣后面都會包含一個空行。

當(dāng)輸入一行為”0 0 0”時街图，表示輸入終止浇衬。

c++tuple的用法：(保險起見用struct代替)

typedef tuple<int,int,int> U3I ;  // 名稱重新定義
U3I tp[30] ;  // tuple 數(shù)組
tp[2] = {1,2,3} ;  // 賦值
cout << get<2>(tp[2])<< endl;  // 元素的獲取

//偏移量
int dx[] = {1,-1,0,0,0,0} ;
int dy[] = {0,0,1,-1,0,0} ;
int dz[] = {0,0,0,0,1,-1} ;


int bfs(Point sr) 
{
    queue<Point> q ;
    q.push(sr) ;
    memset(dist , -1 , sizeof dist) ;
    dist[sr.x][sr.y][sr.z] = 0 ;
    while(q.size()) 
    {
        auto t = q.front() ;
        q.pop() ;
        
        
        for(int i = 0 ; i < 6 ; i ++ )
        {
            int x = t.x + dx[i] ;
            int y = t.y + dy[i] ;
            int z = t.z + dz[i] ;
            // 過濾
            if(x < 0 ||x >= l || y < 0 || y >= r ||z < 0 || z >= c) continue ;
            if(dist[x][y][z] != -1 ) continue ;
            if(g[x][y][z] == '#') continue ;
            
            // 距離加一
            dist[x][y][z] = dist[t.x][t.y][t.z] +1 ;
            if(g[x][y][z] == 'E') return dist[x][y][z] ;
            //填充隊(duì)列
            q.push({x,y,z}) ;
            
        }
    }
    return -1 ;
}

二維迷宮BFS

阿爾吉儂是一只聰明又慵懶的小白鼠，它最擅長的就是走各種各樣的迷宮台夺。

今天它要挑戰(zhàn)一個非常大的迷宮径玖，研究員們?yōu)榱斯膭畎柤獌z盡快到達(dá)終點(diǎn)，就在終點(diǎn)放了一塊阿爾吉儂最喜歡的奶酪颤介。

現(xiàn)在研究員們想知道，如果阿爾吉儂足夠聰明赞赖，它最少需要多少時間就能吃到奶酪滚朵。

迷宮用一個 R×CR×C 的字符矩陣來表示。

字符 S 表示阿爾吉儂所在的位置前域，字符 E 表示奶酪所在的位置辕近，字符 # 表示墻壁，字符 . 表示可以通行匿垄。

阿爾吉儂在 1 個單位時間內(nèi)可以從當(dāng)前的位置走到它上下左右四個方向上的任意一個位置移宅，但不能走出地圖邊界。

第一行是一個正整數(shù) TT椿疗，表示一共有 TT 組數(shù)據(jù)漏峰。

每一組數(shù)據(jù)的第一行包含了兩個用空格分開的正整數(shù) RR 和 CC，表示地圖是一個 R×CR×C 的矩陣届榄。

接下來的 RR 行描述了地圖的具體內(nèi)容浅乔，每一行包含了 CC 個字符。字符含義如題目描述中所述。保證有且僅有一個 S 和 E靖苇。

//偏移量
int dx[] = {1,-1,0,0} 席噩；
int dy[] = {0,0,1,-1} ;

int bfs(PII st) 
{
    queue<PII> q ;
    q.push(st) ;
    memset(dist , -1 , sizeof dist ) ;
    dist[st.x][st.y] = 0 ; 
    while(q.size())
    {
        auto  tmp = q.front() ;
        q.pop() ;
        for(int i = 0 ; i < 4 ; i ++  ) 
        {
            int x = tmp.x + dx[i] , y = tmp.y + dy[i] ;
            //過濾
            if(x < 0 || x>= n || y < 0 || y >= m ) continue ;
            if(g[x][y] == '#' ) continue ;
            if(dist[x][y] != -1 ) continue ;
            //距離加一
            dist[x][y] = dist[tmp.x][tmp.y] + 1 ;
            if( g[x][y] == 'E') return dist[x][y] ;
            
            
            //填充隊(duì)列
            q.push({x,y}) ;
        }
    }
    return -1 ;
}

數(shù)論

歐幾里得算法

理論基礎(chǔ)： （a,b） == (a , a % b )
return b ? gcd(b,a% b):a;

更相減損術(shù)的變形

樸素的更相減損術(shù)是用來求最大公約數(shù)的，但效率是線性的贤壁，比歐幾里得算法效率低很多悼枢。然而該算法經(jīng)過改造變形，可以得到新的功能脾拆。

即馒索，輸入 $p^a$ 和 $p^b$ ，將返回 $p^{(a,b)}$

LL gcd_sub(LL a, LL b)
{
    if (a < b) swap(a, b); // 保證a > b 
    if (b == 1) return a;
    return gcd_sub(b, a / b);
}

算術(shù)基本定理

每個==大于1的自然數(shù)均可寫為質(zhì)數(shù)的積==假丧，而且這些素因子按大小排列之后双揪，寫法僅有一種方式。

線性篩素數(shù)

見理論整理文件包帚。線篩.pdf

void get_prm(int n)
{
    for(int i = 2 ; i <= n ; i ++ ) 
    {
        if(!st[i]) 
        {
            minp[i] = i ;
            prm[cnt++] = i ;
        }
        for(int j = 0 ; i * prm[j] <= n ; j ++ ) 
        {
            int t = prm[j] * i ;
            st[prm[j] * i ] = 1 ;
            minp[t] = prm[j] ;
            if(i % prm[j] == 0 ) break; 
        }
    }
}
/*
最后可以得到
prm數(shù)組 渔期， 記錄1-n中素數(shù)分別是多少
minp數(shù)組， minp[i] 記錄i的最小質(zhì)因子是多少
*/

分解質(zhì)因數(shù)

和get_prm() 搭配使用渴邦，建議直接背過疯趟。

//對x分解
int k = 0 , tol = 0 ;  // k是索引，tol記錄一共有多少個質(zhì)因數(shù)
while(x > 1) 
{
    int p = minp[x] ;  // 取出最小的質(zhì)因數(shù)
    fac[k] = p , sum[k] = 0; 
    while(x % p == 0 )
    {
        x /= p;
        sum[k] ++ ;  // p的質(zhì)因數(shù)個數(shù)
        tol ++ ;    
    }
    k ++ ;  //索引加一
}
/*
最后可以得到
fac數(shù)組谋梭，記錄x有什么質(zhì)因子
sum數(shù)組信峻，記錄每一個質(zhì)因子有幾個
tol   ，一共有多少個質(zhì)因子
*/

約數(shù)個數(shù)基本定理

$f(n)$ = $(a_1 +1)(a_2 +1)(a_3 +1)...(a_k +1)$ , 其中 $a_i$ 為質(zhì)因子的指數(shù)瓮床。

約數(shù)之和基本定理

$f(n)$ =

$(p_1^0 +p_1^1 +p_1^2+p_1^3 + ... + p_1^{a_1} )(p_2^0 +p_2^1 +p_2^2+p_2^3 + ... + p_1^{a_2})...(p_k^0 +p_k^1 +p_k^2+p_k^3 + ...+ p_1^{a_k} )$

質(zhì)數(shù)定理（用來大致評估時間復(fù)雜度）

見百度

裴蜀定理

若設(shè)a,b是整數(shù)盹舞，則存在整數(shù)x,y，使得 $ax+by=gcd（a,b）$ 隘庄，(a,b)代表最大公因數(shù)踢步，則設(shè)a,b是不全為零的整數(shù)，則存在整數(shù)x,y丑掺，使得 $ax+by=(a获印，b)$

有以下有用的結(jié)論：

==那么如果 $（a，b）= 1$ 時街州，a與b不能湊出來的最大數(shù)是 $（a-1）*（b-1）-1$ ==

2.如果給出n個數(shù)字兼丰，求算湊不出來的數(shù)字是多少，就是完全背包問題了唆缴。

#include<bits/stdc++.h>
using namespace std ;


const int N = 10010  ;


int n ;
int a[110] , f[110][N] ;


int gcd(int a, int b) 
{
    return b ? gcd(b , a%b) : a ;
}

int main()
{
    
    cin >> n ;
    int d  ;
    for(int i = 1 ; i <= n ; i ++ ) 
    {
        scanf("%d",&a[i]) ;
        d = gcd(d , a[i]) ;
    }
    if(d != 1 )   // 如果最大公因數(shù)不是1鳍征，肯定有無限個數(shù)字無法表示
    {
        puts("INF") ;
    }
    else// 如果最大公因數(shù)是1 ， 就做一遍完全背包
    {
        f[0][0] = 1 ;
        for(int i = 1 ; i <= n ; i ++ )
        {
            for(int j = 0 ; j < N; j ++ ) 
            {
                f[i][j] = f[i-1][j] ;
                if(j >= a[i]) f[i][j] |= f[i][j-a[i]];
            }
        }
        int res = 0 ;
        for(int i = 0 ; i < N ; i ++) 
        {
            if(!f[n][i]) res ++ ;
        }
        cout << res <<endl;
    }
    
    return 0 ;
}

擴(kuò)展歐幾里得算法

用來解決裴蜀定理琐谤，求解系數(shù) $x,y$

int exgcd(int a ,int b , int &x ,int &y) 
{
    if(!b)
    {
        x = 1 ;
        y = 0 ;
        return a ;
    }
    int d = exgcd(b,a%b,y,x)  ;
    y -= a /b * x ;
    return d ;
}

組合數(shù)

組合數(shù)初級(楊輝三角)

快速遞推組合數(shù),處理2000以內(nèi)沒有問題

$C_i^j=C_{i-1}^{j} + C_{i-1}^{j-1}$

//將c數(shù)組預(yù)處理成楊輝三角
for (int i = 0; i < N; i ++ )
    {
        for (int j = 0; j <= i; j ++ )
        {
            if (!j) c[i][j] = 1;
            else c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
        }
    }

組合數(shù)中級（快速冪求逆元）

處理 $10^5$ 級別的組合數(shù)問題

需要預(yù)處理階乘和階乘的逆元

#include<bits/stdc++.h>
using namespace std ;

const int N = 1E5+10 , mod = 1e9+7 ;
int fc[N] , ifc[N] ;
int qmi(int a ,int b ) 
{
    int res = 1 % mod ;
    while(b) 
    {
        if(b&1) res = res *1ll*a % mod ;
        a = a * 1ll * a  % mod ; 
        b >>= 1 ;
    }
    return res ;
}

int main() 
{
    fc[0] = ifc[0] = 1 ;
    for(int i= 1 ; i <N ; i ++ ) 
    {
        fc[i] = fc[i-1] * 1ll *i % mod ;
        ifc[i] = ifc[i-1] * 1ll * qmi(i ,  mod -2 )  % mod ; 
    }
    
    int n;
    cin >> n ;
    for(int i = 0 ; i < n ; i ++ ) 
    {
        int a , b ;
        scanf("%d%d",&a,&b) ;
        printf("%d\n",fc[a] * 1ll * ifc[b] % mod * ifc[a-b] % mod) ;
    }
    return 0 ;
    
}

組合數(shù)高級(Lucas定理)

單獨(dú)命題的話蟆技，極可能是單獨(dú)考察數(shù)學(xué)知識，不太可能和其他題目組合琢岩。

略

DP

AcWing1050 鳴人的影分身（線性）^ 線性Dp

在火影忍者的世界里翎苫，令敵人捉摸不透是非常關(guān)鍵的。

我們的主角漩渦鳴人所擁有的一個招數(shù)——多重影分身之術(shù)——就是一個很好的例子咳短。

影分身是由鳴人身體的查克拉能量制造的眶蕉，使用的查克拉越多砰粹，制造出的影分身越強(qiáng)。

針對不同的作戰(zhàn)情況造挽，鳴人可以選擇制造出各種強(qiáng)度的影分身碱璃，有的用來佯攻，有的用來發(fā)起致命一擊饭入。

那么問題來了嵌器，假設(shè)鳴人的查克拉能量為 M，他影分身的個數(shù)最多為 N谐丢，那么制造影分身時有多少種不同的分配方法爽航？

注意：

影分身可以分配0點(diǎn)能量。
分配方案不考慮順序乾忱，例如：M=7,N=3讥珍，那么 (2,2,3)和 (2,3,2) 被視為同一種方案。

思路: i 枚舉需要的能量窄瘟，j 枚舉分身個數(shù)衷佃。

#include<bits/stdc++.h>
using namespace std ;

const int N = 15; 
int T ;
int m , n ;
int f[N][N] ;
int main() 
{
    cin >>T ;
    while(T--) 
    {
        scanf("%d%d",&m,&n) ;
        
        f[0][0] = 1 ;
        for(int i = 0 ; i <= m ; i ++ ) 
        {
            for(int j = 1 ; j <= n ; j ++   )
            {
                f[i][j] = f[i][j - 1] ;
                // 每次必定可以有一個0能量的分身，所以f[i][j] 可以從f[i][j-1] 轉(zhuǎn)化來
                
                
                // 如果新的分身不是0能量的 蹄葱， f[i][j] 的方案數(shù) 其實(shí)包含  f[i-j][j]
                // 也就是把每個分身的能量減一 氏义， 把一個子集映射成已經(jīng)求解的子集去
                if(i >= j ) f[i][j] += f[i-j][j] ;
            }
        }
        cout << f[m][n] <<endl;
    }

    return 0 ;
}

AcWing1222 密碼脫落（區(qū)間）^ 區(qū)間Dp

X星球的考古學(xué)家發(fā)現(xiàn)了一批古代留下來的密碼。

這些密碼是由A图云、B觅赊、C、D 四種植物的種子串成的序列琼稻。

仔細(xì)分析發(fā)現(xiàn)，這些密碼串當(dāng)初應(yīng)該是前后對稱的（也就是我們說的鏡像串）饶囚。

由于年代久遠(yuǎn)帕翻，其中許多種子脫落了，因而可能會失去鏡像的特征萝风。

你的任務(wù)是：

給定一個現(xiàn)在看到的密碼串嘀掸，計算一下從當(dāng)初的狀態(tài)，它要至少脫落多少個種子规惰，才可能會變成現(xiàn)在的樣子睬塌。

思路：運(yùn)用了集合覆蓋思想，適用于求最值。

#include<bits/stdc++.h>
using namespace std ;
const int  N = 1010 ;
string str ;
int f[N][N] ;
int main()
{
    cin >> str ;
    int n = str.length() ;
    for(int len = 1 ; len <= n ; len ++ )
    {
        for(int l = 0 ; l + len - 1 < n ; l ++ ) 
        {
            int r = l + len -1 ;
            if(len == 1) f[l][r] = 1 ;
            else 
            {
                if(str[l] == str[r] ) f[l][r] = f[ l +1 ][r -1 ] + 2 ;
                f[l][r] = max(f[l][r] , f[l +1 ][r ]) ;
                f[l][r] = max(f[l][r] , f[l    ][r -1 ]) ;
            }
        }
    }
    cout <<  n - f[0][n-1] << endl;
    return 0 ;
    
}

模板部分

memset(f,0,sizeof f);//初始dp數(shù)組
for(int len = 1 ; len <= n ; len ++ ){//枚舉區(qū)間長度
    for(int l = 0 ; l + len - 1 < n ; l ++){//枚舉區(qū)間的起點(diǎn)
        int r = l + len -1 ;//根據(jù)起點(diǎn)和長度得出終點(diǎn)
        if(r>n) break;//符合條件的終點(diǎn)
        for(int k=l;k<=r;++k)//枚舉最優(yōu)分割點(diǎn)
            dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+w[l][r]);//狀態(tài)轉(zhuǎn)移方程
    }
}

Acwing 1220. 生命之樹（樹形）^ 樹形Dp

在X森林里揩晴，上帝創(chuàng)建了生命之樹勋陪。

他給每棵樹的每個節(jié)點(diǎn)（葉子也稱為一個節(jié)點(diǎn)）上，都標(biāo)了一個整數(shù)硫兰，代表這個點(diǎn)的和諧值诅愚。

上帝要在這棵樹內(nèi)選出一個非空節(jié)點(diǎn)集 S，使得對于 S 中的任意兩個點(diǎn) a,b劫映，都存在一個點(diǎn)列 {a,v1,v2,…,vk,b} 使得這個點(diǎn)列中的每個點(diǎn)都是 S 里面的元素违孝，且序列中相鄰兩個點(diǎn)間有一條邊相連。

在這個前提下泳赋，上帝要使得 SS 中的點(diǎn)所對應(yīng)的整數(shù)的和盡量大雌桑。

這個最大的和就是上帝給生命之樹的評分。

經(jīng)過 atm 的努力祖今，他已經(jīng)知道了上帝給每棵樹上每個節(jié)點(diǎn)上的整數(shù)校坑。

但是由于 atm 不擅長計算，他不知道怎樣有效的求評分衅鹿。

他需要你為他寫一個程序來計算一棵樹的分?jǐn)?shù)撒踪。

==簡單來說就是求連通塊的最大權(quán)值==

思路：關(guān)鍵是存圖，遞歸大渤。抓住狀態(tài)轉(zhuǎn)移是傳遞性的制妄。

#include<bits/stdc++.h>
using namespace std ;

const int N = 1E5+ 10 , M = 2*N ;

typedef long long LL ;

int n ;
LL  f[N] ;
int w[N] ,h[N], e[M] ,ne[M] , idx ;

void add(int a ,int b )
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ;
}

void dfs(int u , int a)
{
    f[u] = w[u] ;
    for(int i = h[u] ; ~i ; i = ne[i]) 
    {
        int j = e[i] ;
        if(j != a) 
        {
            dfs(j , u ) ;
            f[u] += max(0ll, f[j]) ;
        }
    }
    
}

int main() 
{
    
    memset(h ,-1,sizeof h );
    cin >> n ;
    for(int i = 1 ; i <= n ; i ++ )
    {
        scanf("%d",&w[i]) ;
    }
    for(int i = 0; i < n-1 ; i ++ ) 
    {
        int a,b ;
        scanf("%d%d",&a,&b) ;
        add(a,b) , add(b,a) ;
    }   
    dfs(1,-1) ;
    LL res = f[1] ;
    for(int i = 2 ; i <= n ; i ++ ) res = max(res , f[i]) ;
    cout << res << endl;
    return 0 ;
}

疑難雜題

并查集的另類用法

日期類題目

判斷日期是否合法

int months[13] ={0,31,28,31,30,31,30,31,31,30,31,30,31} ;
bool check(int year , int month , int day ) 
{
    if(month == 0 || month > 12 ) return 0 ;
    if(day == 0 ) return 0 ;
    if(month != 2 ) 
    {
        if(day > months[month]) return 0 ;
    }
    else 
    {
        int leap = year % 4 == 0 && year % 100 || year %400 == 0 ;
        if(day > months[month] + leap) return 0 ;
    }
    return 1 ;
}
int main()
{
     //枚舉日子
    for(int date = 19600101 ; date <= 20591231 ; date ++)    
    {
        int year = date /10000 , month = date % 10000 / 100 ,day = date % 100 ;
        if(check(year , month , day)) 
        {
           //題目需要的操作/
        }                                                      
    } 
}

刁鉆的輸入

這里重點(diǎn)學(xué)習(xí)sscanf的用法

#include<bits/stdc++.h>
using namespace std ;

int get_seconds(int h , int m , int s )
{
    return h * 3600 + m * 60 + s ;
}

int get_time() 
{
    string line ;
    getline(cin , line ) ;
    
    if(line.back() != ')' ) line +=  " (+0)" ;
    
    int h1 , m1 , s1 , h2,  m2,  s2  , d  ; 
    
    sscanf(line.c_str() , "%d:%d:%d %d:%d:%d (+%d)" , &h1,&m1,&s1 , &h2,&m2,&s2 , &d) ;
    
    return get_seconds(h2,m2,s2) - get_seconds(h1,m1,s1)  + d *24*3600 ;
} 
int main() 
{
    int n ;
    scanf("%d",&n) ;
    getchar() ;
    while(n--) 
    {
        int time = (get_time() + get_time() ) /2 ;
        int hour = time / 3600 , minute = time % 3600 / 60 , second = time % 60 ;
        printf("%02d:%02d:%02d\n"  , hour , minute , second ) ;
    }
    
    return 0 ;

}

按照==月份==來枚舉==星期==

十三號星期五真的很不常見嗎？

每個月的十三號是星期五的頻率是否比一周中的其他幾天低泵三？

請編寫一個程序耕捞，計算 N 年內(nèi)每個月的 1313 號是星期日，星期一烫幕，星期二俺抽，星期三，星期四较曼，星期五和星期六的頻率磷斧。

測試的時間段將會開始于 $1900$ 年 11 月 11 日，結(jié)束于 $1900+N?1$ 年 12 月 31日

輸出格式：

共一行捷犹，包含七個整數(shù)弛饭，整數(shù)之間用一個空格隔開，依次表示星期六萍歉，星期日侣颂，星期一，星期二枪孩，星期三憔晒，星期四藻肄，星期五在十三號出現(xiàn)的次數(shù)。

#include<bits/stdc++.h>
using namespace std ;
int n ;
int months[] = {0,31,28,31,30,31,30,31,31,30,31,30,31} ;
int weekdays[7] ; 
int main()
{
    cin >> n ;
    
    int day = 0 ;
    for(  int year = 1900  ; year  <  1900 +n  ; year ++ )
    {
        for(int month = 1 ; month < 13 ; month ++) 
        {
            weekdays[(day + 12 )% 7] ++ ;
            
            day += months[month] ;  // 只維護(hù)day
            if(month == 2) 
            {
                day += (year % 400  ==  0 || year % 100 && year % 4 == 0 ) ;
            }
        }
    }
    
    for(int i = 5 , j = 0 ; j < 7 ;  i = (i+1) % 7 , j ++) 
    {
        printf("%d ",weekdays[i] ) ;
    }
    return 0 ;
}

4.按==日子==枚舉==星期==（比枚舉月份慢）

題目如上

#include<bits/stdc++.h>
using namespace std ;

int n ;
int months[] = {0,31,28,31,30,31,30,31,31,30,31,30,31} ;
int weekdays[7] ; 

int get(int year , int month ) 
{
    if(month != 2) 
    {
        return months[month] ;
    }
    else
    {
        return 28 + (year % 400 == 0 || year % 100 && year % 4 == 0 ) ;
    }
}

int main()
{
    cin >> n ;

    int week = 0 ;
    int year = 1900 , month = 1 , day = 1 ;
    while(year < 1900 + n ) 
    {
        if(day == 13 ) weekdays[week] ++ ;
        
        
        week = (week + 1 ) % 7 ; // 實(shí)時更新week和day
        day ++ ;
        
        if(get(year ,month) < day) day =  1 , month ++ ;  // 按需更新month和day
        if(month > 12) year ++  , month =1 ;  // 按需更新year和month
    }

    for(int i = 5 , j = 0 ; j < 7 ;  i = (i+1) % 7 , j ++) 
    {
        printf("%d ",weekdays[i] ) ;
    }

    return 0 ;
}

基礎(chǔ)算法

求逆序?qū)Γw并）

利用歸并的思想拒担，和歸并排序的代碼基本沒有區(qū)別.

以下是void返回類型的代碼嘹屯。

#include<bits/stdc++.h>
using namespace std ;
typedef long long LL ;
const int N = 1E5+10 ;
int q[N] ;
int tmp[N]  ;
LL res ;
void merge(int q[] , int l ,int r ) 
{
    if(l >= r ) return ;
    int mid = l + r >> 1 ;
    merge(q ,l,mid) , merge(q ,mid +1 ,r) ;
    int i = l , j = mid + 1 , k = 0 ;
    while(i <= mid && j <= r) 
    {
        if(q[i] <= q[j] ) tmp[k++] = q[i++] ;
        else
        {
            tmp[k++] = q[j++] ;
            res += mid - i + 1 ; // 核心
        }
    }
    while(  i <= mid ) tmp[k++] = q[i++ ] ;
    while(  j <= r  ) tmp[k++] = q[j++ ] ;
    
    for(int i = l , j = 0 ; i <= r ; i ++ , j ++ ) q[i] = tmp[j] ;
} 
int main() 
{
    int n ;
    cin >> n ;
    for(int i = 0 ; i < n ; i ++ ) scanf("%d",&q[i]) ;
    merge(q,0,n-1) ;
    cout << res << endl;
    return 0 ;
}

總結(jié)：

前綴和的代碼更好理解，只需要開個數(shù)組澎蛛，背個公式抚垄，直接出來了

差分的代碼需要寫個函數(shù)，特地構(gòu)造一下谋逻。構(gòu)造思路是和前綴和反過來的呆馁。

前綴和思想是“考慮前面”，該減減毁兆，該加加浙滤。（結(jié)合一維二維原理圖）

差分的思想是“考慮后面”，該減減气堕，該加加纺腊。（結(jié)合一維二維原理圖）

形成了一個如下的關(guān)系：

差分?jǐn)?shù)組 <----> 原生數(shù)組 <----> 前綴和數(shù)組

一維前綴和模板

輸入一個長度為n的整數(shù)序列。

接下來再輸入m個詢問茎芭，每個詢問輸入一對l, r揖膜。

對于每個詢問，輸出原序列中從第l個數(shù)到第r個數(shù)的和梅桩。

//s數(shù)組是a數(shù)組的前綴和
for(int i = 1 ; i <= n ; i ++ ) 
{
    s[i] = s[i-1] + a[i] ; // 或者a[i] += a[i-1] ; 把a(bǔ)自己變成自己的前綴和
}

一維差分模板

輸入一個長度為n的整數(shù)序列壹粟。

接下來輸入m個操作，每個操作包含三個整數(shù)l, r, c宿百，表示將序列中[l, r]之間的每個數(shù)加上c趁仙。

請你輸出進(jìn)行完所有操作后的序列。

//構(gòu)造a的差分?jǐn)?shù)組b
void insert(int l ,int r ,int x) 
{
    b[l] += x ;
    b[r+1] -= x ;
}
//還原數(shù)組a垦页，并輸出數(shù)組a
for(int i= 1 ; i <= n ; i ++ ) 
{
    a[i] = a[i-1] + b[i] ;  // 這也是b的定義  a[i] = b[1] + b[2] + b[...] + b[i]
    cout << a[i] <<  " " ;
}
------------------------------------------------------------------
//把源數(shù)組變成自己的差分 
//方式1 ： 回倒法
for(int i = n ; i ; i --) 
{
    b[i] -= b[i-1] ;
}
//方式2 ： 封裝函數(shù)
for(int i  = 1 ; i <= n ; i ++ ) 
{
    int tmp ;
    cin >> tmp ;
    insert(b,i,i,tmp) ;
} 
//我提這兩種方式的原因是想提起注意雀费，差分的構(gòu)造不可以在讀取數(shù)據(jù)后直接在原數(shù)組構(gòu)造，這和前綴和不一樣Ｈ浮Ｕ蛋馈！

二維前綴和

輸入一個n行m列的整數(shù)矩陣薄啥，再輸入q個詢問貌矿，每個詢問包含四個整數(shù)x1, y1, x2, y2，表示一個子矩陣的左上角坐標(biāo)和右下角坐標(biāo)罪佳。

對于每個詢問輸出子矩陣中所有數(shù)的和。

//s數(shù)組是a數(shù)組的前綴和
for(int i = 1 ; i <= n ; i ++ ) 
{
    for(int j = 1 ; j <= m ; j ++) 
    {
        s[i][j] = s[i-1][j] + s[i][j-1] - s[i - 1][j - 1] + a[i][j] ; 
    }
}

二維差分模板

輸入一個n行m列的整數(shù)矩陣黑低，再輸入q個操作赘艳，每個操作包含五個整數(shù)x1, y1, x2, y2, c酌毡，其中(x1, y1)和(x2, y2)表示一個子矩陣的左上角坐標(biāo)和右下角坐標(biāo)。

每個操作都要將選中的子矩陣中的每個元素的值加上c蕾管。

請你將進(jìn)行完所有操作后的矩陣輸出枷踏。

//構(gòu)造a數(shù)組的差分矩陣b
void insert(int x1 , int y1 , int x2 , int y2 , int x) 
{
    b[x1][y1] += x ;
    b[x2 +1][y1] -= x ;
    b[x1][y2 + 1] -= x ;
    b[x2 +1 ][y2 +1 ] += x ;
}
//還原a數(shù)組，并輸出a的元素
 for(int i = 1 ; i <= n ; i ++ ) 
 {
     for(int j = 1 ; j <= m ; j ++ ) 
     {
         a[i][j] = a[i-1][j] + a[i][j-1]  - a[i-1][j-1] + b[i][j] ;  // b的定義
         cout << a[i][j] << " " ;
     }
     puts("");
 }

求樹的直徑

樹的直徑：樹中所有最短路徑距離的最大值即為樹的直徑

思路：隨便找一個點(diǎn)掰曾，求一遍最遠(yuǎn)路旭蠕，得到最遠(yuǎn)點(diǎn)v，從v出發(fā)再求一遍最遠(yuǎn)路旷坦，得到的就是樹的直徑掏熬。

//在樹的背景下，從任意一點(diǎn)出發(fā)秒梅，計算其他點(diǎn)到該點(diǎn)的距離
//（這種路徑是唯一的旗芬，所以dist也可以看成是“最短路”）
void dfs(int u , int father , int dis)
{
    dist[u] = dis ;
    for(int i = h[u] ; ~i ; i = ne[i])
    {
        int j = e[i] ;
        if( j != father) 
        {
            dfs(j,u,dist[u] + w[i]) ;
        }
    }
}

RMQ問題

1.ST算法 (所需時間是線段樹時間的一半)

2.簡單的線段樹（略）

// 注意一點(diǎn)：初始數(shù)據(jù)的讀入，下標(biāo)從1開始
void st_rmq()
{
    for(int j =  0 ; j < M ; j ++ ) 
    {
        for(int i = 1 ; i +(1 << j) -1 <= n ; i ++ ) 
        {
            if(!j) f[i][j] = w[i] ;
            else f[i][j] = max(f[i][j -1 ] , f[i+(1 << j -1 )][j -1]) ;
        }
    }
}

int query(int l , int r) 
{
    int k = log(r - l +1) / log(2) ;
    return max(f[l][k] , f[r - ( 1 << k ) +1 ][k]) ;   
    // f[r - ( 1 << k ) +1 ][k] 要注意一下捆蜀，第一維最后加一千萬別忘了
}

模擬散列表

開放尋址

拉鏈

//開放尋址 
//返回值k有兩種含義  1.若存在疮丛，就返回存放地址  2. 若不存在，就返回將要存放的地址
int find(int x)
{
    int k = (x% N + N)% N ;
    
    while(h[k] != null && h[k] != x) 
    {
        k ++ ;
        if(k == N ) k = 0 ;
    }
    return k ;
}

// 拉鏈法
//需要兩個函數(shù)搭配使用辆它，一個是添加函數(shù)誊薄， 一個是查詢函數(shù)
void add(int a) 
{
    int k = (a % N + N) % N ;
    e[idx] = a , ne[idx] = h[k] , h[k] = idx ++ ;
}
bool query(int a) 
{
    int k = (a % N + N) % N ;
    for(int i = h[k] ; ~i ; i = ne[i]) 
    {
        int j = e[i] ;
        if(j == a) 
        {
            return 1 ;
        }
    }
    return 0 ;
}

以上兩種任選。

楊輝三角(解決2000以內(nèi)的組合數(shù)問題)

快速遞推組合數(shù),用于預(yù)處理

$C_i^j=C_{i-1}^{j} + C_{i-1}^{j-1}$

//將c數(shù)組預(yù)處理成楊輝三角
for (int i = 0; i < N; i ++ )
    {
        for (int j = 0; j <= i; j ++ )
        {
            if (!j) c[i][j] = 1;
            else c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
        }
    }

二叉樹思想解決一般遞歸問題

考慮一種簡單的正則表達(dá)式：

只由 x ( ) | 組成的正則表達(dá)式锰茉。

小明想求出這個正則表達(dá)式能接受的最長字符串的長度呢蔫。

例如 ((xx|xxx)x|(x|xx))xx 能接受的最長字符串是： xxxxxx，長度是6洞辣。

ACwing 正則問題具有代表性

#include<bits/stdc++.h>
using namespace std ;

int k ;
string str ;
int dfs()
{
    int res = 0 ;
    while(k < str.size())
    {
        if(str[k] == '(') 
        {
            k ++ ;
            res += dfs() ;
            k ++ ;
        }
        else if(str[k] == '|') 
        {
            k ++ ;
            res = max(res , dfs()) ;
        }
        else if(str[k] == ')' )
            break; 
        else 
        {
            k ++ ;
            res ++ ;
        }
    }
    return res ;
}

int main()
{
    cin >> str ;
    cout << dfs() << endl;
    return 0 ;
}

十進(jìn)制向任意進(jìn)制轉(zhuǎn)化

使用短除法

// n : 待轉(zhuǎn)化的數(shù)字
// k : 進(jìn)制基數(shù)
char get(int n ) 
{
    if( n <= 9) return n + '0' ;
    if(n>= 10) return n -10 +'A' ;
}
string base(int n , int k ) 
{
    string num ;
    while(n) num += get(n % k) , n /= k ;
    reverse(num.begin()  , num.end());
    return num ;
}

秦九韶算法咐刨，其他進(jìn)制向十進(jìn)制轉(zhuǎn)化

int uget(char c) // char -> int 
{
    if(c <= '9') return c-'0' ;
    return c-'A' +10 ;
}

//秦九韶 ， 把任意k進(jìn)制化成十進(jìn)制
int base10(string num ,int k) 
{
    int res = 0 ;
    for(auto c : num) 
    {
        res = res * k + uget(c) ;
    }
    return res ;
}

a進(jìn)制化成b進(jìn)制（直接轉(zhuǎn)化）

未完待續(xù)

string回文判斷

string tmp = num ;
reverse(num.begin() , num.end()) ;
if( tmp == num)
{
    // 是回文
}

/**
判斷數(shù)字是否是回文
可以使用to_string()將其轉(zhuǎn)化成string扬霜，再通過reverse判斷

實(shí)數(shù)二分和整數(shù)二分的習(xí)題對比

兩道題目的例題背景類似：

求解最優(yōu)化問題定鸟，直接求解很困難，可以將其轉(zhuǎn)化成一個 ==判定== 問題著瓶，在答案的取值范圍內(nèi)搜尋答案即可联予。

//實(shí)數(shù)二分
double l = 0 , r = 1e9 ;
while( r - l > 1e-4) 
{
    double mid = (r + l)/2 ;
    if(check(mid)) l = mid ;
    else r = mid ;
}


//整數(shù)二分

// 找左邊界
int l = 1, r = 1e5;
while (l < r)
{
    int mid = l + r + 1 >> 1;
    if (check(mid)) l = mid;   // 答案在右邊，把l向右推
    else r = mid - 1;
}

// 找右邊界
int l = 1 , r = 1e5 ;
while(l < r) 
{
    int mid = l + r >> 1 ;
    if(check(mid)) r = mid ;  // 答案在左邊材原，把r向左推
    else l = mid +1 ;
}

區(qū)間合并

區(qū)間合并不是指區(qū)間真的合并在一起沸久，嚴(yán)格來講，他只是一種比較聰明的區(qū)間枚舉方式（區(qū)間滿足有序）

sort(sg , sg + n) ;
int sum = 0 ;
int L = sg[0].x , R =sg[0].y ;
for(int i = 1 ; i < n ; i ++) 
{
    if(sg[i].x <= R) R = max(sg[i].y , R) ;    // 區(qū)間有重疊余蟹，更新右端點(diǎn)
    else
    {
        sum += R-L+1 ;  // 區(qū)間長度累加
        L= sg[i].x , R = sg[i].y ;  // 新區(qū)間沒重疊卷胯，全部更新
    }
}
sum += R - L + 1 ;  // 最后一段更新的區(qū)間在循環(huán)外更新
//sum累加不重合的區(qū)間總共長度

從對稱矩陣的角度去遍歷二維數(shù)組矩陣

for(int i = 1 ; i <= n ; i ++ )  // 遍歷行
{
    for(int j= i , k = 1 ; j <= n ; j ++ , k++  ) 
    {
        a[i][j] = k ;
        a[j][i] = k ;
    }
}
// 注意i，j的變化

N皇后問題

給定一個 N×NN×N 的棋盤威酒，請你在上面放置 NN 個棋子窑睁，要求滿足：

每行每列都恰好有一個棋子

每條對角線上都最多只能有一個棋子

#include<bits/stdc++.h>
using namespace std ;
const int N = 15 ;
int ans , n ;
int path[N] ;
bool col[N],dg[N*2],udg[N*2] ;
void dfs(int x) 
{
    if(x > n )
    {
        ans ++ ;
        if(ans <=3)  // 將前三個答案輸出
        {
            for(int i = 1 ; i <= n ; i ++ ) 
            {
                printf("%d ",path[i]) ;
            }
            cout << endl;
        }
    }
    for(int y = 1 ; y <= n ; y ++ )  // 遍歷列
    {
        if(!col[y] && !dg[x+y] && !udg[x-y+n]) 
        {
            path[x] = y ;
            col[y] = dg[x+y] = udg[x-y+n] = 1 ;
            dfs(x+1) ;
            path[x] = 0 ;
            col[y] = dg[x+y] = udg[x-y+n] = 0 ;
        }
    }
}
int main() 
{
    cin >> n ;
    dfs(1) ;
    cout <<ans << endl;
    return 0 ;
}

手寫next_permutation()

#include<bits/stdc++.h>

using namespace std;

const int N = 10010;

int n, m;
int w[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> w[i];
    while (m -- )  // 從最小字典序的序列算起第m個
    {
        int k = n;
        while (w[k - 1] > w[k]) k -- ;  // 從后找到尖峰
        int t = k;
        while (w[t + 1] > w[k - 1]) t ++ ; // 尖峰到末尾第一個大于w[k-1]的挺峡，進(jìn)行交換
        swap(w[k - 1], w[t]);
        reverse(w + k, w + n + 1);  // 尖峰到最后逆置
    }
    for (int i = 1; i <= n; i ++ ) cout << w[i] << ' ';
    cout << endl;

    return 0;
}

/**
while (m -- )  // 從最小字典序的序列算起第m個
{
    int k = n;
    while (w[k - 1] > w[k]) k -- ;  // 從后找到尖峰
    int t = k;
    while (w[t + 1] > w[k - 1]) t ++ ; // 尖峰到末尾第一個大于w[k-1]的，進(jìn)行交換
    swap(w[k - 1], w[t]);
    reverse(w + k, w + n + 1);  // 尖峰到最后逆置
}
等價于
while (m -- )  // 從最小字典序的序列算起第m個
{
    next_permutation(w+1 , w+n+1) ; // w下標(biāo)從1開始的
}
*/

Trie樹

維護(hù)一個字符串集合担钮，支持兩種操作：

“I x”向集合中插入一個字符串x橱赠；

“Q x”詢問一個字符串在集合中出現(xiàn)了多少次。

共有N個操作箫津，輸入的字符串總長度不超過 $10^5$ 狭姨，字符串僅包含小寫英文字母。

模型1：存儲字符串

#include<bits/stdc++.h>
using namespace std ;

const int N = 100010  ;

int  tr[N][26]  ,cnt[N]  ,  idx ;
char str[N] ;


void insert()
{
    int p = 0 ;
    for(int i = 0 ; str[i] ; i++ )
    {
        int u = str[i] - 'a' ;
        if(!tr[p][u]) tr[p][u] = ++ idx ; 
        p = tr[p][u] ;
    }
    cnt[p] ++ ;
}


int query()
{
    int p = 0 ;
    for(int i  = 0 ; str[i] ; i ++ )
    {
        int  u = str[i] - 'a' ;
        if(!tr[p][u]) return 0  ;
        p = tr[p][u] ;
    }
    return cnt[p] ;
}



int main()
{
    int n ;
    cin >> n ;
    while(n-- )
    {
        char op[2] ;
        cin >> op >> str ;
        if(*op == 'I') insert() ;
        else cout << query() << endl;
        
    }
    
    return 0 ;
}

模型2 ：存儲數(shù)字的二進(jìn)制形式

#include<bits/stdc++.h>
using namespace std ;

const int N = 1e5+10  , M = 21* N;
int n ;
int s[N] ;
int son[M][21] , bound[M] , idx; 

void insert(int x , int l )   // insert函數(shù)是大同小異的
{
    int p = 0  ;
    for(int i = 20 ; i >= 0 ; i --)   // 最大數(shù)字的二進(jìn)制形式是20位的
    {
        int u = x >>  i & 1 ;
        if(!son[p][u]) son[p][u] = ++idx ;
        p = son[p][u] ; 
    }
    bound[p] = l ;
}

int query(int x)   // query是因題而異的
{
    int p = 0  ;
    for(int i = 20 ; i >= 0 ; i --) 
    {
        int u = x >>  i & 1 ;
        if(son[p][!u])  p  =son[p][!u]  ;
        else p = son[p][u] ; 
    }
    return bound[p] ;   
}


int main() 
{
    cin >> n ;
    for(int i = 1 ; i <= n ; i ++ ) 
    {
        scanf("%d",&s[i]) ;
        s[i] ^= s[i-1] ; 
    }

    insert(s[0] , 0) ;
    int res = -1 ,  l , r ;
    for(int i =1 ; i <= n ; i ++ ) 
    {
        int left = query(s[i]) ;
        int t = s[i] ^ s[left] ;
        if(t > res) 
        {
            res = t ;
            l = left +1  ;
            r =  i ;
        }
        insert(s[i] , i ) ; 
    }
    printf("%d %d %d\n" , res , l,r ) ;


    return 0 ;
}

快速冪模板

$m{^k}\%p$

int qmi(int m, int k, int p)   
{
    int res = 1 % p;
    while (k)
    {
        if (k&1) res = res * 1ll *m % p;
        m = m *1ll*m % p;   //注意：m隨著循環(huán)的進(jìn)行實(shí)時更新是很重要的苏遥，即使當(dāng)次循環(huán)沒用上
        k >>= 1;
    }
    return res;
}

圖形哈希

圖形hash就是對給定圖內(nèi)的連通塊進(jìn)行hash

大致思想是：組成連通塊的點(diǎn)坐標(biāo)記錄進(jìn)q數(shù)組里面饼拍；然后以 $C_n^2$ 的組合計數(shù)方式，計算q數(shù)組每一個pair坐標(biāo)的歐幾里得距離之和暖眼。和惕耕，作為這個連通塊的hash值。具體參見星空之夜這種hash方法直接背過诫肠。

double get_dist(PII a , PII b )  // 歐幾里得距離計算函數(shù)
{
    double dx= a.x - b.x ;
    double dy = a.y  - b.y ;
    return sqrt(dx * dx + dy * dy) ;
    
}

double get_sh()  // hash 函數(shù)
{
    double sum = 0 ; 
    for(int i = 0 ; i < cnt ; i ++ ) 
    {
        for(int j =  i +1  ; j < cnt ; j ++ ) 
        {
            sum += get_dist(q[i],q[j]) ;
        }
    }
    return sum ;
}

二維四連通遍歷技巧

dx[] = {1,-1,0,0} ;
dy[] = {0,0,1,-1} ;
for(int i = 0 ; i < 4 ; i ++ ) 
{
    int a = x + dx[i] ;
    int b = y + dy[i] ;
    /**....*/
}

八連通遍歷技巧

/**
x , y 是初始的坐標(biāo)
*/
for(int i = x-1 ; i <= x +1 ; i++) 
{
    for(int j = y -1 ; j <= j+1 ; j ++ ) 
    {
        if(i==x && j== y) continue ;
        /**...*/
    }
}

求逆元

單獨(dú)出題本質(zhì)上考察快速冪

更多是和其他條件組合出題司澎。

$給定n組a_i,p_i ，其中p_i是質(zhì)數(shù),求a_i模p_i的乘法逆元栋豫，若逆元不存在則輸出impossible挤安。$

注意：請返回在0～p?1之間的逆元。a有逆元的充要條件是a與p互質(zhì)

#include <iostream>
#include <algorithm>
#include<cmath>
using namespace std;

typedef long long LL;

int qmi(int a , int k ,int p)
{
    int res = 1 ;
    while(k)
    {
        if( k&1) res  = (LL)res * a % p;
        a = (LL) a*a % p ;
        k >>= 1 ;
    }
    return res ;
}

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int a, p;
        scanf("%d%d",&a,&p) ;
        int res  = qmi(a,p-2,p) ;
        if(a%p) printf("%d\n", res );
        else puts("impossible"); 
    }

    return 0;
}

語法拾遺

//結(jié)構(gòu)體排序
struct st  // 按照sum由大到小丧鸯，ch由大到小蛤铜，id由小到大排序，放在重載小于號中
{
    int id , ch , mth , eg ;
    int sum ;
    bool operator< (const st &t) const 
    {
        if(sum != t.sum) return sum > t.sum ;
        else if( ch != t.ch) return ch > t.ch ;
        else if(id != t.id) return id < t.id ;
    }
}stu[N] ;


//自定義cmp(不想用)

// lambda表達(dá)式 丛肢，c++17 围肥，考試恐怕用不了
sort(stu , stu + n ,[](st &a,st &t){     
    if(a.sum != t.sum) return a.sum > t.sum ;
    else if( a.ch != t.ch) return a.ch > t.ch ;
    else if(a.id != t.id) return a.id < t.id ;
}) ;

心得體會

完全背包存在一個項(xiàng)替代n項(xiàng)的時間優(yōu)化問題

空間上，和01背包一樣去掉第一維蜂怎，修改第二層for循環(huán)穆刻。

值得注意的是，01背包和完全背包修改for循環(huán)有不同

根據(jù)他們的狀態(tài)轉(zhuǎn)移方程的不同

01背包狀態(tài)轉(zhuǎn)移需要使用上一層的信息杠步，動用了滾動數(shù)組氢伟，因此會從大到小循環(huán)

完全背包優(yōu)化后的狀態(tài)轉(zhuǎn)移方程只使用當(dāng)前層的信息，優(yōu)化一維之后還是從小到大循環(huán)不變

2021.2.2

在有一個模數(shù)mod的計算背景下幽歼，a / b 同余mod 朵锣，相當(dāng)于a * x 同余mod 。 x就是b模mod的乘法逆元（跟a的關(guān)系不大）

比如在計算十萬級別的組合數(shù)可以看到逆元的應(yīng)用：

mod的存在相當(dāng)于將數(shù)軸連成了一個環(huán)甸私。

如果模數(shù)mod足夠大诚些，那么，在參與計算的數(shù)字規(guī)模不大的情況下皇型，計算出的結(jié)果一般就和我們一般理解的無異泣刹。

六字真言：模數(shù)mod==隨便模助析，隨時模==

一般情況下mod越大，逆元越大椅您。事實(shí)上，某數(shù)對mod的逆元超級大寡键。

2021.2.5

DP專題

數(shù)字三角形模型

題目特點(diǎn)：

  描述了一個地圖掀泳，從左上角通過向下和向右方走，走到右下角西轩。途中經(jīng)過地圖的方格员舵，每個方格有自己價值或者是權(quán)值。求藕畔，途徑的權(quán)值之和的==最大值==马僻。

代碼如下：

 for(int i = 1 ; i <= n ; i ++ ) 
 {
     for(int j = 1 ; j <= m  ; j ++ ) 
     {
         scanf("%d", &g[i][j]) ;  // 讀入地圖的格點(diǎn)權(quán)值
     }
 }
        
// 核心代碼  
for(int i = 1 ; i <= n ; i ++) 
{
    for(int j = 1 ; j <= m ; j ++ ) 
    {
        //          上一行        左一列      當(dāng)前格點(diǎn)權(quán)值
        f[i][j] = max(f[i-1][j] , f[i][j-1]) + g[i][j] ;
    }
}

簡單變形：（本質(zhì)區(qū)別是，求最小值）

穿過一個N×N的正方形的網(wǎng)格

從網(wǎng)格的左上角進(jìn)注服，右下角出韭邓。

==每穿越中間1個小方格，都要花費(fèi)1個單位時間溶弟。==必須在(2N-1)個單位時間穿越出去女淑。(這是在暗示不可以走回頭路)

而在經(jīng)過中間的每個小方格時，都需要繳納一定的費(fèi)用辜御。

期望在規(guī)定時間內(nèi)用最少費(fèi)用穿越出去鸭你。

請問至少需要多少費(fèi)用？

注意：不能對角穿越各個小方格（即擒权，只能向上下左右四個方向移動且不能離開網(wǎng)格）

與求最大值的區(qū)別是：需要初始化f數(shù)組

// f數(shù)組的第0列和第0行邊界初始化為最大值袱巨，這樣保證f的第1行和第1列只會使用合法值
for(int i = 0 ; i <= n ; i ++ ) 
 {
     f[0][i] = 0x3f3f3f3f ;
     f[i][0] = 0x3f3f3f3f ;
 }

f[1][1] = g[1][1] ;
for(int i = 1 ; i <= n ; i ++ ) 
{
    for(int j = 1 ; j <= n ; j ++ ) 
    {
        if(i != 1 || j != 1  ) // 第一個格子不需要狀態(tài)轉(zhuǎn)移,直接初始化就好了
        {
            f[i][j] = min(f[i-1][j] , f[i][j-1]) + g[i][j] ;
        }
    }
}

最長上升子序列模型

模型基本描述：

給定一個長度為N的數(shù)列，求數(shù)值嚴(yán)格單調(diào)遞增的子序列的長度最長是多少碳抄。

DP做法時間復(fù)雜度是 $O(n^2)$

#include<bits/stdc++.h>
using namespace std ;
const int N = 1E3+10 ;
int n ;
int s[N] , f[N] ;
int main()
{

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

    int res = -1 ;
    for(int i = 0 ; i < n ; i ++ ) 
    {
        f[i] = 1 ;
        for(int j = 0 ; j < i ; j++ ) 
        {
            if(s[i]>s[j]) 
            {
                f[i] = max(f[i] , f[j] + 1) ;
                res = max(res , f[i]) ;
            }
        }
    }

    cout << res << endl;

    return 0 ;
}

核心代碼

int res = -1 ;
for(int i = 0 ; i < n ; i ++ ) 
{
    f[i] = 1 ;
    for(int j = 0 ; j < i ; j++ ) 
    {
        if(s[i]>s[j]) 
        {
            f[i] = max(f[i] , f[j] + 1) ;
            res = max(res , f[i]) ;
        }
    }
}

小擴(kuò)展：怪盜基德的滑翔翼

求兩個方向上的最長上升子序列問題愉老，只需正向和反向都求解就max即可。

#include<bits/stdc++.h>
using namespace std;

const int  N = 110 ;
int n ;
int a[N] ;
int f[N] ;
int main()
{
    int T ;
    scanf("%d",&T) ;
    while(T--)
    {
        scanf("%d",&n);
        for(int i = 1 ; i <= n ; i++ )
            scanf("%d",&a[i]) ;
        
        int res = 0 ;    
        for(int i = 1 ; i <= n ; i ++ )
        {
            f[i] = 1 ;
            for(int j = 1 ; j < i ; j  ++ )
            {
                if(a[i] > a[j])
                {
                    f[i] = max(f[i],f[j] +  1) ;
                }
            }
            res = max(f[i] , res ) ;
        }
                
        for(int i = n ; i ; i -- )
        {
            f[i] = 1 ;
            for(int j = n ; j > i ; j  -- )
            {
                if(a[i] > a[j])
                {
                    f[i] = max(f[i],f[j] +  1) ;
                }
            }
            res = max(f[i] , res ) ;
        }      
        printf("%d\n",res ) ;
    }

    return 0 ;
}

背包模型

狀態(tài)機(jī)模型

狀態(tài)壓縮模型

區(qū)間模型

樹形模型

數(shù)位模型

單調(diào)隊(duì)列優(yōu)化模型

斜率優(yōu)化模型

搜索專題

Flood Fill

flood fill 有寬搜和深搜兩種實(shí)現(xiàn)方式纳鼎，但是穩(wěn)妥起見俺夕，我青睞寬搜的實(shí)現(xiàn)。因?yàn)閷捤言谖铱磥順I(yè)已成熟贱鄙。

紅與黑

有一間長方形的房子劝贸，地上鋪了紅色、黑色兩種顏色的正方形瓷磚逗宁。

你站在其中一塊黑色的瓷磚上映九，只能向相鄰（上下左右四個方向）的黑色瓷磚移動。

請寫一個程序瞎颗，計算你總共能夠到達(dá)多少塊黑色的瓷磚件甥。

char g[N][N];
bool st[N][N];
int res;
int dx[] = {1,-1, 0, 0};
int dy[] = {0, 0, 1, -1};
int bfs(PII sr)
{
    queue<PII> q ;
    q.push(sr) ;
    st[sr.x][sr.y] = 1;
    res++;
    while (q.size())
    {
        auto t = q.front() ;
        q.pop() ;
        for (int i = 0; i < 4; i++)
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            // 過濾
            if (a < 0 || a >= n || b < 0 || b >= m)
                continue;
            if (st[a][b])
                continue;
            if (g[a][b] == '#')
                continue;
            // 狀態(tài)更新
            res++;   
            st[a][b] = 1;
            //填充隊(duì)列
            q.push({a, b});
        }
    }
    return res;
}

最短路模型

多源廣搜

最小步數(shù)模型

雙端隊(duì)列廣搜

雙向廣搜

$A^*$

DFS連通性模型

DFS搜索順序

DFS剪枝優(yōu)化

迭代加深

//框架
type dfs(int depth , type others)
{
    if(!depth) //當(dāng)前允許搜索的層數(shù)為0捌议，就立即回溯
        return (type)sth ;
    
    /**other body*/ 
    dfs(depth -1 , other sth)
}


int main()
{
    int depth = 0 ; // 全局最大搜索層數(shù)為m
    while(depth < m  && dfs(depth, sth)) depth ++ ;
    
}

雙向深搜

$IDA^*$

迭代加深和估價函數(shù)結(jié)合的算法，有優(yōu)異的表現(xiàn)引有。

簡單例題參考 acwing1243 糖果

例題核心代碼


int lowbit(int x)  // 返回最低位的1 瓣颅， 這不在IDA*的框架里
{
    return x & -x ;
}



int h(int state)  // 估價函數(shù)
{
    int res = 0 ;
    for(int i = (1 <<m ) -1 - state ; i ; i -= lowbit(i)) 
    {
        int c = log_2[lowbit(i)] ;
        res ++ ;
        for(auto r : col[c]) i &= ~r ;
    }
    return res ;
}


bool dfs(int depth , int state)   // 迭代加深的深搜
{
    if(!depth || h(state) > depth) return state == (1<<m) -1 ;

    // 找到被選擇最少的一列
    int t = -1 ;
    for(int i  = (1 <<m ) -1  - state; i ; i -= lowbit(i)) 
    {
        int c = log_2[lowbit(i)] ;
        if(t == -1 || col[t].size() > col[c].size())
        {
            t = c ;
        }
    }


    //枚舉選哪一行
    for(auto r : col[t]) 
    {
        if(dfs(depth -1 , state | r)) 
            return 1 ;
    }
    return 0 ; 
}




int main()
{
    
    /**other*/
    
    //以下是迭代加深
    int depth = 0 ;
    while(depth <= m && !dfs(depth,0)) depth ++ ;
    
    /**other*/
}

圖論

單源最短路建圖方式

單源最短路綜合應(yīng)用

單源最短路擴(kuò)展應(yīng)用

Floyd

最小生成樹

最小生成樹的擴(kuò)展

負(fù)環(huán)

差分約束

有向圖的強(qiáng)連通分量

無向圖的雙連通分量

二分圖

一個圖 ==是二分圖==

等價于 ==不存在奇數(shù)環(huán)==

等價于 ==染色法不存在矛盾==

染色法

bool dfs(int u ,int c) 
{
    clr[u] =c  ;
    
    for(int i = h[u] ;~i ; i = ne[i]) 
    {
        int j = e[i] ;
        if(!clr[j])
        {
            if(!dfs(j , 3-c , mid) ) return 0 ;
        }
        else
        {
            if(clr[j]  == c ) return 0 ;
        }
    }
    return 1 ;
}

歐拉回路和歐拉路徑

拓?fù)渑判?/h2>

數(shù)據(jù)結(jié)構(gòu)專題

并查集

樹狀數(shù)組

線段樹

線線段樹 + 掃描線（無懶標(biāo)記）

X星球的一批考古機(jī)器人正在一片廢墟上考古。

該區(qū)域的地面堅硬如石譬正、平整如鏡宫补。

管理人員為方便，建立了標(biāo)準(zhǔn)的直角坐標(biāo)系曾我。

每個機(jī)器人都各有特長粉怕、身懷絕技。

它們感興趣的內(nèi)容也不相同抒巢。

經(jīng)過各種測量贫贝，每個機(jī)器人都會報告一個或多個矩形區(qū)域，作為優(yōu)先考古的區(qū)域蛉谜。

矩形的表示格式為 (x1,y1,x2,y2)稚晚，代表矩形的兩個對角點(diǎn)坐標(biāo)。

為了醒目悦陋，總部要求對所有機(jī)器人選中的矩形區(qū)域涂黃色油漆蜈彼。

小明并不需要當(dāng)油漆工，只是他需要計算一下俺驶，一共要耗費(fèi)多少油漆幸逆。

其實(shí)這也不難，只要算出所有矩形覆蓋的區(qū)域一共有多大面積就可以了暮现。

注意还绘，各個矩形間可能重疊。

#include<bits/stdc++.h>
using namespace std ;
const int N = 10010 ;
int n ;
struct Segment
{
    int x , y1 , y2 ;
    int k ;
    bool operator < (const Segment &t) const 
    {
        return x < t.x ;
    }
}seg[N *2] ;
struct node
{
    int l ,r ;
    int cnt , len ;
}tr[N *4 ] ;

void pushup(int u)
{
    if (tr[u].cnt > 0) tr[u].len = tr[u].r - tr[u].l + 1;
    else if (tr[u].l == tr[u].r) tr[u].len = 0;
    else tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

void modify(int u , int l , int r  , int k ) 
{
    if(tr[u].l >= l && tr[u].r <= r )
    {
        tr[u].cnt += k ;
        pushup(u) ;
    }
    else 
    {
        int mid = tr[u].l + tr[u].r >> 1 ;
        if(l <= mid ) modify(u << 1 , l ,r , k ) ;
        if(r > mid ) modify(u << 1  | 1 , l ,r , k ) ;
        pushup(u) ;
        
    }
}

int main() 
{
    scanf("%d",&n ) ;
    int m = 0 ;
    for(int i = 0 ; i < n ; i++ )
    {
        int x1 ,y1,x2,y2 ;
        scanf("%d%d%d%d",&x1, &y1 , &x2 ,&y2) ;
        seg[m++] = {x1 , y1 , y2 , 1} ;
        seg[m++] = {x2 , y1 , y2 , -1} ;
    }
    
    sort(seg  ,seg + m ) ;
    
    build(1,0,10000) ;
    
    int res =  0 ; 
    for(int i = 0 ; i < m ; i ++) 
    {
        if( i > 0 ) res += tr[1].len * (seg[i].x - seg[i -1 ].x ) ;
        modify( 1 ,seg[i].y1 , seg[i].y2  - 1 , seg[i].k ) ;
    }
     
    printf("%d\n" , res) ;

    return 0 ;
}

可持久化數(shù)據(jù)結(jié)構(gòu)

平衡樹

AC自動機(jī)

數(shù)學(xué)知識專題

篩質(zhì)數(shù)

分解質(zhì)因數(shù)

快速冪

約數(shù)個數(shù)

歐拉函數(shù)

同余

矩陣乘法

組合計數(shù)

高斯消元

容斥原理

概率與數(shù)學(xué)期望

博弈論

基礎(chǔ)算法

位運(yùn)算

遞推與遞歸

前綴和與差分

二分

排序

RMQ

由 $|x-a| + | x - b | >= |a-b|$ 演化來的問題栖袋。 ?
指給定區(qū)間問題上拍顷，找尋最少點(diǎn)數(shù)，能被全部區(qū)間包含塘幅。 ?
img

?

最后編輯于：2021.03.13 20:15:16

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末昔案，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子电媳，更是在濱河造成了極大的恐慌踏揣，老刑警劉巖，帶你破解...
沈念sama閱讀 221,430評論 6贊 515
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件匾乓，死亡現(xiàn)場離奇詭異捞稿，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 94,406評論 3贊 398
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門娱局，熙熙樓的掌柜王于貴愁眉苦臉地迎上來彰亥，“玉大人，你說我怎么就攤上這事衰齐∪握” “怎么了？”我有些...
開封第一講書人閱讀 167,834評論 0贊 360
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵耻涛，是天一觀的道長仁卷。經(jīng)常有香客問我，道長犬第，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 59,543評論 1贊 296
?港島之戀（遺憾婚禮）
正文為了忘掉前任芒帕，我火速辦了婚禮歉嗓，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘背蟆。我一直安慰自己鉴分，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 68,547評論 6贊 397
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布带膀。她就那樣靜靜地躺著志珍，像睡著了一般。火紅的嫁衣襯著肌膚如雪垛叨。梳的紋絲不亂的頭發(fā)上伦糯，一...
開封第一講書人閱讀 52,196評論 1贊 308
城市分裂傳說
那天，我揣著相機(jī)與錄音嗽元，去河邊找鬼敛纲。笑死，一個胖子當(dāng)著我的面吹牛剂癌，可吹牛的內(nèi)容都是我干的淤翔。我是一名探鬼主播，決...
沈念sama閱讀 40,776評論 3贊 421
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼佩谷，長吁一口氣：“原來是場噩夢啊……” “哼旁壮！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起谐檀，我...
開封第一講書人閱讀 39,671評論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤抡谐，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后稚补，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體童叠，經(jīng)...
沈念sama閱讀 46,221評論 1贊 320
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 38,303評論 3贊 340
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了厦坛。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片五垮。...
茶點(diǎn)故事閱讀 40,444評論 1贊 352
活死人
序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖杜秸，靈堂內(nèi)的尸體忽然破棺而出放仗，到底是詐尸還是另有隱情，我是刑警寧澤撬碟，帶...
沈念sama閱讀 36,134評論 5贊 350
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布诞挨，位于F島的核電站，受9級特大地震影響呢蛤，放射性物質(zhì)發(fā)生泄漏惶傻。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,810評論 3贊 333
男人毒藥：我在死后第九天來索命
文/蒙蒙一其障、第九天我趴在偏房一處隱蔽的房頂上張望银室。院中可真熱鬧，春花似錦励翼、人聲如沸蜈敢。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,285評論 0贊 24
一樁弒父案汽抚，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽抓狭。三九已至，卻和暖如春造烁，著一層夾襖步出監(jiān)牢的瞬間否过，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 33,399評論 1贊 272
情欲美人皮
我被黑心中介騙來泰國打工膨蛮，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留叠纹，地道東北人。一個月前我還...
沈念sama閱讀 48,837評論 3贊 376
代替公主和親
正文我出身青樓敞葛，卻偏偏與公主長得像誉察，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子惹谐，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,455評論 2贊 359

算法筆記【持續(xù)更新】

貪心

AcWing122.糖果傳遞[1]

Acwing112 .雷達(dá)設(shè)備[2]

付賬問題[3]

圖論

Dijkstra

SPFA

搜索

三維迷宮BFS

二維迷宮BFS

數(shù)論

歐幾里得算法

更相減損術(shù)的變形

算術(shù)基本定理

線性篩素數(shù)

分解質(zhì)因數(shù)

約數(shù)個數(shù)基本定理

約數(shù)之和基本定理

質(zhì)數(shù)定理（用來大致評估時間復(fù)雜度）

裴蜀定理

擴(kuò)展歐幾里得算法

組合數(shù)

組合數(shù)初級(楊輝三角)

組合數(shù)中級（快速冪求逆元）

組合數(shù)高級(Lucas定理)

DP

AcWing1050 鳴人的影分身（線性）^ 線性Dp

AcWing1222 密碼脫落（區(qū)間）^ 區(qū)間Dp

Acwing 1220. 生命之樹（樹形）^ 樹形Dp

疑難雜題

并查集的另類用法

日期類題目

基礎(chǔ)算法

求逆序?qū)Γw并）

一維前綴和模板

一維差分模板

二維前綴和

二維差分模板

求樹的直徑

RMQ問題

模擬散列表

楊輝三角(解決2000以內(nèi)的組合數(shù)問題)

二叉樹思想解決一般遞歸問題

十進(jìn)制向任意進(jìn)制轉(zhuǎn)化

秦九韶算法咐刨，其他進(jìn)制向十進(jìn)制轉(zhuǎn)化

a進(jìn)制化成b進(jìn)制（直接轉(zhuǎn)化）

string回文判斷

實(shí)數(shù)二分和整數(shù)二分的習(xí)題對比

區(qū)間合并

從對稱矩陣的角度去遍歷二維數(shù)組矩陣

N皇后問題

手寫next_permutation()

Trie樹

快速冪模板

圖形哈希

二維四連通遍歷技巧

八連通遍歷技巧

求逆元

語法拾遺

心得體會

DP專題

數(shù)字三角形模型

簡單變形：（本質(zhì)區(qū)別是，求最小值）

最長上升子序列模型

核心代碼

小擴(kuò)展：怪盜基德的滑翔翼

背包模型

狀態(tài)機(jī)模型

狀態(tài)壓縮模型

區(qū)間模型

樹形模型

數(shù)位模型

單調(diào)隊(duì)列優(yōu)化模型

斜率優(yōu)化模型

搜索專題

Flood Fill

最短路模型

多源廣搜

最小步數(shù)模型

AcWing122.糖果傳遞^[1]

Acwing112 .雷達(dá)設(shè)備^[2]

付賬問題^[3]