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

关注

【题解】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

horz

江西理工大学算法工程师

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

2 回复分享

发布于 2020-02-06 19:20

hoi33

西京学院算法工程师

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

2 回复分享

发布于 2020-02-06 18:33

寻开心.

东北大学后端

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

1 回复分享

发布于 2020-02-07 18:17

高博cool

曲阜师范大学安全工程师

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

1 回复分享

发布于 2020-02-07 16:12

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

|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

苯磺酸有没有构型异构

kokodayo小学

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

点赞回复分享

发布于 2020-02-06 18:43

FriedChicken

北京理工大学算法工程师

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

1 回复分享

发布于 2020-02-06 18:24

已注销

请问下A题我这样写和标称有什么区别吗，这个过不了，标程用的min 。ll sum = A>=Y?Y:A + B>=Z?Z:B + C>=X?X:C; 还有1e9为什么不开 ll 过不了

点赞回复分享

发布于 2020-12-29 19:35

无名猫儿山

门头沟学院 C++

H题中间的一些区间不会被分割到小于k吗

点赞回复分享

发布于 2020-02-21 01:29

Uncle_drew

Aston University C++

题解真的好

点赞回复分享

发布于 2020-02-13 10:36

杭州贝微微

东华大学前端工程师

f题可以维护两次牛牛是a-b 牛可乐是b-a 这样做吗？会不会太麻烦了还要标记是不是用过了

点赞回复分享

发布于 2020-02-10 21:52

猪来了

浙江外国语学院 Java

H题的状态转移方程能这样写吗

点赞回复分享

发布于 2020-02-10 19:10

千鹤大大的小板凳

河南工业大学算法工程师

哈哈哈菜鸡前天还在埋怨样例给的不好，今天就被解释给酷到了~

点赞回复分享

发布于 2020-02-08 13:53

Nivke

门头沟学院算法工程师

请问大神，G题判正误为什么一定要对a,b,c用ff函数处理一下呢

点赞回复分享

发布于 2020-02-07 16:09

酸酸jason

东南大学 Java

请问一下 I题 for(inti = 1; i <= n; i++) { va &= v[i]; vo |= v[i]; } va^=vo；再用求得的va找到最小满足的lowbit位这里为什么可以这样求得va呢没有太理解

点赞回复分享

发布于 2020-02-07 14:48

哈尔滨理工大学-李佳奇

哈尔滨理工大学 C++

请问为何统计不重复元素个数的时候，这样写就错了。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int maxn = 2e5 + 5; #define lowbit(x) (x)&(-x) int a[maxn]; int main() { ios; int n; cin >> n; ll ans; for (int i = 0; i < n; ++i) cin >> a[i]; sort(a, a + n); // int tot = unique(a, a + n) - a; int v1 = 0, v0 = 0x7fffffff; for (int i = 0; i < n; ++i) { v1 |= a[i]; v0 &= a[i]; } /*int tot = 0; for (int i = n - 1; i >= 0; --i) tot += (a[i] != a[i + 1]);*/ int tot = unique(a, a + n) - a; // 这里--------------为啥这么写错了 // int k = lowbit(v1 ^ v0); for (int i = 0; i <= 30; ++i) { int cur = 1 << i; if (cur & (v1 ^ v0)) { ans = 1LL * cur * (tot - 1); //这里------为何在这里输出ans就错了，放在最后才能ac break; } } cout << ans << endl; }

点赞回复分享

发布于 2020-02-07 14:15