2021-04-24 23:25 已编辑长沙学院 C++

关注

题解 | #小圆前辈去上学#

小圆前辈去上学

https://ac.nowcoder.com/acm/contest/15332/A

小圆前辈去上学

https://paste.ubuntu.com/p/cXP69W222X/

题解：签到题，字符串存取，判断一下小数点后第一位数即可，为5即以上进位，或者直接用long double。

小圆前辈的素数

https://paste.ubuntu.com/p/ZbQvcKv8hC/

题解：容易看出一种会超时的 $O(n*m)$ 的解法，所以需要考虑优化，我们可以把相同的数用一个cnt数组统计在一起，然后开始组合，举个例子，假如统计出第一个数组中1的个数为5，第二个数组中2的个数为3，那么第一个数组中1和第二个数组中2组合成为素数3的个数就为 $5*3=15$ 个。有了这个基础后观察发现对于复杂度的优化并没有什么实质性的优化，但是这样的运算规则可以映射到多项式中去，两个数之间组合例如1+2可以看作是多项式相乘中，指数的相加，5*3就可以看作是多项式乘法中系数相乘，这样的话对于每一项的组合我们都可以映射到多项式的运算中去，前面的例子就是第一个多项式中 $5x^1$ 这一项与另一个多项式中 $3x^2$ 这一项相乘得到 $15x^3$ 。可以把两个数组中每一项都这样搞，然后两个多项式相乘后得到的结果中指数为素数的项的系数之和就是答案。然后你就会发现，这样的做法仍然是 $O(n^2)$ 的，但是问题可以映射到多项式上其实就会衍生出很多接发，因为前人提出了许多多项式之间计算的性质，这道题应用的就是FFT(快速傅立叶变换)。我们知道，多项式乘法的时间复杂度是 $O(n * m)$ 的，因为我们平时使用的多项式是属于一种系数表达式，如果用另一种表达方式来作乘法的话时间复杂度就可以达到 $O(n)$ ，这种表达方式就是点值表达式，我们现在需要做的就是把系数表达式转换为点值表达式，这个过程就称为傅立叶变换，具体可以百度，就不在这里赘述。快速傅立叶变换的时间复杂度是 $O(log_2^n)$ 的，所以整道题的时间复杂度就是 $O(n*log_2^n)$ 。

小圆前辈去爬山

https://paste.ubuntu.com/p/rMXTPQ6NXZ/

题解：首先floyd预处理两点间最短距离，之后可以利用单调性处理最短距离后对每次二分求答案，也可以将询问离线，对于每个查询的id按费用排序乱搞。

小圆前辈的魔法

https://paste.ubuntu.com/p/dVfkDqB3yP/

题解：线段切割三角形有以下两种情况：

PNG图像-37F2BFF5B02C-1

第一种就是经过三角形的一个顶点，切出来的两个图形就都是三角形，另一种情况线段只经过三角形的两条边，会切出一个三角形和一个四边形。

我们分两种情况来讨论：第一种情况就把两个三角形的面积求出来取min输出，第二种就是找出与切割点形成三角形的点，计算出面积与总面积减去这个三角形的面积取min输出即可。其中涉及了判断线段相交、求线段交点、求凸包面积等知识点，可以自行学习补充。或者直接套用线段切割凸包的模版也可直接AC

小圆前辈的排列组合

https://paste.ubuntu.com/p/HC5zp8s6rP/

题解：素数筛后，取出素数位的字符，有2个C，1个S，1个U输出YES。

小圆前辈的暴力枚举

https://paste.ubuntu.com/p/3pzJTsbkG3/

题解：排列组合问题，n,m为两条边，令x=min(n,m)，答案为

C(n,0) * A(m,0)+C(n,1) * A(m,1)+...+C(n,x) * A(m,x)

相当在棋盘上放0个，1个，2个...x个棋子方案数之和，对于放k个棋子，我们可以理解为从n行中取出k行，从m列中取k行来放棋子，对于第一行的棋子有m种放法，第二行有m-1种放法，即再乘上全排列即可。

小圆前辈的数组Ⅱ

https://paste.ubuntu.com/p/824TV3f2tY/

题解：要求通过打表或常识得知，对于1e5以下的所有数的因子不超过100，同时我们在dp转移时只需要知道最大值即可，所以我们在转移前可先用线段树将当前数因子覆盖，然后区间最大值+1就是当前转移的最大值，再将覆盖的操作还原。

小圆前辈的数组

https://paste.ubuntu.com/p/2VY3vPFcwx/

处理前缀和 $pre_i$ ，由于是要找所有数和为 $k$ 的倍数的数，我们对于每个 $pre_i \%k$ ,当 $pre_i=pre_j$ ， $i<j$ 时，则 $(\sum_{i}^j a[i]) \%k=0$ 。及区间[l,r]的和为k的倍数。这就能找到满足第一个条件的区间。

要满足第二个条件，我们要将pre相等的放进vector里面二分，即枚举 $pre_i$ ,二分查找，有多少个数小于等于 $pre_i-z$ ，即满足和大于等于为k。

小圆前辈的博弈

https://paste.ubuntu.com/p/TFPcnmvyHY/

题解：字典树板题，将T串的所有后缀插入字典树，用S串的所有后缀去查匹配失败的总次数就是答案。

小圆前辈的异或树

https://paste.ubuntu.com/p/ZQ7r9ByCTs/

题解：可用树上启发式合并（或点分治）+字典树解决。在dfs过程中，用当前链的权值去跑字典树查最大值更新答案，子树枚举完后再将贡献插入字典树。

小圆前辈的888

https://paste.ubuntu.com/p/5ZHDWmFrwg/

题解：数位dp，利用两个记忆化搜索解决，一个处理当前位取x时最后一位是8的方案数，一个计算处理当前为取x时产生的价值贡献，很明显每一位的贡献就是其x*取x时最后一位为8的方案数。

全部评论

推荐最新楼层

欠我半块小饼干

长沙学院 C++

一人血书代码来点注释┭┮﹏┭┮

点赞回复分享

发布于 2021-04-25 00:11

❤由比滨结衣❤

网易互娱_引擎开发

为啥我I题这样写错了，还有这个组合数：fac[n]*inv(fac[m])%mod*inv(fac[n-m])%mod;，这个是啥意思emmm 我的组合数是这么写的： ll C(ll x){ return fac[n] / fac[x] / fac[n - x]; } //以下为源码 #include <iostream> using namespace std; const int N = 1005; typedef long long ll; const int mod = 998244353; ll n, m; ll fac[N]; ll C(ll x){ return fac[n] / fac[x] / fac[n - x]; } ll A(ll x){ return fac[m] / fac[n - x]; } void init(){ fac[0] = 1; for(int i = 1; i < N; i++){ fac[i] = fac[i - 1] * i % mod; } } int main(){ init(); cin >> n >> m; ll ans = 0; ll t = min(n ,m); for(ll i = 0; i <= t; i++){ ans += C(i) * A(i) % mod; ans %= mod; } cout << ans; return 0; }</iostream>

点赞回复分享

发布于 2021-04-24 23:59

05-25 21:38

哈尔滨工业大学

设计模式：面试官喜欢问什么

30万真题，揭秘面试官最... 面试经验谈面试之前应该如何准备？

点赞评论收藏

05-24 20:52

东南大学 C++

爱等信，开泡！

点赞评论收藏

04-11 00:51

已编辑

门头沟学院 Java

两个月的努力，抵不过一纸offer

先说一下楼主的情况：双非本大三，两段实习，javaer，想要找一个暑期大厂offer，努力了两个月，三月份每天的状态就是算法，八股，项目，四月份更是一个面试没有，最终还是没有结果，心碎了一地。期间面了一些中小厂，大厂只有腾讯约面，其他大厂都投了一遍，但是还是石沉大海。再看一下楼主的面试结果吧，就不说ttl了腾讯s3:三面挂csig：一面挂teg：三面挂wxg：一面挂没错，面了八次腾讯，两次三面挂，当时真的心都碎了。其他中小厂都有面，有的没过，有的oc，但是都没有去。其他大厂投了简历，但是不是简历挂，就是测评挂，都说今年行情好很多，各大厂都扩招，可是问题出在那里呢？学历背景吗？实习经历吗？还是简历不够好看？依稀记得，从年初七就离开了家里，回到学校，早早准备面试，当时自己认为凭借着自己的两段实习经历，以及大二就开始准备的八股算法，拿大厂offer不是问题，但是还是不敢放松，回校的状态每天就是算法，八股，还有查看各种招聘信息，想着尽早投机会多，但是事实证明，投的早，不如投的刚刚好。当时想着，先投一些中小厂开始面试，找找面试感觉，从2.10就开始有面试了，基本都是线下面试，面试的感觉都很不错，觉得自己的状态慢慢回来了，期间也有oc一些中小厂，但是自己的目标并不在此，只是想练一下手，遂拒。后面投了腾讯的暑期实习基地，不久就约面了，第一次面这么大的厂，多少有点紧张，好在运气还不错，遇到的面试官也比较好，一直干到了三面，期间看牛客有不少说一面就挂了的，感觉自己还是比较幸运的，但是没想到倒在了三面，一周后就挂了，伤心是有的，但是想到这才刚刚开始，还有很多机会，便继续准备下一次面试了，很快，被另外一个部门捞了，一进会议，面试官没开摄像头，看网上说没开摄像头很多都是kpi，但是自己给自己打气，认为面试官只是不方便开摄像头罢了，面完，感觉良好，没问什么很难得问题，基本都答出来了，算法两道也a了一道，感觉实习不会这么严格吧？还是过了一会挂了，因为这个？还是技术不太匹配？面试过程中说搞C++的，心想，搞c++的你面我干啥？唉，这时候有点气馁，然后就接下来半个月没有面试。这时已经是三月底了，看到牛客好多人都已经陆陆续续拿到了offer，看人家的面试准备也没那么早，有0实习的，有没刷算法的，有两个面的，，，唉，反正是一言难尽啊，感觉努力没有什么意义，面试多半是看面试官的感觉，主观性很大啊，只要你技术没有太大的问题。第三次面试腾讯，面试来的比较突然，期间已经有几天没看八股什么的了，临时看了一下之前自己做的面试笔记，但是面试却异常顺利，三天闯到了三面，自己也不敢相信，三面玩感觉也良好，脑子里不得不想着一些“offer结算画面”，但是过了一会查看流程显示“流程终止”，我？哎，当时真的有苦说不出啊，也是一晚没睡。后面就逐渐开始褪去大厂梦了，看着曾经跟自己交流的牛油，朋友，认识的人，觉得他们技术不太如你，算法刷的没你多，进了大厂，但是这又如何呢？能力强不强不是你了说了，面试官说了算。也逐渐知道，不是你能力好就可以了，还得有运气，运气，运气。这个过程太累了，和自己和解吧，不用非得大厂，找个合适一点的就好，放轻松一点。今天有点心事睡不着，闲着想写一些自己的面试过程，勿喷。附上一张面试的情况，公司就不方便透露了。

怒卷的斯科特：八分运气两分实力

点赞评论收藏

05-11 11:58

中国矿业大学 Java

大佬们，为啥这个简历练小厂都不回复啊😦

man,我是真的一点不想考研啊😭😭

程序员牛肉：主要是因为小厂的资金本来就很吃紧，所以更喜欢有实习经历的同学。来了就能上手。而大厂因为钱多，实习生一天三四百的就不算事。所以愿意培养你，在面试的时候也就不在乎你有没有实习（除非是同级别大厂的实习。）按照你的简历来看，同质化太严重了。项目也很烂大街。要么换项目，要么考研。你现在选择工作的话，前景不是很好了。

点赞评论收藏