CERC2015 解题报告

记录了有关 CERC2015 的题目。

所有题目可以在 https://codeforces.com/gym/101480 找到。

A. ASCII Addition

将数字压成一个字符串，然后模拟。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 

map<string, int> pm; 
map<int, string> mp; 
string a[1005], s[1005]; 
i64 num[1005]; 

int main(void) {
    ios::sync_with_stdio(0); 
    mp[0] = "xxxxxx...xx...xx...xx...xx...xxxxxx"; 
    mp[1] = "....x....x....x....x....x....x....x";
    mp[2] = "xxxxx....x....xxxxxxx....x....xxxxx";
    mp[3] = "xxxxx....x....xxxxxx....x....xxxxxx";
    mp[4] = "x...xx...xx...xxxxxx....x....x....x";
    mp[5] = "xxxxxx....x....xxxxx....x....xxxxxx";
    mp[6] = "xxxxxx....x....xxxxxx...xx...xxxxxx";
    mp[7] = "xxxxx....x....x....x....x....x....x";
    mp[8] = "xxxxxx...xx...xxxxxxx...xx...xxxxxx";
    mp[9] = "xxxxxx...xx...xxxxxx....x....xxxxxx";
    mp[10] = ".......x....x..xxxxx..x....x......."; 
    for (int i = 0; i <= 10; ++i) pm[mp[i]] = i; 

    for (int i = 1; i <= 7; ++i) cin >> s[i]; 
    int len = s[1].length();
    for (int i = 1; i <= 7; ++i) {
        int p = 1; 
        for (int j = 0; j < len; ++j)
            if ((j + 1) % 6 == 0) { ++p; continue; }  
            else a[p].push_back(s[i][j]);
    }
    len = (len + 1) / 6;
    for (int i = 1, u = 1; i <= len; ++i) {
        if (pm[a[i]] == 10) { ++u; continue; }
        num[u] = num[u] * 10 + pm[a[i]];
    }
    i64 ans = num[1] + num[2]; len = 0; 
    while (ans) num[++len] = ans % 10, ans /= 10; 

    for (int j = 1; j <= 7; ++j, cout << "\n")
        for (int i = len; i >= 1; i--) {
            for (int k = 0; k < 5; k++) cout << mp[num[i]][(j - 1) * 5 + k];
            if (i != 1) cout << "."; 
        }
    return 0;
}

B. Book Borders

考虑直接枚举，每次跳到相应的合法单词，这样是调和级数复杂度。

查看代码

#include <bits/stdc++.h>
using namespace std;

int n; 
char s[500050]; 
int pre[500050], len[500050];

int main(void) {
    fgets(s, 500010, stdin); n = strlen(s) - 1; s[n] = ' '; 
    int flag = 0, lst = 0, cnt = 0; 
    for (int i = 0; i <= n; ++i) {
        if (s[i + 1] == ' ') pre[i] = i;
        else pre[i] = (i == 0 ? 0 : pre[i - 1]);
        if (!flag && s[i] != ' ') flag = 1, lst = i, cnt = 1; 
        else if (flag && s[i] == ' ') flag = 0, len[lst] = cnt; 
        ++cnt; 
    }
    int a, b; scanf("%d%d", &a, &b); 
    for (int i = a; i <= b; ++i) {
        int cur = 0, ans = 0;
        while (cur < n) {
            ans += len[cur]; 
            cur = pre[min(cur + i - 1, n - 1)] + 2; 
        }
        printf("%d\n", ans - 1); 
    }
    return 0;
}

* C. Cow Confinement

比较抽象的一道题，赛时居然没有人过。

一头牛的话显然是 DP（ $f_{i,j}=f_{i+1,j}+f_{i,j+1}-f_{i+1,j+1}$ ），那么考虑用扫描线从右向左扫，线段树维护当前每个点的 DP 值。如果扫到了一个右区间，那么从上线到下一条下线都要被加在上线上的一个格子，并且线内数据清零。扫到左线线内数据清零，并把原来线外的东西加回来，最后再把右下角算重的部分减去就行。

查看代码

#include <bits/stdc++.h>
using namespace std; 
const int N = 1000001; 

int n, m; 
struct Line {
    int x, y1, y2, id, type; 
    bool operator< (const Line &a) const {
        if (x != a.x) return x > a.x; 
        return type < a.type; 
    }
} Q[8000005]; 
struct SGT {
    int T[4000050], tag[4000050]; 
    inline void pushdown(int o) {
        if (!tag[o]) return; 
        tag[o << 1] = tag[o << 1 | 1] = 1; 
        T[o << 1] = T[o << 1 | 1] = 0; 
        tag[o] = 0; 
    }
    void update(int o, int l, int r, int x, int v) {
        if (l == r) return T[o] += v, void(); 
        pushdown(o); int mid = l + r >> 1; 
        if (x <= mid) update(o << 1, l, mid, x, v); 
        else update(o << 1 | 1, mid + 1, r, x, v); 
        T[o] = T[o << 1] + T[o << 1 | 1]; 
    }
    void clear(int o, int l, int r, int x, int y) {
        if (x <= l && r <= y) return tag[o] = 1, T[o] = 0, void(); 
        pushdown(o); int mid = l + r >> 1; 
        if (x <= mid) clear(o << 1, l, mid, x, y); 
        if (mid < y) clear(o << 1 | 1, mid + 1, r, x, y); 
        T[o] = T[o << 1] + T[o << 1 | 1]; 
    }
    int query(int o, int l, int r, int x, int y) {
        if (x <= l && r <= y) return T[o]; 
        pushdown(o); int mid = l + r >> 1, res = 0; 
        if (x <= mid) res += query(o << 1, l, mid, x, y); 
        if (mid < y) res += query(o << 1 | 1, mid + 1, r, x, y); 
        return res; 
    }
} T;
int ans[200005], tmp[200005]; 
multiset<int> s; 

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n; 
    for (int i = 1; i <= n; ++i) {
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; 
        Q[++m] = {x2, y1, y2, i, 1}; 
        Q[++m] = {x1 - 1, y1, y2, i, 2}; 
    }
    cin >> n; 
    for (int i = 1; i <= n; ++i) {
        int x, y; cin >> x >> y; 
        Q[++m] = {x, y, 0, 0, 3}; 
    }
    cin >> n; 
    for (int i = 1; i <= n; ++i) {
        int x, y; cin >> x >> y; 
        Q[++m] = {x, y, 0, i, 4}; 
    } sort(Q + 1, Q + m + 1); 
    s.emplace(N); 
    for (int i = 1; i <= m; ++i) 
        if (Q[i].type == 1) {
            // 进入框子
            int nxt = *s.upper_bound(Q[i].y2); 
            tmp[Q[i].id] = T.query(1, 0, N, Q[i].y2 + 1, nxt); 
            T.update(1, 0, N, Q[i].y1 - 1, T.query(1, 0, N, Q[i].y1, nxt)); 
            T.clear(1, 0, N, Q[i].y1, Q[i].y2); 
            s.emplace(Q[i].y1 - 1); 
            s.emplace(Q[i].y2); 
        } else if (Q[i].type == 2) {
            // 出了框子
            T.update(1, 0, N, Q[i].y1 - 1, -tmp[Q[i].id]); 
            T.clear(1, 0, N, Q[i].y1, Q[i].y2); 
            s.erase(s.find(Q[i].y1 - 1)); 
            s.erase(s.find(Q[i].y2)); 
        } else if (Q[i].type == 3) T.update(1, 0, N, Q[i].y1, 1); 
        else ans[Q[i].id] = T.query(1, 0, N, Q[i].y1, *s.lower_bound(Q[i].y1)); 
    for (int i = 1; i <= n; ++i) cout << ans[i] << "\n"; 
    return 0; 
}

D. Digit Division

考虑所有最短的可以被 $m$ 整除的部分的个数 $c$ ，那么答案是 $2^{c-1}$ 。

查看代码

#include <bits/stdc++.h>
using namespace std; 
const int P = 1000000007; 

int n, m; 
char a[300005]; 

inline int poww(int a, int b) {
    int r = 1; 
    for (; b; b >>= 1, a = 1ll * a * a % P) if (b & 1) r = 1ll * r * a % P; 
    return r; 
}

int main(void) {
    scanf("%d%d%s", &n, &m, a + 1); 
    int res = 0, c = 0; 
    for (int i = 1; i <= n; ++i) {
        res = (res * 10 + a[i] - '0') % m; 
        if (res == 0) ++c; 
    }
    if (res) puts("0"); 
    else printf("%d\n", poww(2, c - 1)); 
    return 0; 
}

E. Export Estimate

Portal.

给定一个带权无向图，每次询问（互相独立）时：

删掉边权 $<t$ 的边；
枚举 $i\in [1,n]$ ，如果是个孤立点直接删去，如果它的度数为 $2$ 则将其连接的 $(u,v)$ 之间连接一条新边（可能会连出重边），然后删掉 $i$ 自己。

回答点的个数和边的个数。

经验和输入格式几乎已经告诉我们在线不可做。考虑将边按照边权从大到小排序，这样只会有加边操作，也就是说点的度数只会增加。

表面上看，只有度数为 $0$ 的点和度数为 $2$ 的点会产生影响。当有点的度数 $0\rightarrow 1$ 时，点的个数会增加。当度数 $1\rightarrow 2$ 时，边、点的个数均会减少 $1$ 。当 $2\rightarrow 3$ 时，则复原。

理想很美好，现实很骨感。由于操作是按照顺序进行的，因此在操作过程中点的度数也会发生改变。但手搓几个情况后发现这事其实没有什么关系，只有在这个连通块自己是个环的时候会被删成一个点加一个自环。

我们发现并查集，然后再维护一下每个连通块上不同度数的点的个数可以很好地完成这个问题。

查看代码

#include <bits/stdc++.h>
using namespace std; 

int n, m, q; 
struct Edge {
    int u, v, w; 
    bool operator< (const Edge &a) const {
        if (w != a.w) return w > a.w; 
        return u > a.u; 
    }
} a[600005]; 
int tot, an1[300005], an2[300005]; 
int V, E; 

int fa[300005], sz[300005], sz2[300005], c[300005]; 
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
int deg[300005]; 

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> m; 
    for (int i = 1; i <= m; ++i) cin >> a[i].u >> a[i].v >> a[i].w; 
    cin >> q; tot = m; 
    for (int i = 1; i <= q; ++i) {
        int w; cin >> w; ++tot; 
        a[tot].v = i, a[tot].w = w; 
    }
    sort(a + 1, a + tot + 1); 
    for (int i = 1; i <= n; ++i) fa[i] = i, sz[i] = 1; 
    int d0 = n, d2 = 0, cyc = 0, ec = 0; 
    for (int i = 1; i <= tot; ++i) {
        if (a[i].u == 0) { 
            an1[a[i].v] = V, an2[a[i].v] = E; 
            continue; 
        }
        int u = a[i].u, v = a[i].v; 
        // cout << "T " << u << " " << v << "\n"; 
        int uu = find(u), vv = find(v); 
        if (!deg[u]) --d0; if (deg[u] == 2) --d2, --sz2[uu]; 
        if (!deg[v]) --d0; if (deg[v] == 2) --d2, --sz2[vv]; 
        ++deg[u]; ++deg[v]; 
        if (c[vv]) c[vv] = 0, --cyc; 
        if (uu != vv) {
            if (c[uu]) c[uu] = 0, --cyc; 
            fa[uu] = vv, sz[vv] += sz[uu], sz2[vv] += sz2[uu]; 
        }
        if (deg[u] == 2) ++d2, ++sz2[vv]; 
        if (deg[v] == 2) ++d2, ++sz2[vv]; 
        if (sz2[vv] == sz[vv]) c[vv] = 1, ++cyc; 
        V = n - d0 - d2 + cyc; 
        ++ec; E = ec - d2 + cyc; 
        // cout << d0 << " " << d2 << " " << cyc << "\n"; 
        // cout << sz[vv] << " " << sz2[vv] << "\n"; 
    }
    for (int i = 1; i <= q; ++i) cout << an1[i] << " " << an2[i] << "\n"; 
    return 0; 
}

F. Frightful Formula

有点意思的计数题。

发现递推式实际上是算带权的走到当前点的方案数。

首先考虑 $a,b$ 的贡献，以 $(1,i)$ 为例，它相当于是 $(2,i)\rightarrow (n,n)$ ，因此贡献为 $\dbinom{n-2+n-i}{n-2}\times a^{n-i}\times b^{n-1}\times val(1,i)$ 。

然后再考虑 $c$ 的贡献。再 $(i,j)$ 处加入一个 $c$ ，会加上 $\dbinom{2n-i-j}{n-i}a^{n-j}b^{n-i}c$ 的贡献。

直接做是 $O(n^2)$ 的，不难想到考虑一条一条对角线去枚举，式子长这样：

$\sum_{k=0}^{n-2}\left(\sum_{i=0}^{k}\binom k i a^{k-i}b^i\right)+\\ \sum_{k=n-1}^{2n-4}\left(\sum_{i=k-n+2}^{n-2}\binom k i a^{k-i}b^i \right)$

前面的一坨可以使用二项式定理来化简，后面那一坨可以使用增量法计算：

$\begin{aligned} f(k)&=\sum_{i=k-n+2}^{n-2}\binom k i a^{k-i}b^i\\ &=\sum_{i=k-n+2}^{n-2}\binom{k-1} i a^{k-i}b^i+\sum_{i=k-n+2}^{n-2}\binom{k-1}{i-1} a^{k-i}b^i\\ &=af_{k-1}-\binom{k-1}{k-n+1}b^{k-n+1}a^{n-1}+bf_{k-1}-\binom{k-1}{n-2}b^{n-1}a^{k-n+1} \end{aligned}$

查看代码

#include <bits/stdc++.h>
using namespace std; 
const int P = 1000003; 
const int N = 400000; 

inline int poww(int a, int b) {
    int r = 1;
    for (; b; b >>= 1, a = 1ll * a * a % P) if (b & 1) r = 1ll * r * a % P;  
    return r; 
}

int n, a, b, c, pa[400005], pb[400005]; 
int l[200005], t[200005]; 
int fac[400005], ifac[400005]; 
int f[400005]; 

inline int C(int n, int m) {
    if (n < 0 || m < 0 || n < m) return 0; 
    return 1ll * fac[n] * ifac[m] * ifac[n - m] % P; 
}

int calf(int k) {
    int res = 0; 
    for (int i = k - n + 2; i <= n - 2; ++i)
        res = (res + 1ll * C(k, i) * pa[k - i] * pb[i]) % P; 
    return res; 
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> a >> b >> c; 

    for (int i = fac[0] = pa[0] = pb[0] = 1; i <= N; ++i) fac[i] = 1ll * fac[i - 1] * i % P, pa[i] = 1ll * pa[i - 1] * a % P, pb[i] = 1ll * pb[i - 1] * b % P; 
    ifac[N] = poww(fac[N], P - 2); 
    for (int i = N - 1; i >= 0; --i) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P; 

    int ans = 0; 
    for (int i = 1, x; i <= n; ++i) {
        cin >> x; 
        if (i == 1) continue; 
        ans = (ans + 1ll * C(n - 2 + n - i, n - 2) * pa[n - 1] * pb[n - i] % P * x) % P; 
    }
    for (int i = 1, x; i <= n; ++i) {
        cin >> x; 
        if (i == 1) continue; 
        ans = (ans + 1ll * C(n - 2 + n - i, n - 2) * pa[n - i] * pb[n - 1] % P * x) % P; 
    }
    for (int k = 0, B = 1; k <= n - 2; ++k) {
        ans = (ans + 1ll * c * B) % P; 
        B = 1ll * B * (a + b) % P; 
    }
    for (int k = n - 1; k <= n * 2 - 4; ++k) {
        if (k == n - 1) f[k] = calf(k); 
        else {
            f[k] = (1ll * a * f[k - 1] - 1ll * C(k - 1, k - n + 1) * pb[k - n + 1] * pa[n - 1] + 1ll * b * f[k - 1] - 1ll * C(k - 1, n - 2) * pb[n - 1] * pa[k - n + 1]) % P; 
        }
        ans = (ans + 1ll * c * f[k]) % P; 
    }
    cout << (ans + P) % P << "\n"; 
    return 0; 
}

G. Greenhouse Growth

空间大盗扭曲了此处的空间。

我们将于未知时间完成这道题目。

H. Hovering Hornet

时间旅人逆转了此处的时间。

几何。

I. Ice Igloos

死灵法师抹除了此处的灵魂。

几何。

J. Juice Junctions

K. Kernel Knights

类似拓扑排序，直接算就行。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int N = 200005;

int n; 
int a[N], in[N], vis[N]; 

int main(void) {
    cin >> n; 
    for (int i = 1; i <= 2 * n; ++i)
        scanf("%d", a + i), ++in[a[i]]; 
    queue<int> q;
    for (int i = 1; i <= 2 * n; ++i)
        if (!in[i]) q.emplace(i); 
    while (!q.empty()) {
        int u = q.front(); q.pop(); vis[u] = 1;
        if (vis[a[u]] == -1) continue; 
        vis[a[u]] = -1; 
        if (--in[a[a[u]]] == 0) q.emplace(a[a[u]]); 
    }
    
    for (int i = 1; i <= n; ++i) if (vis[i] == 1) printf("%d ", i);
    for (int i = n + 1; i <= n * 2; ++i) if (vis[i] >= 0) printf("%d ", i);
    putchar('\n'); 
    return 0;
}

* L. Looping Labyrinth

太牛逼了。

可以使用 $(r_B,c_B,r_T,c_T)$ 代表一个坐标 $(n\times r_B+r_T,m\times c_B+c_T)$ 。将 $(r_B,c_B)$ 称为块坐标， $(r_T,c_T)$ 称为余坐标。

考虑所有余坐标为 $(0,0)$ 的点，

制毒大枭投掷了神秘的毒药。

我们将于未知时间补完。