记录一下. 总共4题，过题情况4/4第一题：给一个年份，输出一个比当前年份大，每一位均不相等的年份。数据10组以内，年份不超过6位数第二题：给n个二维坐标点，每个点有个ri，如果某个点与当前点距离不超过ri，则激活当前点时也会激活这个ri距离内的其他点，激活可以连锁。问激活任意一个点之后可以激活的最多总点数。n<=100第三题：给一个序列，每次可以花费1的代价让一个元素+1，求把序列变成单峰序列的最小代价。n<=10^5第四题：n个点，每个点有一个数字a[i]，有m条边，保证边是从编号小的点连向编号大的点，每条边有权值b[i]，表示走这条边至少需要b[i]个补给包。初始时补给包为0个，从1号点出发，每次从一个点i出发，可以选择拿不超过a[i]个补给包，拿了就不能丢，走过边也不会消耗补给包。问能不能走到终点n，如果可以，走到终点n时身上补给包最少是多少个。n<=10^5,m<=5*10^5第一题就是不断重复+1枚举年份，暴力判断即可。值得注意的是，测试数据的输入格式和样例的格式似乎有不同，我使用python写第一题直接在输入这就报错了，最后写了两种输入，用try给干过去了。如果直接用cpp的scanf应该不会有这个问题。第二题直接枚举初始激活点，然后暴力dfs每个次级激活点即可。这样做最坏是O(n^3)的，python直接超时了，优化了一下，不难发现，如果点x被点y激活，那么初始激活x的答案肯定<=初始激活y的答案，因此一个点如果在dfs中被找过，那就不需要将它作为初始激活点了，这样复杂度降低到O(n^2)第三题考虑设f[i]表示前i个数字组成递增序列的最小代价，g[i]表示从i开始到最后一个数字组成递减序列的最小代价，顺便记录达到最小代价时位置i的数字是多少，最后枚举峰的位置，统计代价最小值即可。复杂度O(n)第四题，如果直接按照题意硬做，我是不会的，因为选取更少的补给包这个决策是不利于最后走到n这个目标的。先考虑判断有无解该怎么做，可以发现，找到最大的边权，最终答案肯定不超过这个边权，设为mx。则我们可以在走的过程中进行贪心，记录f[i]表示走到位置i时，能获得的最大补给包数量。按顺序枚举点i（注意，这样枚举肯定是无后效性的，因为边都是小编号连向大编号），然后枚举点i的出边，假设有边(i,y,b[x])，如果f[i]>=b[x]说明这条边能走，则更新f[y]为max(f[y],f[i]+a[y])，注意，f[y]的值不应该超过mx，最后验证f[n]是否有正常转移过来的值即可判断是否有解。不难发现，如果我们限制了补给包的上限，我们就可以判断在这个上限下有没有解，且如果上限c1是可行的，那么对于任意c2>c1都是可行的，存在一个边界区分有无解，这是很好的性质，可以直接二分补给包上限，用上面的判定决定往左还是往右二分即可。复杂度O((n+m)logm)总体来说还是稍微有点trick的，前三题贪图代码简单直接用python写了，第四题怕py超时，用cpp过了。整体写起来需要想的东西比较多，只能说有几个月没写算法题了，略有生疏。希望给个面试。。。

8.3晚笔试，服务端开发岗位，4题ac感觉还是有难度的。。。提前交卷跑了。希望能给个面试

本篇用于记录面试过程中遇到的算法题和编程题。我在找实习过程中看了很多人的面经，学到了很多知识，很幸运能获得前人的经验，因此我也稍微留下一点点东西。八股、场景题我都不擅长，算法和编程题我还是回答得比较好的。介绍一下背景：西北农林科技大学本科，ACM EC银 regional 银淘天 客户端开发一面：题面：给一副牌，可能有重复，判断是否存在顺子。做法：桶排序去重，然后看是否有连续的5张牌，最后特判10 J Q K A。这样写复杂度是严格不超过牌数的。现场情况：我当时也写了上文提到的方法，没什么问题。字节 后端开发一面：题面：滑动窗口，给一个数组，长度为K的滑窗，求每个滑窗最大值。做法：很经典的题，我的写法是双端单调队列，队列一端控制窗口不越界，另一端控制队列里的数字均为有效。举个例子，一对下标i,j(i<j)，如果nums[j]>=nums[i]，那么i就没有存在队列里的必要了，可以出队。现场情况：我写的就是上文的做法。然后面试官让分析了复杂度，这样做复杂度是O(n)的。面试官问了一下有没有优化的空间。我当时队列大小是数组长度，提出将队列换成双端队列，动态大小，这样额外空间不超过O(K)。而且代码里我是单独处理了前K个元素，后来换了个写法，在一个for循环里处理完。非常建议大家记一点优化，可以不会具体怎么做，写的代码也可以非完美，但面试官问如何优化时要能说出点东西。具体优化思路：代码方面（冗余代码，太多if，变量名称，有没有好的方法写短点）时间方面（有没有复杂度更低的做法，不知道怎么优化可以指出当前代码复杂度瓶颈在哪，即哪一部分用的最多，可以直接诚恳地说不懂，但觉得这里可以优化）空间方面（是否使用了定长数组，尽量用多少空间开多少空间，能不能不用额外空间等等）字节 后端开发二面：题：给一个十进制数n，和一个包含若个1位数的数组，用数组中的数字组成小于n的最大数。做法：分情况讨论+贪心。如果本题是不超过n，先看看不超过n怎么做，从高位往低位考虑。每次从数组里选一个能填的最大值，如果某一位填的数字没有n上的数字大，那么后面的位均可以填最大数。特殊处理最高位找不到合法数字的情况，假设n是x位数，这时候答案就是x-1个数组里的最大数。特殊情况里还需要特判x=1的情况，这时候无解。如果小于n，特殊情况是不变的，我们可以先按照不超过n的方法构造出一个解，如果此时解满足小于n，直接输出。           否则从低位往高位找到第一个可以填写小于n对应位数字的位置，如果有则修改该位，其余低位填上最大数。如果找不到这样的位置，那就输出x-1个数组最大数。现场情况：我一开始没有考虑任何特殊情况，写完贪心之后自己出数据的时候想到了特殊情况，直接把代码推翻重写。好在前面写得比较快，总共用了20分钟完成所有情况的讨论。面试官问了我思路，并且让我说了一下复杂度，其实严谨复杂度就是O(10*log_10(n))然后解释了一下复杂度的含义，log_10(n)是n的位数，1位数数组大小不超过10，面试官表示没什么问题。字节 后端开发三面：题1：给一个字符串s，和一个字符串数组arr，问字符串能否由数组里的串组成。做法：动态规划，将arr里字符串存入哈希表，枚举s的每个子串去哈希表里找是否出现。如果出现就用链表连一条子串头到子串尾的边。设dp[i]表示s的前i个字符是否能被匹配，转移方程就是dp[i]转移到dp[j](j>i)，当且仅当i+1到j有连边。这样做复杂度是O(n^2 hash())的，这里hash()是和你选择的哈希表有关，我用的是C++的map，所以是log现场情况：我写的也是动态规划，但是判断串是否出现用了map。面试官问复杂度，这里直接说了n^2logm其中n=len(s)，m=arr.size()，面试官不太满意，问了一下优化。我当时并没有特别严谨想过这个优化问题，我首先考虑的瓶颈是判断每个子串是否出现这部分。给面试官说了这个瓶颈，表示认同。我说可以试试AC自动机优化这个匹配过程。面试官赞同。反问，回答用哈希。题2：设计一个数据结构，满足：①O(1)插入、修改、删除；②能够按照插入顺序遍历元素。做法：这里很明显每个元素有两个顺序，一个是结构顺序，一个是插入顺序。开两个链表+哈希表分别表示两个结构即可，和跳表有点像。现场情况：我一开始回答得差不多。面试官反问了为什么哈希表是O(1)的。回答哈希表并不是严格O(1)，而是均摊O(1)，如果数据过大或者哈希函数不合适或者冲突不合适，复杂度也会高。再问如果数据类型是字符串该怎么哈希，回答将哈希映射成一个高进制数，用自然溢出或者取特殊模数。取双哈希，双种子等方法增强哈希强度。题3：n个数字，数字范围[0,m]，求任意两数异或和的最大值。做法：0/1字典树经典问题，将数字转成0/1串，高位往低位插入字典树中，查询时尽量往异侧走，这样异或值最大。现场情况：看到题10分钟内写完了。面试官问了问复杂度，复杂度是O(nlogm)然后讲了讲做法就没了。腾讯 后台开发一面：题1：给一个没有括号的四则运算表达式，求值做法：经典栈模拟题。现场情况：写了栈做法，并讨论了除以0的情况。面试官范围如果字符串非法怎么办。忘记考虑了，回答增加合法性判断题2：给一个数组，问是否存在满足和为K的倍数的子数组做法：前缀和套路题，在模K意义下求前缀和，只有有某一种前缀值出现2次，那就有解。现场情况：和上面做法一致，加上map判断，其实可以用哈希表，但面试官没有追问。题3：给一个数组，只有两个数字出现1次，其他数字都出现2次。求对应的两个数字。做法：求异或和，得到的异或值肯定非0，异或和里任意找某个非0二进制位，将数组按这一位分类异或。得到的两个异或和即为答案。现场情况：和上面做法一致，给出了为什么异或和一定非0的证明。三道题只用了20分钟，面试官没有追问。还有一些其他厂的，面完没复盘就不记得了，想起来再补充。面试里的算法、编程题，我感觉还是需要一些trick的，遇到的题目几乎都是很有章法的题。在面试时编程部分算是我的舒适区，每次都在编程题这里找回场子，大部分面试官都挺满意我编程题的表现。不过不是很清楚这样的表现能否为面评加分...在与一些其他竞赛选手交流的时候发现，奖项的作用是使面试时遇到的题目变难，以及更加严格的要求，写出题是理所应当，写不出就是巨大减分项。所以整体来说，面试的时候我写编程题还是很紧张的，虽然目前没有遇到过让我思考超过1分钟的题目，但我还是不感到轻松，每次知道做法之后都在绞尽脑汁想合法性、想corner case、如何让代码优美一点、如何增加可读性...最后祝大家面试顺利，拿到想要的offer

西农本，一个与后端没什么关系的项目，一段写在简历上是减分项的实习，ACM EC银 regional银，方向是后端开发。技术水平一般，勉强算人类。因为一些奇怪的原因，被迫六月才开始重新找实习。投了可能有上百份简历，市面上能见到的可能有实习的厂基本都投递了。大部分都是简历挂。把实习经历删了之后，简历反而好过了。淘天 客户端开发：6.4一面挂完全不对口，客户端相关的内容一点不会腾讯 后台开发：6.10一面简单自我介绍，简单问了项目，把我以前的奖项拿出来问了问，为什么简历上没写某个拿过的银牌（当时自己实力一般+运气好，不认为那块银牌能代表什么，再加上后来拿了ec银，简历上不想写得太冗余），然后是40min写3个算法题，都是有trick的题，20分钟写完了。接下来是深挖项目，由项目引申出的很多问题，问得特别深，面试官人很好，一直在鼓励，让我不要太大压力。语言内容问的很多，我一直在回答错误或者说不好意思我不会，过程中差点崩溃。后面多讨论了一下项目的性能问题。面试官反馈语言基础一般，计网os还可以，有点竞赛选手通病，对我的印象不错，不过即使他放我过了，也不足以通过二面，让我注意弥补自己的缺点。话说得让人特别舒服，我也是感到非常羞愧，有点难过自己糟糕的基础浪费了面试官1.5h字节 后端开发：6.5一面问项目、八股、写算法题。前两个答得很一般。面试过程中面试官不怎么反馈正确与错误，结束的时候还是很友善地帮我总结了问题，让我多探究具体八股问题的原因，不能只知道现象，不知道本质。考虑问题得从：现象+原因+避免方法+解决办法四个角度考虑。6.6一面过，约二面6.9二面先提了一嘴项目，再问了八股，从一个问题引申到很多问题的探究，再详细挖了挖项目。然后写了一个题，这个题所需要考虑的情况比较多，面试官很耐心听我讲完了全部情况，我自己感觉讲得很烂。二面面试官更加友善了，一直在鼓励和支持，反馈是各方面都还不错，下一面可以再扎实一下（此时已经明示有三面了，非常感谢qwq）6.11二面过，约三面6.12三面先让我详细介绍了项目，问了很多项目的细节，实现方法之类的。简单问了两个八股问题。然后是三个算法题，算法题过程中问了复杂度相关，数据结构相关，如何设计等等，这里是我的舒适区，基本没啥问题。最后再重新问了项目。问了能实习多久，最快什么时候能入职。过了2小时通知三面过，约hr面pdd：简历过，等测评没提到的厂基本都是简历挂。本篇是一个基本上只有竞赛成绩的纯比赛选手的第一视角。总体感觉项目和实习是最重要的，竞赛只能证明学习能力，在基础知识都比较扎实的情况下，竞赛奖项才能起到作用。特别是现在竞赛选手很多，感觉面试官经验都很丰富，很熟悉acm选手和非acm选手的区别和特点，竞赛选手有扎实的八股和能聊的项目会是巨大加分项（前提是你的竞赛实力是扎实的）写本篇的目的旨在分享一波实际求职体验，我觉得在应届生求职的过程中，如何减少自己的短板非常关键，各方面的能力可以勉强是60分水平，但绝对不能是糟糕水平。闪光点只有在没硬伤的情况下才是闪光点（除了真的特别闪光，比如多段大厂实习，github上大量star的项目，acm ecf金甚至world final，不过这样的人能有多少呢，他们和我就不属于一个赛道，对自己的求职定位和求职目标就是普通白菜offer，碰到这些大神我一般直接投降，默认竞争剩下的岗位）希望这篇分享能够帮到其他竞赛选手，非竞赛选手也可以看个乐子，看看真实一般水平选手的求职qwq，别再捧杀acmer辣，不存在掏出奖项大厂舔着要的情况（至少对98%的选手来说不存在这个情况qwq）

训练题目集链接https://ac.nowcoder.com/acm/contest/16092过题数：7 签到题是G，是一个模拟除，直接淦了。 然后看榜，过题比较多的是H，是一个dp，非常简单。一开始mle了一发，然后改成滚动数组就过了，有惊无险。 D题我没看，栋哥说他切了，他上了，他过了。 然后现场有人过的题目只剩下BCM了。 看B，呃呃呃这个随机生成的方式不就是ECfinal的题面吗......太艹了。随机生成的点权，边权是点权的gcd，求mst。嘻嘻，这样子答案肯定是n-1啊，太容易互质了。对n比较小的情况就暴力。结果wa了...后来发现是暴力部分没有输出哈哈哈哈哈哈哈。 然后M题看了...

显然，排序后再选择n-1的人，要么选择前n-1个，要么选择后n-1个然后分两种情况讨论，起始位置在n-1个人之外或者之内，取个min即可

bfs即可。

可以使用二分。每次二分答案，判断使用的箱子数是否小于n。但是需要注意一下二分的起始条件，箱子的承重最小是货物的最大重量，从这里开始二分

一个结论，a * b的矩形的对角线切割的方格数=gcd(a,b) * (a/gcd(a,b)+b/gcd(a,b)-1)原因是这样的，当gcd(p,q)=1时，p*q的矩形的对角线，除了起点和终点，不会经过任何整点。在这条对角线穿过一个方格边缘的时候，切割的方格数会加一。可以穿过的边缘=p-1+q-1由于出发时的格子也会被切割，所以总切割方格数为p+q-1回到原来的结论，我们可以枚举gcd(a,b)，把问题变成寻找互质的p和q使得切割方格数为n/gcd(a,b)

简单动态规划设f[i][j][0/1]表示第i天时，精力为j，这一天不玩或者玩时的最大答案。转移的话，f[i][j][0]可以从f[i-1][j-1][0/1]转移过来。f[i][j][1]可以从f[i-1][j+1][0/1]转移过来。对于j==m的情况特殊判断一下即可。

这题采用dp设f[i][j]表示你获得i分，你的朋友获得j分时的胜率。当i==n的时候，显然f[i][j]=1然后就是转移，枚举你选择的副本加分分值，分四种情况讨论：1.你通关，朋友通关2.你通关，朋友没通关3.你没通关，朋友通关4.你没通关，朋友没通关最后一种情况恰好是f[i][j]转移到f[i][j]，这个时候就联合前面三种情况，移项即可。

结论：奇数时后手必胜，偶数时，如果是2的奇数次幂，后手必胜，否则先手必胜。这个结论可以用决策树处理出前100个数的答案然后发现规律。证明的话：如果是奇数，当这个奇数是质数时，后手直接赢；否则这个奇数就是若干个奇数的积。此时无论先手如何变化，都会将奇数变成偶数。后手只需要和先手减去相同的数即可。 如果是偶数，首先把因子2提出来，偶数就是若干个2和若干个奇数的乘积。当这些奇数只有1时，每次变化相当于保留一部分2，将剩下的部分变成一个奇质数或者1，因为2的次幂减一都是质数或1，如果先手变化成质数，后手可以反将剩下的2也变成1个奇质数或者1，先手就陷入了奇数的必败态，显然先手不会这么做。先手的做法应该...

A型，由于必须一刀切到底，假设木板的长宽分别为x,y那么最多切出的材料是max([x/L]* [y/W],[x/W]*[y/L])而O型显然是作为B型使用更加好。O和B能够切出的材料就是O型和B型的面积和除以LW

毫无疑问，如果答案在[0,l-1]的话，肯定是d。如果不在的话，就是比r大的第一个d的倍数。非常简单的题目。