2021 软件学院 ACM 集训队筛选赛 - 题解

比赛已经结束,封榜状态已经解除,评测信息已经恢复可见,重现赛已开。感谢大家的参与!

正赛 重现 出题与验题 题解
内网 / 外网 内网 / 外网 ponyinchina bobby285271

A. 可莉的蹦蹦炸弹

考虑倍增思想,用 dp_{i,j} 表示从 i 出发跳 2^j 次到达的位置的编号,则可用各个位置出发跳 2^{j-1} 步到达的位置推出各个位置出发跳 2^{j} 步到达的位置 :

dp_{i,0}=a_i \\ dp_{i,j} = dp_{dp_{i,j - 1},j - 1}

由于 n \leq 2 \times 10^5 ,对于任何给定的数据,跳的次数都不会超过 2^{20} 次。

for (int j = 1; j <= 20; j++)
{
    for (int i = 2; i <= n; i++)
    {
        dp[i][j] = dp[dp[i][j - 1]][j - 1];
    }
}

不妨将问题转化为从 r 出发最多能跳多少次使得最终到达的位置仍然大于 l ,注意到对于任何大于 l 的位置 x ,如果 dp_{x,0}>l ,则显然必定存在唯一的非负整数 y 使得 dp_{x,y+1} \leq ldp_{x,y} > l 。同理对于位置 dp_{x,y} 如果满足 dp_{dp_{x,y},0}>l ,则必定存在唯一的非负整数 z 使得 dp_{dp_{x,y},z+1} \leq ldp_{dp_{x,y},z} > l 。用反证法可以证明 y>z ,那么我们就可以从大到小枚举这个『唯一的非负整数』的值,假设当前枚举到的值为 j ,如果 dp_{r,j} > l 我们就可以直接跳 2^j 步,这是因为根据前面的结论,剩余可以跳的步数必定小于 2^j

for (int j = 20; j >= 0; j--)
{
    if (dp[r][j] > l)
    {
        r = dp[r][j];
        ans += (1 << j);
    }
}

注意转化后的问题和原问题答案会相差 1 ,输出答案时候记得加上。

B. 阿贝多的拼图

改编自 2020 ICPC 银川站 Let’s Play Jigsaw Puzzles。根据题目我们得到的信息是一个未知编号拼图块的上下左右方位拼图块的编号。由于编号未知的拼图块不好处理,我们从已知编号的拼图块着手,注意到给定的信息可以转换为一个已知编号拼图块的左上 / 右上 / 左下 / 右下方位拼图块的编号,因此我们开一个 N^2 \times 4 的二维数组,第一维为拼图块编号,第二维 0 表示左上角, 1 表示右上角, 2 表示右下角, 3 表示左下角,也就是这样存储拼图块的信息:

for (int i = 0; i < n * n; i++)
{
    cin >> a >> b >> c >> d;
    if (a)
    {
        p[a][2] = d; // a 的右下角是 d
        p[a][3] = c; // a 的左下角是 c
    }
    if (b)
    {
        p[b][0] = c; // b 的左上角是 c
        p[b][1] = d; // b 的右上角是 d
    }
    // TODO: c 和 d 同理
}

n=1 答案显然,可直接特判处理。当 n>1 ,我们根据上面所述认为每个拼图块都和它的左上 / 右上 / 左下 / 右下的拼图块连通,那么整个拼图中就有两个连通块。两个连通块我们只需要各知道其中一个拼图块的编号就可以使用 DFS 知道同一连通块其他拼图块的编号:

int dx[] = {-1, -1, 1, 1};
int dy[] = {-1, 1, 1, -1};

void dfs(int ind, int x, int y)
{
    ans[x][y] = ind;
    for (int i = 0; i < 4; i++)
    {
        if (p[ind][i] != 0)
        {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (!ans[xx][yy])
            {
                dfs(p[ind][i], xx, yy);
            }
        }
    }
}

现在的问题就转化为了找到两块属于不同连通块的拼图块,显然坐标 (1,1) 和坐标 (2,1) 的两块拼图块就满足条件,要得知他们的编号,可以借助边界的信息:对于位于 (1,1) 的拼图块,其左上角、左下角、右上角拼图块编号都为 0 (也就是边界);对于位于 (2,1) 的拼图块,其左上角、左下角,以及右上角的右上角的拼图块编号都为 0 。我们可以根据这些信息,枚举所有拼图块并找到符合条件的拼图块进行放置,随后开始 DFS。

for (int i = 1; i <= n * n; i++)
{
    if (p[i][0] == 0 && p[i][1] == 0 && p[i][3] == 0)
    {
        dfs(i, 1, 1);
    }
    if (p[i][0] == 0 && p[i][3] == 0 && p[i][1] != 0 && p[p[i][1]][1] == 0)
    {
        dfs(i, 2, 1);
    }
}

输入量达到了 4 \times 10^6 ,注意使用较为高效的输入输出方式。

C. 凝光的游戏

改编自 2020 ICPC 上海站 Mine Sweeper II。既然没有颜色的点会显示一个数字,表明与其相连的点中有多少个是有颜色的,我们也可以假设有颜色的点也会显示一个数字,表明与其相连的点中有多少个是没有颜色的。我们在统计这些显示的数字的时候可以发现,每当一个没有颜色的点显示的数字加 1 ,必有另外一个有颜色的点显示的数字加 1 ,这是因为数字加 1 意味着存在一条边,边的两个端点颜色不同。那么我们就可以得出结论,无论边的分布如何,将所有有颜色的点显示的值相加,必定等于将所有没有颜色的点显示的值相加。由于将 Y 图中每个点修改成跟 X 相同的颜色,跟将 Y 图中每个点修改成跟 X 相反的颜色两种操作中,必定至少有一种需要的操作数小于等于 \lfloor \frac{n}{2} \rfloor 且两种方式操作数之和必定等于 n ,统计任意一种方式所需的操作数即可得到满足题意的策略。

for (int i = 1; i <= n; i++)
{
    cnt += (x[i] != y[i]);
}
if (cnt > n / 2)
{
    cout << n - cnt << '\n';
    for (int i = 1; i <= n; i++)
    {
        // 将 Y 图中每个点修改成跟 X 相反的颜色
        if (x[i] == y[i])
        {
            cout << i << '\n';
        }
    }
}
else
{
    // TODO: 执行另一种操作
}

D. 罗莎莉亚的伐木工作

改编自 Codeforces 1519E。这道题的结论是:对于一个有 m 条边的连通图,我们可以匹配 \lfloor{m\over 2}\rfloor 组边,即最多只有一条边剩余。我们使用邻接表存图,对于每个节点记录其所有子结点以及连向子结点的边的编号。接下来我们尝试使用归纳法前面的结论,对这张图跑 DFS,假设我当前所在的节点为 vv 有子节点 G_v=\{u_1,u_2,...\}u_i 的『子树』中可能会剩余一条未匹配的边,这条边其中一个端点是 u_i ,那就将 \langle v,u_i\rangle 与这条边匹配,否则不进行处理。

int dfs(int v)
{
    used[v] = 1; // 0 未被使用,1 正在使用,2 使用完毕
    for (auto it : G[v])
    {
        int u = it.x;     // v 的子结点的编号
        int i = it.y;     // 『由 v 连向 u 的边』的编号
        int nw = i;

        if (used[u] == 1) // 用于避免『由 v 连向父节点的边』发起配对
            continue;
        if (!used[u])
        {
            int tmp = dfs(u); // u 的『子树』中可能会剩余一条未匹配的边
            if (tmp != -1)
            {
                ans.push_back({nw, tmp}); // 『由 v 连向 u 的边』跟上面的『剩余的一条未匹配的边』配对
                nw = -1;
            }
        }
        // TODO: 请接着看下文
    }
    used[v] = 2;
    // TODO: 返回 v 的『子树』中剩余的一条未匹配的边,或者返回 -1 表示没有
}

经过上面的操作,所有 v 的子节点都完全匹配了,也就是 u_1,u_2,... 这些点的『子树』中的边都配对好了。我们只看 v 这个点的『子树』,可以发现剩下没配对边都以 v 作为公共端点,两两匹配即可。显然最多剩一条边,并且其中一个端点是 x ,那么我们的归纳就成立了。

int dfs(int v)
{
    used[v] = 1; // 0 未被使用,1 正在使用,2 使用完毕
    int cur = -1;
    for (auto it : G[v])
    {
        int u = it.x; // v 的子结点的编号
        int i = it.y; // 『由 v 连向 u 的边』的编号
        int nw = i;

        // TODO:『由 v 连向 u 的边』跟 u 的『子树』中的『剩余的一条未匹配的边』配对
        //       如果配对成功了将 nw 更新为 -1(上文已经实现了这部分)

        if (nw != -1) // 配对失败,意味着有一条『由 v 连向 u 的边』目前等候配对
        {
            if (cur != -1) // 看看有没有另外的等候配对的『由 v 连向 u' 的边』边
            {
                ans.push_back({cur, nw});
                cur = -1;
            }
            else
            {
                cur = nw;
            }
        }
    }
    used[v] = 2;
    return cur;
}

E. 重云的阵法图

见 CEOI2008 Knights。

F. 刻晴的每日精进

一般评测机每秒运算次数不会超过 10^9 ,直接线性递推会超时。考虑矩阵快速幂,由于当 i>3f(i)=2 \cdot f(i−1)+f(i−2)−f(i−3) ,即每项都由它的前三项 f(i-1),f(i-2),f(i-3) 得出,我们可以将这些信息放入矩阵,并试推导一个矩阵 \text{base} ,使得:

\left[\begin{array}{ccc}f(i-1) & f(i-2) & f(i-3) \end{array}\right] \times \text{base} = \left[ \begin{array}{ccc} f(i) & f(i-1) & f(i-2)\end{array}\right]

不难发现 \text{base}3 \times 3 的矩阵,还是因为当 i>3f(i)=2 \cdot f(i−1)+f(i−2)−f(i−3) ,为了得出 f(i) ,矩阵的第一列应该是 \left[\begin{array}{ccc} 2 \\ 1 \\ {-1} \end{array}\right] ,即取递推式各项系数。同理为了得出 f(i-1) ,矩阵第二列应该是 \left[\begin{array}{ccc} 1 \\ 0 \\ 0 \end{array}\right] ,同理为了得出 f(i-2) ,矩阵的第三列应该是 \left[\begin{array}{ccc} 0 \\ 1 \\ 0 \end{array}\right] ,建议结合矩阵乘法计算过程理解推导过程,不记得矩阵乘法怎么算的可百度可翻书也可看下面的代码:

struct Matrix
{
    ll a[5][5];
    Matrix() { memset(a, 0, sizeof a); }
    Matrix operator*(const Matrix &b) const
    {
        Matrix res;
        for (int i = 1; i <= 3; i++)
        {
            for (int j = 1; j <= 3; j++)
            {
                for (int k = 1; k <= 3; k++)
                {
                    res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]) % mod;
                }
            }
        }
        return res;
    }
} ans, base;

现在原式化为:

\left[\begin{array}{ccc}f(i-1) & f(i-2) & f(i-3) \end{array}\right] \times \left[\begin{array}{ccc} 2 & 1 & 0 \\ 1 & 0 & 1 \\ -1 & 0 & 0 \end{array}\right] = \left[ \begin{array}{ccc} f(i) & f(i-1) & f(i-2)\end{array}\right]

不难从递推式得出通项公式,即当 i>3 时有:

\left[\begin{array}{ccc}f(3) & f(2) & f(1) \end{array}\right] \times \left[\begin{array}{ccc} 2 & 1 & 0 \\ 1 & 0 & 1 \\ -1 & 0 & 0 \end{array}\right]^{i-3} = \left[ \begin{array}{ccc} f(i) & f(i-1) & f(i-2)\end{array}\right]

对于 \left[\begin{array}{ccc} 2 & 1 & 0 \\ 1 & 0 & 1 \\ -1 & 0 & 0 \end{array}\right]^{i-3} 这一部分我们可以使用矩阵快速幂处理。

void qpow(ll b)
{
    while (b)
    {
        if (b & 1)
            ans = ans * base;
        base = base * base;
        b >>= 1;
    }
}

特别注意的是答案要对 10^9+7 取模,需对矩阵中的负数进行处理,由于 -1\equiv m-1 \pmod m ,将矩阵中的 -1 替换为 10^9+6 在模 10^9+7 意义下不影响计算结果。

ans.a[1][1] = ans.a[1][2] = ans.a[1][3] = 1;
base.a[1][2] = base.a[2][1] = base.a[2][3] = 1;
base.a[1][1] = 2;
base.a[3][1] = mod - 1;

其它需要注意的地方包括当给定的 a_i 小于等于 3 时直接输出 1 以及由于是多组数据记得清空数组。

G. 丘丘人的数学题

唯一的签到题。因为 N \leq 10^{18},a \geq 0 ,为了保证 c \geq 0 ,当 b \geq 60 时,因为 2^b > 10^{18}a 只能等于 0 ,此时 c=Na+b+c \geq N + 60 。由于 a'=1,b'=0,c'=N-1 同样满足题意且 a'+b'+c'=N ,因此对于给定的 Nb \geq 60 时总是无法取到最优解。

既然 0 \leq b <60 ,我们就可以枚举 b 的值。由带余除法的性质,我们知道对于一个确定的 b ,当 a= \lfloor \frac{N}{2^b} \rfloora+b+c 取到最小值。或者如果你不想听人话的话,就是因为当 a> \lfloor \frac{N}{2^b} \rfloor 时, c<0 不符合题意;现假设有非负整数 ka= \lfloor \frac{N}{2^b} \rfloor -k ,则 c= N +2^b \times (k- \lfloor \frac{N}{2^b} \rfloor ) ,有 a+b+c =(2^b-1) \times k +N -2^b \times \lfloor \frac{N}{2^b} \rfloor + \lfloor \frac{N}{2^b} \rfloor +b 。把这个式子看作关于关于 k 的一次函数, Nb 都看作常数,由于 k 必须是非负整数,显然是当 k=0a+b+c 取到最小。

还是那句话,比赛时当然不用像上面这样推,只需要注意到 b 可以枚举,结合带余除法的性质把 a,c 算出来取最小就行了;枚举 b 的时候注意一下 2^b 不要溢出,推出来对应的 a,c 不放心的就检验一下看看能不能算出 N ,是不是非负的,应该也没啥坑。

H. 迪奥娜的调酒配方

改编自 2019 ICPC 沈阳站 Flowers。考虑二分调制酒的数量,则问题转化为给定正整数 x ,问题目中的调料能否调制 x 杯酒。

注意到当固定了酒的数量为 x 之后,每种调料最多只能取 \min(a_i,x) 份,否则(当取用份数超出 a_i 时)会出现调料不够用的情况或(当取用份数超出 x 时)根据抽屉原理至少会有一杯酒出现两份或以上同种调料。同时我们发现每种调料恰好取 \min(a_i,x) 份必定存在分法使得每种调料只放一份量,简单来说就是由于 \min(a_i,x) \leq x ,我们可以将所有的 \sum_{i=1}^{n} \min(a_i,x) 份调料以调料类别为排序关键字排好队,即按调料类别对应的数量递减排列,在队伍中第 q 份调料就放在第 q \bmod x + 1 杯酒中。这种分配方式可以保证拥有最多调料的酒调料数量跟拥有最少调料的酒调料数量相差不超过 1 。接下来问题就简单了,只需要计算 \lfloor \frac{\sum_{i=1}^{n} \min(a_i,x)}{x} \rfloor 即拥有最少调料的酒调料数量是否大于等于 m 即可。

bool check(ll x)
{
    ll s = 0;
    for (int i = 0; i < n; i++)
    {
        s += min(a[i], x);
    }
    return s / x >= m;
}

注意如果判断条件写成 s \geq x \times m 可能会爆 long long。题目数据允许 O(n\log n) 解法通过,但是由于输入量达到了前所未有的 10^7 ,需要使用快读读入。如果你不希望被卡输入,注意到题目中的 a_i 是升序排列的,可以对 a 进行前缀和处理,在计算上面代码中的 s 时,可以直接二分找到从何开始 a_i > x ,从而将查询答案的时间复杂度降为 O(\log ^2n) ,注意读入和前缀和的复杂度依然是 O(n) 的。

此外还有 O(m) 时间复杂度的贪心做法:

首先,以下的讨论的前提是调料种类数 n \geq m ,如果小于 m 的话根据题意可以直接输出0即可。

首先忽视每杯酒的调料的种类要互不相同的规则,直接求最多能调多少被酒的话,酒的数量就是调料的份量数的和除以每杯酒的可放的调料数,设调料的份量数的和为 sum 的话,此时答案就是 sum/m 。然后根据上文提到过的 “必定存在分法使得每种调料只放一份量” 相关的证明,可以发现,当数量最多的那种调料的数量小于等于 sum/m 时,就能用那种分法且满足每杯酒调料的种类互不相同,那么此时贪心的正确性得证。又因为在忽视规则的情况下, sum/m 本来就是可以达到的最多的酒的数量,所以贪心的最优性也得证。所以我们就证明了:当数量最多的那种调料的数量小于等于 sum/m 时,答案就是 sum/m

然后我们继续讨论当数量最多的那种调料的数量大于 sum/m 的情况。此时,因为数量最多的那种调料由于抽屉原理,其对答案的贡献没这么大了,那我们不妨就先将它忽略掉。我们设一个新的变量 sum^{\prime} ,表示调料的份量数的和减去数量最多的那种调料后的数量。那么根据刚刚提到过的证明,易类推出当数量次多的那种调料的数量小于等于 sum^{\prime}/(m-1) 时,就有分法满足每杯酒调料的种类互不相同,且这 sum^{\prime}/(m-1) 是在忽略数量最多的那种调料时的最优答案。那么再考虑上数量最多的那种调料呢?由于抽屉原理,它不可能在不违反调料种类互不相同的情况下对答案做更多的贡献。那么此时这种情况的贪心的正确性和最优性也得证了。

而在数量次多的那种调料的数量大于 sum^{\prime}/(m-1) 时,也可以以此类推,得出对应的答案。这种递推最多进行 m 次,那么时间复杂度就是 O(m) 。核心代码如下:

while(sum/m<a[suf])
{
    sum-=a[suf];
    suf--;
    m--;
}
return sum/m;
4 个赞