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

05-12 08:44

蚌埠坦克学院嵌入式软件开发

简历里写熟悉通信协议、驱动、BSP，面试官真正要听的其实是一整条数据链路

很多人写嵌入式简历，最容易堆上去的词就是 UART、SPI、I2C、CAN、以太网、Linux 驱动、BSP、FreeRTOS、DMA、中断。这些词本身当然没错，问题在于只要简历里出现得够多，面试官通常不会再按“名词解释”的方式问你。现在更常见的追问方式，是挑一条你项目里真实存在的数据链路，从外设收发开始，一路往上问到中断、DMA、缓存、任务切换、驱动接口、异常恢复、日志定位，再回到为什么这样设计。答得出来，说明你真做过；答到一半就散，说明大概率只是配过、调通过、抄过一版能跑的代码。最近公开面经、岗位要求和讨论里反复出现的几个方向也很一致：Linux、RTOS、驱动/BSP、C/C++、通信协...

点赞评论收藏

05-12 10:10

已编辑

门头沟学院人工智能

非科班+本科目前正在做AI工程师，说说我这3年。。。

写这篇之前我犹豫了挺久。一方面是怕被人骂，"又一个收割焦虑的转行帖"；另一方面是看了太多用 GPT 套娃出来的「学习路线」文章，AI 味重得让人没法读完。所以这篇全是亲身踩过的坑，时间线、用过的项目、当时的心路全都尽量原样写出来。如果你是大学生在迷茫要不要转 AI，或者已经在转的路上，希望能给点参考。 一个反共识的开场：你以为进 OpenAI 的人都是博士？ 先讲个故事，跟我没关系，但跟所有想转 AI 的人都有关系。 OpenAI 的 Sora 团队（就是搞文生视频那个）一共 13 个人。这里面有两个人特别有意思： Will DePue，密歇根大学计算机系，直接辍学了。17...

_hengheng：我也本，也算是做ai相关，我最开始感觉做ai工程师有多么多么困难，后来发现懂了原理后整体训练完全可以看成一个流程化的内容，开源方案太多了，大多基本都是按着模子在自家业务上做各种操作，就算是大厂的小部门也没那么多资源去训基模，反而更多的是像怎么把技术往业务方向靠近了，不过当前时代如果本科学历没那么好加上自己执行力不是特别强还真不建议走ai工程师这条路，可以试试其他ai的偏业务方向，不然校招不太好杀出来

点赞评论收藏