A – 玩具谜题

sb 题，随便搞。

// P1563.cpp
#include <iostream>

using namespace std;

int main()
{
    int N, M;
    cin >> N >> M;
    int dir[N];
    string occupations[N];
    int cmdKeys[M];
    int cmdPath[M];
    // I/O;
    for (int i = 0; i < N; i++)
        cin >> dir[i] >> occupations[i];
    for (int j = 0; j < M; j++)
        cin >> cmdKeys[j] >> cmdPath[j];
    // Process;
    int currentBias = 0;
    for (int i = 0; i < M; i++)
        if (cmdKeys[i] == 0)
            if (dir[currentBias % N] == 1)
                currentBias += cmdPath[i];
            else
            {
                currentBias -= cmdPath[i];
                if (currentBias < 0)
                    currentBias = N + currentBias;
            }
        else if (dir[currentBias % N] == 1)
        {
            currentBias -= cmdPath[i];
            if (currentBias < 0)
                currentBias = N + currentBias;
        }
        else
            currentBias += cmdPath[i];
    cout << occupations[currentBias % N];
    return 0;
}

B – 天天爱跑步

草，出在 D1T2 是真的毒。当然，思路还是非常巧妙的。

首先，把树之类的都存进来，对于一个玩家预处理出其 LCA，并在 LCA 上打标记（只有到了 LCA 这颗子树才能产生贡献）。开一个桶，关键字是深度。当一个进入了一个 LCA 子树之后，就可以让子树内的点生效：在桶子里++即可。

剩下的回答，再来一遍 DFS，每次经过一个监视点就回答询问即可。细节超级超级多，看看代码吧。

// P1600.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3e6 + 2000;
int head[MAX_N], current, fa[20][MAX_N], dep[MAX_N], wi[MAX_N], max_dep;
int bucket[MAX_N << 1], n, m, si[MAX_N], di[MAX_N], status[MAX_N], answer[MAX_N];
int bucket_up[1000011];
vector<int> lcaS[MAX_N], lcaT[MAX_N], tbuck[MAX_N];
struct route
{
    int s, t, lca, len;
} routes[MAX_N];
struct edge
{
    int to, nxt;
} edges[MAX_N << 1];
void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}
void initialize(int u)
{
    max_dep = max(max_dep, dep[u]);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa[0][u])
        {
            dep[edges[i].to] = dep[u] + 1;
            fa[0][edges[i].to] = u;
            initialize(edges[i].to);
        }
}
int getLCA(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = 19; i >= 0; i--)
        if (dep[fa[i][x]] >= dep[y])
            x = fa[i][x];
    if (x == y)
        return x;
    for (int i = 19; i >= 0; i--)
        if (fa[i][x] != fa[i][y])
            x = fa[i][x], y = fa[i][y];
    return fa[0][x];
}
void dfs_downward(int u)
{
    int now = wi[u] + dep[u], previous;
    if (now <= max_dep)
        previous = bucket[now];
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa[0][u])
            dfs_downward(edges[i].to);
    bucket[dep[u]] += status[u];
    if (now <= max_dep)
        answer[u] = bucket[now] - previous;
    for (int i = 0, siz = lcaS[u].size(); i < siz; i++)
        bucket[dep[lcaS[u][i]]]--;
}
void dfs_upward(int u)
{
    int now = dep[u] - wi[u] + MAX_N, previous = bucket_up[now];
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa[0][u])
            dfs_upward(edges[i].to);
    for (int i = 0, siz = tbuck[u].size(); i < siz; i++)
        bucket_up[MAX_N + tbuck[u][i]]++;
    answer[u] += bucket_up[now] - previous;
    for (int i = 0, siz = lcaT[u].size(); i < siz; i++)
        bucket_up[MAX_N + lcaT[u][i]]--;
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
    }
    dep[1] = 1, initialize(1);
    for (int i = 1; i < 20; i++)
        for (int j = 1; j <= n; j++)
            fa[i][j] = fa[i - 1][fa[i - 1][j]];
    for (int i = 1; i <= n; i++)
        scanf("%d", &wi[i]);

    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &routes[i].s, &routes[i].t);
        status[routes[i].s]++;
        routes[i].lca = getLCA(routes[i].s, routes[i].t);
        routes[i].len = dep[routes[i].s] + dep[routes[i].t] - 2 * dep[routes[i].lca];
        lcaS[routes[i].lca].push_back(routes[i].s);
    }
    dfs_downward(1);

    for (int i = 1; i <= m; i++)
    {
        tbuck[routes[i].t].push_back(dep[routes[i].t] - routes[i].len);
        lcaT[routes[i].lca].push_back(dep[routes[i].t] - routes[i].len);
    }
    dfs_upward(1);

    for (int i = 1; i <= m; i++)
        if (dep[routes[i].s] - dep[routes[i].lca] == wi[routes[i].lca])
            answer[routes[i].lca]--;
    for (int i = 1; i <= n; i++)
        printf("%d ", answer[i]);
    return 0;
}

C – 换教室

概率期望 DP 的经典题目。

先考虑用 Floyd 处理完图上最短路，然后设计状态\(dp[i][j]\)为第\(i\)个时间段内换了\(j\)次教室。然后根据两种选择，随便转移就可以了。代码可能比较丑。

// P1805.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2020, MAX_V = 330;
const double INF = 1e17 + 5;
int n, m, v, e, ci[MAX_N], di[MAX_N], dist[MAX_V][MAX_V], tmpx, tmpy, tmpz;
double pi[MAX_N], dp[MAX_N][MAX_N][2];
int main()
{
    memset(dist, 63, sizeof(dist));
    scanf("%d%d%d%d", &n, &m, &v, &e);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ci[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &di[i]);
    for (int i = 1; i <= n; i++)
        scanf("%lf", &pi[i]);
    for (int i = 1; i <= e; i++)
        scanf("%d%d%d", &tmpx, &tmpy, &tmpz), dist[tmpx][tmpy] = min(dist[tmpx][tmpy], tmpz), dist[tmpy][tmpx] = dist[tmpx][tmpy];
    for (register int k = 1; k <= v; k++)
        for (register int i = 1; i <= v; i++)
            for (register int j = 1; j <= v; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    for (int i = 1; i <= v; i++)
        dist[i][i] = dist[0][i] = dist[i][0] = 0;
    memset(dp, 127, sizeof(dp));
    dp[1][0][0] = dp[1][1][1] = 0;
    for (int i = 2; i <= n; i++)
    {
        dp[i][0][0] = dp[i - 1][0][0] + dist[ci[i - 1]][ci[i]];
        for (int j = 1; j <= min(i, m); j++)
        {
            int C1 = ci[i - 1], C2 = di[i - 1], C3 = ci[i], C4 = di[i];
            dp[i][j][0] = min(dp[i][j][0], min(dp[i - 1][j][0] + dist[C1][C3], dp[i - 1][j][1] + dist[C1][C3] * (1 - pi[i - 1]) + dist[C2][C3] * pi[i - 1]));
            dp[i][j][1] = min(dp[i][j][1], min(dp[i - 1][j - 1][0] + dist[C1][C3] * (1 - pi[i]) + dist[C1][C4] * pi[i], dp[i - 1][j - 1][1] + dist[C2][C4] * pi[i] * pi[i - 1] + dist[C2][C3] * pi[i - 1] * (1 - pi[i]) + dist[C1][C4] * (1 - pi[i - 1]) * pi[i] + dist[C1][C3] * (1 - pi[i - 1]) * (1 - pi[i])));
        }
    }
    double ans = INF;
    for (register int i = 0; i <= m; i++)
        ans = min(ans, min(dp[n][i][0], dp[n][i][1]));
    printf("%.2lf", ans);
    return 0;
}

D – 组合数问题

先预处理对\(k\)取模的值，然后前缀和处理。

// P2822.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_DOM = 2200;
struct ask
{
    int n, m;
} asks[(int)1e4 + 20];
ll t, k, c_table[MAX_DOM][MAX_DOM], prs[MAX_DOM][MAX_DOM];
int max_dom;
int main()
{
    scanf("%lld%lld", &t, &k);
    c_table[1][1] = c_table[1][0] = 1 % k;
    for (int i = 1; i <= t; i++)
        scanf("%d%d", &asks[i].n, &asks[i].m), max_dom = max(max_dom, max(asks[i].n, asks[i].m));
    for (int i = 2; i <= max_dom; i++)
    {
        c_table[i][0] = 1;
        for (int j = 1; j <= i; j++)
            c_table[i][j] = (c_table[i - 1][j - 1] + c_table[i - 1][j]) % k;
    }
    for (int i = 1; i <= max_dom; i++)
        for (int j = 1; j <= max_dom; j++)
        {
            int res = ((c_table[i][j] == 0 && j <= i) ? 1 : 0);
            prs[i][j] = prs[i - 1][j] + prs[i][j - 1] - prs[i - 1][j - 1] + res;
        }
    for (int i = 1; i <= t; i++)
        printf("%d\n", prs[asks[i].n][min(asks[i].n, asks[i].m)]);
    return 0;
}

E – 蚯蚓

这题蛮好。思考发现越后被切断的蚯蚓的长度越小，所以我们不需要用堆来保证单调性，考虑用一个「原生」队列、两个「被切断」队列来进行维护，每次取最大就直接取 max 就行。至于增长就直接用全局增量搞就可以了。

// P2827.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 7e6 + 200;

int n, m, q, u, v, t, seq[int(1e5) + 200];
queue<int> q1, q2, q3;
int queryans[MAX_N], acc;

int main()
{
    scanf("%d%d%d%d%d%d", &n, &m, &q, &u, &v, &t);
    for (int i = 1; i <= n; i++)
        scanf("%d", &seq[i]);
    sort(seq + 1, seq + 1 + n), reverse(seq + 1, seq + 1 + n);
    for (int i = 1; i <= n; i++)
        q1.push(seq[i]);
    for (int tick = 1; tick <= m; tick++)
    {
        // get the biggest;
        queue<int> *ptr = NULL;
        int val = -0x3f3f3f3f;
        if (!q1.empty() && q1.front() >= val)
            ptr = &q1, val = q1.front();
        if (!q2.empty() && q2.front() >= val)
            ptr = &q2, val = q2.front();
        if (!q3.empty() && q3.front() >= val)
            ptr = &q3, val = q3.front();
        ptr->pop();
        // split it;
        val += acc, queryans[tick] = val;
        int lft = 1LL * val * u / v, rig = val - lft;
        acc += q;
        q2.push(lft - acc), q3.push(rig - acc);
    }
    for (int i = t; i <= m; i += t)
        printf("%d ", queryans[i]);
    puts("");
    int cnt = 1;
    while (!(q1.empty() && q2.empty() && q3.empty()) && cnt <= n + m)
    {
        queue<int> *ptr = NULL;
        int val = -0x3f3f3f3f;
        if (!q1.empty() && q1.front() >= val)
            ptr = &q1, val = q1.front();
        if (!q2.empty() && q2.front() >= val)
            ptr = &q2, val = q2.front();
        if (!q3.empty() && q3.front() >= val)
            ptr = &q3, val = q3.front();
        ptr->pop();
        if (cnt % t == 0)
            printf("%d ", val + acc);
        cnt++;
    }
    return 0;
}

F – 愤怒的小鸟

应该比较好推。首先看到数据范围就显然是状态压缩，然后你就去找每一个点集是否能只被一个抛物线经过。之后裸的 DP 一下就可以了。

// P2831.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define pr pair<double, double>
using namespace std;
const double eps = 1e-8;
int T, n, dotset[19][19], dp[(1 << 19)], lbit[(1 << 19)], m;
pr prs[20];
void solve(double &x, double &y, double a1, double b1, double c1, double a2, double b2, double c2)
{
    y = (a1 * c2 - a2 * c1) / (a1 * b2 - a2 * b1);
    x = (c1 - b1 * y) / a1;
}
int main()
{
    for (int i = 0; i < (1 << 18); i++)
    {
        int bit = 0;
        for (; bit < 18 && (i & (1 << bit)) ; bit++)
            ;
        lbit[i] = bit;
    }
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        memset(dp, 0x3f, sizeof(dp)), memset(dotset, 0, sizeof(dotset));
        for (int i = 0; i < n; i++)
            scanf("%lf%lf", &prs[i].first, &prs[i].second);
        // process the curves;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                if (fabs(prs[i].first - prs[j].first) < eps)
                    continue;
                double a, b;
                solve(a, b, prs[i].first * prs[i].first, prs[i].first, prs[i].second,
                      prs[j].first * prs[j].first, prs[j].first, prs[j].second);
                if (a > -eps)
                    continue;
                for (int k = 0; k < n; k++)
                    if (fabs(a * prs[k].first * prs[k].first + b * prs[k].first - prs[k].second) < eps)
                        dotset[i][j] |= (1 << k);
            }
        dp[0] = 0;
        for (int stat = 0; stat < (1 << n); stat++)
        {
            int esspt = lbit[stat];
            dp[stat | (1 << esspt)] = min(dp[stat | (1 << esspt)], dp[stat] + 1);
            for (int k = 0; k < n; k++)
                dp[stat | dotset[esspt][k]] = min(dp[stat | dotset[esspt][k]], dp[stat] + 1);
        }
        printf("%d\n", dp[(1 << n) - 1]);
    }
    return 0;
}