kal0rona 越来越 sb了。

餐馆

典型的树形 DP，我特么考试的时候竟然写着写着把一种情况删掉了。

考虑设置状态\(dp[i][j][0/1]\)，\(i\)表示节点编号，\(j\)表示所用的单位时间，\(0\)代表不一定走回根部，而\(1\)代表一定走回根部。大概模拟一下就知道怎么转移了。

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

using namespace std;

const int MAX_N = 550;

int head[MAX_N], current, n, m, ai[MAX_N];
ll dp[MAX_N][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)
{
    dp[u][1][0] = dp[u][1][1] = ai[u];
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
        {
            dfs(edges[i].to, u);
            for (int k = m; k >= 0; k--)
            {
                for (int j = m - k; j >= 0; j--)
                {
                    if (j >= 1)
                        dp[u][j + k][0] = max(dp[u][j + k][0], dp[edges[i].to][j - 1][0] + dp[u][k][1]);
                    if (j >= 2)
                        dp[u][j + k][1] = max(dp[u][j + k][1], dp[edges[i].to][j - 2][1] + dp[u][k][1]);
                    if (j >= 2)
                        dp[u][j + k][0] = max(dp[u][j + k][0], dp[edges[i].to][j - 2][1] + dp[u][k][0]);
                }
            }
        }
}

int main()
{
    /*
    freopen("dostavljac.in", "r", stdin);
    freopen("dostavljac.out", "w", stdout);
    */
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]);
    for (int i = 1, u, v; i <= n - 1; i++)
        scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
    dfs(1, 0);
    printf("%lld", max(dp[1][m][1], dp[1][m][0]));
    return 0;
}

随机

这道题我的方法不太一样，没用 Two-Pointers + Multiset。

我发现：对于一个可能对答案贡献的点对\((a_i, a_j)\)，只需要考虑这两个值作为左右端点的情况即可。所以，我们在归并排序的时候，可以把所有差值尽量小的贡献更新答案，并且更新原生位置。

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

using namespace std;

const int MAX_N = 1e6 + 200;

int seq[MAX_N], n, tmp[MAX_N], tmp_pos[MAX_N], pos[MAX_N], ans = 0x3f3f3f3f;

void mergeSort(int l, int r)
{
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    mergeSort(l, mid), mergeSort(mid + 1, r);
    int ptr1 = l, ptr2 = mid + 1, ptr = l;
    while (ptr1 <= mid && ptr2 <= r)
        if (seq[ptr1] < seq[ptr2])
        {
            tmp[ptr] = seq[ptr1], tmp_pos[ptr++] = pos[ptr1], ans = min(ans, max(abs(seq[ptr2] - seq[ptr1]), abs(pos[ptr1] - pos[ptr2]) + 1)), ptr1++;
            continue;
        }
        else
        {
            tmp[ptr] = seq[ptr2], tmp_pos[ptr++] = pos[ptr2], ans = min(ans, max(abs(seq[ptr2] - seq[ptr1]), abs(pos[ptr1] - pos[ptr2]) + 1)), ptr2++;
            continue;
        }
    while (ptr1 <= mid)
        tmp[ptr] = seq[ptr1], tmp_pos[ptr++] = pos[ptr1++];
    while (ptr2 <= r)
        tmp[ptr] = seq[ptr2], tmp_pos[ptr++] = pos[ptr2++];
    for (int i = l; i <= r; i++)
    {
        seq[i] = tmp[i], pos[i] = tmp_pos[i];
        if (i > l)
            ans = min(ans, max(abs(pos[i] - pos[i - 1]) + 1, abs(seq[i] - seq[i - 1])));
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &seq[i]), pos[i] = i;
    mergeSort(1, n), printf("%d", ans);
    return 0;
}

树

每一种定向都存在着两种方向可选，我们在处理询问的时候，把两点到\(LCA\)的两条链拆开来，然后选择相反的方向，这个可以用并查集搞定。合并的总次数不会超过\(n – 1\)次，所以复杂度不高。最后答案就是\(2^{\text{连通块个数}}\)。

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

using namespace std;

const int MAX_N = 300100, mod = 1e9 + 7;

int head[MAX_N], current, dep[MAX_N], fa[20][MAX_N], n, m, val[MAX_N], mem[MAX_N << 1];
int queries[MAX_N][3];
bool side[MAX_N];

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

int find(int x)
{
    if (x == mem[x])
        return x;
    int pre = mem[x];
    mem[x] = find(mem[x]);
    side[x] ^= side[pre];
    return mem[x];
}

void unite(int x, int y)
{
    x = find(x);
    while (dep[x] - 2 >= dep[y])
    {
        int tmp = fa[0][x];
        tmp = find(tmp);
        mem[x] = tmp;
        x = find(x);
    }
}

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

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

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];
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= 2 * n; i++)
        mem[i] = i;
    for (int i = 1, u, v; i <= n - 1; i++)
        scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
    dfs(1, 0);
    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 id = 1; id <= m; id++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        int lca = getLCA(x, y);
        queries[id][0] = x, queries[id][1] = y, queries[id][2] = lca;
        unite(x, lca), unite(y, lca);
    }
    for (int i = 1; i <= m; i++)
    {
        int x = queries[i][0], y = queries[i][1], lca = queries[i][2];
        if (x == lca || y == lca)
            continue;
        int fx = find(x), fy = find(y);
        if (fx == fy)
        {
            if ((side[x] ^ side[y]) != 1)
                puts("0"), exit(0);
            continue;
        }
        mem[fx] = fy;
        side[fx] = 1 ^ side[x] ^ side[y];
    }
    int ans = 1;
    for (int i = 2; i <= n; i++)
        if (find(i) == i)
            ans = 1LL * ans * 2 % mod;
    printf("%d", ans);
    return 0;
}

不等数列

直接计算非常的困难，我们可以考虑另外一种思路：把数字插入序列，然后计算贡献的时候，这个数字会自适应地符合不等条件。设置状态\(dp[i][j]\)为插入了\(i\)个数字之后有\(k\)个小于号。我们加入之后，计算小于和大于的贡献即可。

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

using namespace std;

const int MAX_N = 1010, mod = 2012;

int dp[MAX_N][MAX_N], n, k;

int main()
{
    scanf("%d%d", &n, &k);
    dp[1][0] = 1;
    for (int i = 2; i <= n; i++)
        for (int j = 0; j <= min(n - 1, k); j++)
            dp[i][j] = (1LL * dp[i - 1][j - 1] * (i - j) % mod + 1LL * dp[i - 1][j] * (j + 1) % mod) % mod;
    printf("%d", dp[n][k]);
    return 0;
}

经营与开发

这道题真的是神题。

我们可以反着来推：如果修复的话，就乘上之前答案一个系数；开发同理。

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

using namespace std;

const int MAX_N = 100010;

int n, w, ai[MAX_N], bi[MAX_N];
double k, c, ans;

int main()
{
    scanf("%d%lf%lf%d", &n, &k, &c, &w);
    k = 1 - 0.01 * k, c = 1 + 0.01 * c;
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &ai[i], &bi[i]);
    for (int i = n; i >= 1; i--)
        if (ai[i] == 1)
            ans = max(ans, ans * k + bi[i]);
        else
            ans = max(ans, ans * c - bi[i]);
    printf("%.2lf", ans * w);
    return 0;
}

CF292D Connected Components

前缀并查集和后缀并查集，询问的时候暴力合并即可。

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

using namespace std;

const int MAX_N = 10010;

struct ufs
{
    int fa[550], antiComponentCount;
    int find(int x) { return fa[x] ? fa[x] = find(fa[x]) : x; }
    void unite(int x, int y)
    {
        if (find(x) != find(y))
            antiComponentCount++, fa[find(x)] = find(y);
    }
} lft[MAX_N], rig[MAX_N], ans;

int n, m, xi[MAX_N], yi[MAX_N], q;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d%d", &xi[i], &yi[i]), lft[i] = lft[i - 1], lft[i].unite(xi[i], yi[i]);
    for (int i = m; i >= 1; i--)
        rig[i] = rig[i + 1], rig[i].unite(xi[i], yi[i]);
    scanf("%d", &q);
    while (q--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        ans = lft[l - 1];
        for (int i = 1; i <= n; i++)
            if (rig[r + 1].fa[i])
                ans.unite(rig[r + 1].fa[i], i);
        printf("%d\n", n - ans.antiComponentCount);
    }
    return 0;
}

IOI 2008 Island

维护每一颗基环数的直径，加起来就行。

麻烦就麻烦在：维护基环数的直径考虑两种情况，一个是环加两条链，还有一个是单链。环上链的困难在于需要用单调队列来进行优化，反正是一道非常毒瘤的题目。

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

const int MAX_N = 3e6 + 200;

int head[MAX_N], n, deg[MAX_N], current, org[MAX_N], ccnt;
ll chain_dist[MAX_N], dist[MAX_N], dp[MAX_N], ans, q[MAX_N], chain[MAX_N];
bool vis[MAX_N];

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

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

void toposort()
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (deg[i] == 1)
            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] > 1)
            {
                deg[edges[i].to]--;
                dp[org[u]] = max(dp[org[u]], dist[u] + dist[edges[i].to] + edges[i].weight);
                dist[edges[i].to] = max(dist[edges[i].to], dist[u] + edges[i].weight);
                if (deg[edges[i].to] == 1)
                    q.push(edges[i].to);
            }
    }
}

void dfs(int u, int fat, int og)
{
    org[u] = og;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (!org[edges[i].to])
            dfs(edges[i].to, u, og);
}

void solve(int id, int blk)
{
    int m = 0;
    ll pt = id;
    bool flag = false;
    do
    {
        flag = false, chain[++m] = dist[pt];
        deg[pt] = 1;
        for (int i = head[pt]; i != -1; i = edges[i].nxt)
            if (deg[edges[i].to] > 1)
            {
                flag = true, pt = edges[i].to;
                chain_dist[m + 1] = chain_dist[m] + edges[i].weight;
            }
    } while (flag);
    if (m == 2)
    {
        // 2-node-loop;
        ll mx_len = 0;
        for (int i = head[pt]; i != -1; i = edges[i].nxt)
            if (edges[i].to == id)
                mx_len = max(mx_len, edges[i].weight);
        dp[blk] = max(dp[blk], dist[id] + dist[pt] + mx_len);
        return;
    }
    for (int i = head[pt]; i != -1; i = edges[i].nxt)
        if (edges[i].to == id)
        {
            chain_dist[m + 1] = chain_dist[m] + edges[i].weight;
            break;
        }
    for (int i = 1; i <= m; i++)
        chain[i + m] = chain[i], chain_dist[i + m] = chain_dist[m + 1] + chain_dist[i];
    int head = 1, tail = 1;
    q[1] = 1;
    for (int i = 2; i <= 2 * m; i++)
    {
        while (head <= tail && i - q[head] >= m)
            head++;
        dp[blk] = max(dp[blk], chain[q[head]] + chain[i] + max(chain_dist[i] - chain_dist[q[head]], chain_dist[m + 1] - (chain_dist[i] - chain_dist[q[head]])));
        while (head <= tail && chain[i] - chain_dist[i] >= chain[q[tail]] - chain_dist[q[tail]])
            tail--;
        q[++tail] = i;
    }
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int u = 1, v, w; u <= n; u++)
        scanf("%d%d", &v, &w), addpath(u, v, w), addpath(v, u, w), deg[u]++, deg[v]++;
    // done the preprocess;
    for (int i = 1; i <= n; i++)
        if (!org[i])
            dfs(i, 0, ++ccnt);
    toposort();
    // get the loop done;
    for (int i = 1; i <= n; i++)
        if (!vis[org[i]] && deg[i] > 1)
        {
            solve(i, org[i]);
            vis[org[i]] = true, ans += dp[org[i]];
        }
    printf("%lld", ans);
    return 0;
}