CF786B.Legacy
留着以后复习

#include <iostream>
#include <cstring>
#include <functional>
#include <queue>
#include <vector>

using namespace std;

using i64 = long long;
using PII = pair<i64, int>;

const int N = 100010, M = 5000010, P = 400000;
const i64 INF = 1e18;

struct Node {
    int l, r;
}tr[N << 3]; // 两棵树一起开 同一个真实结点在两棵树里面的叶子结点编号差值相同 用偏移量
int e[M], ne[M], h[N << 3], idx;
int w[M]; 
int mp[N]; // 真实结点编号到线段树结点编号的映射
int n, m, S;
i64 dis[N << 3]; // 不开longlong见祖宗
bool vis[N << 3];

void insert(int u, int v, int d) {
    e[idx] = v, ne[idx] = h[u], w[idx] = d, h[u] = idx++;
}

void build(int u, int l, int r) {
    tr[u] = {l, r};
    if (l == r) return void(mp[l] = u);
    int mid = l + r >> 1;
    insert(u, u << 1, 0), insert(u, u << 1 | 1, 0); // 出树往子节点连
    insert((u << 1) + P, u + P, 0), insert((u << 1 | 1) + P, u + P, 0); // 入树往父节点连
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int l, int r, int v, int w, int op) {
    if (tr[u].l >= l && tr[u].r <= r) { // 连边区间完全包含结点区间
        if (op == 2) insert(v + P, u, w); // 入树叶子结点连出树区间结点
        if (op == 3) insert(u + P, v, w); // 入树区间结点连出树叶子结点
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) modify(u << 1, l, r, v, w, op);
    if (r > mid) modify(u << 1 | 1, l, r, v, w, op);
}

int main() {
    cin.tie(0), cout.tie(0)->sync_with_stdio(false);

    cin >> n >> m >> S;

    memset(h, -1, sizeof h);
    build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        insert(mp[i], mp[i] + P, 0);
        insert(mp[i] + P, mp[i], 0); // 入树出树叶子结点互连
    }

    while (m--) {
        int op, u, v, l, r, w;
        cin >> op;
        if (op == 1) cin >> u >> v >> w, insert(mp[u] + P, mp[v], w); // 单点连单点直接连
        else cin >> v >> l >> r >> w, modify(1, l, r, mp[v], w, op);
    }

    function<void(int)> dijkstra = [&](int S) {
        memset(dis, 0x3f, sizeof dis);
        priority_queue<PII, vector<PII>, greater<PII>> heap;
        dis[S] = 0;
        heap.push({0, S});
        while (heap.size()) {
            auto tt = heap.top();
            heap.pop();
            int t = tt.second;
            if (vis[t]) continue;
            vis[t] = true;
            for (int i = h[t]; ~i; i = ne[i]) {
                int j = e[i];
                if (dis[j] > dis[t] + w[i]) {
                    dis[j] = dis[t] + w[i];
                    heap.push({dis[j], j});
                }
            }
        }
    };

    dijkstra(mp[S] + P);
    for (int i = 1; i <= n; i++) {
        if (dis[mp[i]] > INF / 2) cout << "-1 ";
        else cout << dis[mp[i]] << ' ';
    }
    return 0;
}



二分图最大团+暴力枚举

先看题意 求无向图的最大团 那么这个问题是没有多项式解的 要从题的特殊性质入手

观察到A国两个人互为朋友的条件是奇偶性不同

那么在最大团中 A国最多只能出现0或1或2个人 因为3个A国人中至少有两个奇偶性相同 不满足条件

又观察到B国两个人互为朋友的[充分]条件是奇偶性相同

那么B国人是一个二分图 二分图的最大团即为二分图补图(把原图中没边的点都连上边 有边的点都不连边)的最大独立集 从定义出发很好证明

于是我们可以枚举A国人的所有选择方案 找出B国中和这些A国人都认识的人

每次重新建图求B国中的最大团 然后加上选出的A国人

跑最大流的话每次要重新建图 所以时间复杂度很玄学 我这里加了个最优性剪枝才过:对于某个A国人的选择方案 即使把B国所有能选的人都选上之后仍然小于等于之前的最优解 就直接跳过

听说匈牙利时间戳优化可以不用重新建图 跑的巨快 但是我不会!

代码挺长 但大部分是板子和重复代码

$Code$

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

using i64 = long long;

const int N = 3110, M = 5000010, INF = 0x3f3f3f3f;

int S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
int A, B, m;
bool g[N][N];
short cnt[N][N];
int a[N], b[N];
vector<int> odd_B, even_B;
int res;

int count(int x) {
    int res = 0;
    while (x) x -= x & -x, res++;
    return res;
}

void init() {
    for (int i = 1; i <= B; i++) h[i] = -1;
    h[S] = h[T] = -1;
    idx = 0;
}

void insert(int u, int v, int d) {
    e[idx] = v, ne[idx] = h[u], f[idx] = d, h[u] = idx++;
    e[idx] = u, ne[idx] = h[v], f[idx] = 0, h[v] = idx++;
}

bool bfs() {
    int hh = 0, tt = -1;
    memset(d, -1, sizeof d);
    q[++tt] = S, d[S] = 0, cur[S] = h[S];
    while (hh <= tt) {
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (d[j] == -1 && f[i]) {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                if (j == T) return true;
                q[++tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int limit) {
    if (u == T) return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
        cur[u] = i;
        int j = e[i];
        if (d[j] == d[u] + 1 && f[i]) {
            int t = find(j, min(f[i], limit - flow));
            if (!t) d[j] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic() {
    int r = 0, flow;
    while (bfs()) while (flow = find(S, INF)) r += flow;
    return r;
}

void none_A() {
    init();
    for (auto odd : odd_B) insert(S, odd, 1);
    for (auto even : even_B) insert(even, T, 1);
    for (auto odd : odd_B) 
        for (auto even : even_B) 
            if ((cnt[odd][even] & 1) == 0)
                insert(odd, even, 1);
    res = max(res, B - dinic());
}

void one_A() {
    int tot;
    for (int i = 1; i <= A; i++) {
        init(), tot = 0;
        for (auto odd : odd_B) {
            if (g[i][odd]) {
                tot++; 
                insert(S, odd, 1);
            }
        }
        for (auto even : even_B) {
            if (g[i][even]) {
                tot++; 
                insert(even, T, 1);
            }
        }
        if (tot + 1 <= res) continue;
        for (auto odd : odd_B) {
            if (!g[i][odd]) continue;
            for (auto even : even_B) {
                if (!g[i][even]) continue;
                if ((cnt[odd][even] & 1) == 0)
                    insert(odd, even, 1);
            }
        }
        res = max(res, tot - dinic() + 1);
    }
}

void two_A() {
    int tot;
    for (int i = 1; i <= A; i++) {
        for (int j = i + 1; j <= A; j++) {
            if (((a[i] ^ a[j]) & 1) == 0) continue;
            init(), tot = 0;
            for (auto odd : odd_B) {
                if (g[i][odd] && g[j][odd]) {
                    tot++;
                    insert(S, odd, 1);
                }
            }
            for (auto even : even_B) {
                if (g[i][even] && g[j][even]) {
                    tot++;
                    insert(even, T, 1);
                }
            }
            if (tot + 2 <= res) continue;
            for (auto odd : odd_B) {
                if (!g[i][odd] || !g[j][odd]) continue;
                for (auto even : even_B) {
                    if (!g[i][even] || !g[j][even]) continue;
                    if ((cnt[odd][even] & 1) == 0)
                        insert(odd, even, 1);
                }
            }
            res = max(res, tot - dinic() + 2);
        }
    }
}

int main() {
    S = N - 1, T = S - 1;
    scanf("%d%d%d", &A, &B, &m);
    for (int i = 1; i <= A; i++) scanf("%d", a + i);
    for (int i = 1; i <= B; i++) {
        scanf("%d", b + i);
        if (b[i] & 1) odd_B.push_back(i);
        else even_B.push_back(i);
    }
    for (int i = 1; i <= B; i++)
        for (int j = i + 1; j <= B; j++)
            cnt[i][j] = cnt[j][i] = count(b[i] | b[j]);
    while (m--) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u][v] = g[v][u] = true;
    }
    res = 0;
    none_A();
    one_A();
    two_A();
    printf("%d\n", res);
    return 0;   
}


新鲜事 原文

AcWing《Linux基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/57/group_buy/68351/


新鲜事 原文

a卡夫卡
2小时前
越来越感觉中国大多数人……唉😮‍💨。无力改变众生
卡夫卡



美琴
3小时前

平衡条件

  1. 左右括号相等
  2. 任意前缀左括号不少于右括号

记左括号数为 $L$,右括号数为 $R$

  1. 若字符串长度为奇数,反转任意位置都不能满足平衡条件 $1$
  2. $L = R$
    1. 字符串已平衡,此时反转任意位置都会破坏平衡条件 $1$
    2. 字符串未平衡,必然存在某前缀,左括号比右括号少一,为了满足平衡条件 $2$,要把此前缀中某个右括号变为左括号,此时整个字符串中左右括号不再相等,平衡条件 $1$ 被破坏,因此一次反转无法使之平衡
  3. $abs(L - R) \neq 2$,不妨设 $L > R$
    1. $L - R = 1$
      1. 把一个左括号变为右括号会使 $L - R = -1$,不满足平衡条件 $1$
      2. 把一个右括号变为左括号会使 $L - R = 3$,不满足平衡条件 $1$
    2. $L - R > 2$
      1. 把一个左括号变为右括号会使 $L - R > 0$,不满足平衡条件 $1$
      2. 把一个右括号变为左括号会使 $L - R > 4$,不满足平衡条件 $1$
  4. $abs(L - R) = 2$
    1. $L - R = 2$,把某个左变为右,就能满足平衡条件 $1$
      1. 若某个前缀中 $L - R < 2$,把一个左变为右会使 $L - R < 0$ 不满足平衡条件 $2$
      2. 反之,若前缀中 $L - R = 2$,把一个左变为右有 $L - R = 0$ 满足平衡条件 $2$
    2. $R - L = 2$,把某个右变为左,就能满足平衡条件 $1$。要满足平衡条件 $2$,就要调整 $R > L$ 的最左前缀,反转该前缀任意右括号均可
#include <iostream>

using namespace std;

const int N = 1e5 + 10;
char s[N];
int L[N], R[N];

int main() {
    scanf("%s", s + 1);

    int n = 0;
    for (int i = 1; s[i]; n = i ++) {
        L[i] += L[i - 1] + (s[i] == '(');
        R[i] += R[i - 1] + (s[i] == ')');
    }

    if (n & 1 || abs(L[n] - R[n]) != 2) {
        puts("0");
        return 0;
    }        

    int ans = 0;
    if (L[n] > R[n])
        for (int i = 1; s[i]; i ++) {
            if (s[i] == '(') ans ++;
            if (L[i] - R[i] < 2) ans = 0;
        }
    else
        for (int i = 1; s[i]; i ++)
            if (s[i] == ')') {
                ans ++;
                if (R[i] > L[i]) break;
            }

    printf("%d\n", ans);

    return 0;
}


新鲜事 原文

xy____
3小时前
AcWing《语法基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/21/group_buy/68349/谢谢各位


新鲜事 原文

AcWing《语法基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/21/group_buy/68338/



XingHe
3小时前

题目描述

有 N 个物品和一个容量是 V 的背包。

物品之间具有依赖关系,且依赖关系组成一棵树的形状。如果选择一个物品,则必须选择它的父节点。

如下图所示:
QQ图片20181018170337.png

如果选择物品5,则必须选择物品1和2。这是因为2是5的父节点,1是2的父节点。

每件物品的编号是 i,体积是 vi,价值是 wi,依赖的父节点编号是 pi。物品的下标范围是 1…N。

求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。

输出最大价值。

输入格式
第一行有两个整数 N,V,用空格隔开,分别表示物品个数和背包容量。

接下来有 N 行数据,每行数据表示一个物品。
第 i 行有三个整数 vi,wi,pi,用空格隔开,分别表示物品的体积、价值和依赖的物品编号。
如果 pi=−1,表示根节点。 数据保证所有物品构成一棵树。

输出格式
输出一个整数,表示最大价值。

数据范围
1≤N,V≤100
1≤vi,wi≤100
父节点编号范围:

内部结点:1≤pi≤N;
根节点 pi=−1;

样例

输入样例
5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2
输出样例:
11

算法1

(树形dp+分组背包) $O()$

时间复杂度

参考文献

python3 代码

import collections

def main():
    def dfs(x: int) -> None:
        v = vv[x]
        w = ww[x]
        for y in adjvex[x]:
            dfs(y)
            for j in range(V - v, -1, -1):
                for k in range(j + 1):
                    dp[x][j] = max(dp[x][j], dp[x][j - k] + dp[y][k])

        for j in range(V, v - 1, -1):
            dp[x][j] = dp[x][j - v] + w
        for j in range(v - 1, -1, -1):
            dp[x][j] = 0


    N, V = map(int, input().split())
    vv = []
    ww = []
    pp = []
    adjvex = collections.defaultdict(list)
    root = -1
    for i in range(N):
        v, w, p = map(int, input().split())
        vv.append(v)
        ww.append(w)
        pp.append(p)
        if p == -1:
            root = i
        else:
            pp[i] -= 1
            adjvex[pp[i]].append(i)

    dp = [[0 for _ in range(V + 1)] for _ in range(N)]
    dfs(root)
    res = dp[root][V]
    print(res)

if __name__ == "__main__":
    main()

C++ 代码

#pragma GCC optimize(2)

#include <iostream>
#include <string.h>
#include <algorithm>
#include <unordered_map>

using namespace std;

int N;
int V;
int * vv;
int * ww;
int * pp;

int root;
unordered_map<int, vector<int>> adjvex;
int ** dp;

void dfs(int x)
{
    int v = vv[x];
    int w = ww[x];
    for (int y: adjvex[x])
    {
        dfs(y);
        for (int j = V - v; j > -1; j --)
        {
            for (int k = 0; k < j + 1; k ++)
            {
                dp[x][j] = max(dp[x][j], dp[x][j - k] + dp[y][k]);
            }
        }
    }

    for (int j = V; j > v - 1; j --)
    {
        dp[x][j] = dp[x][j - v] + w;
    }
    for (int j = v - 1; j > -1; j --)
    {
        dp[x][j] = 0;
    }
}


int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> V;
    vv = new int [N];
    ww = new int [N];
    pp = new int [N];
    for (int i = 0; i < N; i ++)
    {
        cin >> vv[i] >> ww[i] >> pp[i];
        if (pp[i] == -1)
        {
            root = i;
        }
        else
        {
            pp[i] --;
            adjvex[pp[i]].push_back(i);
        }
    }

    dp = new int * [N];
    for (int i = 0; i < N; i ++)
    {
        dp[i] = new int [V + 1];
    }

    dfs(root);
    int res = dp[root][V];

    cout << res << endl;

    return 0;
}

java 代码

import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

public class Main
{
    static int N;
    static int V;
    static int [] vv;
    static int [] ww;
    static int [] pp;
    static int root;
    static Map<Integer, List<Integer>> adjvex = new HashMap<>();

    static int [][] dp;

    static void dfs(int x)
    {
        int v = vv[x];
        int w = ww[x];

        for (int y: adjvex.getOrDefault(x, new ArrayList<>()))
        {
            dfs(y);
            //----01背包
            for (int j = V - v; j > -1; j --)
            {
                //----组内选哪个
                for (int k = 0; k < j + 1; k ++)
                {
                    dp[x][j] = Math.max(dp[x][j], dp[x][j - k] + dp[y][k]);
                }
            }
        }

        //----必须选x
        for (int j = V; j > v - 1; j --)
        {
            dp[x][j] = dp[x][j - v] + w;
        }
        //----选不到x
        for (int j = v - 1; j > -1; j --)
        {
            dp[x][j] = 0;
        }

    }

    public static void main(String [] args) throws Exception
    {
        Scanner scan = new Scanner(System.in);

        N = scan.nextInt();
        V = scan.nextInt();

        vv = new int [N];
        ww = new int [N];
        pp = new int [N];
        for (int i = 0; i < N; i ++)
        {
            vv[i] = scan.nextInt();
            ww[i] = scan.nextInt();
            pp[i] = scan.nextInt();
            if (pp[i] == -1)
            {
                root = i;
            }
            else
            {
                pp[i] --;       //归一化成从0开始
                adjvex.putIfAbsent(pp[i], new ArrayList<>());
                adjvex.get(pp[i]).add(i);
            }
        }

        dp = new int [N][V + 1];
        dfs(root);

        int res = dp[root][V];
        System.out.println(res);
    }
}


算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



hpstory
4小时前

C# 二维 代码

namespace _3_完全背包问题
{
    class Program
    {
        static void Main()
        {
            int n = Convert.ToInt32(Console.ReadLine());
            int m = Convert.ToInt32(Console.ReadLine());
            const int N = 1010;
            int[] v = new int[N];
            int[] w = new int[N];
            int[,] dp = new int[N, N];

            for (int i = 1; i <= n; i++)
            {
                v[i] = Convert.ToInt32(Console.ReadLine());
                w[i] = Convert.ToInt32(Console.ReadLine());
            }

            for (int i = 1; i <= n; i++)
            {
                for (int j = 0; j <= m; j++)
                {
                    dp[i, j] = dp[i - 1, j];
                    if (j >= v[i])
                    {
                        dp[i, j] = Math.Max(dp[i, j], dp[i, j - v[i]] + w[i]);
                    }
                }
            }

            Console.WriteLine(dp[n, m]);
        }
    }
}

C# 一维 代码

namespace _3_完全背包问题
{
    class Program
    {
        static void Main()
        {
            int n = Convert.ToInt32(Console.ReadLine());
            int m = Convert.ToInt32(Console.ReadLine());
            const int N = 1010;
            int[] v = new int[N];
            int[] w = new int[N];
            int[] dp = new int[N];

            for (int i = 1; i <= n; i++)
            {
                v[i] = Convert.ToInt32(Console.ReadLine());
                w[i] = Convert.ToInt32(Console.ReadLine());
            }

            for (int i = 1; i <= n; i++)
            {
                for (int j = v[i]; j <= m; j++)
                {
                    dp[j] = Math.Max(dp[j], dp[j - v[i]] + w[i]);
                }
            }

            Console.WriteLine(dp[m]);
        }
    }
}




Mr.Tan
4小时前

双指针算法是利用两个指针(i,j),根据i,j的单调关系把朴素算法的O(n^2)简化成O(n),可以认为是对暴力算法的剪枝,比如归并排序的双指针就是利用了两个区间的元素是有序的,如果a[i]大于b[j],那么b[j]之前的一定小于a[i],所有j直接++就好了,不用从j=0重新开始循环(可以看成剪枝)

#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],s[N];
int main()
{
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1,j=1;i<=n;i++)
    {
        s[a[i]]++;
        while(s[a[i]]>1)  //大多数双指针算法都可以写成外面for的i指针循环,内部是循环条件关于j的以及可以反映
                         //单调性的while循环。
        {
            s[a[j]]--;
            j++;
        }
        ans=max(ans,i-j+1);
    }
    cout<<ans;
    return 0;
}