hz暑假集训 8/12

数字三角形

CF1517C
签到题。

题意:
小 \(D\) 给你一个长度为 \(n\) 的排列 \(p\) ，你需要根据 \(p\) 构造出一个三角形。
该图案需要满足共 \(n\) 行，第 \(i\) 行有 \(i\) 个数，第 \(i\) 行最后一个数是 \(p_i\)。
数值 \(p_i\) 有 \(p_i\) 个且四联通。
几个位置是四联通的，是指从其中某个位置出发，只往上下左右走，只经过这些位置，可以到达其中任意一个位置。

思路：
每个数向左扩展，然后向下扩展。

5 
5 1 4 2 3

5
5 1
5 4 4
5 4 3 3
5 4 3 2 2

代码：

#include <bits/stdc++.h>

using namespace std;

const int maxN = 507;

int n, p[maxN];
int a[maxN][maxN];

void dfs(int x, int y, int num, int stp) {
    if (!stp) return;
    a[x][y] = num;
    if (!a[x][y - 1])
        dfs(x, y - 1, num, stp - 1);
    else
        dfs(x + 1, y, num, stp - 1);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> p[i];
    for (int i = 1; i <= n; i++)
        a[i][0] = -1;
    for (int i = 1; i <= n; i++)
        dfs(i, i, p[i], p[i]);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++)
            cout << a[i][j] << ' ';
        cout << '\n';
    }
}

那一天她离我而去

题意：无向图找出从 1 到 1 的最小环长度。无重边 无自环

思路：
首先考虑暴力，从 1 出发经历一条边到的每个点放到一个数组，\(n^2\) 枚举起点终点跑最短路，再加上 1 到这两个点的距离。

正解非常巧妙，二进制拆分，分别考虑每一位，是 0 的看成起点，是 1 的看成终点，在建超级源点（niubi源点）连每一个起点，边权为 $1 \to x $ 的边权；每一个终点连超级汇点，边权为 \(x \to 1\) 的边权。跑最短路即可。
因为俩个不同的点二进制下一定最少一位不同，所以每个点都会分别被分到起点，终点，所以不漏。

代码：

#include <bits/stdc++.h>

using namespace std;

const int maxN = 1e4 + 7, maxM = 6e4;

struct node {
    int x, hx;
};
vector<node> D;

int head[maxN], tot;
struct edge {
    int ls, to, w;
} e[maxM << 1];
void add(int x, int y, int z, bool record) {
    if (record)
        D.push_back({x, head[x]});
    e[++tot] = {head[x], y, z};
    head[x] = tot;
}

void cancel() {
    while (!D.empty()) {
        auto tp = D.back();
        D.pop_back();
        tot--;
        head[tp.x] = tp.hx;
    }
}

int ans;
int n, m;

int dis[maxN];
bool vis[maxN];
priority_queue<pair<int, int>> q;
void dij(int S) {
    for (int i = 0; i <= n + 1; i++)
        dis[i] = 1e9, vis[i] = false;
    dis[S] = 0;
    q.push({0, S});
    while (!q.empty()) {
        int f = q.top().second;
        q.pop();
        if (vis[f]) continue;
        vis[f] = true;
        for (int i = head[f]; i; i = e[i].ls) {
            int to = e[i].to;
            if (dis[to] > dis[f] + e[i].w) {
                dis[to] = dis[f] + e[i].w;
                q.push({-dis[to], to});
            }
        }
    }
}

vector<pair<int, int>> A;

void solve() {
    cin >> n >> m;
    
    A.clear();
    ans = 1e9;
    tot = 0;
    for (int i = 0; i <= n + 1; i++)
        head[i] = 0;

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (u > v) swap(u, v);
        if (u == 1)
            A.push_back({v, w});
        else {
            add(u, v, w, false);
            add(v, u, w, false);
        }
    }
    
    for (int i = 13; i >= 0; i--) {
        for (auto t : A) {
            int fi = t.first, se = t.second;
	        if ((fi >> i) & 1)
                add(0, fi, se, true);
            else 
                add(fi, n + 1, se, true);
        }
        dij(0);
        ans = min(ans, dis[n + 1]);

        cancel();
    }

    if (ans >= 1e9)
        cout << "-1\n";
    else
        cout << ans << '\n';
}

int main() {
    // freopen("leave.in", "r", stdin);
    // freopen("b.txt", "w", stdout);
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--)
        solve();
}

话说好像好多届都考过这个题了, 网上有学哥的博客。

哪一天她能重回我身边

题意：有 \(n\) 张牌，牌正面是 \(a\)，反面是 \(b\)，初始都是正面。求最小的翻转的次数，使牌上面的数互不相同，以及最少翻转达成目标的方案数。

图论题。。。
很巧妙的建图方法，从每张牌的正面向反面连边。发现方案合法为每个点出度小于等于 1 时。
翻转相当于把有向边翻转。
然后发现对于一个联通块合法其实就是树或基环树。

对于树，就可以考虑换根dp，设 \(g[x]\) 表示以 \(x\) 为根的最小翻转数，那么如果有一条边是 \(x\to to\)，\(g[to] = g[x] - 1\)，如果是 \(to\to x\)，就是 \(g[to] = g[x] + 1\)。
每个联通块内的最小 \(g[x]\) 之和就是最总答案，第二问顺便处理一下就好了。

对于基环树，断掉环上的一条边跑树的情况。最后分讨一下边的方向就可以了。

思路比较难想，代码我选择贺（。

// 抄的学哥的
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int maxN = 2e5 + 7, mod = 998244353;

int n;

struct edge {
    int ls, to, w, st;
} e[maxN << 1];
int head[maxN], tot;
void add(int u, int v, int w) {
    e[++tot] = {head[u], v, w, u};
    head[u] = tot;
}

int np, ne;
bool v[maxN], vi[maxN];
void dfs(int x, int f) {
    vi[x] = true;
    np++;
    for (int i = head[x]; i; i = e[i].ls) {
        ne++;
        if (e[i].to == f || vi[e[i].to]) continue;
        dfs(e[i].to, x);
    }
}
bool pd() {
    for (int i = 1; i <= n * 2; i++)
        if (!vi[i]) {
            np = ne = 0;
            dfs(i, 0);
            if (np < ne / 2)
                return true;
        }
    return false;
}
int f[maxN], S, T, ned;
void dfs1(int x, int fa) {
    v[x] = true;
    f[x] = 0;
    for (int i = head[x]; i; i = e[i].ls)
        if (e[i].to != fa) {
            if (!v[e[i].to]) {
                dfs1(e[i].to, x);
                f[x] += f[e[i].to] + e[i].w;
            }
            else
                S = e[i].st, T = e[i].to, ned = i;
        }
}
int g[maxN];
vector<int> tem;
void dfs2(int x, int fa) {
    tem.push_back(g[x]);
    for (int i = head[x]; i; i = e[i].ls)
        if (e[i].to != fa && i != ned && i != (ned ^ 1)) {
            if (e[i].w) g[e[i].to] = g[x] - 1;
            else g[e[i].to] = g[x] + 1;
            dfs2(e[i].to, x);
        }
}

void solve() {
    tot = 1;
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    memset(v, 0, sizeof(v));
    memset(vi, 0, sizeof(vi));
    memset(head, 0, sizeof(head));
    tem.clear();

    cin >> n;
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b, 1), add(b, a, 0);
    }
    if (pd())
        return cout << "-1 -1\n", void();
    
    int ans = 0;
    int minn = 0, ans2 = 1;
    for (int i = 1; i <= n * 2; i++)
        if (!v[i]) {
            S = T = ned = -1;
            tem.clear();
            minn = 0;
            dfs1(i, 0);
            g[i] = f[i];
            dfs2(i, 0);
            if (S == -1) {
                sort(tem.begin(), tem.end());
                for (unsigned j = 0; j < tem.size(); j++)
                    if (tem[j] == tem[0])
                        minn++;
                    else break;
                ans += tem[0];
            }
            else {
                ned %= 2;
                if (g[S] + ned == g[T] + (ned ^ 1))
                    minn = 2;
                else
                    minn = 1;
                ans += min(g[S] + ned, g[T] + (ned ^ 1));
            }
            ans2 = ans2 * minn % mod;
        }
    cout << ans << ' ' << ans2 << '\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int Tim;
    cin >> Tim;
    while (Tim--)
        solve();
}

T4 不会