1 程序设计基本常识

1.1 关闭cin,cout 同步

使用后不能再使用scanf || printf。

ios::sync_with_stdio(false);

1.2 快速读入

void read(int &x) {x = 0;int f = 1;char ch = getchar();while (ch < '0' || ch > '9') {if (ch == '-') f = -1;ch = getchar();}while (ch >= '0' && ch <= '9') {x *= 10;x += (int) (ch - '0');ch = getchar();}x *= f;
}

1.3 带模快速幂

typedef long long LL;
LL ksm(LL a, LL p, LL k) {LL ans = 1;for (; p; p >>= 1, a = a * a % k)if (p & 1)ans = ans * a % k;return ans;
}

1.4 带模快速乘

typedef long long LL;
LL ksc(LL a, LL b, LL k) { // a*b%kLL ans = 0;while (b) { // 当 b 不为 0 时继续循环if (b & 1) ans = (ans + a) % k;a = (a + a) % k;b >>= 1;}return ans;
}

2 C++ 与 STL

2.1 输入输出

2.1.1 格式串

• %1d 只读1个number char
• %02d 输出2位整数不足前导补零
• %d:%d-%d:%d 格式化读入
• %.2f 保留两位小数
• %o 八进制
• %x %#x %#X 十六进制
• #[^\n] 搭配 getchar() 可读入一行 （?）

2.1.2 读入一行 & 字符串相关

• printf("%s", stringObject.c_str()); 输出C++ string 转化成 char
• gets(aline);
• sscanf("123456 ", "%s", str); sscanf与scanf类似，都是用于输入的，只是后者以屏幕(stdin)为输入源，前者以固定字符串为输入源。
• sprintf(s, "%d", 123); 由于sprintf 跟printf 在用法上几乎一样，只是打印的目的地不同而已，前者打印到字符串中，后者则直接在命令行上输出。这也导致sprintf 比printf 有用得多。

2.2 vector

2.3 stack

2.4 queue & priority_queue

2.5 map

2.6 set

2.7 unordered_map/set

2.8 algorithm sort

3 搜索

3.1 全排列 old

void print() {for (int i = 1; i <= n; ++i)printf("%d ", num[i]);cout << '\n';
}
void dfs(int x) {if (x > n) {print();return;}for (int i = 1; i <= n; ++i) {if (!vis[i]) {num[x] = i;vis[i] = 1;dfs(x + 1);vis[i] = 0;}}
}

3.2 半排列 old

void print() {for (int i = 1; i <= k; ++i)printf("%d ", ans[i]);cout << '\n';
}
void dfs(int x, int last) {if (x > k) {print();return;}for (int i = last + 1; i <= n; ++i) {ans[x] = num[i];dfs(x + 1, i);}
}

3.3 dfs子集枚举 old

void print() {for (int i = 1; i <= n; ++i)printf("%d ", vis[i]);cout << '\n';
}
void dfs(int x) {if (x > n) {print();return;}vis[x] = 0;dfs(x + 1);vis[x] = 1;dfs(x + 1);vis[x] = 0;
}

3.4 二进制子集枚举

    int n; cin >> n;for (int s = 0; s < (1 << n); ++s) {for (int j = n - 1; j >= 0; --j)cout << (bool) (s & (1 << j)) << " ";cout << '\n';}

5 二分

5.1 lower_bound & upper_bound

lower_bound是找到第一个≥x的位置，upper_bound是找到第一个＞x的位置。

5.2 理解和写法

二分边界问题：即l,r分别用来逼近答案和缩小区间。在这个题中，如果不满足条件，那么就l=mid+1缩小区间，满足的话r=mid来逼近。最终符合条件的是mid 或 r。特别注意的一点：这时计算mid的时候要l + (r-l+1)/2否则会因为mid一直==l，而又check==1所以死循环。
类似的二分还可以有另外一种写法：用l逼近区间，r来缩小区间，但是这时候注意是左闭右开的，就是那mid正常写就可了。然后结果l-1的原因：观察最后小区间的状态可以得知：当我们检查到mid，mid是中位数时，因为mid前面的严格小于的元素个数是小于mid所在的位置的，所以会执行l = mid+1，这一句话，所以最终的状态是 l-1 为最后我们检查合法的元素。

5.3 栗子

		while (l < r) {mid = l + (r-l)/2;// cout << l << ", " << r << "mid = " << mid << endl;// cout << "now mid = " << mid << endl;if (check(mid)) { // 如果这个数前面数字达不到中位数个数的情况// 前面如果有小于等于 nums 个数。这个数一定不行l = mid+1;} else {// 这个数字可能彳亍r = mid;}}printf("%d\n",l-1);

		while (l < r) {mid = l + (r-l+1)/2;// cout << l << ", " << mid << ", " << r << endl;// cout << "now mid = " << mid << endl;// 严格小于的个数小于真正中位数的位置if (check(mid)) { // 如果这个数前面数字达不到中位数个数的情况// 前面如果有小于等于 nums 个数。这个数一定不行l = mid;} else {// 这个数字可能彳亍r = mid-1;}}// l-1的原因：观察最后小区间的状态可以得知：当我们检查到mid，mid是中位数时，因为mid前面的严格小于的元素个数是小于mid所在的位置的，// 所以会执行 l = mid+1，这一句话，所以最终的状态是 l-1 为最后我们检查合法的元素。printf("%d\n",l);

6 线性数据结构

6.1 单调栈

6.2 单调队列

7 图与树

7.1 存图邻接表

memset(first,-1,sizeof(first));
void build(int ff, int tt, int dd) {es[++tot] = (edge){ff,tt,dd};nxt[tot] = first[ff];first[ff] = tot;
}

7.2 树的直径

两遍dfs

7.3 并查集

int find(int x) {int t, r = x;while(r != fa[r]) r = fa[r];while(x != r) {t=fa[x];fa[x]=r;x=t;}return r;
}void lianjie(int x, int y) {int fx = find(x), fy = find(y);if(fx != fy) fa[fx] = fy;
}void check(int x, int y) {int fx = find(x), fy = find(y);if(fx != fy) puts("N");	else puts("Y");
}

7.4 最小生成树

int kruskal() {int ans = 0;for(int i = 1; i <= V; ++ i) fa[i] = i;sort(es+1, es+E+1, cmp);for(int i = 1; i <= E; ++ i) {int fu = find(es[i].from);int fv = find(es[i].to);if(fu != fv) {fa[fu] = fv;ans += es[i].cost;}}return ans;
}

7.5 多源最短路 - Floyd

void floyd() {for(int k = 1; k <= V; ++ k)for(int i = 1; i <= V; ++ i)for(int j = 1; j <= V; ++ j)dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
}

7.6 单源最短路 - Dijkstra

struct zt{int u, d;
};
bool operator < (zt a, zt b) {return a.d > b.d;
}
priority_queue <zt> q;
#define INF (1e9)
void Dijkstra(int s) {fill(dis+1,dis+V+1,INF);dis[s] = 0;q.push((zt){s,0});while(q.size()) {int x = q.top().u;q.pop();if(done[x]) continue;done[x] = 1;for(int i = first[x]; i != -1; i = nxt[i]) {int v = es[i].to;if(dis[v] > dis[x] + es[i].cost) {dis[v] = dis[x] + es[i].cost;q.push((zt){v,dis[v]});}}} 
}

7.7 差分约束系统

7.8 强联通分量

8 dp

8.1 LIS & LCS

LIS是最长上升子序列，LCS是最长公共子序列。
求解LIS时，$dp[i]$表示在结尾是$a[i]$的最长答案，所以$dp[i] = max(dp[i], dp[j] + 1)$，条件是当$a[i] > a[j]$的时候更新，保证有序。
求解LCS时，用$dp[i][j]$来表示$a$序列末尾在$i$之前，$b$序列在$j$之前的最优答案，转移情况分为两种，当$a[i] = b[i]$的时候，$dp[i][j]=dp[i-1][j-1]+1$，就相当于加上了当前相等的这个元素；当$a[i] \neq b[i]$的时候，不能加加一，需要从之前的状态取最大值，所以$dp[i][j] = max(dp[i-1][j], dp[i][j-1])$。

    for (int i = 1; i <= n; ++i) dp1[i] = 1;int ans = 1;for (int i = 2; i <= n; ++i) {for (int j = 1; j < i; ++j) {if (A[i] > A[j]) {dp1[i] = max(dp1[i], dp1[j]+1);}}ans = max(ans, dp1[i]);}cout << ans << " "; for (int i = 0; i < n; ++i) dp2[i][0] = 0;for (int j = 0; j < m; ++j) dp2[0][j] = 0;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {if (A[i] == B[j]) {dp2[i][j] = dp2[i-1][j-1] + 1;} else {dp2[i][j] = max(dp2[i-1][j], dp2[i][j-1]);}}}cout << dp2[n][m] << endl;

8.2 背包问题

    for(int i = 1; i <= M; i ++)for(int j = 1; j <= T; j ++)if(j-c[i] >= 0)dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]]+w[i]);else dp[i][j] = dp[i-1][j];cout << dp[M][T] << endl;

8.3 区间型dp

石子归并：

    for(int i = 1; i <= n; i ++)scanf("%d", &sum[i]);for(int i = 1; i <= n; i ++)sum[i] += sum[i-1];memset(dp,63,sizeof(dp));for(int i = 1; i <= n; i ++) dp[i][i] = 0;for(int i = n-1; i >= 1; i --)for(int j = i+1; j <= n; j ++)for(int k = i; k <= j; k ++)dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);cout << dp[1][n] << endl;

8.4 状态压缩dp

8.4 单调队列优化

8.5 树形dp

9 矩阵

9.1 矩阵乘法

9.2 矩阵快速幂

9.3 求解线性递推

9.4 矩阵快速幂优化dp

10 字符串

10.1 hash

std::hash：

    hash<string> my_hash;unsigned long long iic = (unsigned long long)my_hash("yqynb");cout << iic << endl;unsigned long long ull = std::hash<std::string>()( "yqynb" );cout << ull << endl;

附录

乌龟棋

    for(int i = 0; i < n; ++ i)scanf("%d", &maps[i]);for(int i = 1; i <= m; ++ i){int x; scanf("%d", &x); ++ ka[x];}for(int i = 0; i <= ka[1]; ++ i)for(int j = 0; j <= ka[2]; ++ j)for(int k = 0; k <= ka[3]; ++ k)for(int l = 0; l <= ka[4]; ++ l){int tmp = 0;if(i) tmp = max(tmp,dp[i - 1][j][k][l]);if(j) tmp = max(tmp,dp[i][j - 1][k][l]);if(k) tmp = max(tmp,dp[i][j][k - 1][l]);if(l) tmp = max(tmp,dp[i][j][k][l - 1]);dp[i][j][k][l] = tmp + maps[i*1+j*2+k*3+l*4];}cout << dp[ka[1]][ka[2]][ka[3]][ka[4]] << endl;