40min AK T1 Problem 给定一个长度为n的字符串，进行q次操作，每次操作修改其中一个字符，每次修改后输出极长连续字符的段数，如aabbaaa的段数是3。 Solution set存连续段的（起点、终点、字符），每次修改字符的时候最多影响三个连续段，修改后输出set的大小即可。 T2 Problem 同一天内吃糖果的愉悦度为a1+max(0,a2-1)+max(0,a3-2)+...+max(0,ak-k+1)，现在有n个糖果a[]，问最少需要分几天来吃才能使得愉悦度之和大于等于x。 Solution 将a[]从大到小排序，二分天数，检验时贪心地将值更大的糖果放在每一天的最前面。...

还愿，阿里已意向求拉实习群

许愿阿里🙏🙏🙏TimeLine：3.29 投递4.14 电话告知岗位已招满，转部门4.19 笔试测评4.22 一面（简历面）4.26 二面5.6 三面5.10 hr面--------------------------5.13更新，已oc

A.awa开小车我们可以将“小车发射器”看作小车在某个位置、起始运动方向为某个方向的描述，那么考虑按照小车运行方向和位置进行模拟即可，在遇到没有触发过的导向板时执行相应的转向，计数，并将其标记为已经过，离开边界的时候结束模拟。时间复杂度为。B.JokerXuan的明星梦定义两个变量t0 与 t1 ，将他们的二进制的形式初始化为000000……与111111……，每次进行幸运数字的更新，同时以相同的方式更新这两个变量。当遇到“null”时，在当前幸运数字的二进制形式中找到0的位置，如果t0中的相应位置变成了1，那么就需要将这个0所在的位置改成1，其余同理。C.What is ACM签到题，循环判...

D. Half Turns Solution 看不懂题解写的什么…… n和m都为偶数，是一定可以构造出解的。 我们假设n≤mn\le mn≤m，然后分类： 当n=2n=2n=2时，按照如下方式构造 即第一列和最后一列都是拐弯点，中间可以放2的倍数个拐弯点。 接下来考虑n=6的时候，按照如下方式构造 第一、二行从第三列开始的部分可以放2的倍数个拐弯点。 然后考虑n比较大的时候，我们可以将每四行看成一个整体来做，如果n不是4的倍数那么最后一块就包含6行。 先考虑中间的块，不考虑头尾，我们希望能在这4行内构造2m个拐弯点，用如下方式构造 这样就能保证中间每一块从第一列进入，又从第一列出去。 接...

F. Traveling Solution 构造题，注意细节。 考虑怎么样构造用的边数最少，然后如果m更大就加一些不影响任何最短路的边，如果两两连边还是不够m条就输出No。 首先考虑直接从1到n的最短路，显然必须有d[1]=d[n]=min{d[i]}d[1]=d[n]=min\{d[i]\}d[1]=d[n]=min{d[i]}。 怎么用最少的边来构造呢？首先1到n我们直接连长度为d[n]d[n]d[n]的边，然后考虑2∼n−12\sim n-12∼n−1的所有点，将这些点按ddd从小到大排序。 顺着考虑这些点，如果d[i]≡d[n](mod2)d[i]\equiv d[n]\pmod 2d...

K.Great Party Solution 关键是需要推出一个结论：当堆数为奇数时有必胜策略。这样就只需要考虑偶数，偶数堆时谁让堆数-1谁就会输，因此将所有堆的石子数-1，就变成了nim博弈，那么本题就转化成了求区间内区间异或和不为0或长度为奇数的子区间个数，显然求区间内异或和为0的长度为偶数的子区间个数更方便，用莫队可以很容易离线求出所有答案。 时间复杂度O(nn)O(n\sqrt{n})O(nn​)。 int sum[2][1 << 20], pre[N], blo, bel[N]; ll ans[N]; struct Node { int id, l, r; ...

I. Board Game Solution 考虑一组k+xk+xk+x个人实际上可以看成kkk和xxx两组，枚举分出多少组kkk，剩余的人就平均分到mmm组中。 本题实际上定位应该是签到，但是数据有问题。 时间复杂度O(m)O(m)O(m)。 题目数据有问题，下面代码中注释掉的if应该要加上，表示如果不能让m组都有人就不能统计，但是实际上把这种情况统计进来才能ac，这场出题人素质属实不行。 int main() { ll n = fast_IO::read(), m = fast_IO::read(), k = fast_IO::read(), x = fast_IO::read...

A. Falfa with Polygon Solution 考虑我们选出的凸包，从1到n看就只有一条边是从较大编号连到较小编号，考虑dp出fk[i][j]f_{k}[i][j]fk​[i][j]表示长度为k的从iii开始到jjj结束的子序列的最大长度，其与i、j两点长度的和就是凸包的周长。 写出fff的转移方程如下 fk[i][j]={dis(i,j)k=2t{fk−1[i][t]+f2[t][j]}k≥3f_{k}[i][j]=\begin{cases} dis(i,j)& k=2\\ \max\limits_{t}\{f_{k-1}[i][t]+f_{2}[t][j]\}&amp...

F. NIO with String Game Solution 考虑离线，对所有t串（包括后面添加的字符）建出一棵trie树，按从a到z的顺序遍历子节点进行dfs，就可以把dfs序对应成字典序，这样就相当于每次需要在trie上找到s对应的位置，求dfs序比它小的位置上有多少个t串。 对于操作一、四：考虑用树状数组维护dfs序上的贡献前缀和，那么添加一个字符时就将当前tit_iti​串的位置贡献去掉，走到其下一个位置，再添加上贡献，查询时只要找到需要查询的dfs序最大值即可。 对于操作二、三：考虑维护一个nows表示目前s匹配时最终走到哪个点，res表示匹配的部分后面还有多少个字符，sto表示...

C. Link with Nim Game Solution 根据nim博弈，对于先手必胜的情况，每次只需要拿走若干石子后异或和是0即可；先手必败的情况，为了使得拿的次数最多，每次只拿一个且让对手也只拿一个是最优的。 比较难算一点的是第一步可选的方案数，对于先手必胜的情况，记sss为所有石子的异或和，则对于每堆石子可以计算能拿的石子数量x=a[i]−s⊕a[i]x=a[i] - s\oplus a[i]x=a[i]−s⊕a[i]，取max并记录最大值个数即可。 对于先手必败的情况，考虑拿一个石子对异或和的影响是使得从0 lowbit(a[i])0~lowbit(a[i])0&nbsp...

E. Falfa with Substring Solution 考虑容斥，设Gn,kG_{n,k}Gn,k​表示长度为nnn的字符串中有至少kkk个bitbitbit子串的方案数， 则有 Gn,k=(n−2kk)26n−3kG_{n,k}=\begin{pmatrix}n-2k\\k\end{pmatrix}26^{n-3k}Gn,k​=(n−2kk​)26n−3k 那么根据容斥原理，可以推出Fn,kF_{n,k}Fn,k​和Gn,kG_{n,k}Gn,k​的关系如下 Fn,k=∑j≥k(−1)j−k(jk)Gn,j=∑j≥k(−1)j−kj!k!(j−k)!Gn,jF_{n,k}=\sum...

H. Take the Elevator Solution 上行下行两个方向显然分开考虑，一次上下取两者需要移动距离的较大值。 考虑上行时，上升高度取决于最大的bib_ibi​，因此考虑将bib_ibi​大的先满足，在取满mmm个bib_ibi​最大的之后，考虑用大根堆维护已选乘客的aia_iai​最大值，接下来可以将bj≤max⁡{ai}b_j\le \max\{a_i\}bj​≤max{ai​}的乘客加入（相当于有人在iii上电梯前下电梯），持续维护直到无法找到jjj。 考虑下行时，上升高度取决于最大的aia_iai​，因此考虑将aia_iai​大的先满足，在取满mmm个aia_iai​最...

C. Grab the Seat! 题解 观察数据范围发现qqq很小，O(n)O(n)O(n)的复杂度可以通过，考虑对每次询问分别独立地去求解。 观察出一个重要性质：一个被占的座位与屏幕两端连线所夹的区域以外都是会被挡住的点（动手画一画就能看出来）。 实际上，一个被占的座位所去掉的点可以被分成三个部分：只被与(0,1)连线所决定的部分、只被与(0,m)连线所决定的部分、同时被两条连线决定的部分，这就相当于将与(0,1)连线确定的部分和与(0,m)连线确定的部分求并。 那么如何维护一条线决定的部分呢，不难发现对于y相同的座位，最终没有被去掉的座位一定是从(1,y)开始的一段连续区间，而所有连线都...