2020-02-21 16:21 已编辑哈尔滨佛学院

关注

【题解】2020牛客寒假算法基础集训营第二场

2020-2-17 G 题数据已加强但未重测此前提交。

A. 做游戏

尽可能让牛牛的每次出剪刀/石头/布对应到牛可乐出布/剪刀/石头。

$\min(A,Y)+\min(B,Z)+\min(C,X)$ 。

时间复杂度 $O(1)$ 。

42841945

B. 排数字

$1$ 和 $6$ 以外不需要考虑。

要让 $616$ 子串最多一定是 $61616\dots$ ，这样后面的串可以用前面的 $6$ ，数量为 $\max(\min(\text{cnt}_6-1, \text{cnt}_1),0)$ 。（可以理解为前面一个 $6$ 后面 $16$ 循环）

时间复杂度 $O(|S|)$ 。

42857464

C. 算概率

$f_{i,j}$ 表示前 $i$ 道题做对 $j$ 道的概率

转移时考虑第 $j$ 道题是否做对，转移方程为： $f_{i,j}=f_{i-1,j}\times (1-p_i)+f_{i-1,j-1}\times p_i$
时间复杂度 $O(n^2)$ 。

42841954

D. 数三角

一个三角形的三边长 $a,b,c$ （ $c$ 最长）满足 $a^2+b^2<c^2$ （或存在两条边向量的点积 $<0$ ），则该三角形为钝角三角形。

枚举三个点判断即可，注意判断共线和不要算重。

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

42841973

E. 做计数

两边平方，得 $i+j+2\sqrt{ij}=k$ ，显然仅当 $i,j$ 都是整数且 $ij$ 为完全平方数时才会对应一个符合条件的 $k$ 。

枚举 $[1,n]$ 中所有的完全平方数（完全平方数可以表示为 $x^2$ ，只需要枚举 $x$ ），再枚举这个完全平方数的因数，统计答案。

$O(\sqrt n)$ 枚举完全平方数 $O(\sqrt n)$ 枚举因数，时间复杂度 $O(n)$ ，可以进一步优化。

42841984

F. 拿物品

假设物品已经被选完，此时牛牛选择的物品 $A$ 属性的价值和是 $N$ ，牛可乐选择的物品 $B$ 属性价值和是 $M$ 。

如果牛牛的 $(a_1,b_1)$ 物品与牛可乐的 $(a_2,b_2)$ 交换，则 $N'=N-a_1+a_2, M'=M+b_1-b_2$ ，对于牛牛（目标是最大化 $N-M$ ）来说会变得更优仅当 $a_1+b_1<a_2+b_2$ （ $N'-M'>N-M$ 化简就能得到），对于牛可乐也一样。所以两人都会优先选择 $a_i+b_i$ 最大的物品。

将物品按照两个属性的和从大到小排序，依次分给两人即可。

除排序时间复杂度 $O(n)$ 。

42842001

G.判正误

直接计算会 TLE / MLE ，考虑在模意义下进行计算，若 $a^d+b^e+c^f\equiv g \pmod M$ ，则原式有概率成立，多选择一些模数以提高正确率。

42842014

H.施魔法

先将元素按能量值排序，下文默认已排序。

可以证明存在一个最优方案，满足每个魔法一定消耗一段连续的元素。

$f_i$ 表示用掉前 $i$ 个元素的最小代价。

图片说明

维护的前缀最小值就能 $O(1)$ 转移了。

DP 过程时间复杂度 $O(n)$ 。

42842367

I.建通道

首先将权值去重（权值相等的点连接代价为 $0$ ），设去重后有 $m$ 个点，接下来找到最小的二进制位 $k$ ，满足存在 $v_i$ 的这个二进制位是 $0$ 且存在 $v_j$ 的这个二进制位是 $1$ ，答案就是 $2^k\times (m-1)$ （相当于所有这位是 $0$ 的点与 $j$ 点连边，是 $1$ 的点与 $i$ 点连边）。

排序和去重以外时间复杂度 $O(n+\log V)$ ，没有卡 $O(n\log V)$ ，好像两个 $\log$ 也过了。

42852180

J. 求函数

$f_r\left(f_{r-1}\left(\cdots\left(f_{l+1}\left(f_l(1)\right)\right)\cdots\right)\right) \\ =\prod_{i=l}^r {k_i}+\sum_{i=l}^r{b_i\prod_{j=i+1}^r{k_j}}$

注意： $i+1>r$ 时视 $\prod_{j=i+1}^r{k_j}=1$ 。

对加号左右分别用线段树维护，考虑如何合并两个相邻区间 $[l_1,r_1], [r_1+1,r_2]$
$\prod_{i=l_1}^{r_1}k_i=n_1, \prod_{i=l_2}^{r_2}k_i=n_2 \\ \sum_{i=l_1}^{r_1}{b_i\prod_{j=i+1}^r{k_j}}=m_1,\sum_{i=l_2}^{r_2}{b_i\prod_{j=i+1}^r{k_j}}=m_2$

区间 $[l_1,r_2]$ 的 $\prod k_i=n_1\times n_2$ ， $\sum{b_i\prod k_j}=m_1\times n_2+m_2$

一棵线段树维护 $\prod k_i$ ，另一棵维护 $\sum{b_i\prod k_j}$ 即可。

视 $n,m$ 同阶，时间复杂度 $O(n\log n)$ 。

42842027

C 题：不太懂为什么这么少人过。UPD：好像是因为不懂模意义下运算...emmmmmmm

D 题：使用浮点数请考虑精度问题，没 eps 说卡精度就有点那啥..。

G 题：考虑到这个题卡固定模数比卡字符串哈希轻松很多（只要让结果是模数的 lcm 即可）就卡了一些模数，有一些数据不知为何没传上去；使用 math 库中的 pow 函数可以通过，是真的没想到（由于 Yes 的数据都比较有特点，可能被编译器优化了）。以及请不要再纠结哪个模数能AC哪个不能，因为模数相比最终结果小太多，很多模数可能被卡（不管是不是刻意），应该做的是多选一些模数。

以及可能还有一些小问题影响了做题体验，这里说声抱歉

关于样例强度：没有任何义务提供强样例

~~推锅：赛时提问的回答有个别态度不好，那不是我~~

有其他问题请在评论中提出~

全部评论

推荐最新楼层

神崎兰子

牛客网_在线教育部_课程讲师

验题人前来报道，表示验题人并不会做最后3题

12 回复

发布于 2020-02-06 18:21

罗老师是我心中的神

算法工程师

C 题可以用分治 FFT做到 $O(n \log^2 n)$ https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42843674

6 回复

发布于 2020-02-06 18:47

滴滴

校招火热招聘中

官网直投

罗老师是我心中的神

算法工程师

J 只要考虑到函数的复合运算有结合率就可以直接用线段树维护那个函数了。应该和题解是一个意思。

3 回复

发布于 2020-02-06 18:32

hoi33

西京学院

多久没写代码，越来越菜了，做法都比题解复杂多了，尤其是J题没开四倍，菜死了，卡到自闭😭，C题比较好，E题最开始是题解的想法因为写错了，我以为有可能根号处理一个0.5用4ij是完全平方数写了。

2 回复

发布于 2020-02-06 18:33

horz

算法工程师

42844583蒟蒻求解答,D题为什么这样只能过50的数据????

2 回复

发布于 2020-02-06 19:20

FriedChicken

北京理工大学计算机类

J题俺是用线段树维护矩阵乘法过的，感觉会更好写一些？

1 回复

发布于 2020-02-06 18:24

苯磺酸有没有构型异构

kokodayo小学

正如您所见。初学OI爆零记

点赞回复

发布于 2020-02-06 18:43

|Crisp|

C++

int Pow(int a, int b, int c) { int ret = 1; while (b) { if (b & 1) ret = ret * 1ll * a % c; a = a * 1ll * a % c; b >>= 1; } return ret; } 您好，我想问G题，为什么这一段代码可以代替乘方，是怎么实现的呢

1 回复

发布于 2020-02-07 12:15

AsuraKing

字节跳动_后端开发工程师

问下I题，哪个题解k是用来求有多少不相同的数吗？我用set代替就过不了啊，只能过85.7%； for(int i=1;i<=n;i++){ cin>>a[i]; se.insert(a[i]); } int s1=0,s2=0x7fffffff; for(int i=1;i<=n;i++){ s1|=a[i];//找出二进制位有1的位置 s2&=a[i];//找出二进制位都为1的位置 } s2^=s1;//找出二进制位有1但不都为1的位置 ll ans; int t=se.size()-1; for(int i=0;i<=30;i++){ int c=1<<i; if(s2&c){//找出s1二进制位的为1的最小位置 ans=1ll*c*t; break; } }

1 回复

发布于 2020-02-07 13:23

高博cool

安全工程师

请问为啥G题我这样写也过了，是这个题目的数据的问题吗？ ll n1=pow(a,d); ll n2=pow(b,e); ll n3=pow(c,f);

1 回复

发布于 2020-02-07 16:12

寻开心.

东北大学电子信息类

您好，博主，您出的题很棒！我想问您G题计算a^b % m，先令 a' = (a % m + m) ，在计算a' ^ b % m 为什么是等价的啊？您能告诉我嘛

1 回复

发布于 2020-02-07 18:17