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++

点赞回复分享

发布于 2019-04-13 09:51

KirinDr

网易互娱_游戏研发

G快写完了又收到广播，当场我就佛了...QAQ

点赞回复分享

发布于 2019-04-13 09:23

自为风月马前卒

阿里云_技术

👍(就是题目思维难度有点低)

点赞回复分享

发布于 2019-04-13 09:10

YCU_小白菜

宜春学院 Java

# 👍

点赞回复分享

发布于 2019-04-12 23:10

向宇同桌

牛客网创始人

👍

点赞回复分享

发布于 2019-04-12 22:51

03-03 15:53

已编辑

黑龙江大学 Java

我做过的，被面试官夸爆的那些Ai项目(一)

在当前开源项目极为丰富的背景下，付费资源并不一定意味着最前沿的技术优势，在具体执行层面展示出自己的独特价值，才是简历上最重要的加分项。1. WebMCP — 让网站主动告诉 AI 该怎么操作AI 操作浏览器的方案一直靠"猜"——截图识别、DOM 解析，错误率 15-30%。WebMCP 反过来，让网站自己声明能做什么，AI 直接调用结构化接口，准确率接近 100%。Chrome Canary 已实装。企业内部系统的 WebMCP 适配目前几乎没人做，是明确的蓝海。推荐理由：简历上写的不是"我会用某个框架"，而是"我在标准刚发布时就做了企业适配&...

书海为家：#人脑vsAI# 尽管深度学习的最初灵感来源于人类的大脑，但二者的运作方式截然不同：深度学习所需要的数据量远比人脑所需要的多得多。可是一旦经过大数据训练，它在相同领域的表现将远远超过人类（尤其是在数字的量化学习，例如挑选某人最可能购买的产品，或从100万张脸中挑选最匹配的一张）——相对来说，人类在同一时间内只能把注意力放在少数几件事情上面，而深度学习算法却可以同时处理海量信息，并且发现在大量数据背后的模糊特征之间的关联，这些模糊特征不仅复杂而且微妙，人类往往无法理解，甚至可能不会注意到。虽然深度学习拥有人类所缺乏的并行处理海量数据的“绝技”，但不具备人类在面对决策时独一无二的汲取过去的经验、使用抽象概念和常识的能力。与人类相比，深度学习想要充分发挥作用，离不开海量的相关数据、单一领域的应用场景以及明确的目标函数，这三项缺一不可，如果缺少其中任何一项，深度学习将无用武之地。

AI求职实录

点赞评论收藏