2020-02-12 14:40 已编辑西安交通大学算法工程师

关注

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

这场比赛码量小，思维难度适中，不涉及任何高级算法，相信选手们能够顺利体会到AK AC的快乐：）

不知道由于什么原因，过了J的人都没有过I，难道是为了不AK吗？

欢迎在CF上friend出题人。

注意：B题和I题数据已加强，且B题已rejudge。

A、欧几里得

考虑如果a>b，那么gcd(a,b)转移到的gcd(b,a%b)也满足b>a%b。于是我们相当于要从次数少一的一组a,b，将b加上一个或更多个a，就变成次数加一的了。可以观察出每次加一个a是最佳的，就是斐波那契数列。找规律水平高的选手，也可以使用找规律通过此题。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930010

B、括号序列

使用栈，从左到右处理每一个括号：

如果是左括号，那么入栈，然后继续读下一个括号
如果是右括号，那么就要看这个右括号和栈顶的括号是否匹配
如果匹配，那么弹出栈顶的括号，继续读下一个括号，否则说明不合法
最后，如果栈为空，说明此括号序列是合法的。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930024

C、子段乘积

本题可以使用线段树，也可以分治，还可以使用尺取法，维护当前区间中有几个0，同时维护不是0的数字的乘积，这种方法需要使用乘法逆元。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930034

D、子段异或

如果[l,r]是合法的子段，说明前缀和中xorsum[r]^xorsum[l-1] = 0, xorsum[l-1] = xorsum[r]。
求出异或前缀和，然后使用map计数每一个数字有多少个前缀和等于那个数字即可。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930043

E、最小表达式

我们拥有的可以放数字的数位的权值分别是1,1,1,1,1,...,1,10,10,10,10,...,10,100,...（每种各加号个数加一个），于是只需要贪心的将大的数字放到小权值的数位上即可。

考虑题目中的第四个样例：23984692+238752+2+34+
这个样例的数字排序后为['2', '2', '2', '2', '2', '3', '3', '3', '4', '4', '5', '6', '7', '8', '8', '9', '9']，加号有四个，则意味着我们要建立五个数字。每个数字从后向前添加数位，则先添加个位数，十位数，再添加百位数，等等等等。并且我们一定是按照顺序添加，不可能在个位数尚有未填写的情况去填另一个数字的百位数，因为不优。答案为
2369+2359+248+248+237=5461

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930064

F、树上博弈

首先，注意到输掉的唯一方法是自己的唯一一条边有另一个人，那么自己一定是在叶子上。
令两个人之间的距离为D。请注意，每人行动后D增加1或减少1。因此，每有人走一步D的奇偶性都会改变。
假设最初，在牛牛移动之前，D是偶数。那么当牛牛移动时D将始终为偶数，而当牛妹移动时D将始终为奇数。
请注意，只要牛牛和牛妹的令牌位于相邻的节点中，D=1。因此，如果D为偶数，则他们不在相邻的单元格中，并且牛牛始终可以移动。
另一方面，由于牛牛总是可以移动，因此他可以向牛妹的方向移动，将牛妹必然会最终移动到叶子上。同样，如果最初D是奇数，则牛妹获胜。
因此，答案取决于距离的奇偶性：如果是偶数，则牛牛获胜，否则牛妹获胜。
可以发现，只有牛牛的初始位置和牛妹的初始位置距离为偶数时，牛牛获胜。只需要分别求出深度为奇数的点和深度为偶数的点的数量即可。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930091

G、音乐鉴赏

如果随机占比为 $x$ ，一个人分数为 $score$ ，那么他优秀的概率为 $\frac{(score-90)(1-x)}{90x}$ 。

这个概率可以这么计算：首先把分数减90，大于0就优秀，那么就变成 $(score-90)*(1-x)-y*x\ge 0$ ，其中y是一个随机的0到90之间的数字。 $(score-90)*(1-x)\ge y*x$ ， $\frac{(score-90)*(1-x)}{x}\ge y$ ，这个概率就是上面所写的概率。

$E=\sum_{i=1}^{n} \frac{(score_i-90)(1-x)}{90x}=0.1n$ ，解方程可知答案为 $\frac{\sum_{i=1}^n(score_i-90)}{9n+\sum_{i=1}^n(score_i-90)}$ 。

也可以使用二分求解。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930115

H、坐火车

从左向右遍历，使用树状数组维护每种颜色的该车厢左右的对数即可。

如下一个颜色是 $col_i$ ，应当先减去下一个颜色作为右边的匹配数，再加上当前颜色作为左边的匹配数，注意不要爆long long。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930143

I、匹配星星

这道题目可以使用贪心算法求解。先按照X坐标从小到大排序，然后对于每一个点

如果Z = 1，查询比他X坐标小的Y坐标最大的Z= 0的点，进行配对，如果配对成功则将那个点都从候选点中排除。
如果Z = 0，将该点加入候选点。

证明

假设最优方案中排序后 $Z = 1$ 的第 1 个没有按贪心策略匹配的点 $i$ ，在设 $i$ 在 $Z = 0$ 中它能匹配的 $y$ 最大的点为 $j$ ，如果 $j$ 被点 $k$ 匹配了，有两种情况：

原先 $i$ 没有和任何匹配，则直接去掉 $k$ 的匹配，将 $i$ 和 $j$ 匹配。
原先 $i$ 和 $m$ 匹配，则将 $k$ 改成和 $m$ 匹配，将 $i$ 和 $j$ 匹配，由于 $Y_j>Y_m$ ，这样的匹配一定是成立的。并且修改后的匹配数不会变少，因此按照该贪心策略可以得到最优解。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930163

J、二维跑步

首先观察得到所有x坐标相同的位置无论y坐标如何是等价的，然后看出每走一步，如果x坐标增加1则有3种方案，x坐标不变有1种方案，x坐标减小1就有2种方案。

枚举x坐标不变了 $i$ 次，那么就有 $n-i$ 步x坐标改变。如果有 $a$ 次x坐标增加，则知道 $x_{\text{final}} = a-((n-i)-a) = 2a-n+i$ ,那么就有

$-m \le 2a-n+i \le m \\ \lceil \frac{-m+n-i}{2} \rceil\le a \le \lfloor \frac{m+n-i}{2} \rfloor$

那么这种情况下的仅仅走路的方案数就是

$G(i) = \sum_{a = \max(\lceil \frac{-m+n-i}{2} \rceil,0) }^{\min(\lfloor \frac{m+n-i}{2} \rfloor,n-i)} C_{n-i}^{a}3^a2^{n-i-a}\\ \text{ans} = \sum_{i=0}^{n} C_n^i G(i)$

考虑这个东西怎么求呢？首先，我们设 $f(n,m) = C_n^m 3^m 2^{n-m}$ ,则显然有 $f(n,m) =2 f(n-1,m)+3f(n-1,m-1)$ ，这是由于 $C_n^m = C_{n-1}^{m}+C_{n-1}^{m-1}$ 。那么我们考虑如何做到 $O(1)$ 地从 $G(i)$ 推出 $G(i-1)$ 了：我们考虑 $2G(i)+3G(i) = 5G(i)$ ，如果错位相加，那么就能够正确的得出 $G(i-1)$ 中的大多数项，而错误的项只在区间的一边，我们只需要消除这些错误影响即可。

而我们又知道当 $G(n) = 1$ ，那么这道题就解决掉了，复杂度为 $O(n)$ 。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930188

被NTT卡过去了，早就该出1e7 QwQ。

全部评论

推荐最新楼层

与人无语

湖南师范大学 C++

我可能打错比赛了qwq

5 回复分享

发布于 2020-02-11 18:16

1907310214-王利明

广西大学 Java

逐渐发现自己脱离了基础

5 回复分享

发布于 2020-02-11 18:14

坏起来了

abc幼儿园 Erlang

每打一场都发现自己比上一场还菜😥

4 回复分享

发布于 2020-02-11 18:24

zztrans

中山大学 C++

J题题解最后一小段话：我们考虑2G(i)+3G(i)=5G(i) ，如果错位相加，那么就能够正确的得出G(i−1)中的大多数项，而错误的项只在区间的一边，我们只需要消除这些错误影响即可。请问这里有更详细的解释吗？错位相加是指啥？

2 回复分享

发布于 2020-02-12 15:53

Immortal，

河北师范大学 Java

G题题面很迷题解更迷醉了

1 回复分享

发布于 2020-02-15 21:56

newcolder

中原工学院 C++

F题 6 5 5 5 6 1 这个样例跑出来不应该是14吗？

1 回复分享

发布于 2020-02-12 20:39

牛客83135353号

浙江大学算法工程师

楼主想问一下J题算a的左边界是上取整，为什么代码里面是nlwb = max((-m+n-move+1)/2,0),不应该是nlwb = max((-m+n-move-1)/2+1,0)吗？万分感谢

1 回复分享

发布于 2020-02-12 17:19

Corsimy

华东师范大学

e题最小表达式题解没看懂有懂的可以讲一下吗？😢

1 回复分享

发布于 2020-02-11 21:45

AC_automaton

东北农业大学 C++

I题这组数据 ans应该为0吧？ 2 1 1 1 1 0 0 y坐标放入multiset查找时不能保证x<x(multiset)

点赞回复分享

发布于 2020-02-21 02:38

Kaleidoscope.

浙江大学宁波理工学院

C题，尺取加乘法逆元，用了快速幂和快速乘，但通过率为96.15%呜呜呜，求大佬指教一下应该怎么改

点赞回复分享

发布于 2020-02-13 00:03

wased

成都市实验外国语学校（西区） C++

问一下C题第35行为什么是pow-2次幂？

点赞回复分享

发布于 2020-02-12 23:27

牛客204414971号

西北工业大学算法工程师

请问匹配星星那道题 if(it!=s.begin()) 这个判断是啥意思啊看不懂

点赞回复分享

发布于 2020-02-12 19:04

找个实习真难顶

门头沟学院 Java

#include <set> #include <vector> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; struct P{ int a,b,c; bool operator < (const P &rhs) const{ return a<rhs.a; } }alp[300030]; int n; int main() { cin>>n; for(int i=0;i<n;i++) cin>>alp[i].a>>alp[i].b>>alp[i].c; sort(alp,alp+n); multiset<int> pool; multiset<int>::iterator it; int ans = 0; for(int i=0;i<n;i++){ if(alp[i].c){ it = pool.lower_bound(alp[i].b); if(it!=pool.begin()){ --it; pool.erase(it); ans+=1; } }else{ pool.insert(alp[i].b); } } cout<<ans<<endl; return 0; } I题数据还有点问题，这个代码本来不应该过的但是过了，两个x值相同的星星连在一起了。

点赞回复分享

发布于 2020-02-12 17:38

潘小蓝

天津理工大学算法工程师

楼主能解释一下H题query(r[i])-query(l[i]-1)这个查询区间是什么吗？我们输入的时候这个区间不是对颜色的限制区间吗？我们最后要得到的不是两侧匹配的个数么？万分感谢

点赞回复分享

发布于 2020-02-12 17:16

wdbkzsq

浙大宁波理工学院 Java

#include <iostream> #include <cstring> using namespace std; typedef long long ll; int mod = 998244353; template<typename T> void read(T &x){ x = 0;char ch = getchar();ll f = 1; while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();} while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f; } inline int mul(int x,int y){return 1ll*x*y%mod;} inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;} inline int sub(int x,int y){return x-y<0?x-y+mod:x-y;} inline int sq(int x){return 1ll*x*x%mod;} int pow(int a,int b){return b == 0 ? 1 : ( b&1 ? mul(a,sq(pow(a,b/2))) : sq(pow(a,b/2)));} int n,k,a[1000010]; int main(){ read(n);read(k); for(int i=1;i<=n;i++){ read(a[i]); } int ans = 0,md = 1,cnt = 0; for(int i=1;i<=k;i++){ if(a[i] == 0){ cnt++; }else{ md = mul(md,a[i]); } } for(int i=1;i+k-1<=n;i++){ if(!cnt)ans = max(ans,md); if(a[i] == 0)cnt--; else md = mul(md,pow(a[i],mod-2)); if(a[i+k] == 0)cnt++; else md = mul(md,a[i+k]); } cout<<ans<<endl; return 0; } 蒟蒻默默的问一句，为什么c题题解将int改成long long就会WA了呢

点赞回复分享

发布于 2020-02-12 15:02

殃阳仰漾

南京理工大学 C++

f题标程跑的，画出来的图是一样的结构，但是结点序号不同，标程跑出来不一样，还是说我输入的数据不合法，作者可以帮我解答一下么。

点赞回复分享

发布于 2020-02-12 14:26

潘小蓝

天津理工大学算法工程师

楼主,能解释一下F题中的这句话吗？cnt[0]*(cnt[0]-1)+cnt[1]*(cnt[1]-1)

点赞回复分享

发布于 2020-02-12 14:23

胡图图qwq

辽宁大学前端工程师

I题不用multiset直接用set也能过，建议强化数据。本来不能过的代码： #include <iostream> #include <cstring> #include <algorithm> #include <set> using namespace std; const int N = 100010; struct Point{ int x,y,z; bool operator<(const Point &a) const { if(x != a.x) return x < a.x; if(y != a.y) return y < a.y; return z < a.z; } }; int n; Point p[N]; int main() { //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); ios :: sync_with_stdio(false); cin.tie(0); cin >> n; for(int i=1;i<=n;i++) cin >> p[i].x >> p[i].y >> p[i].z; sort(p + 1,p + n + 1); reverse(p + 1,p + n + 1); set<int> s; int res = 0; for(int i=1;i<=n;i++) { int x = p[i].x; int y = p[i].y; int z = p[i].z; if(z == 1) s.insert(y); else { auto it = s.upper_bound(y); if(it != s.end()) { res ++; s.erase(it); } } } cout << res << endl; return 0; }

点赞回复分享

发布于 2020-02-12 12:22

昨晚梦见发财了

南宁师范大学护士

E还是不能ac只通过了一部分数据是怎么回事呢？？？

点赞回复分享

发布于 2020-02-12 10:50

昨晚梦见发财了

南宁师范大学护士

E题写的话，long是不是过不了？

点赞回复分享

发布于 2020-02-12 10:30