感谢一起出题的Miceren。感谢BC管理员和验题人的耐心帮助。 ## 1001 Movie 首先我们考虑如何选择最左边的一个区间 假设最左边的区间标号是$i$, 那选择的另外两个区间的左端点必定要大于$R_i$ 若存在$i$之外的$j$, 满足$R_j < R_i$, 那么另外两个区间的选择余地必定不会减少 因此，为了使另外两个区间有尽可能多的选择，我们选择一个右端点最小的区间作为最左边的区间是最好的 同理，我们选择一个左端点最大的区间作为最右边的区间，也将提供最多的选择 确定了这两个区间之后，只需判断是否存在一个区间位于它们中间且不交叉即可 本题的取模值十分特殊，用unsigned int的自然溢出可以达到同样的效果 时间复杂度$O(N)$ ## 1002 Cycle 此题中的环指的是每条边至多经过一次的环 对于问题1，我们只需要进行二分图染色判定这个图是否是二分图即可 二分图中必定不存在奇环，而非二分图中必定存在奇环 对于问题2，首先我们注意到一个环一定存在于双联通分量（既去掉任何一条边后仍然联通的点集）内 通过tarjan算法，可以分离出所有的双联通分量，然后分别检查其中是否存在偶环 对于一个双联通分量，如果它仅仅是一个环，那么只需判断它是否是偶环即可 否则其中必定存在两个缠绕（共享至少一个点）的环，若这两个环的都是奇环，那么去掉共享的边之后可以组成一个大偶环 因此，除非一个双联通分量仅仅是一个奇环，那么其中必定存在偶环 而我们可以发现，若一个非单点的双联通分量仅仅由一个环构成，那么它的点数必定等于边数，据此判断即可 时间复杂度$O(N~+~M)$ ## 1003 Segment 对于一种可行的排列（使BrotherK停下来的排列）$P$: 若存在$i, j$, 使得： $A_i~<~A_j,~B_{P_i}~>~B_{P_j}$ 那么即使我们交换$P_i$和$P_j$的值，被涂黑的区间仍然是一样的 因此我们可以不断进行这种交换，使得不存在满足 $A_i~<~A_j,~B_{P_i}~>~B_{P_j}$ 的$i, j$，并且这种交换始终不影响最终答案 到此可以发现，所有合法方案的答案都是一样的，并不需要计算概率 因此只需将A, B分别排序，若排序后存在$A_i > B_i$则说明没有合法的排列 否则直接计算出答案，并输出六位小数即可 时间复杂度$O(MlogM)$ ## 1004 Brackets 首先建立一颗线段树，每个节点存储两个值$R,~L$， 代表如果仅仅使用这个区间的括号，那么匹配结束之后剩下$R$个右括号和$L$个左括号，修改操作很容易实现 对于询问操作，我们首先可以在线段树上询问出消除掉匹配的括号之后，每种括号分别剩下多少个（显然，最后必定是'))..)(..(('这种形式），那么我们就知道了第K个括号是哪种类型的（或者不足K个括号，输出-1） 容易发现，如果我们从左向右访问线段树，那么')'的数目是不会减少的；同理，从右向左访问时'('的数量不会减少。如果答案是')'，那么我们从左往右访问，否则从右往左访问。（为了方便说明，我们假设第K个括号是')'，如果不是的话可以类似处理） 如果处理完一个区间，')'的数量不足K个，那我们继续处理下一个区间。如果处理完当前区间后')'的数量已经达到$K$个了，那么我们知道答案必定位于这个区间，计算一下便可以知道答案位于此区间的左半部分还是右半部分，然后我们就可以一路深入下去，直到区间中只有一个点，而这一步往下走的深度最多为线段树的层数 总时间复杂度为$O(QlogN)$ ## 1005 Game 令$F_i,_j$代表剩下$i$个人时，若BrotherK的位置是1，那么位置为$j$的人是否可能获胜 转移的时候可以枚举当前轮指定的数是什么，那么就可以计算出当前位置$j$的人在剩下$i~-~1$个人时的位置（假设BrotherK所处的位置是1），然后利用之前计算出的F值判定此人是否可能获胜 时间复杂度为$O(n^3)$ ## 1006 Repeating 考虑对于一个串$w$，总是存在一个最短周期$x$，使得$w = xxx...$(若干个相同串拼接而成，也可能只有一个$x$) 假设$w$是由$n$个$x$组成，那么判断$w$是否是素串（即不能分解成几个相同的串）的方法可以通过莫比乌斯函数来计算 把$n$的所有约数的莫比乌斯函数值加起来，当$n$为1的时候，也就是$w$是素串时，和为1，否则为0。 设$u(x)$为莫比乌斯函数。 那么一个自然的想法就是，我们对每一个$w$的拆分方式，比如$w = yyyy$($m$个$y$，很明显，$m$是$n$的约数)，我们把答案累加$u(n / m)$，即可得到最终的答案。 那么如何统计呢，可以发现重复子串的性质，如果$w$不是素串，那么把$w$的第一个字母放到$w$的末尾，它还不是一个素串，反之亦然。 由此受到启发，我们可以首先枚举一个周期长度$len$，然后把整个串$str$每$len$个字符分成一组，现在我们要考虑的就是，长度为$len$的倍数的，周期长度可以为$len$的那些串，并且根据它们各自的长度乘上不同的莫比乌斯函数，再累加起来就是我们可以得到的答案。 把之前区分的长度为$len$的字符串组，相同且连续的合并在一起，成一块，假设区间为$[l, r]$。用后缀数组，算出$[1, l - 1]$和$[l, r]$的最长公共后缀，假设是到$L$, 再算$[r + 1, length]$和$[l, r]$的最长公共前缀，假设到$R$。那么在$[L, R]$中，任意一个长度大于$len$，且为$len$倍数的串，都是周期可以为$len$的子串。通过简单的一些数学计算和莫比乌斯函数的预处理，可以高效的计算出我们要的累加和。 最后总体复杂度为$O(nlogn)$。 ## 1007 GAL 为了方便处理，我们首先把角色按照性格进行排序 考虑折半搜索的思想，我们选择一个$X$, 将$1$ ~ $X$的角色分开处理 因为角色已经通过性格排序了，那么除了中间的至多一种性格之外，其余的性格必须在它所属的那一部分被选到 如果存在一种性格在两部分都出现，假设其为性格$Z$。我们可以先忽略它的限制计算出一个答案。这个答案是不对的，因为它包含的方案中可能存在一些方案没有角色的性格是$Z$，那么我们直接抛弃那些性格为$Z$的角色，用类似的过程重新计算一次，就得到了上述答案包含的不合法方案的数量 那么怎么统计方案数呢？ 首先我们考虑一下$Face$属性的限制，如果一个$Face$仅在一个部分出现，那么在这个部分内检查合法性即可 而对于在两个部分中都出现的$Face$，这种$Face$最多有$min(X, N - X)$个，我们可以用一个二进制数来表示一种方案中，哪些$Face$出现过（每一位用1或0代表一种$Face$是否出现过） 对于大小为$X$的一个部分，一共有$2^X$种可行的选择，去除掉一些不合法的方案后，对于剩下的方案，我们可以计算出$Face$值的出现情况（一个二进制数）以及xor和 对于任意一种方案，我们需要知道在另一个部分中，有多少种方案xor和与其相同，并且$Face$值不冲突（既$Face$选择的集合是当前方案集合补集的子集） 那么可以对于另一个部分进行预处理，把每一种方案的$Magic$值插入其$Face$值集合的超集中，假设这一部分有X个角色，那么复杂度上界是$O(3^Xlog(3^X))$，而预处理完之后查询的复杂度是$O(2^(N - X)log(3^X))$ 需要注意的是，后半段的$Face$可能有重复的情况，那我们考虑，如果一种$Face$多出现一次，那么集合的大小将减少一半，枚举子集的复杂度将降低三分之二，而相同的Face集合出现次数最多增加两倍，因此复杂度将降低 通过合理调整X（例如在N = 32的时候，取X = 12）的值，整个算法复杂度约为$100wlog50w$，可以接受，而且实际上是比较松的 ## 1008 Occupation 以下解法需要一些基本的树链剖分知识 考虑在dfs的过程中，如果首先访问的是最大的子树，那么一条重链上的点其dfs序是连续的 容易发现，一颗子树的dfs序也是连续的 因此我们可以使用一个set维护当前未被覆盖的节点的dfs序，对于子树覆盖的操作直接删除一个区间内的点，对于链覆盖的操作可以分成若干条重链，对于每条重链删除一个区间内的点，并且在删除、增加点的过程中维护答案即可 直接做的复杂度是$O(Qlog^2N)$ 考虑到对于不同的重链可以分别维护一个set, 如果当前set已经是空的了（既这条链全部被覆盖），那么可以跳过这颗链 这种做法减少了二分的次数，通过势能分析可以得出复杂度$O(QlogN)$ ## 1009 Exploration 首先对于所有的无向边，我们使用并查集将两边的点并起来 若一条边未合并之前，两端的点已经处于同一个集合了，那么说明必定存在可行的环（因为这两个点处于同一个并查集集合中，那么它们之间至少存在一条路径） 如果上一步没有判断出环，那么仅靠无向边是找不到环的 考虑到，处于同一个并查集集合中的点之间必定存在一条路径互达，因此将一个集合的点合并之后，原问题等价于在新生成的有向图中是否有环 我们知道，有向无环图必定存在拓扑序，因此只需使用拓扑排序判定即可 时间复杂度$O(N + M1 + M2)$ ## 1010 GCD 首先，数组中每个元素至少是1 然后对于任意一个询问$L_i,~R_i,~Ans_i$, 说明$L_i$ ~ $R_i$中的元素必定是$Ans_i$的倍数，那么只需将其与$Ans_i$取最小公倍数即可 如果在计算过程中有一个值超出了可行范围，那么就无解了 在计算完成之后，注意这个解并不一定是正确的，还需要对于所有询问检查一遍 时间复杂度$O(NQlogX)$, $X$为值的范围

## 1001 Delete 用一个$cnt$数组记下每个数在$a$序列中出现了几次 在删数的时候贪心，尽可能删那些出现次数$>1$的数 这样就可以使最后有最多不同的数 ## 1002 Mutiple 从右向左查看序列 维护一个数组$p[1..10000]$表示该数上一次出现的位置 遇到一个数就暴力查看它的所有倍数，取最小值即可 时间复杂度为$O(n/1+n/2+...+n/n)=O(nlogn)$ ## 1003 Code 这道题需要一些莫比乌斯反演、线性筛的知识 定义$f(x)=x*(x-1)$ 题目所求即为$\sigma(f(gcd(ai,aj)|i!=j,1 \le i,j \leq n)$ 先用线性筛求出miu在[1,10000]的函数值 利用莫比乌斯反演公式我们可以$O(vlogv)$暴力求解出函数g在$[1,10000]$的函数值，其中$g$满足： $\sigma(g(d)|x\%d==0)==f(x)$ 这样所求答案即为： $\sigma(g(d)*cnt(d)*cnt(d)|1 \le d \le 10000)$，其中$cnt$函数满足： $cnt(x)=$在$a1, a2, ..,an$中是x的倍数的个数 而$cnt$的取值也可以$O(vlogv)$暴力计算出 所以总的时间复杂度就是$O(vlogv)$的 ## 1004 Lucky 这道题需要一些莫队算法的知识 定义记号$f(A,B)$表示询问区间A，B时的答案 用记号＋表示集合的并 利用莫队算法我们可以计算出任意$f(A,A)$的值 不妨假设$A=[l1,r1],B=[l2,r2],C=[r1+1,l2-1]$ 容易知道$f(A,B)=f(A+B+C,A+B+C)+f(C,C)-f(A+C,A+C)-f(C+B,C+B)$ 因此一个询问被拆成四个可以用莫队算法做的询问 总的时间复杂度为$O(msqrt(n))$

感谢提供大量出题思路的jsl422同学和测题人Immanuel。感谢BC管理员和验题人的耐心帮助。 ## 1001 Four Inages Strategy 判断空间上4个点是否形成一个正方形方法有很多，这里给出一种方法，在$p2,p3,p4$中枚举两个点作为$p1$的邻点，不妨设为$pi, pj$，然后判断$p1pi$与$p1pj$是否相等、互相垂直，然后由向量法，最后一个点坐标应该为$pi+pj-p1$，判断是否相等就好了。 另外，由于点都是整点，所以很多奇奇怪怪的方法是找不到数据hack的，如果以后碰到以浮点数读入的可要小心咯。 ## 1002 Greatest Greatest Common Divisor 由于出题人业(ying)界(yu)良(zhuo)心(ji)，题面十分简洁，给定一组数，取两个数，使得$gcd$最大，这里提供两种做法。 第一种先$nlogn$预处理出${10}^{5}$所有数的因子，然后用$cnt$数组计数给定数的因子个数，再找到最大的$i$，满足$cnt[i]>=2$，复杂度为$nlogn$。 第二种先用$cnt$计数给定数组，然后倒着枚举答案为$d$，计算$\sum_{k=1}^{{10}^{5}/d}cnt[kd]$，如果$sum\geq 2$，则$d$就是答案，复杂度为$nlogn$ 另外，大于${10}^{4}$数据不超过$10$组有两个目的，一是放过$n\sqrt{n}$的解法，二是使得数据读入量不大。 ## 1003 Where is Bob 这题可以用数位DP解决。我们从二进制高位向低位考虑，决策的时候优先考虑高位，同时维护双方选择数字的上下界。如果上下界在某位是同一个数，那么这个人就一定要选这个数字，我们可以算出相应的代价。如果一个人有选择的余地，而另一个人没有，他一定会选对自己有利的选项，因为更低位贡献的总和都不会超过当前位。如果两个人都有选择的余地，那么Alice在这位选$x$，JSL一定也选$x$让Alice获取不到这位的价值。选择之后后面数字可选的上下界就发生改变了。当时我们发现下界只有两种可能，全$0$或$L$的后若干位，上界只有两种可能全$1$或$R$的后若干位。于是定义$dp[i][l1][r1][l2][r2]$，$i$为考虑后$i$位，$4$个$l$，$r$都是$0-1$变量表示两个人上界的情况，整个$dp$值就是最后的价值。按照上面的方法去转移就可以了。 ## 1004 Magic Toy Brick 定义$dp[n]$表示n个积木所有的排法，我们先拿出第一个积木，然后从后n-1个积木中选出t个积木，将这$t+1$个积木放在第一行。设置${h}_{1}$到${h}_{t+1}$，使得其为单调不降序列，我们可以令${h}_{0}=1$,${h}_{t+2}=m$,${s}_{i}={h}_{i}-{h}_{i-1}$,其中${s}_{1}+{s}_{2}+...+{s}_{t+2}=m-1$并且${s}_{i}\geq 0$,$1\leq i\leq t+2$,选法为$\binom{t+2+m-1-1}{m-1}$，那么转移方程为$dp[i]=\sum_{t=0}^{i-1}\binom{i-1}{t}\binom{t+m}{m-1}dp[i-t-1]$，初始$dp[0]=1$。

##1001 Rikka with string 如果没有不是回文串的限制可以把所有的?都变成a，这样一定是字典序最小的。而现在有了回文串的限制，我们可以从小到大枚举最靠后的不在字符串正中心的问号选什么，其他的问号依然换成a，显然如果有解，这样一定可以得到字典序最小的解。注意特判没有问号以及问号在正中心的情况。 时间复杂度$O(n)$ Hack点：pretest挺强的也没有什么能hack的了吧 ##1002 Rikka with wood sticks 先求出所有不牢固小木棍中最左边的位置$L$和最右边的位置$R$，可以确定的是其中一段一定是$[L,R]$。 接着分两种情况考虑： 1. $L=1$或$R=n$ 这样剩下的三段是由一整段木棒截来，我们可以枚举最左边一段的长度，这样可以得到一个关于第二段木棍的不等式，稍微讨论一下即可。 2. 除了$1$以外的情况 这种情况相对容易，枚举是左边一段还是右边一段作为完整的一段，然后再枚举另外一段的切割点，判断是否合法，如果合法就使答案加一。 时间复杂度$O(n+m)$。 Hack点：1.没开long long。2.没有考虑到第一种情况或者第一种情况写错。3.直接尝试用 $O(n^{2})$的暴力 ##1003 Rikka with sequence 这题看起来一副非常厉害的样子。。其实是大水题。 对于一个询问，考虑这个询问前第$i$次修改操作，那么这次修改操作出现在序列中第一个位置是$2^{i-1}$。然后在询问范围内最多只有$60$个数，暴力大法好就好了，时间复杂度$O(nlogR)$，$R$是询问的最大下标。 Hack点：pretest里的操作$1$最多只有$30$次，即没有超过int。所以可能有人会爆int？不过我觉得是不会有那么逗逼的人的。。 ##1004 Rikka with graph 显然一个图是优美的图的充要条件是所有点的度数为偶数。 接下来提供两个做法： 第一种做法是一个叫做jiry_2的逗逼脑洞出来的很无脑的做法。 先不考虑边的限制，一个$n$个点满足条件的图与$n-1$个点的简单无向图一一对应。这个不难理解，一个$n-1$个点的简单无向图我们可以加上第$n$个点然后与所有度数为奇数的点连边，这样就可以得到一个n个点的优美的图。 所以不考虑边数限制的话答案就是$2^{C(n-1,2)}$。接下来考虑去掉边数不到$m$的优美的图的个数。因为$n$比较大，所以比较难处理，考虑去掉孤立点的贡献，即求边数为m点数为n的每一个联通块都至少一条边的优美的图的个数，这样就可以在最后乘上组合数去掉贡献。考虑DP求解，令$dp[i][j][k]$表示$i$个点，$j$个奇点，$k$条边的方案数，转移的时候考虑连向这些边的同时可能会有几个度数为0的点接上去。我们枚举新点连向多少个度数为0编号小于它的点，多少个度数为偶正数的点，多少个奇点，转移$O(m^{3})$，状态数$O(m^{3})$，时间复杂度$O(m^{6})$，显然这通过不了$m=80$的数据范围。 我没有仔细去想怎么优化这个DP，可能场上有人可以想到优化的方法。但是由于我比较懒，所以就用懒人的方法了。一个简单的思路是最后用到的只有$dp[i][0][k]$，即$m^{2}$个状态，于是我们可以索性打表大法好。这样只要记$6400$个不到的状态，可以在64K代码限制之内完成。 第二个做法是xudyh在比赛的时候教我的。膜杜爷。。。 点数为$n$边数小于等于m的优美的图的个数应该是关于$n$的$m$次多项式。然后暴力DP $n$比较小的情况，插值出多项式的系数带入就好了。至于复杂度，暴力的话大约是$O(n^{5})$，打表依然能过。 Hack点：pretest里唯一m非$0$的点的$m=10$且$n=10$。所以所有想要大力出奇迹的都可以hack啦。 【总结】 题目很水数据很弱。

##1001 Strange Class 这是一个简单题，先判断长度是不是3的倍数。 然后再判断前中后三段里面的字符是不是一样。 最后判断一下这三段之间的字符是不一样的。 ##1002 Gunner 先对数据进行排序，然后对每一个查询进行二分查找。注意查找到之后要删除。 还有一种做法是用hash，两个算法的效率差不多。 ##1003 Trees 本题其实是查询删除一些树木之后连续树木的段数。可以先对树木高度从小到大排序，对输入的查询也从小到大排序。 对于当前的查询h，在线段树中删除比h小的树木，在线段树中维护，每一段里面连续的断数。 这样总的复杂度是nlogn+qlogq. 线段树中存放的节点信息为 ```cpp struct Segtree { int seg, Lsum, Rsum, sum;//连续段数，从左端点数来最多有几个连续，从右端点数过来有几个连续，当前段有几个树木。 int l, r;//当前区间 }node[MAX * 3]; ``` 每次删除之后从儿子向父亲更新。 ```cpp node[tag].sum = node[LL(tag)].sum + node[RR(tag)].sum; node[tag].seg = node[LL(tag)].seg + node[RR(tag)].seg; if (node[LL(tag)].Rsum&&node[RR(tag)].Lsum)node[tag].seg--;//因为这儿中间是连着的，所以之前直接加是多数了一段，应该减去。 node[tag].Lsum = node[LL(tag)].Lsum; node[tag].Rsum = node[RR(tag)].Rsum; ``` Just now, I came up with another way of deleting the trees. This way can be implemented without segment tree, so the time complexity of one deleting can be O(1). When deleting one tree of number “x”, we just need to judge whether x-1 and x+1 have been deleted. Here is some cases should be considered: 1) If x-1 and x+1 have been deleted, then number of block should decrease by one. 2) If x-1 and x+1 have not been deleted both, then number of block should increase by one. 3) In other cases, number of block should remain unchanged. ##1004 The Monkey King 这题的本质是求 $x_1+x_2+x_3+......+x_m = n$ 且 $x_1 > x_2,x_3,x_4,......,x_m$ 这个方程有多少整数解。 可以枚举 $x_1$.设当前 $x_1 = u$,那么问题转化为求 $x_1+x_2+x_3+......+x_m = n - u$ 且 $u > x_2,x_3,x_4,......,x_m$，可以用生成函数来解决。 每一个项的生成函数是 $f(x) = 1 + x + x^2 + ...... + x^{u-1} = \frac{1-x^u}{1-x}$ 那么$m-1$个相加的生成函数是 $G(x) = [f(x)]^{m-1} = \frac{(1-x^u)^{m-1}}{(1-x)^{m-1}}$ 再利用$(1+x)^k = 1+\sum_{n=1}^{\infty}\frac{k*(k-1)*(k-2)*......*(k-n+1)}{n!}x^n$对上边的分子分母进行展开。枚举分子中$x^u$的次数，求出G(x)里$x^{n-u}$的系数。 总的复杂度是$nlogn$