自用隨便記錄

C++

排序
stl

頭文件

全能頭文件：

#include<bits/stdc++.h>

自定義排序函數

bool compare(const int &odd1,const int &odd2)
{return odd1>odd2;
}

stl

枚舉map

  map<int, string> mapStudent;  mapStudent.insert(pair<int, string>(1, "student_one"));  mapStudent.insert(pair<int, string>(2, "student_two"));  mapStudent.insert(pair<int, string>(3, "student_three"));  map<int, string>::reverse_iterator  iter;  for(iter = mapStudent.rbegin(); iter != mapStudent.rend(); iter++)  {  cout<<iter->first<<"   "<<iter->second<<endl;  }  

優先隊列

算法

堆

數據結構

堆
圖

樹狀數組

int tree[maxn<<2];
int lowbit(int x){return x & -x;
}
int get_sum(int idx){int sum = 0;while(idx){sum += tree[idx];idx -= lowbit(x);}return sum;
}
void update(int idx, int value){while(idx < LIMIT){tree[idx] += value;idx += lowbit(idx);}
}

數學

快速冪
gcd和最小公倍數（ab的最小公倍數=ab/gcd(ab)）

int gcd(int x, int y){if(x<y) return gcd(y, x);return y == 0?x:gcd(y, x%y);
}

ex_gcd
質數

字符串

manacher

找最長回文子串

void initialize(int n, char ch[maxn]){int nn = n<<1|1;for(int i = nn-1, j=n-1; i>=2; i-=2){ch[i] = '#';ch[i-1] = ch[j];}ch[0] = '#';
}void manacher(int n, char ch[maxn]){memset(d, 0, sizeof(d));//d[i]是不包括i在內的半徑int mid = -1;int maxr = -1;for(int i = 0; i < n; i++){if(maxr>d[i]){int other = mid * 2 - i;d[i] = min(d[other], maxr-i);}while(i-d[i]>=0 && i+d[i]<n && ch[i-d[i]]==ch[i+d[i]])i++;d[i]--;if(i+d[i]>maxr){mid = i;maxr = i+d[i];}}
}

kmp

模式匹配
前綴函數https://oi-wiki.org/string/kmp/
特點1：“一個重要的觀察是 相鄰的前綴函數值至多增加 1。”
特點2：當不符合最優的增加1的情況的時候，如何快速找到下一個可以匹配的對象？
注意 前綴數組pi[0]=0!!!
其他情況下 表示的是重復前后綴的長度，比如對于abab字符串，pi[3]=2（有重復串ab）

KMP：給定一個文本 t 和一個字符串 s，我們嘗試找到并展示 s 在 t 中的所有出現（occurrence）
力扣測試題：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/

const int maxn = 1e4 + 10;
class Solution {
public:int pi[maxn];//前綴數組void get_pi(string s){int n = s.length();memset(pi, 0, sizeof(pi));for(int i = 1; i < n; i++){int j = pi[i-1];while(j != 0 && s[j] != s[i]){j = pi[j-1];}if(s[i] == s[j]) pi[i] = j+1;else pi[i] = 0;}}int strStr(string haystack, string needle) {int n_needle = needle.length();get_pi(needle);int n = haystack.length();int j = 0;for(int i = 0; i < n; i++){while(j != 0 && haystack[i] != needle[j]){j = pi[j-1];}if(haystack[i] == needle[j]){j++;}//printf("i:%d, ch:%c, j:%d, chj:%c\n", i, haystack[i], j, needle[j]);if(j == n_needle) return i - n_needle + 1;}return -1;}
};