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。

全部评论

推荐最新楼层

1907310214-王利明

广西大学计算机类

逐渐发现自己脱离了基础

送花回复

发布于 2020-02-11 18:14

与人无语

C++

我可能打错比赛了qwq

送花回复

发布于 2020-02-11 18:16

秋招专场

校招火热招聘中

官网直投

坏起来了

Erlang

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

送花回复

发布于 2020-02-11 18:24

zztrans

中山大学计算机类

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

送花回复

发布于 2020-02-12 15:53

Corsimy

华东师范大学

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

送花回复

发布于 2020-02-11 21:45

牛客83135353号

浙江大学

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

送花回复

发布于 2020-02-12 17:19

newcolder

Java

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

送花回复

发布于 2020-02-12 20:39

Immortal，

Java

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

送花回复

发布于 2020-02-15 21:56

瑜画

C++

#include <iostream> #include <cstdio> long long mod=998244353; using namespace std; long long n, k; long long number[200100],s,ans=0; struct node { long long l, r, v; node() { l = r = v = 0; } }a[800010]; void update(int k) { a[k].v= a[k * 2].v %mod* a[k * 2 + 1].v % mod; } void build(int k, int l, int r) { a[k].l = l, a[k].r = r; if (l == r) { a[k].v = number[l]; return; } int mid = (l + r) / 2; build(k * 2, l, mid); build(k * 2 + 1, mid + 1, r); update(k); } int query(int k,int l,int r) { if(a[k].l==l&&a[k].r==r) return a[k].v; int mid=(a[k].l+a[k].r)/2; if(r<=mid) return query(k*2,l,r); if(l>mid) return query(k*2+1,l,r); return query(k*2,l,mid)*query(k*2+1,mid+1,r)%mod; } int main() { cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> number[i]; } build(1, 1, n); for (int i = 1; i <= n + 1 - k; i++) { s = query(1, i, i - 1 + k) % mod; if (s > ans) ans = s; } cout << ans << endl; } 出题人你好，为什么这份代码通过率61.54%？

送花回复

发布于 2020-02-11 18:05

栖雁江南

软件测试

为了不快乐

送花回复

发布于 2020-02-11 18:13

翔村渡渡鸟

厦门大学计算机类

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 998244353; const ll N = 200005; ll a[N]; ll Max = 0; ll sum = 1; int main() { ll n,k; cin>>n>>k; for(int i=1;i<=n;i++) { cin>>a[i]; } ll l = 1; ll r = 1; while(r<=n) { if(a[r]) { sum=(sum*a[r])%mod; if((r-l+1)%k==0) { if((sum%mod)>Max) Max = sum%mod; sum =sum/a[l]%mod; l++; } } else if(a[r]==0) { int x = r; l = x + 1; sum = 1; } r++; } cout<<Max%mod<<endl; return 0; } 麻烦大佬帮帮我等蒟蒻，c题，wa了25次。我这思路我感觉没毛病啊，用的取尺法，看区间里面有没有0，不是0才乘，但是通过率只有61%。

送花回复

发布于 2020-02-11 18:16

深海里的鱼

Java

为什么E把java的大数卡了，QAQ

送花回复

发布于 2020-02-11 18:20

WynnLu

Java

def Multi(lst): res = 1 for l in lst: res = res * l return res % mod def solve(): n, k = map(int, input().split()) array = list((' ' + input()).split(' 0')) arr = [] for a in array: arr.append(list(map(int, a.split()))) arr = [a for a in arr if len(a) >= k] curMax = 0 for a in arr: left = 0; right = k curMulti = Multi(a[left: right]) if curMulti > curMax: curMax = curMulti while right < len(a): curMulti = curMulti * a[right] curMulti = int(curMulti / a[left]) left += 1; right += 1 if curMulti % mod > curMax: curMax = curMulti % mod print(curMax) mod = 998244353 solve() 我想问下C题这份python代码哪里有写得不对的地方吗？先根据0把数组分成几个子序列，再对每个子序列分别处理求最大余数。通过65.38%。

送花回复

发布于 2020-02-11 18:21

咸鱼王的xiaofan

信息技术岗

#pragma GCC optimize(2) #include<bits/stdc++.h> #define pii pair<int,int> #define ll long long #define cl(x,y) memset(x,y,sizeof(x)) #define ct cerr<<"Time elapsed:"<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; const int N=1e6+10; const int mod=1e7+9; const int maxn=0x3f3f3f3f; const int minn=0xc0c0c0c0; const int inf=99999999; using namespace std; ll prec[N]= {0},sufc[N]= {0}; inline int read() { char ch=getchar(); int x=0,f=1; while(ch<'0' || ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } struct train { int l,r,col; } a[N]; struct node { int l,r,p,s; ll sum; int mid() { return (l+r)/2; } } tree[N<<2]; void pp(int x) { tree[x].sum=tree[x*2].sum+tree[x*2+1].sum; } void build(int x,int l,int r) { tree[x].l=l; tree[x].r=r; if(l==r) { tree[x].p=prec[l]; tree[x].s=sufc[l]; tree[x].sum=1ll*tree[x].p*1ll*tree[x].s; return ; } int mid=tree[x].mid(); build(x*2,l,mid); build(x*2+1,mid+1,r); pp(x); } void cp(int x,int pos,int v) { if(tree[x].l==pos && tree[x].l==tree[x].r) { tree[x].p+=v; tree[x].sum=1ll*tree[x].p*1ll*tree[x].s; return ; } int mid=tree[x].mid(); if(pos<=mid) cp(x*2,pos,v); else cp(x*2+1,pos,v); pp(x); } void cs(int x,int pos,int v) { if(tree[x].l==pos && tree[x].l==tree[x].r) { tree[x].s+=v; tree[x].sum=1ll*tree[x].p*1ll*tree[x].s; return ; } int mid=tree[x].mid(); if(pos<=mid) cs(x*2,pos,v); else cs(x*2+1,pos,v); pp(x); } ll query(int x,int l,int r) { if(l<=tree[x].l && tree[x].r<=r) { return tree[x].sum; } ll ans=0; int mid=tree[x].mid(); if(l<=mid) ans+=query(x*2,l,r); if(r>mid) ans+=query(x*2+1,l,r); return ans; } int main() { int n,i,j,cma=minn,cmi=maxn; n=read(); for(i=1; i<=n; i++) { a[i].col=read(); a[i].l=read(); a[i].r=read(); sufc[a[i].col]++; cma=max(cma,a[i].col); cmi=min(cmi,a[i].col); } build(1,1,n); for(i=1; i<=n; i++) { cs(1,a[i].col,-1); printf("%lld ",query(1,max(cmi,a[i].l),min(cma,a[i].r))); cp(1,a[i].col,1); } printf("\n"); return 0; } 这份代码为什么只能过90

送花回复

发布于 2020-02-11 18:35

H&W

C++

为什么这个 y 不要减90

送花回复

发布于 2020-02-11 18:38

不是ww

C++

可以问一下g题这种格式哪里错误了吗？我赛后用了别人的输出就过了。 printf("%d.%02d%%\n",(int)((r*100)),(int)((r*10000))%100);

送花回复

发布于 2020-02-11 18:41

C++Rookie.

浙江大学电子信息类

只有我觉得这场最难嘛

送花回复

发布于 2020-02-11 18:47

我不会玩锐雯

Java

这一场好难，没有大佬ak

送花回复

发布于 2020-02-11 18:52

domeya

中国人民大学计算机类

出题人你好，请问您能再详细说明一下F题博弈，为什么两人距离为偶数时先手必胜啊？

送花回复

发布于 2020-02-11 18:53

Alone_xiao

南京大学

#include <iostream> #define ll long long #define mod 998244353 #define N 200005 using namespace std; ll a[N]; ll quickpow(ll x,ll y){ ll ans=1; while(y){ if(y&1) ans=(ans*x)%mod; x=(x*x)%mod; y>>=1; } return ans; } int main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); int n,k; cin>>n>>k; ll ans=1; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=k;i++) ans=(ans*a[i])%mod; ll temp=ans; for(int i=k+1;i<=n;i++){ ll niyuan=quickpow(a[i-k],mod-2); temp=(temp*niyuan)%mod; temp=(temp*a[i])%mod; if(temp>ans) ans=temp; } cout<<ans<<endl; return 0; } 费马小定理求逆元吧，但只过了百分之80

送花回复

发布于 2020-02-11 19:01