2021-08-11 12:55 北京大学 C++

关注

牛客多校第五场题解

B Boxes

题意：有 $n$ 个盒子，每个盒子中装有黑球白球概率均为 $\displaystyle \frac{1}{2}$ 。打开第 $i$ 个盒子所需代价为 $w_i$ 。现在有一个机会，使用 $c$ 的代价知晓剩余盒子中黑球个数，问使用最优策略开盒子直到直到全部盒子装球颜色情况的期望最小代价。

解法：显然询问盒子中有几个黑球这个策略一定只会用一次：第二次用的答案一定可以通过第一次询问的结果与中间新开出来的结果得到。并且越早用越好，因而在 $\sum w_i<c$ 的情况下一定是先用 $c$ 的代价去询问。

由于每个盒子黑白球概率相同，因而一定是先开权值小的盒子。按照权值排序，从小到大的开盒子。接下来考虑第 $i$ 个盒子在什么时候会打开。

记一开始的询问结果为 $x$ 。开盒子的终止条件，可以是摸到了 $x$ 个黑球，也可以是摸到了 $n-x$ 个白球——但是有一点是共同的，那就是在这个盒子之后，剩余球的颜色全部相同，要么全黑要么全白。考虑第 $i$ 个盒子，如果没有开到这个盒子，证明前面就已经停了。恰好在第 $i$ 位停止的概率为 $P(i)=\displaystyle \frac{1}{2^{n-i-1}},i<n$ ，显然最后一个盒子一定是不会开的。那么打开第 $i$ 位盒子的概率为 $\displaystyle 1-\sum_{j=1}^{i-1}P(j)=1-\frac{1}{2^{n-i}}$ 。因而期望概率为 $\displaystyle \sum_{i=1}^{n-1} w_i (1-\frac{1}{2^{n-i}})$ 。注意精度问题，使用 long double 可以通过。

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
long double w[100005], sum[100005];
int main()
{
    int n;
    long double c;
    scanf("%d%Lf", &n, &c);
    for (int i = 1; i <= n; i++)
        cin >> w[i];
    sort(w + 1, w + n + 1);
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + w[i];
    long double ans = 0, p = 1;
    for (int i = n; i >= 1;i--)
    {
        ans += (1 - p) * w[i];
        p /= 2;
    }
    printf("%.10Lf", min(ans + c, sum[n]));
    return 0;
}

C Cheating and Stealing

题意：给定 $n$ 局乒乓球赛的结果，求出当赛点为 $i \in [1,n]$ 时的比赛结果。 $n \leq 1\times 10^5$ 。

解法：容易发现，当赛点为 $x$ 时，总体局数仅 $\displaystyle O(\frac{n}{x})$ 局，根据调和级数的性质， $\displaystyle \sum_{i=1}^{n} O(\frac{n}{x})=O(n \log n)$ ，因而只要每一局能用 $O(1)$ 时间计算即可。

考虑如何快速的找到一局的结束。以第一局为例，此时赛点为 $x$ 。后面的局的分数判定可以使用前缀和将前面的局数分数挖掉。

首先找到二人达到 $x$ 分时的位置，取小者。此处可以使用桶进行存储，快速找到多少分在哪一场，与哪一场现在积累多少分。不妨令 PJ King 先拿到了 $x$ 分，在第 $y$ 场。如果此时 PJ King 在第 $y$ 场拿到的分数不足 $x-2$ 分，则本局结束。

显然此时二人分数不可能相同，并且 PJ King 领先。如果下一局还是他赢了，那么本局也结束了。否则，二人此时分数相同。那么接下来可能产生拉锯战——交错赢球，时刻平局。

引入第二个数组—— $\rm Tiebreak$ 。这个数组表示了当前一人领先的情况下该人获胜的场次。只需要一个递推即可求出该数组：

    tiebreak[n] = tiebreak[n + 1] = n + 1;
    for (int i = n - 1; i >= 1;i--)
        tiebreak[i] = a[i] == a[i + 1] ? i + 1 : tiebreak[i + 2];

那么我们现在可以快速的找到终止这种平局的位置了—— $y= {\rm Tiebreak}[y+1]$ 。因为第 $y$ 局时是平局，所以要加一。那么此时二人分数已定，本局结束，统计结果。

整体复杂度 $O(n \log n)$ 。

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const long long mod = 998244353;
int tiebreak[2000005], sumw[2000005], suml[2000005], posw[2000005], posl[2000005];
//posl是PJ King 在x分时对应场数，posw同理
char a[2000005];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n * 2;i++)
        posw[i] = posl[i] = n + 1;
    scanf("%s", a + 1);
    for (int i = 1; i <= n; i++)
    {
        sumw[i] = sumw[i - 1];
        suml[i] = suml[i - 1];
        if (a[i] == 'W')
        {
            sumw[i]++;
            posw[sumw[i]] = i;
        }
        else
        {
            suml[i]++;
            posl[suml[i]] = i;
        }
    }
    tiebreak[n] = tiebreak[n + 1] = n + 1;
    for (int i = n - 1; i >= 1;i--)
        tiebreak[i] = a[i] == a[i + 1] ? i + 1 : tiebreak[i + 2];
    long long ans = 0, x = 1;
    for (int i = 1; i <= n;i++)
    {
        int res = 0;
        int old = 0, place = 0;
        while (old < n)
        {
            int Wwin = posw[sumw[old] + i];
            int Lwin = posl[suml[old] + i];
            place = min(Wwin, Lwin);
            if(place>n)
                break;
            if (abs((sumw[place] - sumw[old]) - (suml[place] - suml[old])) >= 2)
            {
                if (sumw[place] - sumw[old] > suml[place] - suml[old])
                    res++;
                old = place;
                continue;
            }
            place++;
            if (place > n)
                break;
            if (abs((sumw[place] - sumw[old]) - (suml[place] - suml[old])) >= 2)
            {
                if (sumw[place] - sumw[old] > suml[place] - suml[old])
                    res++;
                old = place;
                continue;
            }
            place = tiebreak[place + 1];
            if(place>n)
                break;
            if (sumw[place] - sumw[old] > suml[place] - suml[old])
                res++;
            old = place;
        }
        ans = (ans + res * x % mod) % mod;
        x = x * (n + 1) % mod;
    }
    printf("%lld", ans);
    return 0;
}

D Double strings

题意：给定长度为 $n$ 与 $m$ 的两个字符串 $S,T$ ，问分别从 $S,T$ 中选出长度相同的子串 $a,b$ 且满足 $a$ 的字典序小于 $b$ 的方案数。 $n,m \leq 5\times 10^3$ 。

解法：将问题拆解成以下的几个子问题，

找到一段公共前缀
找到第一位不同的地方
找到后面任意长的等长子串

不妨令 $f_{i,j}$ 表示 $S$ 串到第 $i$ 位， $T$ 串到第 $j$ 位的公共前缀取法总数。这个转移是非常好写的：

$f_{i,j} = \begin{cases} f_{i-1,j}+f_{i,j-1}, & a_i\neq b_j \\[2ex] f_{i-1,j}+f_{i,j-1}+f_{i-1,j-1}, & a_i=b_j \end{cases}$

记 $sumf$ 为 $f$ 的二维前缀和，它表示了 $S$ 串的前 $i$ 位与 $T$ 的前 $j$ 位中取公共前缀的总方案数。则由上式与 $sumf_{i,j}=sumf_{i-1,j}+sumf_{i-1,j}-sumf_{i-1,j-1}$ 可以得到，

$sumf_{i,j} = \begin{cases} sumf_{i-1,j}+sumf_{i,j-1}-sumf_{i-1,j-1}, & a_i\neq b_j \\[2ex] sumf_{i-1,j}+sumf_{i,j-1} & a_i=b_j \end{cases}$

之后我们会用到 $sumf$ 进行答案的统计。

接下来是第三个问题。记 $g_{i,j}$ 为 $S$ 串从第 $i$ 位往后， $T$ 串从第 $j$ 位往后，满足 $a_i<b_j$ ，后面任取等长后缀的总方案数。它的计算公式为：

$g_{i,j} = \begin{cases} \dbinom{n+m-i-j}{n-i} & a_i< b_j \\[2ex] 0, & a_i \geq b_j \end{cases}$

关于其公式的得到：其本质为在 $n$ 个与 $m$ 个物品中各选取 $k$ 个物品方案的总和，即 $\displaystyle \sum_{k=1}^{\min(n,m)} \dbinom{n}{k} \dbinom{m}{k}=\dbinom{n+m}{n}$ 。此处可以使用 DP 求解，容易发现和杨辉三角的规律。

做 $g$ 的二维后缀和 $sumg$ ，表示了从 $S$ 串的后面 $i$ 位与 $T$ 串的后面 $j$ 位中选取的合法方案总和。

$sumg_{i,j} = \begin{cases} sumg_{i+1,j}+sumg_{i,j+1}-sumg_{i+1,j+1}+\dbinom{n+m-i-j}{n-i} & a_i< b_j \\[2ex] sumg_{i+1,j}+sumg_{i,j+1}-sumg_{i+1,j+1}, & a_i \geq b_j \end{cases}$

最后考虑第二步，只需要 $O(nm)$ 的枚举这样的分段点即可。当 $a_i=b_j$ 时，其方案总数为恰好在第 $i-1,j-1$ 位终止的方案数乘以其后缀的方案数，即 $f_{i,j} sumg_{i+1,j+1}$ 。

注意本题空间限制严格，不能开 long long。

总体复杂度 $O(nm)$ 。

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int mod = 1000000007;
int power(int a,int x)
{
    int ans = 1;
    while(x)
    {
        if(x&1)
            ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        x >>= 1;
    }
    return ans;
}
int inv(int x)
{
    return power(x, mod - 2);
}
int sumf[5005][5005], sumg[5005][5005];
int fac[10005], invfac[10005];
char a[5005], b[5005];
int C(int n,int m)
{
    if(m<0 || n<m)
        return 0;
    return (long long)fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}
int main()
{
    fac[0] = 1;
    for (int i = 1; i <= 10000;i++)
        fac[i] = fac[i - 1] * (long long)i % mod;
    invfac[10000] = inv(fac[10000]);
    for (int i = 9999; i >= 1;i--)
        invfac[i] = invfac[i + 1] * (long long)(i + 1) % mod;
    invfac[0] = 1;
    scanf("%s", a + 1);
    scanf("%s", b + 1);
    int n = strlen(a + 1);
    int m = strlen(b + 1);
    sumf[0][0] = 1;
    for (int i = 1; i <= n;i++)
        sumf[i][0] = 1;
    for (int i = 1; i <= m;i++)
        sumf[0][i] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i] == b[j])
                sumf[i][j] = (sumf[i - 1][j] + sumf[i][j - 1]) % mod;
            else
                sumf[i][j] = ((sumf[i - 1][j] + sumf[i][j - 1] - sumf[i - 1][j - 1]) % mod + mod) % mod;
    for (int i = n; i >= 1;i--)
        for (int j = m; j >= 1;j--)
        {
            sumg[i][j] = ((sumg[i][j + 1] + sumg[i + 1][j] - sumg[i + 1][j + 1]) % mod + mod) % mod;
            if(a[i]<b[j])
                sumg[i][j] = (sumg[i][j] + C(n + m - i - j, n - i)) % mod;
        }
    int ans = sumg[1][1];
    for (int i = 1; i <= n;i++)
        for (int j = 1; j <= m;j++)
            if(a[i]==b[j])
            {
                long long temp = (((long long)sumf[i][j] - sumf[i][j - 1] - sumf[i - 1][j] + sumf[i - 1][j - 1]) % mod + mod) % mod;
                ans = (ans + temp * sumg[i + 1][j + 1] % mod) % mod;
            }
    printf("%d", ans);
    return 0;
}

E Eert Esiwtib

题意：给定一个树，第 $i$ 个点点权为 $w_i$ ，边上有运算符与、或、异或。 $q$ 次互相独立的询问 $(d,u)$ ，该次询问中将点权修改成 $w_i +di$ ，问 $u$ 节点的子树中全部节点到 $u$ 路径上的权值按照边上给定的符号求出的权值的与、或、异或值。 $d \leq 100$ ， $n,q \leq 1\times 10^5$ 。

解法：询问虽多，但是 $d$ 很小，即本质不同的权值数不多，考虑分 $d$ 进行询问的回答，因而对整个流程执行 $100$ 次即可。

现在点的权值给定了。容易发现这是一个树形 DP， $f_{u,0/1/2}$ 表示 $u$ 的子树下全部节点到 $u$ 路径上的权值的或、与、异或值。考虑合并操作，根据 $u$ 到其儿子 $v$ 边上的符号，分三种情况。

$(u,v)$ 边符号为或。
再分三小点
A. 或值
考虑 $v$ 上 $f_{v,0}$ 的构成，可以写作：
$(w_{\alpha_1} {\rm op_{\alpha_1} }w_{\alpha_2} {\rm op_{\alpha_2} } \cdots )|(w_{\beta_1} {\rm op_{\beta_1} }w_{\beta_2} {\rm op_{\beta_2} } \cdots )|(w_{\gamma_1} {\rm op_{\gamma_1} }w_{\gamma_2} {\rm op_{\gamma_2} } \cdots ) | \cdots$
那么 $f_{u,0}$ 可以写作：
$(w_v|w_{\alpha_1} {\rm op_{\alpha_1} }w_{\alpha_2} {\rm op_{\alpha_2} } \cdots )|(w_v|w_{\beta_1} {\rm op_{\beta_1} }w_{\beta_2} {\rm op_{\beta_2} } \cdots )|(w_v|w_{\gamma_1} {\rm op_{\gamma_1} }w_{\gamma_2} {\rm op_{\gamma_2} } \cdots ) | \cdots$
但是这样分析是麻烦的，直接考虑每一位上的结果即可，下同。如果 $w_v$ 上二进制位为 $1$ ，那么无论内部这些值或出来原来是多少，现在一定都是 $1$ ；如果当前 $w_v$ 的二进制位上为 $0$ ，则直接看原来的结果。因而 $f_{u,0}=w_v|f_{v,0}$ 。注意：这只是一个子树的合并结果，因而最终结果还要或上每一个子树，下同。
B.与值
如果 $w_v$ 当前位为 $1$ ，那么每一个后代节点（即最大的大括号内）中的值全部刷成 $1$ ，当前与值中一定具有 $w_v$ 全部为 $1$ 的二进制位；如果为 $0$ ，那就看之前的结果。因而 $f_{u,1}=w_v\& f_{v,1}$ 。
C.异或值
异或值较为特殊，需要统计这一位上 $1$ 出现的次数。如果子树大小为奇数，则 $w_v$ 最后被异或了奇数次。 $w_v$ 上为 $0$ 的位显然是无所谓的，只考虑 $1$ 的情况。显然之前无论这位是否为 $1$ ，呈现在这一步的运算中的全为 $1$ ，因而当前这一位有 $1$ 的条件为子树大小为奇—— $f_{u,2}=w_v | f_{v,2}$ ；如果子树大小为为偶，则全部挖掉—— $f_{u,2}=(w_v | f_{v,2}) \oplus w_v$ 。
$(u,v)$ 符号为与
A.或值 $w_v$ 上为 $0$ 的位直接将每个括号里对应位全部刷成了 $0$ ，因而这些位或出来也是 $0$ 。如果 $w_v$ 上二进位位为 $1$ ，则得看之前的结果。因而 $f_{u,0} = w_v\& f_{v,0}$ 。
B.与值
同上，有 $1$ 的位上才可能有贡献， $f_{u,1}=w_v \& f_{v,1}$ 。
C.异或值 $w_v$ 上为 $0$ 的位直接退出讨论，剩余有 $1$ 的位上，若括号内为 $1$ 的次数为偶数次，那么现在与上之后，还是偶数次；之前为奇数次现在还是奇数次。因而 $f_{u,2} = w_v \& f_{v,2}$ 。
$(u,v)$ 符号为异或
A.或值 $w_v$ 二进制位为 $0$ 的情况非常简单，直接承接此部分；如果为 $1$ ，则最后这一位上为 $1$ 要看有没有这一位上存在 $0$ 的位——只有这种才可能出现一个 $1$ 。因而去查询 $f_{v,1}$ 来得到 $f_{u,0}$ 的结果。
B.与值
同上，如果当前 $w_v$ 这一位为 $1$ ，那么只有这一位之前全为 $0$ 这一位才可能有 $1$ 。
C.异或值
依旧分子树大小。此处可以考虑直接将 $w_v$ 从每一个括号中拆出，如果拆出来奇数次则异或，否则不动。

整体复杂度 $O(nd)$ 。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const long long inf = 0xffffffffffffffffll;
struct line
{
    int from;
    int to;
    int next;
    int op;
};
struct line que[200005];
long long w[100005], oldw[100005];
int cnt, headers[100005], siz[100005];
long long f[100005][3], old[100005][3];
void add(int from,int to,int op)
{
    cnt++;
    que[cnt].from = from;
    que[cnt].to = to;
    que[cnt].op = op;
    que[cnt].next = headers[from];
    headers[from] = cnt;
}
//考虑逐位观察影响
void dfs(int place,int father)
{
    siz[place] = 1;
    f[place][0] = 0;
    f[place][1] = inf;
    f[place][2] = 0;
    for (int i = headers[place]; i; i = que[i].next)
        if(que[i].to!=father)
        {
            dfs(que[i].to, place);
            siz[place] += siz[que[i].to];
            switch(que[i].op)
            {
                case 0:
                {
                    f[place][0] |= w[place] | f[que[i].to][0];
                    f[place][1] &= w[place] | f[que[i].to][1];
                    if (siz[que[i].to] & 1)
                        f[place][2] ^= w[place] | f[que[i].to][2];
                    else
                        f[place][2] ^= (w[place] | f[que[i].to][2]) ^ w[place];
                    break;
                }
                case 1:
                {
                    f[place][0] |= w[place] & f[que[i].to][0];
                    f[place][1] &= w[place] & f[que[i].to][1];
                    f[place][2] ^= w[place] & f[que[i].to][2];
                    break;
                }
                case 2:
                {
                    f[place][0] |= ((~w[place]) & f[que[i].to][0]) | (w[place] & (~f[que[i].to][1]));
                    f[place][1] &= ((~w[place]) & f[que[i].to][1]) | (w[place] & (~f[que[i].to][0]));
                    if (siz[que[i].to] & 1)
                        f[place][2] ^= w[place] ^ f[que[i].to][2];
                    else
                        f[place][2] ^= f[que[i].to][2];
                    break;
                }
            }
        }
    old[place][0] = f[place][0];
    old[place][1] = f[place][1];
    old[place][2] = f[place][2];
    f[place][0] |= w[place];
    f[place][1] &= w[place];
    f[place][2] ^= w[place];
    return;
}
struct node
{
    int id;
    int u;
};
vector<node> ask[100005];
long long ans[100005][3];
int main()
{
    int n, q;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n;i++)
    {
        scanf("%lld", &w[i]);
        oldw[i] = w[i];
    }
    for (int i = 1; i < n;i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, i + 1, b);
        add(i + 1, a, b);
    }
    for (int i = 1; i <= q; i++)
    {
        int u, d;
        scanf("%d%d", &d, &u);
        ask[d].push_back((node){i, u});
    }
    for (int d = 0; d <= 100;d++)
    {
        for (int i = 1; i <= n; i++)
            w[i] = oldw[i] + (long long)i * d;
        dfs(1, 0);
        for(auto i:ask[d])
            for (int j = 0; j <= 2;j++)
                ans[i.id][j] = old[i.u][j];
    }
    for (int i = 1; i <= q;i++)
    {
        for (int j = 0; j <= 2;j++)
            printf("%lld ", ans[i][j]);
        printf("\n");
    }
    return 0;
}

F Finding Points

题意：按照顺时针方向，给定一个凸多边形，求多边形中一点到各边形成的夹角最小值的最大值。

解法：最大值的最小或者最小值的最大，一律二分答案。二分出角度后，对于每条边，可以使用圆心角与圆周角的关系求出对应的轨迹圆。

已知圆周角与对应的弦，求圆。首先圆心一定在弦的中垂线上，将圆周角 $\alpha$ 变成圆心角 $2\alpha$ 或 $2\pi -2\alpha$ 。这样圆心、弦中点、线段任意一个顶点构成一直角三角形，使用三角函数即可计算。

剩下的就是求圆的交——枚举每个圆的交点与圆心，看它是否在剩下的圆中。

求两圆交点。首先将圆心纵坐标小的圆放在下部，记为 $(x,y)$ ，其半径为 $r$ 。记两圆连心线与 $x$ 轴形成的夹角为 $\alpha$ ，交点弦在下部的圆对应的圆心角为 $\beta$ ，则交点可以表示为 $(x+r\cos (\alpha + \beta),y+r \sin (\alpha + \beta))$ 与 $(x+r\cos (\alpha - \beta),y+r \sin (\alpha - \beta))$

整体复杂度 $O(n^3)$ 。

G Greater Integer, Better LCM

题意：给定三个数 $a,b,c$ ，求满足 ${\rm lcm}(a+x,b+y)=c$ 的 $(x,y)$ 的 $x+y$ 最小值。满足 $c$ 是由不超过 $100$ 个质数构成，全部次方数不超过 $18$ 。使用 int128。

解法：考虑每一个构成 $c$ 的质数 $p$ ，其次方数为 $q$ 。由于 $\rm lcm$ 的性质， $a+x$ 与 $b+y$ 中必然要有一个数在这个质因子上次方得达到 $q$ 次。此时另一个数可以不达到。

设计 DP 状态： $f[mask]$ 为 $a+x$ 满足了多少个质因子的条件（由 mask 的二进制状态表示），得到了一个数 $y\geq a$ ，记录此时最小的 $y-a=x$ 。我们只需要枚举这每一个质数的次方数即可完成这个 DP。最后还需要 $1$ 少的状态承接 $1$ 多的状态的答案。

注意到满足 $a$ 与满足 $b$ 条件是一样的。我们记录对应的 $mask$ 值与得到的乘积 $v$ ，枚举全部的这样状态，对于 $b$ 及其 $y$ ，使用 $v-b$ 得到；而 $a$ 与 $x$ 的状态，则已经记录在 DP 数组中了，只需要找到 $mask$ 的补状态即可。

总体复杂度 $O(n 2^n)$ ， $n \leq 18$ 。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const __int128_t inf = (__int128_t)1e36;
vector<pair<int, __int128_t>> dif;
int n;
void scan(__int128_t &now)
{
    char num[45];
    scanf("%s", num);
    int len = strlen(num);
    for (int i = 0; i < len;i++)
    {
        now *= 10;
        now += num[i] - 48;
    }
    return;
}
void print(__int128_t value)
{
    if(value==0)
    {
        printf("0");
        return;
    }
    vector<int> num;
    while(value)
    {
        num.push_back(value % 10);
        value /= 10;
    }
    for (int i = num.size() - 1; i >= 0;i--)
        printf("%d", num[i]);
    return;
}
__int128_t f[1 << 18], a, b, prime[20];
int times[20];
void dfs(int step,__int128_t value,int mask)
{
    if (step == n + 1)
    {
        dif.push_back(make_pair(mask, value));
        if(value>=a)
            f[mask] = min(f[mask], value - a);
        return;
    }
    for (int i = 0; i <= times[step];i++)
    {
        if(i==times[step])
            mask |= (1 << (step - 1));
        dfs(step + 1, value, mask);
        value *= prime[step];
    }
    return;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n;i++)
    {
        scan(prime[i]);
        scanf("%d", &times[i]);
    }
    scan(a);
    scan(b);
    for (int i = 0; i < (1 << n);i++)
        f[i] = inf;
    dfs(1, 1, 0);
    for (int i = 0; i < n;i++)
        for (int j = 0; j < (1 << n);j++)
            if ((j & (1 << i)) == 0)
                f[j] = min(f[j], f[j | (1 << i)]);
    __int128_t ans = inf;
    for(auto i:dif)
        if(i.second>=b)
        {
            int fora = (1 << n) - 1 - i.first;
            ans = min(ans, i.second - b + f[fora]);
        }
    print(ans);
    return 0;
}

J Jewels

题意：有 $n$ 个宝藏分别位于 $(x_i,y_i,z_i)$ 处，在第 $t$ 时所需挖掘花费为 $(x_i+y_i+z_i+tv_i)^2$ ，问最小的花费总和。 $n \leq 300$ 。

解法：很容易发现，我们只需要将每一个时刻 $t$ 和这一时刻挖掘的宝藏 $i$ 所进行匹配即可，匹配的边权就是这一时刻挖掘这一宝藏所需时间，然后使用 KM 算法即可。使用时需要将边权转成负数。

复杂度 $O(n^3)$ 。

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const long long inf = 0x3f3f3f3f3f3f3fll;
long long distance(long long x,long long y,long long z)
{
    return x * x + y * y + z * z;
}
long long dis[305][305];
long long ex_left[305], ex_right[305];
//左侧期望匹配权值、右侧期望匹配权值。
int match[305];
long long lack[305];
//右侧需要匹配到左侧的一个点所需的最小权值差。
bool left[305], right[305];
int n;
bool dfs(int now)
{
    left[now] = 1;
    for (int i = 1; i <= n;i++)
    {
        if(right[i])
            continue;
        long long gap = ex_left[now] + ex_right[i] - dis[now][i];
        if(gap==0)
        {
            right[i] = 1;
            if(!match[i] || dfs(match[i]))
            {
                match[i] = now;
                return 1;
            }
        }
        else
            lack[i] = min(lack[i], gap);
    }
    return 0;
}
long long x[305], y[305], z[305], v[305];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n;i++)
    {
        scanf("%lld%lld%lld%lld", &x[i], &y[i], &z[i], &v[i]);
        for (int j = 1; j <= n; j++)
            dis[j][i] = -distance(x[i], y[i], z[i] + v[i] * (j - 1));
    }
    for (int i = 1; i <= n;i++)
    {
        ex_left[i] = -inf;
        for (int j = 1; j <= n; j++)
            ex_left[i] = max(ex_left[i], dis[i][j]);
    }
    for (int i = 1; i <= n;i++)
    {
        for (int j = 1; j <= n;j++)
            lack[j] = inf;
        while(1)
        {
            for (int j = 1; j <= n;j++)
                left[j] = right[j] = 0;
            if(dfs(i))
                break;
            long long d = inf;
            for (int j = 1; j <= n;j++)
                if(!right[j])
                    d = min(d, lack[j]);
            for (int j = 1; j <= n;j++)
            {
                if(left[j])
                    ex_left[j] -= d;
                if(right[j])
                    ex_right[j] += d;
                else
                    lack[j] -= d;
            }
        }
    }
    long long ans = 0;
    for (int i = 1; i <= n;i++)
        ans -= dis[match[i]][i];
    printf("%lld", ans);
    return 0;
}

K King of Range

题意：给定长度为 $n$ 的序列，进行 $m$ 次询问，每次问有多少个区间其极差严格大于 $k$ 。 $n \leq 1\times 10^6$ ， $m \leq 100$ 。

解法：单次询问复杂度可以使用双指针优化到 $O(n)$ 。考虑每次右移最右边界 $r$ ，然后尽可能移动现有的左边界 $l$ 直到无法移动，那么右端点在 $r$ 对答案的贡献就是 $l$ 。这么做的合理性在于，当右端点单增时，最右左边界也是在单增的。

判定时只需要使用 $O(1)$ 的 RMQ 或者单调队列即可实现。RMQ 做法不再赘述，下面代码就是使用的 RMQ。

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int a[100005];
int minimum[100005][35], maximum[100005][35];
inline int query_maximum(int left,int right)
{
    int now = left;
    int ans = 0;
    for (int i = 16; i >= 0; i--)
    {
        if (now + (1 << i) <= right + 1)
        {
            ans = max(ans, maximum[now][i]);
            now += (1 << i);
        }
    }
    return ans;
}
inline int query_minimum(int left,int right)
{
    int now = left;
    int ans = 999999999;
    for (int i = 16; i >= 0; i--)
    {
        if (now + (1 << i) <= right + 1)
        {
            ans = min(ans, minimum[now][i]);
            now += (1 << i);
        }
    }
    return ans;
}
int main()
{
    int n, m, k;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        maximum[i][0] = minimum[i][0] = a[i];
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            minimum[i][j] = min(minimum[i][j - 1], minimum[i + (1 << (j-1))][j - 1]);
            maximum[i][j] = max(maximum[i][j - 1], maximum[i + (1 << (j-1))][j - 1]);
        }
    while(m--)
    {
        long long ans = 0;
        scanf("%d", &k);
        int left = 0, right = 0;
        for (right = 1; right <= n;right++)
        {
            while (left <= right && right <= n)
            {
                if (left && query_maximum(left, right) - query_minimum(left, right) <= k)
                {
                    left--;
                    break;
                }
                left++;
            }
            if (left && right <= n && query_maximum(left, right) - query_minimum(left, right) > k)
                ans += left;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

单调队列做法为：维护两个单调队列——一个单增一个单减，每次配合所在的 $[l,r]$ 进行插入与弹出。然后直接统计两个队首元素的差值就是极差。二者的复杂度均为 $O(nm)$ ，单次询问摊还复杂度均为 $O(n)$ 。