AtCoder Regular Contest 061

C - Many Formulas

给定一个数字串，可以在任意位置添加加号，问所有表达式结果的和是多少。

考虑一个前缀后面补一个新的数字： + 如果断开，那么前缀的贡献是前面的结果 + 如果不断开，那么前缀的贡献是前面除去最后一段 + 最后一段 \(\times 10\) + 最后一个数字的贡献就是数值 \(\times 2^{len}\) ，即可能的划分方案数

记 \(f_i\) 表示前缀 \(i\) 的答案，\(g_i\) 表示前缀 \(i\) 最后一段的答案，有：

\[ \begin{array}{l} f_i &= 2^i * digit_i + f_{i-1} + (f_{i-1} - g_{i-1}) + g_{i-1} \times 10\\ g_i &= 2^i * digit_i + g_{i-1} \times 10 \end{array} \]

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
#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
  
inline int rd() {  
    int x = 0;  
    bool f = 0;  
    char c = getchar();  
    for (; !isdigit(c); c = getchar()) f |= (c == '-');  
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);  
    return f ? -x : x;  
}  
  
char s[11];  
  
ll f[11], g[11];  
  
int main() {  
    scanf("%s", s + 1);  
    int len = strlen(s + 1);  
    for (int i = 1, pw = 1; i <= len; ++i, pw = pw * 2) {  
        f[i] = pw * (s[i] - '0') + f[i - 1] * 2 + g[i - 1] * 9;  
        g[i] = pw * (s[i] - '0') + g[i - 1] * 10;  
    }  
    printf("%lld\n", f[len]);  
    return 0;  
}

D - Snuke's Coloring

给定一个 \(H\times W\) 的网格，初始所有位置都是白色，然后给定 \(n\) 个点染成黑色。 问所有的九宫格里，黑色点数为 \(0\dots 9\) 的九宫格分别有多少个。

初始所有的九宫格都是白色，然后每次加入一个点模拟一下即可。

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
#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
  
inline int rd() {  
    int x = 0;  
    bool f = 0;  
    char c = getchar();  
    for (; !isdigit(c); c = getchar()) f |= (c == '-');  
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);  
    return f ? -x : x;  
}  
  
unordered_map<ll, bool> vis;  
  
inline ll pos(int x, int y) {return 1ll * x * 1000000000 + y;}  
  
ll ans[10];  
  
int main() {  
    int h = rd(), w = rd();  
    ans[0] = 1ll * (h - 2) * (w - 2);  
    for (int n = rd(); n; --n) {  
        int x = rd(), y = rd();  
        for (int a = max(1, x - 2); a <= min(x, h - 2); ++a)  
            for (int b = max(1, y - 2); b <= min(y, w - 2); ++b) {  
                int cnt = 0;  
                for (int dx = 0; dx < 3; ++dx)  
                    for (int dy = 0; dy < 3; ++dy) cnt += vis[pos(a + dx, b + dy)];  
                --ans[cnt]; ++ans[cnt + 1];  
            }  
        vis[pos(x, y)] = 1;  
    }  
    for (int i = 0; i < 10; ++i) printf("%lld\n", ans[i]);  
    return 0;  
}

E - Snuke's Subway Trip

\(n\) 个点 \(m\) 条边的无向图，每个边有一个颜色。 一个路径的初始代价是 \(1\) ，每换一次颜色代价 \(+1\) ，求 \(1\) 到 \(n\) 的最短路。

考虑直接建分层图（每个点的实点建立 \(m\) 个虚点，虚点间连原图的边）。

真实的点向对应的虚点连边权为 \(1\) ，虚点之间连原图的边边权为 \(0\) ，最终答案除 \(2\) 即可。

可以发现有用的点其实只有 \(\mathcal{O}(n+m)\) ，因此可以直接建图做（用一个 unordered_map ）。

然后在图上跑 01-BFS 即可，复杂度 \(\mathcal{O}(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
#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
  
inline int rd() {  
    int x = 0;  
    bool f = 0;  
    char c = getchar();  
    for (; !isdigit(c); c = getchar()) f |= (c == '-');  
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);  
    return f ? -x : x;  
}  
  
#define N 500007  
#define M 2000007  
  
unordered_map<int, int> id[N];  
  
int tot, hd[N];  
  
struct node{int to, nxt; bool w;} e[M];  
  
inline void add(int u, int v, bool w) {  
    e[++tot].to = v; e[tot].w = w; e[tot].nxt = hd[u]; hd[u] = tot;  
    e[++tot].to = u; e[tot].w = w; e[tot].nxt = hd[v]; hd[v] = tot;  
}  
  
int dis[N];  
  
bool vis[N];  
  
deque<int> q;  
  
int main() {  
    int n = rd(), m = rd();  
    int totn = n;  
    for (int i = 1; i <= m; ++i) {  
        int u = rd(), v = rd(), c = rd();  
        if (!id[u][c]) {id[u][c] = ++totn; add(u, totn, 1);}  
        if (!id[v][c]) {id[v][c] = ++totn; add(v, totn, 1);}  
        add(id[u][c], id[v][c], 0);  
    }  
    memset(dis, 0x3f, sizeof(dis));  
    dis[1] = 0; q.push_back(1);  
    while (!q.empty()) {  
        int u = q.front(); q.pop_front();  
        if (vis[u]) continue; vis[u] = 1;  
        for (int i = hd[u], v; i; i = e[i].nxt) {  
            if (dis[u] + e[i].w < dis[v = e[i].to]) {  
                dis[v] = dis[u] + e[i].w;  
                e[i].w ? q.push_back(v) : q.push_front(v);  
            }  
        }  
    }  
    printf("%d\n", dis[n] == dis[0] ? -1 : dis[n] / 2);  
    return 0;  
}

F - Card Game for Three

三个人 A,B,C ，每个人分别有 \(n,m,k\) 张卡，每张卡的卡面都可能是 A/B/C 之一。 从 A 开始翻牌，每次翻到的牌子上写的是谁，下一个翻牌的就是谁。 轮到某个人时，如果他没有牌了就胜利，问总共 \(3^{n+m+k}\) 种方案中，A 胜利的方案数有多少。

这道题目的出发点完全想错了，不能将三个人分开想，因为有可能会有 A - B - C - A 循环。

考虑将整个操作序列连起来（长度 \(n+m+k\) ），每个操作序列一定对应于一种牌序。

那么也就是要求：某个前缀有 \(n\) 个 A ，且这段前缀内 B, C 的数量对应不超过 \(m,k\) 。

  • 前一个条件避免数重，强制最后一个是 A 即可。
  • 后一个条件考虑容斥做，由于长度限制容易发现两个反例只会出现一个：

\[ \begin{array}{l} ans &= \displaystyle \sum_{len=n}^{n+m+k} {len - 1\choose n - 1}\bigg({2^{len - n} - \sum_{a = m+1}^{len - n}{len - n\choose a}-\sum_{b=k+1}^{len - n}{len - n\choose b}}\bigg)3^{n+m+k-len} \end{array} \] 设 \(f_x=\sum_{i=m}^x{x\choose i}\) ，然后用组合数定义优化这个东西：

\[ f_x = \sum_{i=m}^x{x\choose i} = \sum_{i=m}^x \bigg({x-1\choose i}+{x-1\choose i - 1}\bigg) = 2f_{x-1} + {x - 1\choose m - 1} \] 就变成 \(\mathcal{O}(n+m+k)\) 的了。。。

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
#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
  
inline int rd() {  
    int x = 0;  
    bool f = 0;  
    char c = getchar();  
    for (; !isdigit(c); c = getchar()) f |= (c == '-');  
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);  
    return f ? -x : x;  
}  
  
#define N 1000007  
#define mod 1000000007  
  
namespace Comb {  
    int fac[N], ifac[N];  
  
    inline int fpow(int x, int t) {  
        int res = 1;  
        for (; t; t >>= 1, x = 1ll * x * x % mod)  
            if (t & 1) res = 1ll * res * x % mod;  
        return res;  
    }  
  
    inline void init() {  
        fac[0] = ifac[0] = 1;  
        for (int i = 1; i < N; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;  
        ifac[N - 1] = fpow(fac[N - 1], mod - 2);  
        for (int i = N - 2; i; --i) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;  
    }  
  
    inline ll C(int n, int m) {  
        if (n < m) return 0;  
        return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;  
    }  
}  
using namespace Comb;  
  
ll pw2[N] = {1}, pw3[N] = {1}, f1[N], f2[N];  
  
int main() {  
    init();  
    ll ans = 0;  
    int n = rd(), m = rd(), k = rd();  
    for (int i = 1; i < N; ++i) {  
        pw2[i] = (pw2[i - 1] << 1) % mod;  
        pw3[i] = pw3[i - 1] * 3 % mod;  
        f1[i] = (2 * f1[i - 1] + C(i - 1, m)) % mod;  
        f2[i] = (2 * f2[i - 1] + C(i - 1, k)) % mod;  
    }  
    for (int l = n; l <= n + m + k; ++l) {  
        ll w = ((pw2[l - n] - f1[l - n] - f2[l - n]) % mod + mod) % mod;  
        ans = (ans + C(l - 1, n - 1) * w % mod * pw3[n + m + k - l]) % mod;  
    }  
    printf("%lld\n", ans);  
    return 0;  
}