2019-04-13 09:26 已编辑门头沟学院自然语言处理

关注

【题解】牛客小白月赛13

A-小A的签到题

显然复制代码并不能AC，实际上要求的是 $f_{n}^{2}-f_{n-1}f_{n+1}$ ，其中 $f_{n}$ 是斐波那契数列的第n项，简单观察或推导可以得出结论： $\forall n \geq 3$ , 若为奇数则为-1，否则就为1。

复杂度： $O(1)$

B-小A的回文串
求n个串的最大回文子串的长度的最大值。枚举每一个变化后的字符串，对每个串跑一遍马拉车即可。

复杂度： $O(n^2)$

C-小A买彩票
考虑买n张彩票的总的方案数是 $4^{n}$ ,然后统计不亏本的方案数，记录 $f[i][j]$ 是买到第i张彩票总获利为j的总方案数。 $f[i][j]=∑f[i-1][j-k],k = 1,2,3,4$ ,最后统计一下不亏本的方案数即可。由于数据规模很小，考虑分别组合枚举有多少个1，2，3，4也可以通过。

复杂度： $O(n^2)$

D-小A的位运算
预处理了一下前缀和后缀，然后枚举那个不选的数就可以了。

复杂度： $O(n)$

E-小A的路径
矩阵表示第一天的时候u到v有多少条路径，然后直接做矩阵k次幂就能得到k天从u到v的路径数，最后统计一下就可以了。

复杂度： $O(n^3logk)$

F-小A的最短路
这张图可以认为是边权全为1的树上增加了一条边权为0的边。

首先先不考虑多出来的一条边，那么dep[u]表示点u的深度，任意两点u，v的最短的距离就是 $dep[u]+dep[v]-2dep[lca(u,v)]$ ,加上这条边后另外一种可能最短的路径就是经过这条边权为0的边，可以建图之后跑一次最短路，每次查询的答案都是 $min(dis[u]+dis[v],dep[u]+dep[v]-2dep[lca(u,v)])$ 。

复杂度： $O((n+q)logn)$

G-小A和小B
这题由于疏忽，一开始的时候题意上误导了大家，在这里向大家道歉。
双向BFS，只要搜索的时候判断当前走过的位置是否被对方走过就可以了。

复杂度： $O(nm)$

H-小A的柱状图
单调栈的模板题，考虑每个位置向两边拓展的最左边的边界和最右边的边界 $L[i],R[i]$ ,分别从左到有和从右到左用一个单调栈维护。处理一下底边的前缀和，扫一遍就可以求出最大值。

复杂度： $O(n)$

I-小A取石子
判断一下小A是否能够取石子，当且仅当小A原本就是必败态并且不能取出任何石子的情形下，小A会输否则小A都会赢。

复杂度： $O(n)$

J-小A的数学题
有很多种做法，一种比较常规的做法是：

$∑_{i=1}^{n}∑_{j=1}^{m}gcd(i,j)^{2}$
= $∑_{d=1}^{min(n,m)}d^{2}(∑_{i=1}^{n}∑_{j=1}^{m}gcd(i,j)=d)$
$记f(d)=(∑_{i=1}^{n}∑_{j=1}^{m}gcd(i,j)=d)$
$有F(t)=∑_{d|t}f(d)=[\frac{n}{d}][\frac{m}{d}]$
$有f(d)=∑_{d|t}\mu(\frac{t}{d})F(t)=∑_{d|t}\mu(\frac{t}{d})[\frac{n}{d}][\frac{m}{d}]$
处理因子直接计算复杂度 $O(nlogn)$ 就可以通过本题

全部评论

推荐最新楼层

易向以归宁

厦门大学嘉庚学院 C++

I题数据需要加强QAQ，很多人没有考虑k都能通过。比如这组数据： 4 1 1 1 1 1 正确结果应该是YES，但是很多AC代码会出来NO。

点赞回复分享

发布于 2019-04-13 10:02

菜是原罪1

闽南师范大学 Java

请问最后一题为什么是i*i*(ll)mu[j/i]*(n/j)*(m/j)？？题解没看懂。。。

点赞回复分享

发布于 2019-04-17 01:50

hhhhhhhhh1

门头沟学院 Java

有大佬可以帮我看看I题吗。可以过91%的样例，不知道哪儿错了 #include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; int a[maxn]; int main() { int n,k; scanf("%d%d",&n,&k); int ans=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); ans^=a[i]; } if(ans=!0){ printf("YES\n"); }else{ for(int i=1;i<=n;i++){ if(a[i]>=k){ if(((ans^a[i])^(a[i]-k))){ ans=((ans^a[i])^(a[i]-k)); break; } } } if(ans){ printf("YES\n"); }else { printf("NO\n"); } } return 0; }

点赞回复分享

发布于 2019-04-13 15:01

TianTianUp

江西师范大学前端工程师

秒啊

点赞回复分享

发布于 2019-04-13 11:03

朴范

CDFLS C++