A – 完全背包

这道题真的是令人窒息，也告诉了我比赛的时候上 QQ 是一个非常坏的习惯。

这道题 60 分做法非常之显然：相同体积的物品归为一种物品，且价值为同体积内最大的价值。这样就可以把物品数量压到 100 个以内。

但是这样是通过不了全部分数的，而且全部分数的容量非常之大，所以正常的 DP 优化是行不通的。做完上面的压缩之后，可以考虑做一些贪心进行优化。接下来我会详细的介绍这个贪心策略：

引理 1  给定任意的\(n\)个正整数，其中一定存在一个子集，其和为\(n\)的倍数。

证明  考虑设置前缀和：\[ S_i = \sum_{j = 1}^i a_j \]之后会发现，这个前缀和两两之间并不相同。考虑对\(S_i\)进行取模，然后有两种情况：

• 如果存在两个\(S\)取模后的值相等，那么其差值取模之后的值就是\(0\)，也就为\(n\)的倍数。
• 如果不存在两个\(S\)取模后的值相等，那么一定存在取模后为\(0\)的前缀和，那么也为\(n\)的倍数。

证毕。

 

策略  对于一个性价比（\(rate_i = \frac{b_i}{a_i}\)）最高的物品\(i\)，剩下的\(x\)件物品，如果\(a_i \leq x\)时，肯定用\(a_i\)来替换掉\(x\)会更优。这是因为，\(a_i \leq x\)时，\(x\)件物品的组合一定会出现\(a_i\)的倍数，然后我们完全可以用性价比更高的物品\(i\)来替代掉这些组合获得更优的答案。我们用这个策略替代掉这些组合之后（可以换掉很多空间），我们就可以把剩下的空间搞出来进行暴力的完全背包就行。

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

using namespace std;

const int MAX_N = 1e6 + 200;

ll n, m;
int volumes[MAX_N], weights[MAX_N], wgt[110];
int upper_tot, max_rate = 0, dp[2][MAX_N];
long double rate[110];

int main()
{
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &volumes[i], &weights[i]);
        wgt[volumes[i]] = max(wgt[volumes[i]], weights[i]);
        upper_tot = max(upper_tot, volumes[i]);
    }
    for (int i = 1; i <= upper_tot; i++)
    {
        rate[i] = (long double)wgt[i] / i;
        if (rate[i] > rate[max_rate])
            max_rate = i;
    }
    ll minus_part = m / max_rate - 100, answer = 0;
    if (minus_part > 0)
        m -= minus_part * max_rate, answer += wgt[max_rate] * minus_part;
    for (int i = 1; i <= upper_tot; i++)
        for (int j = 0; j <= m; j++)
        {
            dp[i & 1][j] = dp[(i - 1) & 1][j];
            if (j >= i)
                dp[i & 1][j] = max(dp[i & 1][j], dp[i & 1][j - i] + wgt[i]);
        }
    printf("%lld", dp[upper_tot & 1][m] + answer);
    return 0;
}

B – 中间值

这道题真的是分治板题（但是我分治是真的菜，根本不会写，还是需要进行加强啊）。

这道题保证了两个序列都是上升的，那么我们可以考虑做个分治来进行寻找。我们初始是寻找\(a[l_1 \dots r_1], b[l_2 \dots r_2]\)拼起来之后第\(k = \lfloor \frac{length}{2} \rfloor + 1\)个数。我们可以将\(k\)折半之后各放在这两个区间之中，假设为\(s, t\)。如果\(a_s > b_t\)，就知道\(\{b_i\}\)中后半部分就是没用的部分了，亦而反之。大概就这样写写。

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

using namespace std;

const int MAX_N = 5e5 + 200;

int ai[MAX_N], bi[MAX_N], n, m;

namespace IO
{
const int MAXSIZE = 1 << 20;
char buf[MAXSIZE], *p1, *p2;
#define gc()                                                                 \
    (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) \
         ? EOF                                                               \
         : *p1++)
inline int rd()
{
    int x = 0, f = 1;
    char c = gc();
    while (!isdigit(c))
    {
        if (c == '-')
            f = -1;
        c = gc();
    }
    while (isdigit(c))
        x = x * 10 + (c ^ 48), c = gc();
    return x * f;
}
char pbuf[1 << 20], *pp = pbuf;
inline void push(const char &c)
{
    if (pp - pbuf == 1 << 20)
        fwrite(pbuf, 1, 1 << 20, stdout), pp = pbuf;
    *pp++ = c;
}
inline void write(int x)
{
    static int sta[35];
    int top = 0;
    do
    {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top)
        push(sta[--top] + '0');
}
} // namespace IO

inline void solve(int l1, int r1, int l2, int r2, int k)
{
    if (k == 1)
    {
        if (l1 > r1)
            printf("%d\n", bi[l2]);
        else if (l2 > r2)
            printf("%d\n", ai[l1]);
        else
            printf("%d\n", min(ai[l1], bi[l2]));
        return;
    }
    int s = l1 + (k >> 1) - 1, t = l2 + (k >> 1) - 1;
    if (s > r1)
        s = n + 1;
    if (t > r2)
        t = n + 1;
    if (ai[s] > bi[t])
        solve(l1, r1, l2 + (k >> 1), r2, k - (k >> 1));
    else
        solve(l1 + (k >> 1), r1, l2, r2, k - (k >> 1));
}

using namespace IO;

int main()
{
	freopen("median.in", "r", stdin);
	freopen("median.out", "w", stdout);
    n = rd(), m = rd();
    // scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i++)
        // scanf("%d", &ai[i]);
        ai[i] = rd();
    for (int i = 1; i <= n; i++)
        // scanf("%d", &bi[i]);
        bi[i] = rd();
    ai[n + 1] = bi[n + 1] = 0x3f3f3f3f;
    while (m--)
    {
        int opt, x, y, z, l1, l2, r1, r2;
        // scanf("%d", &opt);
        opt = rd();
        if (opt == 1)
            x = rd(), y = rd(), z = rd(), ((x == 0) ? ai[y] : bi[y]) = z;
        else
            l1 = rd(), r1 = rd(), l2 = rd(), r2 = rd(), solve(l1, r1, l2, r2, (((r1 - l1 + 1) + (r2 - l2 + 1)) >> 1) + 1);
    }
    return 0;
}

C – Sequence

真你妈的毒瘤。

首先，\(f(x)\)显然是个积性函数，所以我们只需要知道如何计算素数幂的情况（形如\(p^k\)）就行了。（这应该算是一种套路）

\(f(x)\)中包含了连续的\(gcd\)，分解之后发现其实就是在做每一个素数指数的最小值，且题目给出了\(B\)，所以最后肯定所有的指数的上界就是\(B\)中对应素因子的指数。

所以就是说，我们定\(p\)为其中的一个素数，定\(d\)为\(B\)中\(p\)的最大指数，也就是最大的\(p^d | B\)，有：

\[ f(p_c) = \begin{cases} p_d(c – d + 1)^n + \sum_{i = 0}^{d – 1} [(c – i + 1)^n – (c – i)^1], c > d \\ \sum_{i = 0}^c p^i[(c – i + 1)^n – (c – i)^n], c \leq d \end{cases} \]

然后在线性筛的时候记录一些信息就行了。

// C.cpp
#include <bits/stdc++.h>
#define pr pair<int, int>
typedef long long ll;

using namespace std;

const int MAX_N = 2e7 + 200, mod = 998244353;

ll n, m, B;
int fi[MAX_N], prime[MAX_N], tot, pows[105], min_prime[MAX_N];
pr g[MAX_N];

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

void sieve()
{
    for (int i = 2; i <= m; i++)
    {
        if (!min_prime[i])
            prime[++tot] = min_prime[i] = g[i].second = i, g[i].first = 1;
        for (int j = 1; j <= tot && 1LL * i * prime[j] <= m; j++)
        {
            int tmp = prime[j] * i;
            g[tmp].first = 1, g[tmp].second = min_prime[tmp] = prime[j];
            if (i % prime[j] == 0)
            {
                g[tmp].first += g[i].first, g[tmp].second *= g[i].second;
                break;
            }
        }
    }
}

int main()
{
	freopen("sequence.in", "r", stdin);
	freopen("sequence.out", "w", stdout);
    scanf("%lld%lld%lld", &n, &m, &B);
    sieve();
    for (int i = 0; i <= 100; i++)
        pows[i] = quick_pow(i, n % (mod - 1));
    fi[1] = 1;
    for (int i = 2; i <= m; i++)
        if (g[i].second == i)
        {
            for (int j = 0, tmp = 1; j <= g[i].first; j++)
            {
                fi[i] = (1LL * fi[i] + 1LL * tmp * (1LL * pows[g[i].first - j + 1] - 1LL * pows[g[i].first - j] + mod) % mod) % mod;
                if ((B / tmp) % min_prime[i] == 0)
                    tmp *= min_prime[i];
            }
        }
        else
            fi[i] = 1LL * fi[i / g[i].second] * fi[g[i].second] % mod;
    for (int i = 1; i <= m; i++)
        fi[i] = (1LL * fi[i] + 1LL * fi[i - 1]) % mod;
    printf("%d\n", fi[m]);
    return 0;
}