方格取数

看一眼复杂度，\(O(nm)\)级别的，考虑两个循环的 DP。分析整个题面之后发现，我们穿过边界时，当且仅当另一个连通块的权值比当前的大，否则便不会为了穿过边界而损失当前金块。所以，我们做一个 DP 一样的东西：因为发现每个格子只能走一遍，那么在每一列你只能选择一直向上走和一直向下走，所以这个 DP 便没了后效性，然后再处理连通块之间的连接判断就做完了。

// B.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 1030;

int mp[MAX_N][MAX_N], n, m, T;
ll dp[MAX_N][MAX_N];

int main()
{
    while (scanf("%d%d", &n, &m) != EOF)
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%d", &mp[i][j]);
        for (int j = 1; j <= m; j++)
        {
            ll cur = -1e18;
            for (int i = 1; i <= n; i++)
                if (mp[i][j] == -1)
                    cur = -1e18, dp[i][j] = cur;
                else
                    cur = max(cur, dp[i][j - 1]) + mp[i][j], dp[i][j] = cur;
            cur = -1e18;
            for (int i = n; i >= 1; i--)
                if (mp[i][j] == -1)
                    cur = -1e18;
                else
                    cur = max(cur, dp[i][j - 1]) + mp[i][j], dp[i][j] = max(cur, dp[i][j]);
            int down_bound = 0;
            for (int i = n; i >= 1; i--)
                if (mp[i][j] == -1)
                    break;
                else if (dp[i][j - 1] >= 0)
                {
                    down_bound = i;
                    break;
                }
            cur = 0;
            for (int i = 1; i < down_bound; i++)
                if (mp[i][j] == -1)
                    break;
                else
                    cur += mp[i][j], dp[i][j] = max(dp[i][j], cur);
            int up_bound = n + 1;
            for (int i = 1; i <= n; i++)
                if (mp[i][j] == -1)
                    break;
                else if (dp[i][j - 1] >= 0)
                {
                    up_bound = i;
                    break;
                }
            cur = 0;
            for (int i = n; i > up_bound; i--)
                if (mp[i][j] == -1)
                    break;
                else
                    cur += mp[i][j], dp[i][j] = max(dp[i][j], cur);
        }
        ll ans = -1;
        for (int i = 1; i <= n; i++)
            ans = max(ans, dp[i][m]);
        printf("%lld\n", ans);
    }
    return 0;
}

染色

真的是您🐎的签到题。

首先，我们可以枚举有\(i\)个\(A\)，然后判断剩下的是否整除\(B\)。如果整除，那么就可以加入答案，考虑计算部分贡献，在\(n\)个砖块里选择\(i\)个作为\(A\)的，剩下再乘上\(n\)个砖块里面选择\(\frac{n – iA}{B}\)个，如果重叠的就算做是\(C\)，如果非重叠就是\(B\)。

// A.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 3e5 + 200, mod = 998244353;

int fac[MAX_N], fac_inv[MAX_N], T;
ll n, A, B, x;

int quick_pow(int bas, int tim)
{
    int ans = 1;
    while (tim)
    {
        if (tim & 1)
            ans = 1LL * ans * bas % mod;
        bas = 1LL * bas * bas % mod;
        tim >>= 1;
    }
    return ans;
}

int combinator(int n_, int k_)
{
    if (n_ < k_ || n_ < 0 || k_ < 0)
        return 0;
    return 1LL * fac[n_] * fac_inv[k_] % mod * fac_inv[n_ - k_] % mod;
}

int main()
{
    scanf("%d", &T);
    for (int i = fac[0] = 1; i < MAX_N; i++)
        fac[i] = 1LL * fac[i - 1] * i % mod;
    fac_inv[MAX_N - 1] = quick_pow(fac[MAX_N - 1], mod - 2);
    for (int i = MAX_N - 2; i >= 0; i--)
        fac_inv[i] = 1LL * fac_inv[i + 1] * (i + 1) % mod;
    while (T--)
    {
        scanf("%lld%lld%lld%lld", &n, &A, &B, &x);
        ll res = 0, ans = 0;
        for (int i = 0; i <= n; i++)
        {
            ll tmp = x - 1LL * i * A;
            if (tmp > 0 && (tmp % B == 0))
                ans = (1LL * ans + 1LL * combinator(n, i) * combinator(n, tmp / B) % mod) % mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

字符串

这道题其实比较好想，思考计算子序列的递推公式：

\[ dp[i] = 2dp[i – 1] – dp[lastPos[str[i]]] \]

先计算前缀的子序列个数，然后在考虑向后构造：我们发现，DP 数组是由单调递增的性质的，那么我们每次转移的时候取最小的\(lastPos[char]\)即可。

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

using namespace std;

const int MAX_K = 27, mod = 1e9 + 7;

int dp[MAX_K], n, m, k, prev_pos[MAX_K], ans;

int main()
{
    scanf("%d %d\n", &m, &k);
    int ans = 1, x, old;
    char ch;
    while (true)
    {
        ch = getchar(), x = ch - 'a' + 1;
        if (x < 1 || x > 26)
            break;
        old = ans;
        ans = 2LL * ans % mod, ans = (1LL * ans + mod - dp[x]) % mod;
        dp[x] = old, prev_pos[x] = ++n;
    }
    for (int i = 1; i <= m; i++)
    {
        x = 0;
        for (int j = 1; j <= k; j++)
            if (!x || prev_pos[x] > prev_pos[j])
                x = j;
        prev_pos[x] = ++n, old = ans;
        ans = 2LL * ans % mod, ans = (ans + mod - dp[x]) % mod;
        dp[x] = old;
    }
    printf("%d", ans);
    return 0;
}

膜方俱乐部

sb 基环树，记录下环的值还有链上的值，然后就可以愉快的 AC 了。

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

using namespace std;

const int MAX_N = 200100;

int head[MAX_N], current, deg[MAX_N], n, val[MAX_N], deletion[MAX_N], mem[MAX_N], sum[MAX_N], loop[MAX_N];

struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

int find(int x) { return x == mem[x] ? x : mem[x] = find(mem[x]); }

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

void toposort()
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (deg[i] == 0)
            q.push(i);
    while (!q.empty())
    {
        int u = q.front();
        q.pop(), deg[u]--;
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (--deg[edges[i].to] == 0)
                q.push(edges[i].to);
    }
    for (int i = 1; i <= n; i++)
        if (deg[i] > 0)
            loop[find(i)] += val[i];
}

void dfs(int u, int fat)
{
    if (deg[fat] <= 0)
        val[u] += val[fat];
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fat && deg[edges[i].to] <= 0)
            dfs(edges[i].to, u);
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &val[i]), mem[i] = i, sum[i] = val[i];
    for (int i = 1, v; i <= n; i++)
    {
        scanf("%d", &v), addpath(i, v), addpath(v, i), deg[v]++;
        int x = find(i), y = find(v);
        if (x != y)
            mem[y] = x, sum[x] += sum[y];
    }
    toposort();
    for (int i = 1; i <= n; i++)
        if (deg[i] > 0)
            dfs(i, 0);
    for (int i = 1; i <= n; i++)
        if (deg[i] > 0)
            printf("%d\n", loop[find(i)]);
        else
            printf("%d\n", val[i] + loop[find(i)]);
    return 0;
}

排名

为什么可以这么简单啊？

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

using namespace std;

int n, m, prefix, suffix;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1, p; i <= n; i++)
        scanf("%d", &p), prefix += p - 1, suffix += m - p;
    printf("%d\n%d\n", max(1, m - suffix), min(m, prefix + 1));
    return 0;
}

或者过于完美亦未可知

这道题就是数据结构和思维结合的题目。题目求的是：怎样安排\(q\)个操作，使得最后的串与目标串相差最小。

首先，把答案定为目标串中\(0\)的个数，假定整个序列完全覆盖了\(1\)。我们要求的答案就是尽量把这个答案减干净（也就是求最小值）。所以，对于每一个操作，我们都在他的左端点和右端点上打上一个标记，来标注最少能少多少个，然后这道题就可以解决了（有点像最小割的方法）。

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

using namespace std;

const int MAX_N = 800010, INF = 0x3f3f3f3f;

int min_val[MAX_N], seq[MAX_N], n, q, ans;
vector<int> queries[MAX_N];

#define mid ((l + r) >> 1)
#define lson (p << 1)
#define rson ((p << 1) | 1)

void pushup(int p)
{
    min_val[p] = min(min_val[lson], min_val[rson]);
}

void build(int l, int r, int p)
{
    if (l == r)
        return (void)(min_val[p] = ((l == 0) ? 0 : INF));
    build(l, mid, lson), build(mid + 1, r, rson);
    pushup(p);
}

void update(int qx, int l, int r, int p, int val)
{
    if (l == r)
        return (void)(min_val[p] = min(min_val[p], val));
    if (qx <= mid)
        update(qx, l, mid, lson, val);
    else
        update(qx, mid + 1, r, rson, val);
    pushup(p);
}

int query(int ql, int qr, int l, int r, int p)
{
    if (ql <= l && r <= qr)
        return min_val[p];
    int ret = INF;
    if (ql <= mid)
        ret = min(ret, query(ql, qr, l, mid, lson));
    if (mid < qr)
        ret = min(ret, query(ql, qr, mid + 1, r, rson));
    return ret;
}

#undef mid
#undef lson
#undef rson

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &seq[i]), ans += !seq[i];
    scanf("%d", &q);
    for (int i = 1, x, y; i <= q; i++)
        scanf("%d%d", &x, &y), queries[x - 1].push_back(y);
    build(0, n, 1);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0, siz = queries[i].size(); j < siz; j++)
            update(queries[i][j], 0, n, 1, query(i, queries[i][j], 0, n, 1));
        update(i + 1, 0, n, 1, query(i, i, 0, n, 1) + (seq[i] ? 1 : -1));
    }
    printf("%d\n", ans + query(n, n, 0, n, 1));
    return 0;
}

献给许许多多的忌日

先求一遍树上最大独立集，然后计算一下：如果独立集的两倍都小于\(n\)，那么对于警察来讲可以建造更多无法起火的房屋；如果独立集大于\(k\)，那么断边也行不通；

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

using namespace std;

const int MAX_N = 5050;

int head[MAX_N], current, n, k, dp[MAX_N][2];

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 dfs(int u, int fa)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            dfs(edges[i].to, u), dp[u][0] += max(dp[edges[i].to][1], dp[edges[i].to][0]);
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            dp[u][1] = max(dp[u][1], dp[u][0] - max(dp[edges[i].to][1], dp[edges[i].to][0]) + dp[edges[i].to][0] + 1);
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &k);
    for (int i = 1, u, v; i <= n - 1; i++)
        scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
    dfs(1, 0);
    int independent_set = max(dp[1][0], dp[1][1]);
    if ((independent_set << 1) < n || k < independent_set - 1)
        puts("policeman");
    else
        puts("arsonist");
    return 0;
}