方程式

这个搜索好骚啊。

首先直接枚举 20 个数来搞初始根。假设我们拿到了\(s\)个根，那么我们还剩下\(n – s\)个，肯定是重根。所以我们考虑直接搜索剩下的\(n – s\)到底是哪个重根。这个复杂度就是\(\Theta(s^{n – s})\)。至于我们怎么验证解的正确性，就是这道题的精髓了：考虑把这组解写成零点式：

\[ \prod_{i = 1}^n (x – a_i) = 0 \]

我们做一个小的多项式乘法展开这个积式，然后与原式的系数进行对比即可。

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

using namespace std;

const int MAX_N = 10100;

ll seq[MAX_N], n, B[MAX_N], sol[MAX_N], cnt;

bool check()
{
    memset(B, 0, sizeof(B)), B[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j >= 1; j--)
            B[j] = B[j - 1] - B[j] * sol[i];
        B[0] = -B[0] * sol[i];
    }
    for (int i = 0; i <= n; i++)
        if (seq[i] != B[i])
            return false;
    return true;
}

void dfs(int pos)
{
    if (pos > n)
        if (check())
        {
            sort(sol + 1, sol + pos);
            for (int i = 1; i <= pos - 1; i++)
                printf("%d ", sol[i]);
            exit(0);
        }
        else
            return;
    else
        for (int i = 1; i <= cnt; i++)
        {
            sol[pos] = sol[i];
            dfs(pos + 1);
        }
}

int main()
{
    scanf("%lld", &n);
    for (int i = 0; i <= n; i++)
        scanf("%lld", &seq[i]);
    for (int i = 1; i <= 20; i++)
    {
        ll pans = 0;
        for (int j = n; j >= 0; j--)
            pans = pans * i + seq[j];
        if (pans == 0)
            sol[++cnt] = i;
    }
    dfs(cnt + 1);
    return 0;
}

树的重量

这道题有点像异象石的处理方式。对于每一条链我们都可以用多个距离来处理，然后发现最小的那个链就是我们要的结果（因为你枚举所有情况，答案必然是最小的那种）。

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

using namespace std;

const int MAX_N = 33;

int n, matrix[MAX_N][MAX_N];

int main()
{
    while (scanf("%d", &n) && n != 0)
    {
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
                scanf("%d", &matrix[i][j]), matrix[j][i] = matrix[i][j];
        ll ans = matrix[1][2];
        for (int i = 3; i <= n; i++)
        {
            ll pans = 0x3f3f3f3f3f3f3f3f;
            for (int k = 2; k <= i - 1; k++)
                pans = min(pans, 1LL * (matrix[1][i] + matrix[i][k] - matrix[k][1]) >> 1);
            ans += pans;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

小A的礼物

裸的线段树合并，开动态权值线段树就行了。（比线段树好写的多）

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

using namespace std;

const int MAX_N = 100100;

int head[MAX_N], n, current, q, tmpx, ptot, roots[MAX_N];

struct node
{
    int sum, lson, rson;
} nodes[MAX_N * 20];

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

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

int update(int qx, int l, int r)
{
    int p = ++ptot;
    nodes[p].sum = 1;
    if (l == r)
        return p;
    int mid = (l + r) >> 1;
    if (qx <= mid)
        nodes[p].lson = update(qx, l, mid);
    else
        nodes[p].rson = update(qx, mid + 1, r);
    return p;
}

int merge(int p1, int p2, int l, int r)
{
    if (p1 == 0)
        return p2;
    if (p2 == 0)
        return p1;
    if (l == r)
    {
        nodes[p1].sum = max(nodes[p1].sum, nodes[p2].sum);
        return p1;
    }
    int mid = (l + r) >> 1;
    nodes[p1].lson = merge(nodes[p1].lson, nodes[p2].lson, l, mid);
    nodes[p1].rson = merge(nodes[p1].rson, nodes[p2].rson, mid + 1, r);
    nodes[p1].sum = nodes[nodes[p1].lson].sum + nodes[nodes[p1].rson].sum;
    return p1;
}

void dfs(int u)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        dfs(edges[i].to), merge(roots[u], roots[edges[i].to], 1, 60000);
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 2, tmp; i <= n; i++)
        scanf("%d", &tmp), addpath(tmp, i);
    for (int i = 1, tmp; i <= n; i++)
        scanf("%d", &tmp), roots[i] = update(tmp, 1, 60000);
    dfs(1), scanf("%d", &q);
    while (q--)
        scanf("%d", &tmpx), printf("%d\n", nodes[roots[tmpx]].sum);
    return 0;
}

[CERC2017]Kitchen Knobs

这道题蛮有意思的。

首先容易想到的是：每一个 Knob 的最优转数是可以直接 sb 计算的。然后发现有点像积木大赛，然后我就想不到了。

真实做法是这样的：

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

using namespace std;

const int MAX_N = 510;

int n, tot;
short rot[MAX_N], bucket[10], stats[MAX_N][4], dp[MAX_N][MAX_N][MAX_N];
char opt[10];

int main()
{
    scanf("%d", &n), tot++;
    // 先计算出所有的最优转步;
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", opt);
        int now = 0;
        bool flag = false;
        for (int ptr = 0; ptr < 7; ptr++)
        {
            if (ptr > 0 && opt[ptr] != opt[ptr - 1])
                flag = true;
            int tmp = 0;
            for (int k = 0; k < 7; k++)
                tmp = tmp * 10 + opt[(ptr + k) % 7] - '0';
            if (tmp > now)
                now = tmp, rot[tot] = ptr;
        }
        if (flag)
            tot++;
    }
    // 再做差分，意义就是如果连续按下，需要多转 rot[i] 次。记录多转 rot[i] 的次数，存在 bucket[] 中。
    for (int i = tot; i >= 1; i--)
        rot[i] = (rot[i] - rot[i - 1] + 7) % 7, bucket[rot[i]]++;
    // 我们现在把这个问题差分之后，发现在 rot[i] 上做修改其实就是在对一段区间进行修改。
    // 那么我们修改就相当于这个区间转了相同的次数。如果我们要一个区间归零（转到最优），
    // 那么我们肯定就希望端点配对（1和6，2和5，3和4）。
    // 配对出来之后做背包，然后用最大空间放最小的操作代价。
    int ans = 0, x = 1, y = 2, z = 3;
    int t = min(bucket[1], bucket[6]);
    ans += t;
    if (bucket[1] -= t)
        x = 1;
    if (bucket[6] -= t)
        x = 6;

    t = min(bucket[2], bucket[5]);
    ans += t;
    if (bucket[2] -= t)
        y = 2;
    if (bucket[5] -= t)
        y = 5;

    t = min(bucket[3], bucket[4]);
    ans += t;
    if (bucket[3] -= t)
        z = 3;
    if (bucket[4] -= t)
        z = 4;

    // DP part;
    // preprocess the status;
    int stot = 0;
    for (int i = 0; i <= 7; i++)
        for (int j = 0; j <= 7; j++)
            for (int k = 0; k <= 7; k++)
                if ((i + j + k) && (i * x + j * y + k * z) % 7 == 0)
                {
                    stats[stot][0] = i, stats[stot][1] = j;
                    stats[stot][2] = k, stats[stot++][3] = i + j + k - 1;
                }
    x = bucket[x], y = bucket[y], z = bucket[z];
    for (int i = x; i >= 0; i--)
        for (int j = y; j >= 0; j--)
            for (int k = z; k >= 0; k--)
                if (x + y + z - i - j - k)
                {
                    short tmp = 0x3f3f;
                    for (int sid = 0; sid < stot; sid++)
                        if (i + stats[sid][0] <= x && j + stats[sid][1] <= y && k + stats[sid][2] <= z)
                            tmp = min(tmp, (short)(dp[i + stats[sid][0]][j + stats[sid][1]][k + stats[sid][2]] + stats[sid][3]));
                    dp[i][j][k] = tmp;
                }
    printf("%d", ans + dp[0][0][0]);
    return 0;
}

支付宝

这道题用二进制拆分一下，然后暴力往上跳状态就行了。（我一开始存下了所有的 pair，直接 GG）。

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

using namespace std;

const int MAX_N = 4020, MAX_E = 21000;

int n, m, wi[MAX_N], ci[MAX_N], tot, wi_tmp[MAX_N], ci_tmp[MAX_N], idx[MAX_N];
int dp[MAX_E], bucket[MAX_N];

int main()
{
    
    freopen("pay.in", "r", stdin);
    freopen("pay.out", "w", stdout);
    
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &wi_tmp[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ci_tmp[i]);
    scanf("%d", &m);
    for (int i = 1; i <= n; i++)
    {
        int now = 1;
        while (ci_tmp[i] >= now)
        {
            wi[++tot] = wi_tmp[i] * now, idx[tot] = i;
            ci[tot] = now, ci_tmp[i] -= now, now <<= 1;
        }
        if (ci_tmp[i])
        {
            wi[++tot] = wi_tmp[i] * ci_tmp[i];
            ci[tot] = ci_tmp[i], idx[tot] = i;
        }
    }
    memset(dp, 0x3f, sizeof(dp)), dp[0] = 0;
    for (int i = 1; i <= tot; i++)
        for (int j = m; j >= 0; j--)
            if (j >= wi[i] && dp[j] > dp[j - wi[i]] + ci[i])
                dp[j] = dp[j - wi[i]] + ci[i];
    int cur = m;
    while (cur > 0)
        for (int i = tot; i >= 1; i--)
            if (cur >= wi[i] && dp[cur] == dp[cur - wi[i]] + ci[i])
                cur -= wi[i], bucket[idx[i]] += ci[i];
    printf("%d\n", dp[m]);
    for (int i = 1; i <= n; i++)
        printf("%d ", bucket[i]);
    return 0;
}