20231002题解

发表于 分类于 ， 阅读次数：

T1 toy

挺简单的 DP。看到数据范围就想到 \(\mathcal O(nm)\)。定义 \(f_i\) 表示前 \(i\) 个玩具的最小代价。枚举 \(j\) 表示第 \(i\) 个玩具所在的区间是 \([j, i]\)，则 \(f_i = \min_j (f_{j - 1} + (i - j + 1)\cdot k + b - a)\)

1
2
3
4
5
6
7
8
9
10
for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    dp[i] = k + dp[i - 1];
    int mini = a[i], maxi = a[i];
    for (int j = i - 1; j >= max(1, i - m + 1); j--) {
        mini = min(mini, a[j]);
        maxi = max(maxi, a[j]);
        dp[i] = min(dp[i], dp[j - 1] + k + 1LL * (maxi - mini) * (i - j + 1));
    }
}

T2 program

大模拟。

首先考虑 CE： 1. 调用了没有声明的函数 2. 声明了已经声明过的函数

然后考虑 RE： 1. 递归调用自己 2. 调用了会 RE 的函数

最后看一下答案：既然没有递归，所有的调用关系呈现有向无环图，而最小的函数作用是 ++，所以就是在 DAG 上跑 DP，统计总 ++ 个数。

另外，输入的顺序正好就是逆拓扑序，所以直接统计就好。

注意多测清空，另外强烈谴责把一个制表符打成 4 个空格的出题人，导致一行的代码长度超过了他自己说的 30 个字符，害得我虚空调试了 1h。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
fgets(buf, 64, stdin);
sscanf(buf, "%d", &n);

fgets(buf, 64, stdin);
fgets(buf, 64, stdin);
fgets(buf, 64, stdin);
//无用的三行

memset(ans, 0, sizeof ans);
memset(re, 0, sizeof re);
int cnt = 0; map<string, int> mp;
mp["A"] = 0; ans[0] = 1ull;
bool ce = false;

for (int i = 4; i <= n; i++) {
    fgets(buf, 64, stdin);
    if (ce) continue;
    char fst[64]; sscanf(buf, "%s", fst);

    if (fst[0] == '}' || fst[0] == 'p' || fst[0] == '_') continue;
    if (fst[0] == 'v' || fst[0] == 'i') {
        sscanf(buf, "%*s%s", name[++cnt]);
        name[cnt][strlen(name[cnt]) - 3] = 0;
        if (mp.count(string(name[cnt]))) {
            ce = true;
            continue;
        }
        mp[string(name[cnt])] = cnt;
        continue;
    }
    
    fst[strlen(fst) - 3] = 0;
    if (!(mp.count(string(fst)))) ce = true;
    else if (string(fst) == string(name[cnt])) re[cnt] = true;
    else {
        if (re[mp[string(fst)]]) re[cnt] = true;
        else ans[cnt] += ans[mp[string(fst)]];
    }
}

if (ce) printf("Compile error\n");
else if (re[cnt]) printf("Segmentation fault\n");
else printf("%llu\n", ans[cnt]);

T3 sukeban

\(c_i \leq n\) 就像思想钢印一样打在我脑子里，但实际是 \(c_i \leq k\)，又导致虚空调试 1.5h。

首先考虑一个队伍的概率问题。建出所有可能在最短路上的边组成的最短路图，这一定是一个 DAG。

起点的概率是 1，既然他说是均匀选择，直接像水流一样平均分配就好了，是一个简单的 DAG 上模拟（我都不好意思说是 DP）。

平均流算法（雾）

然后考虑同一个势力的两支队伍。如果两只队伍分别以 \(p_1\) 和 \(p_2\) 的概率到达某个点 \(u\)，则 \(u\) 上存在这一势力的概率为 \(1 - (1 - p_1)(1 - p_2)\)。其实就是正难则反，比较简单的容斥。多个队伍可以两个两个做。

最后考虑所有势力合在一起：如果第 \(i\) 个势力以 \(p_i\) 的概率在 \(u\) 点出现，则这个点动乱的概率就是 1 - 没有势力出现的概率 - 只有一个势力出现的概率。记 \(\Pi = \prod_{i}(1-p_i)\) ，则要求的结果就是：

\[ 1 - \Pi - \sum{\frac{p_i\Pi}{1-p_i}} \]

但是注意细节：如果 \(p_i = 1\)，做分母就没有意义，所以将 \(p_i=1\) 的单独考虑，如果超过两个势力必然出现则答案为 1，如果有一个势力必然出现就是不考虑 \(p_i=1\) 的 \(\Pi\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
memset(dis, 0x3f, sizeof dis);
for (int s = 1; s <= n; s++) {
    // bfs 求 s 开始的最短路 dis[s][i]
}

for (int i = 1; i <= k; i++) {
    int s, t, c; scanf("%d %d %d", &c, &s, &t);
    memset(tp, 0, sizeof tp);
    memset(book, 0, sizeof book);
    tp[s] = 1;
    queue<int> q;
    q.emplace(s);
    book[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        int cnt = 0;
        for (int v : graph[u]) {
            if (dis[u][t] - 1 == dis[v][t]) {
                cnt++;
                if (!book[v]) {
                    q.emplace(v);
                    book[v] = true;
                }
            }
        }
        long long inv_cnt = quick_pow(cnt, mod - 2);
        for (int v : graph[u]) {
            if (dis[u][t] - 1 == dis[v][t]) {
                (tp[v] += inv_cnt * tp[u] % mod) %= mod;
            }
        }
    }
    for (int u = 1; u <= n; u++) {
        long long np = (1 - p[c][u] + mod) % mod;
        long long ntp = (1 - tp[u] + mod) % mod;
        p[c][u] = (1 - np * ntp % mod + mod) % mod;
    }
    // puts("");
}
for (int i = 1; i <= n; i++) {
    long long zero = 1, zz = 1, as = 1;
    int cnt = 0;
    for (int j = 1; j <= n; j++) {
        (zz *= (1 - p[j][]))
        if (p[j][i] == 1) cnt++;
        else (zero *= (1 - p[j][i] + mod) % mod) %= mod;
    }
    if (cnt > 1) printf("1\n");
    else if (cnt == 1) printf("%lld\n", (1 - zero + mod) % mod);
    else {
        for (int j = 1; j <= n; j++) {
            (one += (zero * quick_pow((1 - p[j][i] + mod) % mod, mod - 2) % mod * p[j][i] % mod)) %= mod;
        }
        printf("%lld\n", (1 - (zero + one) % mod + mod) % mod);
    }
}

T4 mito

建图好题。

传递的过程肯定是这样的：

1 到 \(a_1\) 频段，\(i\) 到 \(a_1\) 频段，传递信息；\(i\) 到 \(a_2\) 频段，\(j\) 到 \(a_2\) 频段，传递信息……

任意一个人最多只可能出现连续的 2 次，即：拿到信息+传出信息。出手了就没有理由再入手（最短路肯定无环）。

所以一个人的作用就是把信息从一个频段转移到另一频段。考虑从频段 \(a_i\) 转移到 \(a_j\)，而初始频段是 \(a_s\)，频率是 \(f\)，那么实际代价就是 \(\frac{|a_s - a_i| + |a_i - a_j|}{f}\)。

我们可以直接这样 \(O(n^2)\) 建图，但是让我们再想一想：

如果两个不同的人有相同的频率，并且其频段关于 \(f\) 同余，则它们对应的 \(|a_i - a_j|\) 就都是一样的。记 \(r = a_s \mod f\)我们可以对于每一个二元组 \((r, f)\) 建立一组辅助点，分别对应原点中的 \(r, r+f, r+2f...\)，那么相邻辅助点之间连一条边权 1 的无向边，这样就表示了 \(\frac{|a_i - a_j|}{f}\)。但是从原点 \(a_i\) 到原点 \(a_j\) 还有一段 \(\frac{|a_s - a_i|}{f}\)，考虑将 \(a_i\) 到它辅助点的边权设为 \(\frac{|a_s - a_i|}{f}\)，而 \(a_j\) 的辅助点到 \(a_j\) 的距离设为 0，则经过辅助点就得到了 \(a_i\) 到 \(a_j\) 的最短路。

由于可能有多个人拥有相同的 \((r, f)\)，我们在连 \(a_i\) 到其辅助点的边的时候，选择使得边权最小的 \(a_s\) 即可。

这样子会连出多少条边呢？\(f = 1\) 时一组辅助点就能有 \(N\) 个，但是 \(f = 2\) 时就需要两组点，\(f = 3\) 时需要三组……考虑最坏情况，如果所有 \(m\) 组点都使得辅助点尽可能多，设总共得到 \(kN\) 个辅助点，则 \(\sum_{i=1}^{k}{i} \leq m\)，所以我们有 \(k = \mathcal{O}(\sqrt{m})\)。

这样子点数是 \(\mathcal{O}(N\sqrt m)\)，边数也是，跑 Dijkstra 复杂度就是 \(\mathcal{O}(N\sqrt m(\log N + \log m))\)。

代码中 \(N\) 和 \(m\) 互换了位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e6 + 5;

struct node {
    int v, w;
    node() {}
    node(int _v, int _w) {
        v = _v, w = _w;
    }
    bool operator > (const node &x) const {
        return w > x.w;
    }
};

int n, m, sa, ta, tf;
vector<node> graph[maxn];
map<pair<int, int>, vector<int> > in_f;
priority_queue<node, vector<node>, greater<node> > pq;
int dis[maxn];

int main() {
    freopen("mito.in", "r", stdin);
    freopen("mito.out", "w", stdout);
    scanf("%d %d", &m, &n);
    int cnt = m;
    for (int i = 1; i <= n; i++) {
        int a, f;
        scanf("%d %d", &a, &f);
        if (i == 2) {
            ta = a, tf = f;
            continue;
        }
        in_f[make_pair(a % f, f)].emplace_back(a);
        if (i == 1) sa = a;
    }
    for (auto &x : in_f) {
        const auto &a = x.first.first, &f = x.first.second;
        auto &s = x.second;
        sort(s.begin(), s.end());
        auto p = s.begin();
        for (int j = a; j < m; j += f) {
            graph[cnt].emplace_back(j, 0);
            while (p + 1 != s.end() && abs(*(p + 1) - j) < abs(*p - j)) p++;
            graph[j].emplace_back(cnt, abs(*p - j) / f);

            if (j + f < m) {
                graph[cnt].emplace_back(cnt + 1, 1);
                graph[cnt + 1].emplace_back(cnt, 1);
            }
            cnt++;
        }
    }
    pq.emplace(sa, 0);
    memset(dis, 0x3f, sizeof dis);
    while (!pq.empty()) {
        auto now = pq.top();
        pq.pop();
        if (now.w >= dis[now.v]) continue;
        dis[now.v] = now.w;
        for (auto e : graph[now.v]) {
            if (now.w + e.w < dis[e.v]) {
                pq.emplace(e.v, now.w + e.w);
            }
        }
    }
    int ans = 0x3f3f3f3f;
    for (int j = ta % tf; j < m; j += tf) {
        ans = min(ans, dis[j] + abs(ta - j) / tf);
    }
    printf("%d\n", ans);
    return 0;
}