腾讯音乐2023暑期实习生招聘后台开发

第一题

标签：dfs、双指针

题意：给一棵树节点个数为n，现为每个节点赋权，要求每个节点权值不同、权值范围为1~n、奇数层节点权值和与偶数层节点权值和差值的绝对值不超过1。

思路：首先把奇数节点和偶数节点存储起来，得到奇数和偶数节点的个数分别为$n_1,n_2(n_1+n_2=n)n\_1,n\_2(n\_1+n\_2=n)$。设权值和为$A={\sum }_{i=1}^{n}iA\; =\; \backslash sum\_\{i=1\}^\{n\}\; i$，不难发现奇数节点的权值和为$\frac{A}{2}\backslash frac\{A\}\{2\}$或者$A-\frac{A}{2}A\; -\; \backslash frac\{A\}\{2\}$，且当奇数节点存在一个方案则偶数一定存在一个对应方案，因此只需要考虑奇数节点即可。
此时问题转换为，1~n中选取$n_{1}n\_1$个数$x_1,\mathrm{.}\mathrm{.}\mathrm{.},x_{n_1}x\_1,...,x\_\{n\_1\}$，使得${\sum }_{i=1}^{n_1}{x}_i=\frac{A}{2}\mathrm{或}=A-\frac{A}{2}\backslash sum\_\{i=1\}^\{n\_1\}\{x\_i\}=\backslash frac\{A\}\{2\}或=A-\backslash frac\{A\}\{2\}$。下面只以$\frac{A}{2}\backslash frac\{A\}\{2\}$为例解释，$n_{1}n\_1$个数和应满足条件${\sum }_{i=1}^{n_1}i\le \frac{A}{2}\le {\sum }_{i=n-n_1+1}^{n}i\backslash sum\_\{i=1\}^\{n\_1\}i\; \backslash leq\backslash frac\{A\}\{2\}\backslash leq\; \backslash sum\_\{i=n-n\_1+1\}^\{n\}\{i\}$，即$n_{1}n\_1$个数和范围的最小、最大。当在这个范围内则一定有解（我猜的，不会证明）。

当满足条件进行赋权过程，构造一个bool数组$st[n]st[n]$标记赋给奇数的值，初始$n_{1}n\_1$个节点权值赋为$1,\mathrm{.}\mathrm{.}\mathrm{.},n_{1}1,...,n\_1$即最小的情况，并维护两个指针$l,rl,r$初始$ll$指向$n_{1}n\_1$，r指向$nn$，每次用$rr$指向的值预替换$ll$指向的值，若替换后超过目标值（即$\frac{A}{2})\backslash frac\{A\}\{2\})$则$ll$左移，若替换后不超过目标值则直接替换，并将$l,rl,r$左移并设$st[l]=true,st[r]=flasest[l]\; =\; true,st[r]=flase$，直到等于目标值。此时标记结束，为true的赋值给奇数节点、为false的赋值给偶数节点即可。

第二题

标签：二分答案

题意：只有小写字符的字符串，设字符串的长度为n、字符串字符种类数为m，如(aabc，n=4 m=3）则字符串的价值为n*m。现给一个字符串s，需要将字符串分为连续的k份，得到k个子串$s_1,\mathrm{.}\mathrm{.}\mathrm{.},s_k\mathrm{（}s=s_1+,\mathrm{.}\mathrm{.}\mathrm{.}+s_k)s\_1,...,s\_k（s=s\_1+,...+s\_k)$。现请最小化 k个子串价值的最大值。

思路：k个子串实际就是每次划分后的前缀。设子串价值最大值为Max_Val，初始化$l=0,r=26\ast 500000l\; =\; 0,r\; =\; 26\; *\; 500000$，现二分Max_Val，取$m=\frac{l+r}{2}m\; =\; \backslash frac\{l\; +\; r\}\{2\}$每次check取最长前缀$s_{i}s\_i$使得$s_{i}s\_i$的价值小于等于m，若划分的子串个数小于等于k则更新$r=mr\; =\; m$，否则更新$l=m+1l\; =\; m\; +\; 1$。最终输出$ll$即可。

第三题

标签：水题

给一个字符串s，求$s_i=s_{i-1}s\_i\; =\; s\_\{i-1\}$的对数，for循环一遍判断计数就行。