1091

qlc23333
dp_53
LiHaoyu
Forelsket_2
Jettblue

shengshu_
Dr孟
AsarumZJ

## 模拟

#include <iostream>
using namespace std;

int main()
{
int n;
cin >> n;
int first = (n - 1) * 2;
if (n % 2) // 奇数
{
for (int i = 1; i <= n; ++i)
{
printf("%d\n", first);
if (i < (n + 1) / 2)
first -= 2;
else
first += 2;
}
}
else
{
for (int i = 1; i <= n; ++i)
{
printf("%d\n", first);
if (i < (n + 1) / 2)
first -= 2;
else if (i > (n - 1) / 2 + 1)
first += 2;
}
}

return 0;
}


## 递推 二维前缀和

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

const int maxn = 2010;
int C[maxn][maxn];   // 组合数
int st[maxn][maxn];  // 0不是倍数 1是倍数
int sum[maxn][maxn]; // 前缀和数组
int n, m, k, t;

void pre(int N)
{
for (int i = 0; i <= N; ++i)
{
C[i][0] = 1 % k;
st[i][0] = 1; // 0是k的倍数 ?
}
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= i; ++j)
{
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % k; // 递推式
if (!C[i][j] && j <= i)
st[i][j] = 1;
}

for (int i = 1; i <= N; ++i)
for (int j = 1; j <= N; ++j) // 对每个位置求前缀和
sum[i][j] = st[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}

int main()
{
cin >> t >> k;
pre(maxn - 10);
while (t--)
{
cin >> n >> m;
cout << sum[n][m] << endl;
}

return 0;
}


## LCA Tarjan算法

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

typedef pair<int, int> PII;
const int maxn = 10010;
int n, m;
int h[maxn], w[maxn * 2], e[maxn * 2], ne[maxn * 2], idx;
int res[maxn * 2];           // 存储查询的答案
vector<PII> query[maxn * 2]; // query[i][first][second]  first存查询 距离i的另外一个点j，second存查询编号idx
int p[maxn];                 // 并查集 祖宗结点
int dist[maxn];              // 每个结点到根节点的距离
int st[maxn];                // 标记结点状态 0未遍历 1已遍历未回溯 2已遍历并完成回溯

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

void dfs(int u, int father)
{
for (int i = h[u]; ~i; i = ne[i]) // 每一条边
{
int j = e[i]; // 结点
if (j == father)
continue;
dist[j] = dist[u] + w[i]; // w[i]边权
dfs(j, u);
}
}

int find(int x)
{
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}

void tarjan(int u)
{
st[u] = 1; // 标记遍历到此处
// 将u这条路上的根节点的左下的点用并查集合并到根节点
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!st[j])
{
tarjan(j); // 往左下搜
p[j] = u;  // 从左下回溯后把左下的点合并到根节点
}
}
// 对于当前点u 搜索所有和u有关的询问
for (auto item : query[u])
{
int y = item.first, id = item.second;
if (st[y] == 2) // 如果查询的这个点已经是左下的点(已经搜索过且回溯过,标记为2)
{
int anc = find(y);                           // x与y的LCA
res[id] = dist[y] + dist[u] - dist[anc] * 2; // 距离公式
}
}
// 点u已经搜索完且要回溯了 把st[u]标记为2
st[u] = 2;
}

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

memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; ++i)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}

for (int i = 0; i < m; ++i)
{
int x, y;
scanf("%d%d", &x, &y);
if (x != y)
{
query[x].push_back({y, i});
query[y].push_back({x, i});
}
}

for (int i = 1; i <= n; ++i)
p[i] = i; // 初始化并查集

dfs(1, -1); // 先算出每个点到根的距离，任意指定一个结点为根，此处指定为1
tarjan(1);  // 求LCA

for (int i = 0; i < m; ++i)
printf("%d\n", res[i]);

return 0;
}


## 背包+贪心优化

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector> // 模m的余数相同的数的数量不一定，用vector存
using namespace std;

const int maxn = 1010;
int n, m;
vector<int> a[maxn];
int f[4][maxn];

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

memset(f, -0x3f, sizeof f); // 初始化
f[0][0] = 0;                // 边界
for (int i = 0; i < m; ++i)
{
sort(a[i].begin(), a[i].end());
reverse(a[i].begin(), a[i].end()); // 降序

for (int u = 0; u < 3 && u < a[i].size(); ++u) // 只枚举每类前3大的数
for (int j = 3; j > 0; --j)                // 倒序
for (int k = 0; k < m; ++k)
f[j][k] = max(f[j][k], f[j - 1][(k - a[i][u] % m + m) % m] + a[i][u]);
}
printf("%d\n", f[3][0]);

return 0;
}


## 并查集

#include <iostream>
#include <cstdio>
using namespace std;

const int maxn = 1100010; // 共1e5个数，每个数最大1e6，最大值1e6+1e5
int p[maxn];              // 每个数的下一个未被使用过的数

int find(int x)
{
if (p[x] != x)
p[x] = find(p[x]); // 路径压缩
return p[x];
}

int main()
{
int n;
scanf("%d", &n);

for (int i = 1; i < maxn; ++i)
p[i] = i; // 都未被使用过 初始化为自环

for (int i = 0; i < n; ++i)
{
int x;
scanf("%d", &x);
x = find(x);
if (i)
printf(" ");
printf("%d", x);
p[x] = x + 1;
}

return 0;
}


## 线性DP 矩阵快速幂

// 数据范围1e9，需要用 矩阵快速幂 优化

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

typedef long long LL;
const int maxn = 6, mod = 1e9 + 7;
int op[7] = {0, 4, 5, 6, 1, 2, 3};
int A[maxn][maxn] = {0};
int n, m;

void mul(int c[], int a[], int b[][maxn])
{
int tmp[maxn] = {0};
for (int i = 0; i < maxn; ++i)
for (int k = 0; k < maxn; ++k)
tmp[i] = (tmp[i] + (LL)a[k] * b[i][k]) % mod;

memcpy(c, tmp, sizeof tmp);
}

void mul(int c[][maxn], int a[][maxn], int b[][maxn])
{
int tmp[maxn][maxn] = {0};
for (int i = 0; i < maxn; ++i)
for (int j = 0; j < maxn; ++j)
for (int k = 0; k < maxn; ++k)
tmp[i][j] = (tmp[i][j] + (LL)a[i][k] * b[k][j]) % mod;

memcpy(c, tmp, sizeof tmp);
}

int main()
{
cin >> n;
for (int i = 0; i < 6; ++i)
for (int j = 0; j < 6; ++j)
A[i][j] = 4; // 初始化系数为4

cin >> m;
while (m--)
{
int a, b;
cin >> a >> b;
A[op[a] - 1][b - 1] = 0;
A[op[b] - 1][a - 1] = 0;
}

n--;
int F1[maxn] = {4, 4, 4, 4, 4, 4}; // 初始向量，下标从0~n-1

while (n)
{
if (n & 1)
mul(F1, F1, A);
mul(A, A, A);
n >>= 1;
}

int ans = 0;
for (int i = 0; i < 6; ++i)
ans = ((LL)ans + F1[i]) % mod;
cout << ans << endl;

return 0;
}


## 树形DP 树的直径

### 法一：换根DP

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

const int maxn = 200010;
int first[maxn], second[maxn], up[maxn], p[maxn]; // 该点向下走的最大长度、次大长度、该点向上走的最大长度、该点向下最大长度上的下一个点
int h[maxn], e[maxn * 2], ne[maxn * 2], idx;
int n, lp; // 结点数 最长路径

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

void dfs_down(int root, int father) // 返回该点到叶子的最大长度 用于求直径 自下往上
{
for (int i = h[root]; ~i; i = ne[i])
{
int j = e[i];
if (j == father)
continue;
dfs_down(j, root); // 先递归到下层，算出下方最大长度
int d = first[j] + 1;
if (d > first[root]) // 更新根结点的最大与次大
{
second[root] = first[root];
first[root] = d;
p[root] = j; // 记录该点为向下最大路径上的点
}
else if (d > second[root])
second[root] = d;
}

int ans = first[root] + second[root];
if (ans > lp)
lp = ans;
}

void dfs_up(int root, int father) // 算出每个结点向上走的最大路径长 自上而下
{
for (int i = h[root]; ~i; i = ne[i])
{
int j = e[i];
if (j == father)
continue;
up[j] = up[root] + 1;
if (p[root] == j)
up[j] = max(up[j], second[root] + 1);
else
up[j] = max(up[j], first[root] + 1);
dfs_up(j, root); // 向下一层
}
}

int main()
{
memset(h, -1, sizeof h);

cin >> n;
for (int i = 0; i < n - 1; ++i) // n个结点n-1条边
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
add(b, a);
}

dfs_down(0, -1); // 规定0为根
dfs_up(0, -1);
// printf("lp = %d\n", lp);
for (int i = 0; i < n; ++i)
{
int d[3] = {first[i], second[i], up[i]};
sort(d, d + 3); // 取最大的两个
if (d[1] + d[2] == lp)
printf("%d\n", i);
}

return 0;
}


### 法二

// 找到直径上的点，标记他们向下走前二长的路径经过的点
#include <iostream>
#include <cstring>
using namespace std;

const int N = 2 * 100010, M = 2 * N;

int n;
int d1[N], d2[N];
int h[N], e[M], ne[M], idx, ans;
bool st[N]; // 标记直径上的点

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

int dfs1(int u, int father)
{
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == father)
continue;
int d = dfs1(j, u) + 1;
if (d > d1[u])
{
d2[u] = d1[u];
d1[u] = d;
}
else if (d > d2[u])
d2[u] = d;
}
ans = max(ans, d1[u] + d2[u]);
return d1[u];
}

void dfs2(int u)
{
st[u] = true;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (d1[u] == d1[j] + 1)
dfs2(j);
}
}

void dfs3(int u)
{
st[u] = true;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (d2[u] == d1[j] + 1)
dfs2(j);
}
}

int main()
{
cin >> n;
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; ++i)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
add(b, a);
}

dfs1(0, -1);
for (int i = 0; i < n; ++i)
{
if (d1[i] + d2[i] == ans) // 树的最高点
{
dfs2(i);
dfs3(i);
}
}

for (int i = 0; i < n; ++i)
if (st[i])
printf("%d\n", i);

return 0;
}


## 区间DP

// 区间DP 求最小值 O(N^3)
// 状态计算 枚举顺序?

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

const int maxn = 110, INF = 0x3f3f3f3f; // 要求最小值 初始化为无穷大
char s[maxn];
int f[maxn][maxn]; // 在l r闭区间内最少要加几个括号使整体合法

bool match(int l, int r)
{
if ((l == '(' && r == ')') || l == '[' && r == ']')
return true;
return false;
}

int main()
{
scanf("%s", s);
int n = strlen(s);

for (int i = 0; i < n; i++)
f[i][i] = 1;                   // 长度为1时要特判
for (int len = 2; len <= n; ++len) // 从长度为2开始
{
for (int l = 0; l + len - 1 < n; ++l)
{
int r = l + len - 1;
f[l][r] = INF; // 初始化为无穷大
if (match(s[l], s[r]))
f[l][r] = f[l + 1][r - 1];
f[l][r] = min(f[l][r], min(f[l][r - 1], f[l + 1][r]) + 1);

for (int k = l; k < r; ++k)
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r]); // AB情况
}
}

printf("%d\n", f[0][n - 1]);

return 0;
}


## 完全背包 裴蜀定理

// 裴蜀定理：任意两个数的组合必定是他们gcd的倍数
// 若一些数的gcd是d，则他们的组合一定是d的倍数。若d!=1，则必有无限个无法被表示

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

const int maxn = 110;
int w[maxn], n;
bool f[maxn][10000]; // 能否从前i中选出体积为j
// 数据范围<=100 最大不能表示的数为 (100-1)*(99-1)-1 不超过10000

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

int main()
{
cin >> n;
int d = 0;
for (int i = 1; i <= n; ++i)
{
cin >> w[i];
d = gcd(d, w[i]); // 求n个数的gcd
}

if (d != 1) // 多个整数互质，不一定两两互质 6 10 15
puts("INF");
else
{
f[0][0] = true;
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= 10000; ++j)
f[i][j] = f[i - 1][j] || (j >= w[i] ? f[i][j - w[i]] : false);

int cnt = 0;
for (int i = 0; i <= 10000; ++i)
if (!f[n][i])
cnt++;
cout << cnt << endl;
}

return 0;
}


## 快速幂

#include <iostream>
using namespace std;

typedef long long LL;

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

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

int main()
{
int n;
cin >> n;
while (n--)
{
int a, p;
cin >> a >> p;
// if (gcd(a, p) == 1) // 存在逆元的充要条件是a p互质
if (a % p) // 又因为p一定是质数，故根据性质，只要a不是p的倍数，a p一定互质
printf("%d\n", qmi(a, p - 2, p));
else
puts("impossible");
}

return 0;
}