## sequence1 按照题目要求，枚举任意两个数检查是否符合题意。 值得注意的是一开始所有数先对$b$取模这个方法是错误的。 ## sequence2 我们可以通过$dp[i][j]$表示第$i$个数，当前这个数为序列中的第$j$个数的方案总数。 转移为$dp[i][j] = sum{dp[k][j-1]}(k < i, b_k < b_i)$。 本题需要高精度。 ## matrix 令$dp[i][j]$表示当前走到第$i,j$个位置的最小贡献，我们可以假定$(i+j)$为奇数，由该状态可以转移向最多$4$个位置，就可以了。 ## balls 考虑贡献$x^{2}$即为颜色相同的对数，因此只要考虑任意两个球颜色相同的概率，将这些概率加起来就是答案了。通过一些方法可以做到与读入同阶的复杂度。 ## tree 异或可以按位考虑，所以这里只考虑$a_i$为$0$或$1$。 考虑修改$i$号点$a_i$的值，那么答案需要减去所有点$j(a_j = a_i \ xor \ {1})$到点i的距离，再加上所有所有点$j(a_j = a_i)$到点$i$的距离。 这里考虑用点分治来维护这些路径。对于点分治树，根及其儿子节点记录其子树中$a$值分别为$0$、$1$的数量和$a$值分别为$0$、$1$的到根的距离的总和。对于每一个点，记录在每一棵点分治树中到根的距离和点$j$(他的祖先，根节点的儿子)。 查询时，设查询点为$x$，根为$y, z$为$x$的祖先、$y$的儿子，那么贡献为： “$y$的子树中$a$值为$a[x] \ xor \ 1$的数量*$x$到$y$的距离”+“$y$的子树中$a$值为$a[x] \ xor \ 1$的点到$y$的距离和”-“$z$的子树中$a$值为$a[x] \ xor \ 1$的数量*$x$到$y$的距离”-“$z$的子树中$a$值为$a[x] \ xor \ 1$的点到$y$的距离和” 对于修改，只需在每棵点分治树中修改对应根和记录点的数据即可。 时间复杂度$O(nlogn*$位数)

感谢bc，感谢验题组的帮助。 // uwi码力太神辣！orz。 ## Clarke and food 可以证明从小到大一直拿，拿到不能拿为止是最优的。 所以排序一下即可。 ## Clarke and five-pointed star 容易看出只需要判断这5个点是否在一个正五边形上。 因此我们枚举排列，然后依次判断即可。 判定方法是，五条相邻边相等，五条对角线相等。 当然题目给的精度问题，窝只能说，如果泥做法不复杂，精度足够好的话，是可以过的。毕竟题目说的小于$10^{-4}$是指理论上的，所以理论上适用所有的数之间的比较。所以有人问我开方前和开方后，我只能说，哪个精度高用哪个.... 当然你也可以先求出凸包然后再判相邻距离...... ## Clarke and digits 考虑dp，令$d(i, j, k)$表示长度为$i$第$i$位为$j$余数为$k$的方案数，则$d(1, j, j \ mod \ 7) = 1, 0 < j < 10$, $d(i+1, x, (k * 10+x) \ mod \ 7) += d(i, j, k)$。发现转移相同，所以我们用矩阵快速幂来计算即可。题目要求前缀和，那么我们在矩阵里加一维就行了。 ## Clarke and baton 我们首先计数排序，即开个可变长数组a来将所有值为i的下标按顺序存入a[i]中。然后再开个可变长数组b，用b[i]来存储由a[i+1]降到i的数。然后考虑从大到小枚举值i，首先从b[i]和a[i]中找一个下标最小的数j，弹出，更新了这个j的值后，插入到b[i-1]中。依次类推即可。时间复杂度$O(Tq)$。 由于标程常数大的原因，标程被各种带log的虐。发现很难卡（出题人懒癌），所以放过了= =。 ## Clarke and room 考虑离线： 考虑树链剖分，对于每一次询问，我们把路径上的$O(logn)$条路径的线段树打上标记。离线处理完。 之后枚举每一个被标记过的线段树，建立ac自动机，然后更新答案即可。复杂度$O((m+|S|)log^2n+nlogn)$ 当然也可以用欧拉序+离线分块+lct做到$O(mn^{0.5}log|S|)$ 友情提示别爆栈哦 其实这题可以在线，由于种种原因题目还是给离线过了，orz Claris 在线做法就是我们先树链剖分，得到dfs序$dfn(x)$，那么我们对所有$name$建立ac自动机。然后对于自动机上的每一个结点，建立一个主席树$T(x)=T(fail(x))+w(x)$，主席树维护的区间是dfs序。假设在这个自动机对应的原树结点为$y$，则$w(x)$表示在$dfn(y)$这个地方更新主席树的值为$len(x)$。这样预处理完后，每一次查询一个串，我们只需要将这个串在自动机经过的点中查询主席树中对应的树剖区间即可。复杂度$O(|S|log^2n)$。

# Numbers 先排序然后从大到小枚举i，把右边的数用一个数组标记其出现过，再枚举左边的数判断其加上Ai是否出现过. # Game 无解的情况只有起点和终点位置一样且N不为1。终点和起点都在边界上答案为0，如果起点在边界上或者起点终点相邻答案为1，其他答案为2. # Subtrees 一颗完全二叉树，左右子树都会为完全二叉树，其中必然有一个最后一层是满的。对于最后一层是满的完全二叉树，每一层的节点的子树形态都是相同的，只统计logN种，然后递归处理另一颗子树。最后对记录下的所有子树根据节点数判重. # Product 把N化成$N=\prod_{i=1}^{k}{{p}_{i}}^{{a}_{i}}$，其中p为互不相等的质数，则含${p}_{x}$个数为j的约数有$\frac{\prod_{i=1}^{k}({a}_{i}+1)}{{a}_{x}+1}$个,而j的取值范围是0到${a}_{x}$,从而得到${p}_{x}$在所有约数中出现了$\frac{(1+{a}_{x}){a}_{x}}{2}*\frac{\prod_{i=1}^{k}({a}_{i}+1)}{{a}_{x}+1}$次。根据费马小定理${a}^{p-1}\equiv 1(mod p)$,统计${a}_{x}$时可以对p-1取模，由于后面还要除2，所以先对2(p-1)取模。求$\frac{\prod_{i=1}^{k}({a}_{i}+1)}{{a}_{x}+1}$部分时不能取逆元，可以分别对前缀和后缀计算积。计算出N包含的所有质因子出现次数后用快速幂统计一遍，复杂度$O(NlogN)$. # Lie 根据左右边同班同学的人数可以得知其班级人数和其在班上相对位置，只有班级人数相同才可能为同一个班级，而在同一个班级的人出现矛盾的只能是班上相对位置相同。先根据班级人数排序，对于班级人数相同的统计每个相对位置上有多少人，枚举人数为x的班级有y个，当y确定的时候就可以贪心得出最大不矛盾数量。这就转化成了分组背包，最后使得挑选出来的年级人数不超过N即可。复杂度$O({n}^{2})$.

感谢BC管理员胡杰给我的不懈帮助，感谢BC验题组的验题和建议。 这次比赛有选手觉得题意不太清楚，我表示特别的抱歉。（本人语文不好><） # 1001 GT and sequence 注意先特判$0$的情况：如果读入的数据有$0$，那么去掉所有的$0$且最后答案和$0$取一个max。 剩下的正数显然全部乘起来比较优。 对于负数的话，如果个数是奇数个我们就去掉绝对值最小的那一个，然后全部乘起来即可。 # 1002 GT and numbers 如果$A$大于$B$那么显然无解。 考虑把$A$和$B$分解质因数。 若$B$存在$A$没有的质因数也显然无解。 对于某一个$A$的质因数的次数。为了加速接近$B$，它一定是每次翻倍，最后一次的时候把剩下的加上。 那么答案就是最小的$k$使得$2^{k}*A_{num} \geq B_{num}$。 最后把每个质因数的答案max起来即可。 感觉本场比赛没有trick（雾~），我就打算加入一个很经典的trick： $B$可以刚好等于$2^{63}$，这样就要开unsigned long long。 同时我还在题目里特别提醒了“注意M的范围” 可惜仍然有很多选手没有注意。 这里我表示歉意，也希望你们以后可以更加仔细一点。 # 1003 GT and set 可能一些选手题意不是很清楚，我这里再提供一个转化后的问题： 给出N个集合。每次你可以指定一个数，然后所有包含这个元素的集合可以被删掉。 问你能否经过最多L轮操作使得所有集合都被删掉。 因为$L$只有$5$，考虑直接dfs。 对于第一个集合，我们枚举它的那个公共的数是多少。 然后线性扫描过去，找到接下来第一个没有这个数的集合。 （它显然不能通过这个公共的数与第一个数在同一个部分） 对于这个集合，再枚举它公共的数是多少，然后线性扫描过去找到第一个没有这两个数的集合…… 这样重复$5$次后如果还是没有，就直接NO好了。若中途扫完序列就是YES。 这样最坏的效率就是$O(N*10^{5})$，足以通过此题。 其实我们可以预处理使得效率变成$O(10^5)$ ><然而出题人很良（lan）心（duo）。 # 1004 GT and strings 其实这题就是一个大暴力。 首先可以证明：如果对于每次询问，计算的效率是$min(|Si|,|Sj|)$， 且把同样的询问记下来（map记忆化），效率是正确的。 我就感性地证明一下。首先我们来考虑如何hack这个算法。 首先因为效率是min的，我们询问的时候要尽量做到两个串长度一样。 （如果不一样的话，还不如把大的串分给小的串一点。) 那么数据一定是之前有一堆一样长且比较长的串（后面可能还存在较短的串凑数）。 设有P个比较长的串，有效的两两询问只有$P^2$级别的。 那么效率就是$min(P^2,100000)*(L/P)$ 当$P = sqrt（N）$的时候取到最大效率$O(N^{1.5})$。 所以这道题直接按$min(|Si|,|Sj|)$计算即可。 对于子序列，直接建一个“序列自动机”（第$i$个点以后$j$字母第一个出现的位置）跑一下。 对于子串，我们就可以AC自动机或SAM预处理再做，总之很模板。 # 1005 GT and trees 众所周知，众数是一个很难搞的东东，很难用数据结构维护。 这里采用的是树上莫队的方法，由于还带修改，所以效率为$N^{5/3}$ （$N$和$Q$同阶） 现在考虑维护这样一个操作：每次加一个数或者删除一个已经出现了的数，在线询问现在次数最大的数是多少。 本来可以很方便地开一个线段树维护一下，但是之前的效率已经很满了，加个log显然会T。 为了降下插入和删除的效率，我们可以利用块状数组。 具体的做法是：记$f[i]$表示权值i出现的次数，$size[i]$表示出现了$i$次的权值个数。 然后对于$size$的下标我们分块，假设块的大小为$S$，记$best[i]$表示$\sum size[k]$，其中$(i-1) * S + 1 \leq k \leq i*S$ 每次加入和删除一个点的时候，只需$O(1)$更新f和size和best数组。 查询的时候，我们倒序扫描每个块$i$，若$best[i] > 0$那么答案肯定在这个块中。然后再在这个块里暴力寻找最后一个$size[i] > 0$的$i$即可。 这样效率就是$O(N^{5/3}+N^{3/2})$

## SDOI By davidlee1999WTK 直接按照题意计算出最后每名选手的最终得分，接着按最终得分排序。 先找出来一个得分最高的女生，然后找出其余的选手中得分最高的$m-1$个人，把所有进入省队的选手再按分数重新排一下序，最后输出即可。 ## Reorder the Books By davidlee1999WTK 把这题的模型简化一下，有一个$1\rightarrow n$的排列形成的数列，我们要用最少的操作次数把这个数列排序，每次操作都是把一个数放到整个数列的最前面。 首先我们可以注意到每个数最多只会被操作一次。因为假如有一个数被往前拿了两次，显然第一次的操作是没有意义的。 然后能发现一定先操作大的数，再操作小的数。因为假如先把小的数放前面去了，再把大的数放前面去，小的数就又在大的数后面了，小的数必定还得再操作一次，然而操作两次是不划算的。 到这里，对于19的数据范围，我们有一个很暴力的做法，$2^n$枚举要操作哪些数，这些操作按数的大小从大往小的顺序，模拟一下，然后检查一下最后的序列是否有序，复杂度$O(n*2^n)$。 我们很快又能发现，假如操作了大小等于$k$的数，那么所有小于$k$的数也都得操作了。所以我们不用2^n枚举，直接$m$从$1$开始从小到大枚举，表示要操作前$m$小的数，然后模拟，验证，这样复杂度为$O(n^2)$。 不过其实$m$也是不用枚举的。 首先可以发现最大的数$n$是不用操作的（其他数操作好了，数"$n$"自然就在最后面了）。 于是我们先找到最大的数"$n$"的位置，从这个位置往前找，直到找到$(n-1)$。假如找到头也没找到$(n-1)$，那么数"$(n-1)$"需要操作，而一旦操作了$(n-1)$，根据前面结论，总共就需要$(n-1)$次操作了;假如找到了(n-1)，那么数"$(n-1)$"也不需要操作（和数"$n$"不需要操作一个道理）。 同理，我们接着从$(n-1)$的位置往前找$(n-2)$,再从$(n-2)$的位置往前找$(n-3)$...假如数$k$找不到了，那么就至少需要$k$次操作。这种做法的复杂度是$O(n)$的 ## The Highest Mark By davidlee1999WTK 这道题考察的是贪心思想和动态规划。 首先我们考虑，假如我们已经确定了要做哪些题目，按什么顺序做这些题目最好。 假设已经确定了要做其中的$m$道题，某一个方案中做题的顺序是依次做$x_{1},x_{2}\rightarrow{x}_{m}$，那么对于这个方案中任意的相邻两项${x}_{i}$,${x}_{i+1}$,考虑交换这两项的顺序，方案是否会变得更优，交换方案中的相邻两项，只会对这两道题的得分有影响，对其余的题目不会产生影响。 如果不交换这两项，损失的分数是 $C_{x_{i}} * B_{x_{i+1}} + K$，如果交换这两项，损失的分数是$C_{x_{i+1}} * B_{x_{i}} + K$ (K是一个常数) 所以只需要判断是否 $C_{x_{i}} * B_{x_{i+1}} \leq C_{x_{i+1}} * B_{x_{i}} + K$，如果此不等式成立，那么应该交换这两项。对上式移项得 $B_{x_{i+1}} / C_{x_{i+1}} > B_{x_{i}} / C_{x_{i}}$ 。所以对于一个确定的题目集合，做题的最优顺序只与每道题目的$ B_i / C_i $有关，按每道题目扣分速度与做题时间的比值排序，按照比值从大到小做题。 因此我们先对所有的题目按照这个比值进行排序，接下来，只要按照排好的顺序，选择做哪些题目就可以了。这相当于一个简单的“背包问题”，使用动态规划来解决。${dp}_i$表示恰好用了$i$分钟的最高得分。状态转移方程为${dp}_i = \max_{1\leq j\leq n}{dp}_{i-C_j} + A_j - (i * B_j)$。 最终答案是$\max_{0 \leq i \leq t}{dp_i}$。 ## Candy Game By Evensgn 我们将最后装有糖果最多的盒子中的糖果数记作$A$。 令 $P(x)$ 为 $A \leq x$ 的概率，我们枚举 $i (1 \leq i \leq n + 1)$，如果能求出每个 $P(i)$，那么 $A = i$ 的概率就是 $P(i) - P(i - 1)$。 那么最后的期望 $Ans = \sum_{1}^{n+1}(i * (P(i) - P(i - 1)))$。 怎样来求 $P(x)$ 呢？我们用 $f_i$ 表示前 $i$ 轮游戏结束时，当前的 $A$ 不超过 $x$ 的概率（$f_{n+1}$ 表示全部 $n$ 轮游戏结束，当前的 $A$ 不超过 $x$ 且最终桌上剩余的糖果也不超过 $x$ 的概率），那么 $f_i$ 可以从 $i$ 之前的连续的一段 $f_j (i-x+1 \leq j < i) $转移过来。每个 $f_j$转移到 $f_i$ 时乘上的系数是不同的，但是这一段 $f_j$ 转移过来的和是可以在不断求 $f_i$ 的同时维护的。那么求出的 $f_{n + 1}$ 就是 $P(x)$。这样求一个 $P(x)$ 的时间复杂度是 $O(n)$ 的。 因此总的时间复杂度是 $O(n^2)$。 ## EarthCup By davidlee1999WTK 首先，我们检验一下所有队伍的积分的总和是否等于$n*(n-1)/2$，因为显然每场比赛有一个队伍获胜，积分总和应该等于比赛场数。 如果积分的总和不对，就说明一定被修改过，否则继续进行判断。 我们先来考虑数据范围是$n \leq 100$时的解法。我们可以建立一个网络流的模型: 对于每场比赛建立一个点，每支球队也建立一个点，S为源点，T为汇点: 1. 从S到每场比赛连一条容量为$1$的边 2. 每场比赛分别向它对应的两支球队各连一条容量为$1$的边 3. 第i支球队向T连一条容量为${a}_{i}$(第i支球队的积分)的边 假如求一次最大流，这个模型满流了，即总流量为$n*(n-1)/2$,那么就存在至少一种能够满足积分数据的比赛胜负情况，否则数据一定被修改过。 直观理解就是每场比赛有$1$个积分，这个积分要么分给参加这个比赛中的一支队伍，要么给另一支。 利用最大流合理分配每场比赛的胜利(就是每个积分)给球队，使每支队伍的最终积分符合给出的积分数据。 现在我们对这个模型做一点改动，我们把第$i$支队伍拆成${a}_{i}$个点，拆出来的每个点向T连一条容量为$1$的边，然后每场比赛向它对应的两支球队的所有拆出来的点都连一条容量为$1$的边。 在新的模型下，依然是可以满流时有合法方案。 现在的模型是一个二分图匹配模型，左右两部分点的个数相同，我们可以利用霍尔定理来判断能否有符合条件的匹配方案。 应用在这道题中霍尔定理的简单描述就是，对于二分图左边的任意$k$个点，检查右边与他们直接相连的点的个数是否大于等于$k$。详细的解释和证明可以在网上搜索。 对于这道题的模型，我们就可以把所有队伍按积分排序，检查所有积分前$k$小的的队伍积分总和是否大于等于$k*(k-1)/2$,假如检查$k$从$1\rightarrow n$一直都一直符合这个关系那么有合法方案，否则数据是一定被修改过的。 $k*(k-1)/2$是$k$支队伍之间所有比赛的场数，即对应这$k$支队伍之间表示比赛的结点的个数，这些结点只与这$k$支队伍对应的结点相连。 $k$支队伍的积分总和就相当于$k$支球队对应的结点的个数的总和。 其实这题有现成的定理，Landau's Theorem，用来判断一个得分序列是否合法。参见：https://en.wikipedia.org/wiki/Tournament_(graph_theory)#Score_sequences_and_score_sets