Summary1.3 算法板题

[TOC]

算法模版

背包DP-01背包

for (int i = 0; i < m; ++i)
        for (int j = t; j >= c[i] ; --j)
            dp[j] = max(dp[j], dp[j-c[i]]+val[i]);

背包DP-多重背包

for (int i = 1; i <= n; ++i)
    for (int j = w; j >= c[i]; --j)
        for (int k = 1; k <= num[i] && k*c[i]<=j; ++k)
            dp[j] = max(dp[j], dp[j-k*c[i]]+k*val[i]);

背包DP-多重背包二进制加速

类似于快速幂的思路,对首先将多重背包拍平成01背包,然后再跑01,将跑01的过程用快速幂加速。

int n, m ,ta, tb ,tc, c[maxn], val[maxn], idx = 0, dp[maxn];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d%d", &ta, &tb, &tc);
        for (int j = 1; j <= tc; j<<=1) {
            c[++idx] = tb*j; val[idx] = ta*j;
            tc-=j;
        }
        if (tc) {c[++idx] = tb*tc;val[idx] = ta*tc;}
    }
    for (int i = 1; i <= idx; ++i)
        for (int j = m; j >= c[i]; --j)
            dp[j] = max(dp[j], dp[j-c[i]]+val[i]);
        printf("%d\n", dp[m]);}

区间DP-区间合并代价

题目大意:删除一段数组的数,代价为这个区间的左右端点值的差的绝对值*长度,求全部删去的最大代价。

区间DP的水题,维护一个dp二维数组,然后三层遍历左右端点+中间割点,利用状态转移方程dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][j])即可。

注意:要上来初始化一下,初始化的值就是运算法则算出来的,而dp所做的就是排列组合来搜索组合。


int n, a[maxn], dp[maxn][maxn]; // dp[i][j] 表示区间[i, j]所获得的最大价值
// dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][j]);
int main() {
    scanf("%d", &n);for (int i = 1; i <= n; ++i) scanf("%d", a+i);
    for (int i = 1; i <= n; ++i)
        for (int l = 0; l+i <= n; ++l)
            if (l == 0) dp[i][i+l] = a[i];
            else dp[i][i+l] = abs(a[i]-a[i+l])*(l+1);
    for (int i = 1; i <= n; ++i)
        for (int j = i+1; j <= n; ++j)
            for (int k = i; k <= j; ++k)
                dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][j]);
    printf("%d\n", dp[1][n]);}

区间DP-环形区间合并代价

题目大意:环形的一圈石子,合并相邻的两个,得到最大的和最小的合并代价。

1、不可以用贪心,因为贪心出来的话,不能确定选取的那最小的两个是相邻的,因为题目要求只能合并最小的两个

2、把环形拆解成链状,也就是转换成了第一个问题,线性的问题。 => 通过延长到2倍的长度。思路类似于原来的并查集的对立集,也是将数组长度延长到了两倍

3、遍历次序:通过先遍历长度,然后再遍历左索引i,从而得到右索引j,就得到一个区间(i, i+len-1),然后再在区间中遍历k,也就是分割点即可。dp_max[i][j] = max(dp_max[i][j], dp_max[i][k]+dp_max[k+1][j]+cost(i, j));

4、代价计算:通过前缀和来维护,或者直接用区间来算出来。sum[i][j]表示合并区间的代价

int n, a[maxn], sum[maxn][maxn], dp_min[maxn][maxn], dp_max[maxn][maxn], ans_min = INF, ans_max;
int main() {
    scanf("%d", &n);for (int i = 1; i <= n; ++i) {scanf("%d", &a[i]);a[i+n] = a[i];}
    for (int i = 1; i <= 2*n; i++)
        for (int j = 1; j <= 2*n; j++)
            for (int k = i; k <= j; k++)
                sum[i][j] += a[k];
    for (int i = 1; i <= n; ++i) dp_min[i][i] = dp_max[i][i] = 0;
    for (int len = 1; len < n; len++)
        for (int i = 1, j = i+len; i <= 2*n - 1 && j < 2*n; i++, j = i + len) {
            dp_min[i][j] = INF;
            for (int k = i; k < j; k++) {
                dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] + dp_max[k + 1][j] + sum[i][j]);
                dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] + dp_min[k + 1][j] + sum[i][j]);
            }
        }
    for (int i = 1; i <= n; ++i) {ans_min = min(ans_min, dp_min[i][i+n-1]);ans_max = max(ans_max, dp_max[i][i+n-1]);}
    printf("%d\n%d\n", ans_min, ans_max); }

树形DP-子树和

题目大意:获取该棵树中最大的子树和

对于该题:数据结构:链式前向星储存,然后通过维护一个dp[i]数组,表示第i个节点为根的子树的最大和。dp状态转移方程:dp[x] = max(dp[x], dp[x]+dp[to]);

int n, dp[maxn], in[maxn], ta, tb;
struct node {
    int to, next;
}edges[maxn<<1];int head[maxn], tot;
void addedge(int from, int to) {
    edges[++tot].to = to;    edges[tot].next = head[from];    head[from] = tot;    in[to]++;}
void tree_dp(int x) {
    for (int i = head[x]; i; i=edges[i].next) {
        int to = edges[i].to;
        tree_dp(to);
        dp[x] = max(dp[x], dp[x]+dp[to]);   }}
int main() {
    scanf("%d", &n);    for (int i = 1; i <= n; ++i) scanf("%d", dp+i);
    for (int i = 1; i < n; ++i) {
        scanf("%d%d", &ta, &tb);
        addedge(tb, ta);}
    for (int i = 1; i <= n; ++i)
        if (!in[i]) {
            tree_dp(i);
            printf("%d\n", dp[i]);        }}

树形DP-依赖关系子树和

题目大意:没有上司的晚会,某个节点出现的条件是上下节点不出现。(在树上体现出来就是上下不相邻),如何挑选树上节点使得快乐值最大

对于该题:数据结构:链式前向星储存,然后通过维护一个dp[i][j]数组,在i=0表示不取当前这个节点的时候所获的的值 i=1表示取这个节点所获得的值;dp状态转移方程:dp[0][x] += max(dp[0][to], dp[1][to]); dp[1][x] += dp[0][to];

int n, dp[5][maxn], in[maxn], ta, tb;
struct node {
    int to, next;
}edges[maxn<<1];int head[maxn], tot;
void addedge(int from, int to) {
    edges[++tot].to = to;    edges[tot].next = head[from];    head[from] = tot;    in[to]++;}
void tree_dp(int x) {
    for (int i = head[x]; i; i=edges[i].next) {
        int to = edges[i].to;        tree_dp(to);        dp[1][x] += dp[0][to];
        dp[0][x] += max(dp[1][to], dp[0][to]);    }}
int main() {
    scanf("%d", &n);    for (int i = 1; i <= n; ++i) scanf("%d", &dp[1][i]);
    for (int i = 1; i <= n-1; ++i) {
        scanf("%d%d", &ta, &tb);
        addedge(tb, ta);}
    for (int i = 1; i <= n; ++i) if (!in[i]) {tree_dp(i);printf("%d\n", max(dp[0][i],dp[1][i]));}}

树形DP-依赖关系背包和

题目大意:有先后关系,需要是一条树上的前后关联,然后问最大的和

int n, dp[maxn][maxn], ta, tb, q;
struct node {
    int to, next;
}edges[maxn];int head[maxn], tot;
void addedge(int from, int to) {
    edges[++tot].to = to;    edges[tot].next = head[from];    head[from] = tot;}
void tree_dp(int x) {
    for (int i = head[x]; i; i=edges[i].next) {
        int to = edges[i].to;
        tree_dp(to);
        for (int j = q+1; j >= 1; --j)
            for (int k = 0; k < j; ++k)
                dp[j][x] = max(dp[j][x], dp[k][to]+dp[j-k][x]);}}
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &ta, &tb);
        dp[1][i] = tb;
        addedge(ta, i);
    }
    tree_dp(0);
    printf("%d\n", dp[q+1][0]);}

线性DP-LIS 单个序列最大递增子序列


int n, a[maxn], dp[maxn], ans; // dp[i]表示到i之前的最长递增序列 // 状态转移方程:dp[j] = max

int main() {
    scanf("%d", &n);    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    for (int i = 0; i < n; ++i) {
        dp[i] = 1;
        for (int j = 0; j < i; ++j)
            if (a[i] > a[j]) dp[i] = max(dp[i], dp[j]+1);
            ans = max(ans, dp[i]);}
    printf("%d\n", ans);}

线性DP-LCS 两个序列之间最长公共相同序列

int n, a[maxn], b[maxn], dp[maxn][maxn]; //dp[i][j] i是在第一个串中的索引的位置,j是第二个串中的索引的位置
// 状态转移方程:dp[i][j] = a[i] == a[j] ? dp[i-1][j-1]:max(dp[i-1][j], dp[i][j-1]);
int main() {
    scanf("%d", &n);for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            dp[i][j] = (a[i] == b[j] ? dp[i-1][j-1]+1:max(dp[i-1][j], dp[i][j-1]));
    printf("%d\n", dp[n][n]);}

回文DP-判断最长回文串

  • bool dp[i][j]表示从[i,j]这一段是否为回文串
  • 状态转移方程:dp[i][j] = (s[i] == s[j] && (j-i == 1||dp[i+1]dp[j-1]))?true:false (j > i)
  • j-i == 1 是对aa这种两个字符呈对称形式的情况
int len = strlen(s),ans = 0;bool dp[len][len];
for (int i = 0; i < len; i++) dp[i][i] = true;
for (int j = 1; j < len; j++)
    for (int i = 0; i < j; i++)
        if (s[i] == s[j] && (j-i == 1 || dp[i+1][j-1])) {dp[i][j] = true;ans = max(ans,j-i+1);}
        else dp[i][j] = false;
printf("%d\n",ans);

回文DP-最小删除次数使字串为回文串

  • dp[i][j]表示区间[i,j]的最少抽取次数
  • 状态转移方程 if (s[i] == s[j]) dp[i][j] = (j-i == 1)?1:dp[i+1][j-1] dp[i][j] = min(dp[i][k]+dp[k+1][j],dp[i][j])
int dp[maxn][maxn],a[maxn];     //dp[i][j]表示i-j这段区间合并所需要的次数      a是储存的原来的
int n,len,i,j,k;   //j是起点加上重点的位置,然后k是这段区间中第一段分割的长度
int main(int argc, const char * argv[]) {
    scanf("%d",&n);    cl(dp, INF);
    for (i = 1; i <= n; i++) {scanf("%d",&a[i]);dp[i][i] = 1;}
    for (len = 1; len < n; len++)   //先遍历长度,在遍历起点
        for (i = 1; i+len <= n; i++) {
            j = i+len;
            if (a[i] == a[j]) dp[i][j] = len == 1?1:dp[i+1][j-1];
            for (k = i; k < j; k++) dp[i][j] = min(dp[i][k]+dp[k+1][j],dp[i][j]);}   //从中间找切断点k
    cout<<dp[1][n]<<endl;}

二维DP-01坐标系中最大正方形

首先每个坐标都是变长为1的正方形,然后进行状态转换的话要根据i-1,j-1/i,j-1/i-1,j这三个点进行转移(并且需要满足合成正方形的条件才可以转移),从而得到0~当前点范围内的最大正方形。

int n, m, a[maxn][maxn], dp[maxn][maxn], ans; // dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])+1;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j)
            if (a[i][j]) dp[i][j] = min(min(dp[i-1][j-1], dp[i][j-1]), dp[i-1][j])+1;
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) ans = max(ans, dp[i][j]);
    printf("%d\n", ans);}

排序-逆序对数,最少相邻交换次数

int n, a[maxn], t[maxn], tidx, lidx, ridx; ll ans;
void mergesort(int l, int r){
    if (r > l) {
        int mid = (l+r)>>1;        mergesort(l, mid);        mergesort(mid+1, r);
        tidx = lidx = l, ridx = mid+1;
        while (lidx <= mid && ridx <= r) {
            if (a[lidx] <= a[ridx]) t[tidx++] = a[lidx++];
            else t[tidx++] = a[ridx++], ans += (mid-lidx+1);        }
        while (lidx <= mid) t[tidx++] = a[lidx++];
        while (ridx <= r) t[tidx++] = a[ridx++];
        for (int i = l; i <= r; ++i) a[i] = t[i];}}
int main() {
    scanf("%d", &n);    for (int i = 1; i <= n; ++i) scanf("%d", a+i);
    mergesort(1, n);    printf("%lld\n", ans);}

并查集-给定处于相同集合的元素关系,元素是否在同一集合,有多少集合

int n, m, p, fa[maxn], ta, tb;
int findfa(int x){return fa[x] == x?x:findfa(fa[x]);}
int main() {
    scanf("%d%d%d", &n, &m, &p);    for (int i = 1; i <= n; ++i) fa[i]=i;
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &ta, &tb);
        if (findfa(ta) != findfa(tb)) fa[findfa(tb)] = findfa(ta);}
    for (int i = 1; i <= p; ++i) {
        scanf("%d%d", &ta, &tb);
        if (findfa(ta) != findfa(tb)) printf("No\n");else printf("Yes\n");}  
  	// 集合个数
		for (int i = 1; i <= n; ++i) if (fa[i] == i) cnt++; printf("%d\n", cnt-1);// cnt即为集合个数}

并查集-给定处于敌对集合的元素关系,敌对集合

关键:敌对的敌对是朋友。运用反集解决。

int n, m, fa[maxn], ta, tb, cnt = 0; char ch;
int findfa(int x){return fa[x]==x?x:findfa(fa[x]);}
int main() {
    scanf("%d%d", &n, &m);for (int i = 1; i <= 2*n; ++i) fa[i] = i;
    for (int i = 0; i < m; ++i) {
        cin>>ch>>ta>>tb;
        if (ch == 'F'){
            fa[findfa(ta)] = findfa(tb);
        } else{
            fa[findfa(ta+n)] = findfa(tb);
            fa[findfa(tb+n)] = findfa(ta);}}
    for (int i = 1; i <= n; ++i) if (fa[i] == i) cnt++; printf("%d", cnt);}

字符串-trie树,动态不断查询,返回当前查询是否是第一次出现或者重复出现

struct trie {
    int nex[maxn][26], cnt; int exist[maxn]; // 0 没出现;1 第一出现;2 重复出现
 		int val[maxn]; // -1 查不到这个人的对应的值
  	void insert(char *s) {
        int p = 0, l = strlen(s);
        for (int i = 0; i < l; i++) {
            int c = s[i] - 'a';
            if (!nex[p][c]) nex[p][c] = ++cnt;
            p = nex[p][c];}// 修改val数组 }        
    int find(char *s) {
        int p = 0, l = strlen(s);
        for (int i = 0; i < l; i++) {
            int c = s[i] - 'a';
            if (!nex[p][c]) return 0;
            p = nex[p][c];}
      	// 修改exist数组的地方
        if (!exist[p]) {exist[p] = 1;return 1;} return 2; }
  	int getvalue(char *s) {
        int p = 0, l = strlen(s);
        for (int i = 0; i < l; i++) {
            int c = s[i] - 'a'; if (!nex[p][c]) return -1; p = nex[p][c];}
        return val[p];}
}tree;
int n, m; char s[55];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) { scanf("%s", s); tree.insert(s);}
    scanf("%d", &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%s", s);
        switch (tree.find(s)) {
        case 0: printf("WRONG\n");break; case 1: printf("OK\n");break; case 2: printf("REPEAT\n");break;}}}

bfs-最短步数、路径

int mp[maxn][maxn], vis[maxn][maxn], dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}, ansx[300], ansy[300], idx;
struct node{int x, y;node * fa;node(){}node(int x, int y, node * fa): x(x), y(y), fa(fa){}};
queue<node> q;
void printTrace(node nw){
    ansx[idx] = nw.x;ansy[idx++] = nw.y;node * nt = nw.fa;
    while (nt!=NULL) { ansx[idx] = nt->x;ansy[idx++] = nt->y; nt = nt->fa;}
    for (int i = idx-1; i >= 0; --i) printf("(%d, %d)\n",ansx[i], ansy[i]);}
void bfs(int x, int y) {
    q.push(node(x, y, NULL));
    while (!q.empty()) {
        node nw = q.front();
        if (nw.x == 4 && nw.y == 4) {printTrace(nw);return;}
        for (int i = 0; i < 4; ++i) {
            int nx = nw.x+dir[i][0], ny = nw.y+dir[i][1];
            if (nx == 4 && ny == 4) {printTrace(node(nx, ny, &nw));return;}
            if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && !mp[nx][ny] && !vis[nx][ny]) {
                vis[nx][ny] = 1; q.push(node(nx, ny, &q.front()));}}
        q.pop();}}
int main() {
    for (int i = 0; i < 5; ++i) for (int j = 0; j < 5; ++j) scanf("%d", &mp[i][j]);
    bfs(0,0); }

dfs-记忆化搜索,重复调用函数,进行记录防止tle

ll ta, tb, tc, dp[maxn][maxn][maxn];
ll dfs(int a, int b, int c) {
    if (a <= 0 || b <= 0 || c <= 0) return 1;
    if (a > 20 || b > 20 || c > 20) return dfs(20, 20, 20);
    if (dp[a][b][c])  return dp[a][b][c];
    if (a < b && b < c) return dp[a][b][c] = dfs(a, b, c-1) + dfs(a, b-1, c-1) - dfs(a, b-1, c);
    else return dp[a][b][c] = dfs(a-1, b, c) + dfs(a-1, b-1, c) + dfs(a-1, b, c-1) - dfs(a-1, b-1, c-1);}
int main() {
    while (scanf("%lld%lld%lld", &ta, &tb, &tc) && !(ta==-1 && tb==-1 && tc==-1))
      printf("w(%lld, %lld, %lld) = %lld\n", ta, tb, tc, dfs(ta, tb, tc));}

dfs-记忆话搜索,固定变量不同的数值组合

int a, b, c, na, nb, nc, vis[25];int v[25][25][25];
void dfs(int x, int y, int z) {
    if (!x && !vis[z]) vis[z] = 1;    if (v[x][y][z]) return;
    v[x][y][z] = 1;
    if (x) {if (y < b) {
            if (x > b-y) dfs(x-(b-y), b, z);
            else dfs(0, y+x, z);}
        if (z < c) {
          	if (x > c-z) dfs(x-(c-z), y, c);
            else dfs(0, y, z+x);}}
    if (y) {if (x < a) {
            if (y > a-x) dfs(a, y-(a-x), z);
            else dfs(x+y, 0, z);}
        if (z < c) {
            if (y > c-z) dfs(x, y-(c-z), c);
            else dfs(x, 0, z+y);}}
    if (z) {if (x < a) {
            if (z > a-x) dfs(a, y, z-(a-x));
            else dfs(x+z, y, 0);}
        if (y < b) {
            if (z > b-y) dfs(x, b, z-(b-y));
            else dfs(x, y+z, 0);}}}
int main() {
    scanf("%d%d%d", &a, &b, &c);na = 0, nb = 0, nc = c;vis[c] = 1;dfs(0, 0, c);
    for (int i = 0; i <= 21; ++i)if (vis[i]) printf("%d ", i);}

DFS-记忆话搜索,前面DFS输出所有组合数

通过剪枝的方式,记录上一层的last,然后保证递增可以,也可以通过记忆话搜索给记录下来

dp[0][0] = 1; // 首先初始化一下
for (int i = 1; i <= total; ++i) // 遍历第一维度的时候就不会再涉及到初始化的那个维度,不然会覆盖掉
    for (int j = i; j <= total; ++j)
        for (int k = 1; k <= n; ++k)
            dp[k][j] += dp[k-1][j-i];

DFS-记忆话搜索,组合数【小于等于4个数平方的和 组合成目标数】 的方案总和

dp[0][0] = 1;
for (int i = 1; i*i <= M; ++i) // 遍历第一维度的时候就不会再涉及到初始化的那个维度,不然会覆盖掉
    for (int j = i*i; j <= M; ++j)
        for (int k = 1; k <= 4; ++k)
            dp[k][j] += dp[k-1][j-i*i];

DFS-记忆话搜索,组合数【不限个数 组合成目标数】的方案总和

dp[1][1]=1;
for (int i = 2; i <= n; ++i)
    for (int j = 0; j <= nn/2; ++j)
        if (j > i) dp[i][j] = dp[i-1][j]+dp[i-1][j-i];
        else dp[i][j] = dp[i-1][j];

DFS-记忆话搜索,地图中最长的路线

int r, c, mp[maxn][maxn], dp[maxn][maxn], ans, dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // dp[i][j]这个点开始的最长连续下降的长度
int dfs(int x, int y) {
    if (dp[x][y]) return dp[x][y];
    dp[x][y] = 1;
    for (int i = 0; i < 4; ++i) {
        int nx = x+dir[i][0], ny = y+dir[i][1];
        if (nx >= 0 && nx < r && ny >= 0 && ny < c && mp[nx][ny] < mp[x][y]){
            dfs(nx, ny);dp[x][y] = max(dp[x][y], dp[nx][ny]+1);}}
    return dp[x][y];}
int main() {
    scanf("%d%d", &r, &c);
    for (int i = 0; i < r; ++i) for (int j = 0; j < c; ++j) scanf("%d", &mp[i][j]);
    for (int i = 0; i < r; ++i) for (int j = 0; j < c; ++j) ans = max(ans, dfs(i, j));
    printf("%d\n", ans);}

数论-获取唯一的奇数个的不匹配的数 & 找未配上的对

  • 思路一:数组存,然后排序,然后再遍历,两个两个遍历=> 爆内存,爆时间。
  • 思路二:map存,找到配对的删除。一边即过。=> 6个点爆内存
  • 正确思路:直接用一个变量,然后来异或^所有的数,a^a = 0,所以最后剩下的那个数就是没匹配的。
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {scanf("%d", &t); ans ^= t;}
printf("%d\n", ans);    

数论-获取唯一的出现偶数次数的 & 找配上对的

这个需要先把所有存在的数都输入进去,得到所有数的异或,然后再异或数组种的所有数,那么出现偶数次的就会显露出来了,出现单次的就会和第一次的异或掉了。

scanf("%d", &n);
for (int i = 1; i <= n; ++i) {scanf("%d", &t);ans^=t;}
scanf("%d", &m);
for (int i = 1; i <= m; ++i) {scanf("%d", &t);ans^=t;}

数论-区间中可以用平方差计算得到的个数

题目大意:区间[a, b]中,某个数i,这个数i可以写成c^2-d^2

正向数学推导:i=(c+d)(c-d),那么c+d/c-d必定为同奇偶,同奇偶必定乘积要不满足是奇数,要不满足是4的倍数(因为是两个2的倍数相乘)。

反推验证:若i为奇数,也就是2k+1,那么可以找到c=k+1, d=k满足c+d=2k+1与c-d=1的乘积为2k+1这个条件。

若i为4的倍数,也就是4k,那么可以找到c=k+1, d=k-1满足c+d=2k与c-d=2的乘积是4k这个条件。

for (int i = a; i <= b; ++i)
    if (i%2 || !(i%4)) ans++;

数论-第二类Stirling数

数学意义:把n个数划分成k个集合

实际意义:将n个球分到k个相同的盒子

// 递归写法
ll stirling(int n, int k){
    if (k==n || k==1) return 1;
    else if (k==2) return pow(2, (n-1)*1.0)-1;
    else return stirling(n-1, k-1)+k*stirling(n-1, k);
}
// 非递归写法

数论-第二类Stirling数的变形

数学意义:把n个数划分成k个不同的集合

实际意义:把n个球分到k个不同的盒子里

和第二类Stirling数的区别:就是划分出来的集合再进行容器的匹配,对于不同的集合划分到不同的容器中。匹配原则:Ann

ll stirling(int n, int k){
    if (k==n || k==1) return 1;
    else if (k==2) return pow(2, (n-1)*1.0)-1;
    else return stirling(n-1, k-1)+k*stirling(n-1, k);
}
// 排列数Ann
ll factorial(ll n) {
    ll fc = 1;
    for (ll i = 1; i <= n; ++i) fc *= i;
    return fc;
}

数论-线性素数筛,高效率达标素数

线性筛:O(n)

prime是质数列表,isprime

#define maxn 10000010
int vis[maxn], prime[maxn], isprime[maxn];

void Prime()
{
    for(int i=2; i<=b; i++)
    {
        if(!vis[i]) prime[cnt++] = i, isprime[i] = 1;
        for(int j=0; j<cnt&&i*prime[j]<=b; j++)
        {
            vis[i*prime[j]] = i;
            if(i%prime[j]==0) break;
        }
    }
}
b = 100; // 设置筛的边界
LPrime();
for (int i = 5; i < 20; ++i) {
    printf("%d %d %d\n", i, prime[i], isprime[i]); // prime是按照顺序的素数存放进来, isprime是索引的数是否为质数
}

数据结构-ST表,RMQ,区间最小最大值RangeMinMaxQuery,包含最大与最小

int n, m, a[maxn], maxx[maxn][21], minn[maxn][21], ta, tb;
inline int read() { // 快速读取模版
    int x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();} return x*f;}
void init() {
    for (int i = 1; i <= n; ++i) {minn[i][0] = a[i]; maxx[i][0] = a[i];}
    for (int j = 1; j <= 21; ++j) for (int i = 1; i+(1<<j)-1 <= n; ++i){
            maxx[i][j] = max(maxx[i][j-1], maxx[i+(1<<(j-1))][j-1]);
            minn[i][j] = min(minn[i][j-1], minn[i+(1<<(j-1))][j-1]);}}
int query_max(int l, int r) { int k = log2(r-l+1); return max(maxx[l][k], maxx[r-(1<<k)+1][k]);}
int query_min(int l, int r) { int k = log2(r-l+1); return min(minn[l][k], minn[r-(1<<k)+1][k]);}
int main() {
    n = read();m = read(); for (int i = 1; i <= n; ++i) a[i] = read(); init();
    while (m--) { ta = read();tb = read(); printf("%d %d\n", query_min(ta, tb), query_max(ta, tb));}}

数据结构-ST表,RGCD,区间最小公倍数,可重复贡献

int n, m, a[maxn], gcdd[maxn][21], ta, tb;
int gcd(int a, int b) {return b>0?gcd(b, a%b):a;}
void init(){
    for (int i = 1; i <= n; ++i) gcdd[i][0] = a[i];
    for (int j = 1; j <= 21; ++j) for (int i = 1; i+(1<<j)-1 <= n; ++i) gcdd[i][j] = gcd(gcdd[i][j-1], gcdd[i+(1<<(j-1))][j-1]); }
int query_gcd(int l, int r) { int k = log2(r-l+1); return gcd(gcdd[l][k], gcdd[r-(1<<k)+1][k]);}
int main() {
    scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);init();
    while (m--) { scanf("%d%d", &ta, &tb); printf("%d\n", query_gcd(ta, tb));}}

二叉树-哈夫曼编码

struct node {    int data;    node *lchild;    node *rchild;} *huffmantree, huffman[maxn];
int n, ll, rr;
struct nd {    int val, idx;    bool operator < (const nd n) const {return val > n.val;}};
priority_queue<nd, vector<nd>, less<nd>> pq;
void PreOrder(node *T) {if (T) {cout << T->data << " "; PreOrder(T->lchild);PreOrder(T->rchild);}}
node * HuffmanTree() {
    for (int j = 0; j < n; ++j) pq.push({huffman[j].data, j});
    for (int i = 0; i < n - 1; i++) {
        ll = pq.top().idx;pq.pop();rr = pq.top().idx;pq.pop();
        node * lnode = new node {huffman[ll].data, huffman[ll].lchild, huffman[ll].rchild};
        huffman[ll] = {huffman[ll].data + huffman[rr].data, lnode, &huffman[rr]};
        pq.push({huffman[ll].data, ll});}
    return &huffman[ll];}
int main(void) {
    scanf("%d", &n);for (int i = 0; i < n; i++) scanf("%d", &huffman[i].data);
    // build tree
    huffmantree = HuffmanTree();PreOrder(huffmantree);}

二叉搜索树

性质情况一:左儿子小于父节点 && 右儿子大于父节点 => 中序遍历得到递增序列情况二:左儿子大于父节点 && 右儿子小于父节点 => 中序遍历得到递减序列

实现二叉链表实现,每添加一次新的值,就build一次,从根节点往下插入新的值;要插入的数比当前节点的值小=>往左子树插入;要插入的数比当前节点的值大=>往右子树插入;然后如果插到最底部了,当前这个节点直接NULL了,那就重新new一个这个要插入的数对应的节点。

struct nd {int val, pri;    bool operator < (const nd n) const {return pri < n.pri;}}a[35];
int n, nwval, nwpri;
struct node {    int val, pri;    node * l, *r;}* root;
node * build(node * nw) {
    if (nw == NULL) {nw = new node();nw->pri = nwpri;nw->val = nwval;nw->l = nw->r = NULL;return nw;}
    if (nwval <= nw->val) nw->l = build(nw->l);else nw->r = build(nw->r);return nw;}
queue<node*> q;
vector<int> v_val, v_pri;
void level_traverse(node * nw) {
    q.push(nw);
    while (!q.empty()) {
        node * nwnode = q.front();q.pop();
        v_val.push_back(nwnode->val);v_pri.push_back(nwnode->pri);
        if (nwnode->l) q.push(nwnode->l);if (nwnode->r) q.push(nwnode->r);}}
int main() {
    scanf("%d", &n);for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i].val, &a[i].pri);sort(a+1, a+1+n);
    for (int i = 1; i <= n; ++i) { nwval = a[i].val, nwpri = a[i].pri; root = build(root);}
    level_traverse(root);
    for (int i = 0; i < v_val.size(); ++i) { if (i != 0) cout<<" ";cout<<v_val[i];}
    for (int i = 0; i < v_pri.size(); ++i) { if (i != 0) cout<<" "; cout<<v_pri[i];}}

二叉链表

由于是二叉链表,实质上是指针指向的,所以就写一个递归的返回指针的函数

node * build() {  char ch;  cin>>ch;
  if (ch == '#') return NULL;  else {// 声明出当前指向结构体的指针
    node * n = (node*)malloc(sizeof(node));n->data = ch-'0';n->lchild = build();n->rchild = build();  }}
// main函数里 => 先创建一个指向根节点的指针,然后就可以开始给这个指针build了
node * tree = (node*)malloc(sizeof(node)); tree = build();

4、前周后序遍历,都只需要将指向根节点的指针传入即可。

struct node {
    int data;    node * lchild;    node * rchild;
    node(){}    node(int data): data(data){}
    node(int data, node * lchild, node * rchild): data(data), lchild(lchild), rchild(rchild){}};
char ch;// 构造二叉树
node * build(){
    cin>>ch; if (ch == '#') return NULL;
    else {
        node * n = (node*)malloc(sizeof(node)); n->data = ch-'0'; n->lchild = build(); n->rchild = build();
        return n;}}
void pre_traverse(node * n) { cout<<n->data<<" "; if (n->lchild) pre_traverse(n->lchild); if (n->rchild) pre_traverse(n->rchild);} // 前序遍历
void in_traverse(node * n) { if (n->lchild) in_traverse(n->lchild); cout<<n->data<<" "; if (n->rchild) in_traverse(n->rchild);} // 中序遍历
void post_traverse(node * n) {if (n->lchild) post_traverse(n->lchild); if (n->rchild) post_traverse(n->rchild);cout<<n->data<<" ";}// 后序遍历
// 非递归遍历
int cnt_node, cnt_1, cnt_2, cnt_leaf, val_min=INT_MAX, val_max;
queue<node*> q1;
void non_recursive_traverse(node * n) {
    q1.push(n);
    while (!q1.empty()) {
        node * nw = q1.front();q1.pop();cnt_node++;
        val_min = min(val_min, nw->data); val_max = max(val_max, nw->data);
        if (nw->lchild && nw->rchild) cnt_2++;
        else if (nw->lchild==NULL && nw->rchild==NULL) cnt_leaf++;
        else cnt_1++;
        if (nw->lchild) q1.push(nw->lchild);        if (nw->rchild) q1.push(nw->rchild);}}
queue<node*> q2;// 选做内容:bfs 层次遍历
void bfs(node * n) {
    q2.push(n);
    while (!q2.empty()) {
        node * nw = q2.front();q2.pop();
        cout<<nw->data<<" "; if (nw->lchild) q2.push(nw->lchild); if (nw->rchild) q2.push(nw->rchild);}}
int main() {
    node * tree = (node*)malloc(sizeof(node));
    tree = build();
    cout<<"前序遍历: "; pre_traverse(tree); cout<<endl<<"中序遍历: "; in_traverse(tree);
    cout<<endl<<"后序遍历: "; post_traverse(tree);
    cout<<endl<<"非递归遍历: "; non_recursive_traverse(tree);
    cout<<"节点个数:"<<cnt_node<<"  度为1的节点个数:"<<cnt_1<<"  度为2的节点个数:"<<cnt_2<<"  叶子节点个数:"<<cnt_leaf<<endl<<"最大值:"<<val_max<<"  最小值:"<<val_min;
    cout<<endl<<"层次遍历(bfs): "; bfs(tree); cout<<endl;}

二叉树建树 - 节点值做索引表示

https://www.luogu.com.cn/problem/P1305

1、节点值做索引的数据结构

结构体中不需要当前节点的值,因为这个节点的值已经在做数据结构的索引了

struct node {int left, right;}tree[maxnode];

要求给出的数据(节点的顺序必须为对应的,不然这样匹配是有问题的)

// 读入字符串abc,得到a为根节点,bc分别为两个子节点 (注意读取单个字符的时候,要给空格来冲刷掉回车的影响)
scanf(" %c", &ch); scanf(" %c%c", &tree[ch].left, &tree[ch].right);

2、前中后序的遍历

  • 前:根->左->右
  • 中:左->根->右
  • 后:右->根->左
void front_traverse(char ch) {
  printf("%c", ch);
  if () front_traverse(tree[ch].left);
  if () front_traverse(tree[ch].right);
}
void mid_traverse(char ch) {
  if () mid_traverse(tree[ch].left);
  printf("%c", ch);
  if () mid_traverse(tree[ch].right);
}
void back_traverse(char ch) {
  if () back_traverse(tree[ch].left);
  if () back_traverse(tree[ch].right);
  printf("%c", ch);
}

AC代码:

#include <iostream>
using namespace std;
int n;
struct node {
    char left, right;
}tree[1000];
char ch, root;

void front_traverse(char ch) {
    // front traverse => root, left, right
    printf("%c", ch);
    if (tree[ch].left != '*') front_traverse(tree[ch].left);
    if (tree[ch].right != '*') front_traverse(tree[ch].right);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf(" %c", &ch);
        if (i == 1) root = ch;
        scanf(" %c%c", &tree[ch].left, &tree[ch].right);
    }
    front_traverse(root);
    return 0;
}

二叉树 - 节点值做索引 搜索深度

https://www.luogu.com.cn/problem/P4913

1、遍历的过程中就筛选出最大的深度,通过维护一个ans来提取。

第一种,通过在dfs深搜到儿子节点之前来判断是否要搜他。

void dfs(int val, int depth) {
  ans = max(ans, depth);
  if (!tree[val].left) dfs(tree[val].left, depth+1);
  if (!tree[val].right) dfs(tree[val].right, depth+1);
}

第二种,通过在搜到之后,判断这个搜到的点是否符合搜的要求。

void dfs(int val, int depth) {
  if (!val) return;
  ans = max(ans, depth);
  dfs(tree[val].left, depth+1);
  dfs(tree[val].right, depth+1);
}

AC代码:

#include <iostream>
using namespace std;
#define maxnode 1000010
struct node{
    int left, right;
}tree[maxnode];
int n, ans;
void dfs(int val, int depth) {
    ans = max(ans, depth);
    if (tree[val].left) dfs(tree[val].left, depth+1);
    if (tree[val].right) dfs(tree[val].right, depth+1);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d%d", &tree[i].left, &tree[i].right);
    dfs(1, 1);
    printf("%d\n", ans);
    return 0;
}

二叉树的前序 中序 后序 dfs序等性质 // 【给出前后,求中序】

题目:给出前序后序,不给中序,求这棵树有多少种形态。【中序有多少种】

分析:前序:根左右,中序:左根右,后序:左右根

性质:一个树有多少种形态,取决于儿子节点只有1个的节点的个数。【形态数 = pow(2, 儿子节点为1的节点个数)】

  • 如果一棵树没有只有一个儿子节点的节点=》也就是是一个完满二叉树,只要有儿子节点,就是两个,要不就没有儿子节点。
    • 此时树形态已经被确定了,例如前序abc后序bca,那这就是一个a->(b,c)的完满二叉树,在例如前序abdecfg后序debfgca,那就是一个a->(b->(d,e), c->(f,g))的完满二叉树
  • 如果一个棵树的节点都只有一个儿子节点=》和一根线一样,就例如如果就是abc往下排列的一根线,那么可以计算得到两个节点满足只有一个儿子节点,那么总共有4种,分别为左左,左右,右左,右右。
#include <iostream>
using namespace std;
string pre, post;
int ans;

int main() {
    cin>>pre>>post;
    for (int i = 0; i < pre.length()-1; ++i)
        for (int j = 0; j < post.length()-1; ++j)
            if (pre[i] == post[j+1] && post[j] == pre[i+1]) ans++;
        printf("%d\n", 1<<ans);
    return 0;
}

二叉树的前序 中序 后序 dfs序等性质 // 【给出中序+前后中的一个,求另一个】

https://www.luogu.com.cn/problem/P1030 该题是由中序+后序求前序

https://www.luogu.com.cn/problem/P1827 该题是由中序+前序求后序

思路:首先明确前:根左右 中:左根右 后:左右根

然后整体思路就是通过前或者后的根在一边的特性,直接从对应的一段提取出根,然后再在中序中找到根,根左边的就是左子树,根右边的就是右子树,然后再递归两颗子树即可。

string pre, in, post;
void transform_pre(string i, string p) {
    if (i.length() > 0) {
        char root = p[p.length() - 1];
        cout << root;
        int pos = i.find(root);
        transform_pre(i.substr(0, pos), p.substr(0, pos));
        transform_pre(i.substr(pos + 1), p.substr(pos, i.size() - pos - 1));}}
void transform_post(string pr, string i) {
    if (i.length() > 0) {
        char root = pr[0];
        int pos = i.find(root);
        transform_post(pr.substr(1, pos), i.substr(0, pos));
        transform_post(pr.substr(pos + 1), i.substr(pos + 1));
        cout << root;}}
int main() {    cin >> in >> pre;    transform_post(pre, in);}
//1 2 3 4 5 6 7//中序遍历: 3256471//后序遍历: 3657421 //1 2 4 5 3 6 7//中序遍历: 4251637//后序遍历: 4526731

树状数组-模版-区间求和(查询)、单点修改(操作)

0、lowbit()看当前节点的归属情况/看当前节点所管辖的节点的个数 eg:8(10) & -8(10) = 8 => 根据树状数组结构图,就是8个节点

eg:4(10) & -4(10) = 4 => 根据树状数组结构图,就是4个节点 eg:6(10) & -6(10) = 2 => 根据树状数组结构图,就是2个节点

1、单点修改 => 自下而上修改 => c数组的索引pos从1开始往上找,但是要限定永远≤n => 从下往上找的话,看当前的节点归属那个父节点范围,则需要pos+=lowbit(pos),此时就可以直接爬升到父节点。

void single_add(int pos, int k) { while(pos <= n) { c[pos] += k; pos += lowbit(pos);}}

2、区间求和「注意这个区间求的是前缀和,也就是1到pos的和。如果区间和的话,可以通过两个前缀和相减得到」=> 自上而下累加 => c数组的索引pos从target目标开始往下找,但是要限定下限,不能让下限爆掉,pos≥1 => 从上往下累加的话,看当前的节点归属那个的子节点,则需要pos-=lowbit(pos),此时就可以直接下降到子节点。

int getsum(int pos) {int ans = 0; while(pos >= 1) { ans += c[pos]; pos -= lowbit(pos); } }
int n, m, tm, tp, ta, tb, c[maxn];
int lowbit(int x) {return x & (-x);}
void single_add(int pos, int k) { while (pos <= n) {c[pos] += k;pos += lowbit(pos);}}
int getsum(int pos) { int ans = 0; while (pos >= 1) { ans += c[pos]; pos -= lowbit(pos);}return ans;}
int main() {
    scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++i) {scanf("%d", &tm);single_add(i, tm);}
    while (m--) {
        scanf("%d%d%d", &tp, &ta, &tb);
        if (tp-1) printf("%d\n", getsum(tb)-getsum(ta-1));else single_add(ta, tb);}}

树状数组-模版-区间修改(操作)、单点求和(查询)

区间修改+单点求和 模版:https://www.luogu.com.cn/problem/P3368

区间修改+单次范围最值 【范围最值也可以看作是所有的点取一遍最值】:https://www.luogu.com.cn/problem/P2367

1、区间修改:考虑到差分,之不过是在树上进行差分,利用树状数组进行差分,此时对于树状数组c的修改就只需要修改两头即可了,也就是在l的位置加上k,在r+1的位置减去k,最后再利用树状数组c进行还原即可。

2、此时沿着树状数组进行求和,求的就不是上面的那个区间和了 => 因为这个树状数组代表的是差分,累加所得到的该索引的数组的值。

P3368模版区间修改+多次查询单个点

int n, m, a[maxn], c[maxn], tp, ta, tb, tc;
int lowbit(int x) {return x & (-x);}
void single_add(int pos, int k) {
    while (pos <= n) {
        c[pos] += k;
        pos += lowbit(pos);    }}
void interval_add(int l, int r, int k) {    single_add(l, k);    single_add(r+1, -k);}
int getsum(int pos) {
    int ans = 0;
    while (pos >= 1) {
        ans += c[pos];
        pos -= lowbit(pos);
    }    return ans;}
int getval(int pos) {    return a[pos] + getsum(pos);}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    while (m--) {
        scanf("%d", &tp);
        if (tp-1) {scanf("%d", &ta);printf("%d\n", getval(ta));}
        else {scanf("%d%d%d", &ta, &tb, &tc);interval_add(ta, tb, tc);}}}

P2367区间修改+最终单次查询所有点

int n, m, a[maxn], c[maxn], ta, tb, tc, minn = (1<<31)-1; // c为树上的差分数组,a为记录原数据的数组
#define lowbit(x) x&(-x)
void add(int pos, int k) {
    while (pos <= n) {
        c[pos] += k;
        pos += lowbit(pos);    }}
void interval_add(int l, int r, int k) {    add(l, k);    add(r+1, -k);}
int query(int pos){
    int ans = 0;
    while (pos >= 1) {
        ans += c[pos];
        pos -= lowbit(pos);}
    return ans;}
int main() {
    scanf("%d%d", &n, &m);   for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    while (m--) {        scanf("%d%d%d", &ta, &tb, &tc);        interval_add(ta, tb, tc);    }
    for (int i = 1; i <= n; ++i) minn = min(a[i]+query(i), minn);
    printf("%d\n", minn);}

树状数组-模版-区间修改(操作)、区间求和(查询)

https://www.luogu.com.cn/problem/P2367

1、区分上面的单点修改+区间求和 // 区间修改+单点查询,都可以解决尾一类问题,核心代码相似,只不过后者就是前者的基础上增添了差分的思想,根据差分用求和来查单点的值 == 根据累加用单点来查求和的值。

2、区间修改+区间查询需要维护两个数组,sum1数组是求和的数组,sum2数组是乘积的数组。进行区间修改的时候,进行差分来修改 // 进行区间查询的时候,根据前缀和来进行查询。

区间修改:

void add(ll pos, ll k) {
    ll tem = k*pos;
    while (pos <= n) {
        sum1[pos] += k;sum2[pos] += tem;
        pos += lowbit(pos);}}
void interval_add(ll l, ll r, ll k) {    add(l, k);    add(r+1, -k);}

区间查询

    ll ans = 0, tem = pos;
    while (pos >= 1) {
        ans += ((tem+1)*sum1[pos] - sum2[pos]);
        pos -= lowbit(pos);
    }
    return ans;
}

ll interval_query(ll l, ll r) {
    return query(r)-query(l-1);
}

完整代码

ll n, m, tm, last, first_val, sum1[maxn], sum2[maxn], tp, ta, tb, tc;
#define lowbit(x) x&(-x)
void add(ll pos, ll k) {
    ll tem = k*pos;
    while (pos <= n) {
        sum1[pos] += k;sum2[pos] += tem;
        pos += lowbit(pos);}}
void interval_add(ll l, ll r, ll k)    add(l, k);    add(r+1, -k);}
ll query(ll pos) {
    ll ans = 0, tem = pos;
    while (pos >= 1) {
        ans += ((tem+1)*sum1[pos] - sum2[pos]);
        pos -= lowbit(pos);}
    return ans;}
ll interval_query(ll l, ll r) {    return query(r)-query(l-1);}
int main() {
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; ++i) {scanf("%lld", &tm);add(i, tm-last);last=tm;}
    while (m--) {
        scanf("%lld", &tp);
        switch (tp) {
            case 1: scanf("%lld%lld%lld", &ta, &tb, &tc);interval_add(ta, tb, tc);break;
            case 2: scanf("%lld", &ta);first_val += ta;break;
            case 3: scanf("%lld", &ta);first_val -= ta;break;
            case 4: scanf("%lld%lld", &ta, &tb);printf("%lld\n", interval_query(ta, tb)+(ta==1)*first_val);break;
            case 5: printf("%lld\n", query(1)+first_val);break;}}}

图论-LCA最近公公祖先

int n, m, root, ta, tb, depth[maxnode], p[maxnode][21];
struct node {    int to, next;}edge[maxnode<<1];int head[maxnode],tot;
void addedge(int from, int to) {edge[++tot].to = to; edge[tot].next = head[from];head[from] = tot;}
void dfs(int from, int fa) {
    depth[from] = depth[fa]+1;
    p[from][0] = fa;
    for (int i = 1; (1<<i) <= depth[from]; ++i) p[from][i] = p[p[from][i-1]][i-1];
    for (int i = head[from]; i; i=edge[i].next) {
        int to = edge[i].to;        if (to != fa) dfs(to, from);}}
int lca(int a, int b) {
    if (depth[a] > depth[b]) swap(a, b);
    for (int i = 20; i >= 0; --i) if (depth[a] <= depth[b]-(1<<i)) b = p[b][i];
    if (a == b) return a;
    for (int i = 20; i >= 0; --i)
        if (p[a][i] == p[b][i]) continue;else a = p[a][i],b=p[b][i];
    return p[a][0];}
int main() {
    scanf("%d%d%d", &n, &m, &root);
    for (int i = 1; i <= n-1; ++i) {scanf("%d%d", &ta, &tb);addedge(ta, tb);addedge(tb, ta);}
    dfs(root, 0);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &ta, &tb);int ans = lca(ta, tb);
        int hh=H[a]+H[b]-H[u]*2+(PZ[u]=='H');
        int gg=G[a]+G[b]-G[u]*2+(PZ[u]=='G');
        if(c=='H'){if(hh) printf("1");else   printf("0");}
        else{if(gg) printf("1");else   printf("0");}
    printf("%d\n", lca(ta, tb));}}

图论-起终点一样,权值和为0,floyd算法

题目大意:给出一个图,有双向边和单向边(其中单向边的权值是负的),问是否存在路径可以满足起终点一样权值和为0

int t, n, m, w, mp[maxn][maxn], ta, tb, tc;
bool Floyd() {
    for (int k = 1; k <= n; ++k)for (int i = 1; i <= n; ++i){for (int j = 1; j <= n; ++j)
                if (mp[i][k]+mp[k][j] < mp[i][j]) mp[i][j] = mp[i][k]+mp[k][j];
            if (mp[i][i] < 0) return true; // 判断负权闭环
        }    return false;}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d", &n, &m, &w);
        for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j){ if (i == j) mp[i][j] = 0; mp[i][j] = mp[j][i] = inf; }
        while (m--){
            scanf("%d%d%d", &ta, &tb, &tc);
            if (tc < mp[ta][tb]) mp[ta][tb] = mp[tb][ta] = tc;
        }
        while (w--){scanf("%d%d%d", &ta, &tb, &tc);mp[ta][tb] = -tc;}
        if (Floyd()) puts("YES"); else puts("NO");}
    return 0;}

图论-Floyd - 传递闭包

题意:给出已知的大小关系,问可以确定具体排名的个数有多少。

#include <iostream>
using namespace std;
const int maxn = 109;
int n, m, mp[maxn][maxn], ta, tb, ans;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &ta, &tb);
        mp[ta][tb] = 1;
    }
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (mp[i][k] && mp[k][j]) mp[i][j] = 1;
    for (int i = 1; i <= n; ++i) {
        int tem = 0;
        for (int j = 1; j <= n; ++j)
            if (mp[i][j] || mp[j][i]) tem++;
        if (tem == n-1) ans++;
    }
    printf("%d\n", ans);
    return 0;
}

Posted on Feb 4, 2020