2020-04-12 11:58 已编辑华东师范大学 C++

关注

【题解】牛客练习赛54

A.乘积Product

$n\leq64$ ，那么 $A_i=2^i-1$ 可以用unsigned long long存，直接 $n^2$ 枚举即可。注意 $A_i\&A_j\neq (A_i\%\text{mod})\&(A_j\%\text{mod})$ 。
也可以对每个 $A_i$ 算其贡献，答案是 $\prod_{i=0}^n(2^i-1)^{n-i+1+n-i}$ 。

B.求和Summation

$0$ 到 $2^n-1$ 可以表示，有 $n$ 个位置，每个位置可以放一个球或者不放。设第一个球到 $1$ 位置的距离为 $dis$ 。对 $\text{lowbit}$ 求和就是在所有情况中， $2^{dis}$ 的和。
枚举第一个球在位置 $i$ ，那么贡献是 $2^{i-1}\times2^{n-i}=2^{n-1}$ ，所以答案就是 $n\cdot2^{n-1}+2^n$ 。
（发现能 $OEIS$ 到，也不知道怎么评价难度...~~于是只能扔到B了...~~）

$n$ 是非负整数，请特判 $n=0$ ，没有卡常的问题。

C.排序Sort

操作可以简化成，每次花费 $1$ 的代价交换相邻两个位置。
考虑 $4!$ 枚举最终的字符串中每种字符的相对位置，然后依次将每个字符换到对应位置上去。
容易想到只考虑向左的代价，向右的不计算。事实上不对，比如AGCAG，如果最终序列是AACGG，会算出 $2$ 的花费，偏小...
将 $i$ 位置的字符放到 $j$ 位置会影响 $i,j$ 之间的字符（若 $i<j$ ，则 $i+1\sim j$ 的字符位置减 $1$ ；否则会令 $j\sim i-1$ 的字符位置 $1$ ）。
先枚举放在最前面的字符，将序列中这种字符的出现位置 $p_1,p_2...$ 依次放到 $1,2...$ 位置上去，同时统计一下代价，再令 $i\sim p_i-1$ 这一段区间加 $1$ （可以把左端点直接设成 $1$ ）。这个可以直接差分，然后求一遍前缀和，再枚举下一个字符即可。
复杂度 $O(24n)$ 。

D.955

暴力的做法就是每次求出 $n$ 家店的花费，sort一下取前 $k$ 个最小的。
正解是和nth_element（或者快速排序）类似的算法。
对于当前区间 $l,r$ ，随机选取一个元素 $cost_i,\ i\in[l,r]$ 作为基准数 $base$ 。然后维护两个指针，将区间中所有小于 $base$ 的元素放到 $base$ 的左边，大于 $base$ 的元素放到 $base$ 右边。这一步可以 $O(区间长度)$ 完成。
设结束时两个指针（即 $base$ ）在 $p$ 位置。 $p$ 左边元素都小于 $base$ ， $p$ 右边的元素都大于 $base$ （可能等于，不影响答案）。
那么我们统计 $p$ 左边的元素个数 $t$ ，如果 $t\geq k$ 就递归到区间 $[l,p]$ ；否则答案加上 $p$ 左边的所有花费， $k$ -= $t$ ，递归到区间 $[p+1,r]$ 。
复杂度为 $T(n)=T(\frac n2)+O(n)=O(n)$ 。总复杂度 $O(nm)$ 。

注意nth_element中 $base$ 只有随机取才能保证不被卡掉。我造了几组数据，取mid和mid+1的应该都过不了。

E.树的直径Diameter

先考虑点不带权的情况。
一个结论：若边权为正，设两个集合 $S_1,S_2$ 的直径分别为 $a\to b,\ c\to d$ ，那么 $S_1\bigcup S_2$ 的直径一定是 $a\to b,\ c\to d,\ a\to c,\ a\to d,\ b\to c,\ b\to d$ 中的一种。
预处理 $ST$ 表，我们可以用 $RMQ\ O(1)$ 合并两个集合的直径。
考虑删掉 $k$ 条边，实际就是一棵大的子树中割掉了若干小的子树，也就是一段大的DFS序区间中扣掉了若干子区间，剩下的区间的并就是该连通块的DFS序区间。显然这些剩下的区间个数也是 $O(k)$ 的。
而一个区间的直径可以用线段树求出。那么就可以 $O(k\log n)$ 解决了。
（具体一点，DFS序区间是互不相交的。观察发现它们可以构成一棵树的形态。把区间按右端点从小到大、左端点从大到小的顺序排序，拿栈维护出这棵树，在这棵树上DFS即可求出答案）
若点带权，仍可以这样做。证明可以考虑，将每个点的点权都加上一个很大的常数 $INF$ （不会改变直径两端点），然后每个点连向一个虚点，边权为此时的点权。
因为不需要修改，线段树可以换成 $ST$ 表 $O(1)$ 查询（但是线段树也可以过，可能需要优化下常数）。
复杂度 $O(n\log n+\sum k\log k)$ 或 $O(n\log n+\sum k)$ 。

F.染色Color

首先 $1,2,\ldots,k+1$ 中必有两个数同色，而 $1,2,\ldots,k+1$ 中任意两个不同元素的和，都是集合 $S'=\{3,4,\ldots,2k,2k+1\}$ 中的元素。所以 $S'$ 是不合法的。所以有 $n\leq 2k-2$ 。
于是我们可以先猜测，对任意正整数 $a$ ， $S=\{a+1,a+2,\ldots,a+2k-2\}$ 是合法的。
考虑怎么设计染色方案。
满足和小于 $a+1$ 或大于 $a+2k-2$ 的数，可以都染同一种颜色。即满足： $i+j<a+1\ 或\ i+j>a+2k-2$ 的 $i,j$ 。不妨直接计算满足 $x+x-1<a+1\ 或\ y+y+1>a+2k-2$ 的 $x,y$ 。
分 $a$ 的奇偶性讨论：

当 $a$ 为奇数时：
$x<\frac{a+2}{2}$ ，把 $1,2,...,\frac{a+1}{2}$ 染色为 $1$ ； $y>\frac{a+2k-3}{2}$ ，把 $\frac{a+2k-1}{2},\frac{a+2k+1}{2},...,\mathbb{INF}$ 都染成 $k$ ；
把 $\frac{a+2i-1}{2}$ 染色为 $i\ (i=2,3,...,k-1)$ 。
任意两个不同的同色数的和要么 $\leq\frac{a-1}{2}+\frac{a+1}{2}=a<a+1$ ，要么 $\geq\frac{a+2k-1}{2}+\frac{a+2k+1}{2}=a+2k>a+2k-2$ ，所以这是合法的。

当 $a$ 为偶数时：
$x<\frac{a+2}{2}$ ，把 $1,2,...,\frac{a}{2}$ 染色为 $1$ ； $y>\frac{a+2k-3}{2}$ ，把 $\frac{a+2k-2}{2},\frac{a+2k}{2},...,\mathbb{INF}$ 都染成 $k$ ；
把 $\frac{a+2i-2}{2}$ 染色为 $i\ (i=2,3,...,k-1)$ 。
同上，这也是合法的。
综上， $n=2k-2$ 。

std：
A:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41771272
B:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41771280
C:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41771284
D:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41771289
E:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41771303
F:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41771323

全部评论

推荐最新楼层

Linqi05

西安电子科技大学教师

C题的答案可以考虑逆序对数。给ATCG赋值，每交换两个相邻的数，逆序对至多 -1.而目标逆序对数为0，则至少要花逆序对数的代价。而事实上存在每次交换相邻的数都让逆序对数 -1的一系列操作（先把值为1的数全部往左移，多个数为1时先移最左边的；然后移动2，以此类推），所以答案就是逆序对数。按24！种方法赋值取最小值。

1 回复分享

发布于 2019-11-16 00:18

UTU

华南农业大学 Java

大佬,你好.B题,我还是听不明白🤣

点赞回复分享

发布于 2019-11-16 18:39