[title]1001 Love[/title] 循环找到每一个的字符串的下划线，后面的字符就是姓了。按照顺序输出即可。 [title]1002 Instruction[/title] 先考虑编码，首先找到operation对应的编码，如果是SET就找后面的一个R后面跟着的数字a,令b=0，否则找后面第一个R后面的数字当作a，第二个R后面的数字当作b，最后依次输出operation二进制编码，a, b的二进制编码。 再说解码，先将前6位，中间5位和后面5位转化成十进制记为oid, a, b。如果$oid < 1||oid > 6$就是Error!,如果$oid < 6$那么a,b都不能为0，如果oid==6那么a!=0&&b==0。其它情况都是Error!,最后按照oid,a,b输出指令即可。 [title]1003 HeHe[/title] 此题的数据规模为1000，普通的矩阵乘法无法通过。要优化，考虑到矩阵的特殊性，使得优化成为了可能。 ans[x][y]就是 a[y]*a[2*n-x] + .... + a[y+n-1]*a[n-x+1] 乘的这部分 a[i]*a[j] i+j是定值 所以 对于i+j等于某个数的，求个前缀和 最后每个值就O(1)得到了 于是最后总复杂度为o(n^2) [title]1004 Counting problem[/title] 设计一个函数G统计0到n之间有多少合法的就行 答案就是G(b)-G(a) 设n有len位 先暴力统计出0到10^(len-len/2)每一个数字的f(x,k)并插入hash表。 然后把n分成前面len/2位和后len-len/2位。前半段枚举，后半段在hash表中查找。 这样总的复杂度是sqrt(n)*C.C是hash表查找的常数 也可以把hash改成二分查找。复杂度是sqrt(n)*log(n)

[title]1001 Harry And Physical Teacher[/title] 这是去年一个学妹问我的物理题。我是这样考虑的：题目告诉我们，小球和车发生的是完全弹性碰撞，那么动能是守恒的，而碰撞过程中，动量也守恒。联立动能守恒，动量守恒方程。然后还有一个很特殊的条件，车的质量远大于小球，那么结合下实际情况，一个质量很小的物体撞质量很大的物体，大的物体的速度是不会发生变化的。有了这个条件，就可以求解了。推导过程如下： 用$V$表示碰撞前车的速度，$V'$表示碰撞后车的速度；用$V_0$表示碰撞前球的速度，用$V_0'$表示碰撞后球的速度；用$M$表示车的质量，用$m$表示球的质量。($M >> m$) $\qquad \left \{ \begin{matrix} \frac{1}{2}MV^2 + \frac{1}{2}mV_0^2 = \frac{1}{2}MV^{'2} + \frac{1}{2}mV_0^{'2} \quad ① \\ MV + mV_0 = MV' + mV'_0 \quad ② \end{matrix}\right.$ $\ \Rightarrow \left \{ \begin{matrix} \frac{1}{2}M(V+V')(V-V') = \frac{1}{2}m(V_0+V_0'(V_0'-V_0)) \quad ③ \\ M(V-V') = m(V_0'-V_0) \quad ④ \end{matrix}\right.$ 由$④$可将$③$约成$V+V'=V_0+V_0'$ 然后将$V'$视作$V$，可得$V_0'=2V-V_0$ [title]1002 Harry And Dig Machine[/title] 由于Harry的dig machine是无限大的，而装载石头和卸载石头是不费时间的，所以问题可以转化成：从某一点出发，遍历网格上的一些点，每个点至少访问一次需要的最小时间是多少。这就是经典的旅行商问题，考虑到我们必须要遍历的点只有不到10个，可以用状态压缩解决。 $Dp[i][j]$表示i状态的点被访问过了，当前停留在点j 需要的最少时间。枚举另一点不在i状态内的点k，从点j节点走向点k，状态转移 $Dp[i|(1 \ll k)][k] = min ( Dp[i|(1 \ll k)][k] , Dp[i][j] + Dis(j,k) )$ 其中$Dis ( j , k )$表示点j与点k的最短距离，这个可以通过坐标O(1)计算得到。若有t个点包含石头，则算法复杂度为$O(n*m+(t^2) * (2^t))$。 [title]1003 Harry And Math Teacher[/title] 我们可以把第i层跟第i+1层之间楼梯的通断性构造成一个2*2的通断性矩阵，1表示通，0表示不通。那么从第a层到第b层，就是将a到b-1的通断性矩阵连乘起来，然后将得到的答案矩阵上的每个元素加起来即为方案数。想到矩阵的乘法是满足结合律的，那么我们可以用线段树来维护矩阵的乘积。每次我们只会修改某一个楼梯的通断性，所以就只是简单的线段树单点更新，成段求乘积而已。 整体复杂度$2*2*2*nlogn$ [title]1004 Harry And Biological Teacher[/title] 这题稍难，题意是有一个字符总数小于等于100000的字符串的集合，然后有100000次询问，每次询问一个二元组{a,b}，表示询问字符串a的后缀与字符串b的前缀最长能匹配多少。我的解法也比较复杂，先将字符串集合建成trie树，然后用trie树建立后缀自动机。然后将询问全部离线出来，然后对于询问中，b相同的，我们一起进行处理（根据b排序，相同的排在一起）。我们考虑某一组{a,b}，这组询问的答案，我们怎么到后缀自动机上去找呢？首先，我们可以找到a在自动机上所对应的节点，考虑后缀自动机的parent tree，那么从这个节点，往上一直到根的链上，所有的节点所包含的子串，都是a的后缀。故而，我们只需要看这个链上有没有b的前缀，如果有，最长是多少。那么我们来看b的所有的前缀，首先，我们可以找到所有的b的前缀在自动机上对应的节点，对于b的长度为j的前缀，令它对应在后缀自动机上的节点为v，那么在parent tree中，v的子树下所有的节点都有可能以j为答案。这里就用到线段树的成段更新，单点求最大值就好了。 整体复杂度为$O(nlogn)$。 其实后来想想，完全是我做复杂了，这题其实用AC自动机即可，只要把上述题解中的后缀自动机完全替换成AC自动机。。。不过标程已经写好了就没改 另外这题elfness学长提出了一个nsqrt(n)的算法，可能数据不是很强，elfness的程序跑的比我的快。。。 还有感谢何阳的耐心帮助，以及elfness提出的一些建议。

[title]1001 Beautiful Palindrome Number[/title] 做法1. 对于数字长度为$L \leq 18$的Beautiful Palindrome Number有$C^9_{(L+1)/2}$个，所以打表就可以了。比如长度为3的Beautiful Palindrome Number数目就是从1-9中选取2个数字$C^9_2$。 做法2. 暴力判断每个数字是否满足，因为$n<1000000$。 做法3. 手算一下，因为最大的已经给出了。 [title]1002 Operation Sequence[/title] 注意到查询次数不超过50次，那么可以从查询位置逆回去操作，就可以发现它在最初序列的位置，再逆回去即可求得当前查询的值，对于一组数据复杂度约为O(50*n)。 [title]1003 Find Sequence[/title] 首先考虑解的结构一定是$C_1, C_1, \ldots, C_1, C_2, C_3, \ldots, C_m$这种形式，其中满足$C1 < C_2 < C_3 < \ldots < C_m$ 所以对$a_1, a_2, a_3, \ldots, a_n$去重后从小到大排序得到$c_1, c_2, c_3, \ldots, c_x$其中x是sqrt(M)级别的，用DP[i][j]表示以$c_i$和$c_j$结尾的满足条件的最长序列 首先初值化 $DP[i][i] = count(ci)$ 即$c_i$在原序列中的个数。 而$dp[i][j] = max(dp[k][i]$ 其中$k \leq i$还满足$c_i-c_k \leq c_j-c_i) + 1$ 这样的复杂度是 O(x^3),在题中x最大为1000级别所以会超时，要使用下面优化 因为 $dp[i][j] = max(dp[k][i]$ 其中$k \leq i$还满足$c_i-c_k \leq c_j-c_i) + 1$ $dp[i][j+1] = max(dp[k][i]$ 其中$k \leq i$还满足$c_i-c_k \leq c_j+1-c_i) + 1$ 注意到$c_{j+1}> c_j$ 所以满足$c_i-c_k \leq c_j-c_i$的dp[k][i]必然满足$c_i-c_k \leq c_{j+1}-c_i$因而不必重复计算 即最后复杂度可以为O(x^2). [title]1004 Oh! My math home work[/title] 对f(x)求导得到f’(x)和f’’(x) f(x) = A*x*x - B*sinx ; f'(x) = 2*A*x - B*cosx ; f''(x) = 2*A + B*sinx 当A或者B 等于0 都好办，注意输出 x是大于等于0的最小值, 还有A和B都等于0的情况也得注意一下。下面讨论它们均不为0: 1. 对于 x 属于 [0,pi/2], $f''(x) > 0$, f’(x)是先-后+,因而f(x)是先减后增，那么找到极值点后，只需2次2分判断y是否在这个区间。 2. 对于 x 属于 [pi/2,3*pi/2], $f'(x) > 0$, f (x)是增的，那么只需2分判断y是否在这个区间。 3. 对于 x 属于 [3*pi/2,5*pi/2], f''(x)是增函数,则f'(x)可能是先减后增，f(x)可能是先增后减再增，只需求出两个极值点后，然后进行3次2分判断y是否在这个区间即可。 4. 重复步骤2-3向后移动pi个单位,当$f(x) > y$还没发现解说明解不存在。 Chenyuehang大牛给的解法是: 以Pi/2为区间，每个区间内部的话，理论上$Ax^2$ 和 $Bsinx+Y$应该最多就只能有两个交点，那么分成三段考虑，如果某段有解的话，$Ax^2-Bsinx-Y$肯定是单调的，所以二分就行了 PS.验题人elfness和管理员herobs是非常负责的，验题过程将1000分题的难度降低2次，然后去掉了约瑟夫环的题，最后因为发现成题换了2次2500题就成就这样咯。。。 最后感谢elfness和herobs的建议和帮助，还有xiaoshua,yangjian和chenyuehang帮我验证题目和chenxiaoyue帮我修改题目描述，以及感谢各位参加这场比赛!!!

[title]1001 So easy[/title] 先对两个集合进行排序，去重，然后比较里面的数字是否一样。 [title]1002 Help him[/title] 先判断第一个是否负号。 如果是把第一个符号拿掉之后判断后面的长度是否<=12,并且是否数字，然后转化成数字看看是否在[a,b]，注意-0这个数据。 如果不是判断长度是否<=12,并且是否数字，然后转化成数字看看是否在[a,b] [title]1003 War[/title] <img src="/images/solution/542-1.png"></img> 首先要求出球体和圆柱体之间的相交的体积。 然后总体积减去相交的体积就是并的体积。 求交的体积可以如上图，想像成一个矩阵和一个圆相交部分绕X轴旋转而成的一个东西，就是上图阴影部分绕X轴出来的一个东西。 然后体积公式为 $\int^{HR}_0 \ 2 \pi y*2 \sqrt{R^2-y^2}dy = - \frac{4}{3} \pi (R^2-y^2)^{3/2}|^{HR}_0$ 总共有五种情况，还有四种情况是 <img src="/images/solution/542-2.png"></img> 这个直接计算中间的球体即可。 <img src="/images/solution/542-3.png"></img> 直接计算圆柱体。 <img src="/images/solution/542-4.png"></img> 这个可以直接套用公式，把HR改成R。 <img src="/images/solution/542-5.png"></img> 分成黄公和灰色两部分计算，灰色部分是圆柱体好算。 黄色部分可以套用公式： $\int^{HR}_{r_0} \ 2 \pi y*2 \sqrt{R^2-y^2}dy = - \frac{4}{3} \pi (R^2-y^2)^{3/2}|^{HR}_{r_0}$ 其中$r_0 = \sqrt{R^2 - HZ^2}$ [title]1004 Not only STL[/title] 第四题刚开始是的数据范围是15的，采用的是n*15*15*15的算法，题目难度比较小。后来elfness说有n^2的算法，数据改成了2000，我们还特意构造数据卡 JAVA大数。 解题报告如下： 定义dp[i] 表示从第i 位到第n 位的所有元素任意重排的方案数，val[i]表示从第i 位到第n 位的数列从当前排列，直至完全降序排列的方案数（含本身， 例如2; 1; 3, val[1] = 4），那么这两个值均可由递推得到，根据排列组合的公式，dp[i] = dp[i+1]*(n+1-i)/(从第i位到第n位中a[i]的个数)， 而val[i] 可以通过枚举第i 位的值来获得，枚举第i 位的值从a[i] + 1 到2000，设为temp，由于第i 位的数值增大，后面从i+1 到n 位的元素可以任意排 列，方案数同样根据公式为dp[i]*(从第i位到第n位中temp的个数)/(n+1-i)，当第i 位不变时，方案数即为val[i+1]，因此可以通过递推在O(n^2) 的时间内求出val[1] 到val[n] 的值。 设题目所需的next_permutation 次数为m，当统计val[i] 的某个时刻（即一边枚举第i 位的值从a[i] + 1 到2000 一边更新答案的时候），发现 有当前的$val[i] > m$，说明最终答案中第i 位的值应该是当前枚举的值，而且第i 位之前的元素均保持不变，那么反过来从前往后枚举每一位的答案（ 每个位置取某个特定值时，后面元素任意排列的方案数计算方法之前已经给出），比如当第k 位取x 时，后面元素重排列的方案数为tval，若$tval <= m$，说 明第k 位应该获得更大的值，故将tval 从m 中减去，继续 枚举，否则开始枚举k + 1 位，注意在这个过程中更新维护dp 数组的值。为了避免产生上溢出，如果当前$dp[i] > m *2000$ 时，显然只要当前位的a[i] 存 在增大的可能（即不是完全降序），必然有$val[i] > m$，因此直接将a[i] 替换为下一个可行的数值，并将后面元素排序，更新m，重新求一遍解，此时求解 必有dp[i] 恒等于val[i]，因此只要$dp[i] > m$，一定有$val[i] > m$，因此避免了溢出问题。 注意m 可能会超过val[1]，此时将val[1] 从m 中减去，并模dp[1]，然后将原数组整体排序，重新求解即可，取模时同样注意溢出问题，如果$dp[i] > m* 2000$ 在之前成立，则不执行取模语句。 最后，非常感谢elfness在验题过程中为我提出了许多宝贵的意见，还有何阳的耐心帮助。

[title]1001 Alice and Bob[/title] 两个人的坐标系不同，如果都走到（x，y）能够碰面的话，只有一种可能：在广场矩形的中心位置。 即： 2*x == N 并且 2*y == M。 [title]1002 Bob and math problem[/title] 题目要求将N个数字（每个数字都是0...9）组合成一个整数。 满足以下三个条件： [1] 这个整数是一个奇数； [2] 且没有前导0； [3] 找出最大的那个满足[1][2]条件的奇数。 解法： 贪心策略。 1、先对这N个数字从大到小排序，得到的序列是一个最大的整数（但它可能还不是奇数）。 2、然后找到最小的一个奇数数字，放到最后一位，即可得到我们所求的最大奇数了。如:"98764" --> "98647"。 3、请注意前导零的情况。如:"900" --> "009" 就非法了，应该输出-1。 [title]1003 Boring count[/title] 枚举字符串下标i，每次计算以i为结尾的符合条件的最长串。那么以i为结尾的符合条件子串个数就是最长串的长度。求和即可。 计算以i为结尾的符合条件的最长串两种方法： 1.维护一个起点下标startPos，初始为1。如果当前为i，那么cnt[str[i]]++，如果大于k的话，就while( str[startPos] != str[i+1] ) cnt[str[startPos]]--, startPos++; 每次都保证 startPos~i区间每个字母个数都不超过k个。ans += ( i-startPos+1 )。 时间复杂度O(n) 2.预处理出所有字母的前缀和。然后通过二分找出以i为结尾的符合条件的最长串的左边界。时间复杂度O(nlogn)，写的不够好的可能超时。 [title]1004 Argestes and Sequence[/title] 方法一： 可以分块统计，块节点内数据：cnt[d][p]：d位为p的数字个数，num[i]：记录数字。 时间复杂度O(n * sqrt(n)) 方法二： 离线算法：读取全部的操作，将更新与询问操作别分存起来，并且询问操作位数不同的位也分别存起来，即开长度为10的数组，分别存1~10的询问，更新操作统一存起来就好了，操作的先后顺序不要变。 用树状数组维护每一位的区间和。 然后遍历1~10位，对于当前位遍历当前位的询问操作，对于每个询问 在询问之前要把该询问操作之前的更新操作插到树状数组中。