## 1001 Souvenir 本题是一个简单的数学题. 如果套装优惠的话就尽量买套装, 否则单件买. 注意一下如果一直用套装的话可能在最后的零头不如单买好, 即$(n \text{ mod } m) \cdot p < q$. ## 1002 Hidden String 这个题怎么暴力怎么搞就好了. 可以枚举最长匹配前缀, 和最长匹配后缀, 中间暴力for. ## 1003 Sequence 这个题看上去是一个贪心, 但是这个贪心显然是错的. 事实上这道题目很简单, 先判断1个是否可以, 然后判断2个是否可以. 之后找到最小的$k (k > 2)$, 使得$(m - k) mod 6 = 0$即可. 证明如下: $3n(n-1)+1 = 6(n*(n-1)/2)+1$, 注意到$n*(n-1)/2$是三角形数, 任意一个自然数最多只需要3个三角形数即可表示. 枚举需要$k$个, 那么显然$m=6(k$个三角形数的和$)+k$, 由于$k \ge 3$, 只要$m-k$是6的倍数就一定是有解的. 事实上, 打个表应该也能发现规律. ## 1004 Bipartite Graph 首先二分图可以分成两类点$X$和$Y$, 完全二分图的边数就是$|X| \cdot |Y|$.我们的目的是$\max \{|X| \cdot |Y|\}$, 并且$|X| + |Y| = n$. 把原图黑白染色, 每个联通块有$a_i$个黑点, $b_i$个白点, 于是就是要确定$a_i$属于$X$还是属于$Y$. 然后我们考虑dp, $dp_{i,x}$表示用了前$i$个联通块, $|X|=x$是否可行. dp方程很容易确定, $dp_{i,x} = dp_{i-1,x-a[i]} \text{ or } dp_{i-1,x-b[i]}$. 直接暴力是$O(n^2)$的, 可以考虑用bitset优化, 这样就可以过了. 实际上由于数据很难造, 一些稍加优化的$n^2$也可以过的 ## 1005 Happy King 出题人的做法是点分治, 比赛的时候有人排序之后用lct维护单调性过了. 设分治中心为$g$, 我们只需要计算跨过$g$的答案, 其他的可以分治计算. 跨过根的可以容斥做, 没有限制的 - ∑端点落在同一颗子树上的. 上述两个过程是一样的, 于是只考虑没有限制的怎么做. 令$x_i,y_i$为$i$到$g$路径上的最大值和最小值. 我们按照$x_i$排序, 然后枚举$x_i$必选, 那么前面可选的$x_j, y_j (j < i)$必须要满足$x_i - d \le x_j, x_i - d \le y_j$, 由于$x_j \ge y_j$, 只需要考虑$x_i - d \le y_j$. 于是只要枚举$x_i$然后用树状数组统计答案即可. 复杂度是$O(n \log^2 n)$. 事实上也是存在$O(n \log n)$的点分治做法, 分治时每次把树差不多分成两半, 就可以利用单调性, 用单调队列维护答案. 做法和POI2010 Pilots类似. 这个做法在比赛开始后Claris想到的. ## 1006 Triangle 这个题是一个比较麻烦的计数题, 有两种方法: 直接算或者容斥之类的. 直接算很麻烦, 这里不详细介绍, 我们考虑容斥的做法. 如果一条边也没有被染色, 我们知道答案是$\binom{n}{3}m(m-1)(m-2)$. 由于边被染色, 我们需要减去多算的答案. 大致可以分为三种: 1. 三条边都被染色 也就是图中的一个三元环, 如果三条边颜色一样, 多计算的部分是$m(m-1)(m-2)-1$, 否则多计算的部分是$m(m-1)(m-2)$. 2. 两条边被染色 如果两条边颜色一样, 那么多算的部分是$m(m-1)(m-2)$, 否则多算的部分就是$m(m-1)(m-2)-(m-2)$. 考虑如何计算有多少个三角形只有两条边被染色. 我们枚举两条边的公共点$x$, 然后至少两条边被染色的有$\binom{deg_x}{2}$, 恰好三条边被染色的数目就是经过$x$的三元环数目. 如果分边颜色一样还是不一样, 可以同样的方法搞. 3. 只有一条边被染色 那么多算的部分就是$m(m-1)(m-2)-(m-1)(m-2)$. 然后计算这样的边有多少条. 枚举边的两个端点是$x$和$y$, 那么这样的边有$deg_x+deg_y - e(x,y)$, 其中$e(x,y)$表示有多少三元环经过这条边$(u,v)$. 于是这个题变成如何快速枚举所有三元环. 首先通过之前的某场BC大家应该了解到三元环的数目是$O(m \sqrt m)$的, 那边也介绍了一种枚举方法. 但是在这道题目里面由于$n$比较大, 不能$O(1)$判断边是否存在, 有两种解决方法, 一种是hash, 另一种是用set存边. 第一种是玄学, 但是不好卡; 第二种多个log, 恐怕会TLE. 这里介绍一种不依赖hash的$O(m \sqrt m)$做法. 统计每个点的度数, 然后给每条边定向, 从度数小的连到度数大的. 那么我们得到的有向图每个点的出边数目是$O(\sqrt m)$级别的. 证明如下: 对于度数小于等于$\sqrt m$的点, 出边最多$\sqrt m$条; 对于度数大于等于$\sqrt m$的点, 最多有$\sqrt m$个, 于是也只会连出$\sqrt m$条边. 然后我们只要枚举一条有向边$a\rightarrow b$, 考虑和$a,b$构成的三环的另一个点必定在$a$和$b$边表的交集中. 于是我们把边表排序, 类似归并的做法合并即可. 这样就可以在$O(m \sqrt m)$时间内枚举所有三元环.

出题人： 1001,1004: 986504542 1002,1003: mambacrose ##1001. wyh and string problem 本题是一道送分的字符串题。这里给出两种解法。 1. 维护一个类似栈的结构，存储wyh2000实际看到的字符串。扫描整个字符串，每看到两个相邻的$\text{v}$就往栈中加入一个$\text{w}$；否则看到什么就加入什么。最后扫一遍看$\text{wyh}$是不是栈中元素组成的串的子序列即可。 2. 我们寻找一个$i$，使得$s_i=\text{v}$且$s_{i+1}=\text{v}$并且$i$尽量小。然后我们寻找一个$j$，使得$s_j=\text{w}$且$j$尽量小。我们再寻找一个$k$，使得$s_k=\text{y},\min(i+1,j)<k$且$k$尽量小。然后我们寻找一个$l$，使得$s_l=\text{h},k<l$。如果我们能找到符合条件的$i,k,l$或符合条件的$j,k,l$，那么答案就是$\text{Yes}$，否则答案就是$\text{No}$。 ##1002. wyh and pupil 如果$a$不认识$b$，那么在$a,b$间连一条边，这样有解当且仅当这张图是二分图。 由于可能有多个二分图，而题目要求第一组的人尽可能多，所以贪心的选择即可。 要注意$m=0$的情况。 ##1003. wyh and sequence 令$f(l,r)$表示$[l,r]$的答案。 我们对于序列分块，对于第$i$块，令$S_i$为第$i$块的左端点。 令$g(a,b)$表示第$a$块开头到第$b$块末尾这一段序列的答案。下面我们讨论如何求$g(a,b)$。 我们枚举$a$，再枚举$j(S_a\leq j\leq n)$，考虑$j$ 转移到$j+1$，$f(S_a,j)$和$f(S_a,j+1)$的关系。 \(f(S_a,j+1)=f(S_a,j)-A_{j+1}^{sum(A_{j+1})}+A_{j+1}^{sum(A_{j+1})+1}\) 其中$sum(x)$表示$x$在区间$[S_a,j]$中出现的次数，这样我们就能用$n\sqrt{n}logn$的时间求出$g(a,b)$。 令$h(i,j)$表示$i$在前$j$个块中出现的次数，这个也很容易用$\sqrt{n}$的时间求出。 考虑询问$[l,r]$，两端的我们可以暴力求出来，中间的块内答案可以直接用$g$数组求出。然后我们可以用类似求$g$数组的方法将两端的数加入中间的块内。复杂度$O(Q\sqrt{n}logn)$。 考虑到那个$log$为快速幂的复杂度，又因为每一个$a^b$我们都可以发现$a$一定是序列中的数，$b$一定小于$a$在序列中出现的次数，所以我们可以$O(n)$预处理，用$vector$存起来即可。 总复杂度$O(n\sqrt n+Q\sqrt n)$。 ## 1004. Fast wyh2000 Transform 这个题要求 \(c_i=\sum_{j+k=i}a_jb_k\binom{i}{j}\) 且模数为$3$。不妨记为子问题$solve(a,b)$。 我们考虑Lucas定理，那么有 \(\binom{i}{j}\equiv\binom{\lfloor{\frac{i}{3}}\rfloor}{\lfloor{\frac{j}{3}}\rfloor}\binom{i mod 3}{j mod 3}( mod 3)\) 如果$i mod 3<j mod 3$，那么$\binom{i}{j}\equiv 0( mod 3)$。 那么可以这么解决$solve(a,b)$：枚举$j mod 3=j_0,k mod 3=k_0$，然后将$a$中所有下标模$3$余$j_0$的元素提出来组成$a_{j_0}$，$b$中所有下标模$3$余$k_0$的元素提出来组成$b_{k_0}$，然后计算$solve(a_{j_0},b_{k_0})$对$c$的贡献。这样一个大小为$n$的任务被转化为$3^2=9$个大小为$\frac{n}{3}$的子任务。 但是注意到$(j_0,k_0)$的$9$种取值中只有$6$种满足$\binom{j_0+k_0}{j_0} mod 3 \neq 0$。那么子任务的个数从$9$个变成了$6$个。复杂度为$T(n)=6T(\frac{n}{3})+O(n)$，经过计算得$T(n)=O(n^{\frac{\ln 6}{\ln 3}})$，约为$O(n^{1.631})$。

1002题的小数据由于出题人和验题人的一点疏忽出现了一个错误，给大家带来的不便，实在抱歉。 还是要感谢BC管理员和验题组人员的帮助，同时也感谢一起参与出题验题的fwm94和icerain94。 ## 1001 Senior's Array 这个题有很多$O(n^2)$的算法，这里说一种：枚举每一个区间，在枚举区间的同时维护区间内的最小值和区间和，将最小值与$P$的大小进行比较，贪心地取最大值即可。注意若枚举到的区间是整个数组，则$P$的值是必须取的。 当然也存在$O(n)$的做法： 从左往右处理出$dp1[i] = max(a[i], dp1[i - 1] + a[i])$,同样从右往左处理出$dp2[i] = max(a[i], dp2[i + 1] + a[i])$，再枚举要修改哪一个数，用两个数组更新答案即可。 ## 1002 Senior's Gun 容易发现最后的方案一定是攻击力最强的k把枪消灭了防御力最弱的k只怪物，那么我们对枪和怪物排序后二分出最多能够使用的枪有多少把，然后再枚举使用几把枪更新答案即可。复杂度$O(nlogn)$。 ## 1003 Senior's String 首先我们用$O(n^2)$的动态规划算法处理出dp数组，$dp[i][j]$表示$X$串的前i个字符和$Y$串的前j个字符的最长公共子序列的长度，在这个基础上我们再进行一个动态规划。用$f[i][j]$表示在$X$串的前i个字符中，有多少个长度为$dp[i][j]$的子序列在$Y$的前j个字符中也出现了。转移：若$dp[i - 1][j] == dp[i][j]$，则$f[i][j] += f[i - 1][j]$，表示i这个字符不选；再考虑选i这个字符，找到$Y$串前j个字符中最靠后的与X[i]匹配的字符的位置，设为$p$，若$dp[i - 1][p - 1] + 1 == dp[i][j]$，则$f[i][j] += f[i - 1][p - 1]$。最终的答案即为$f[n][m]$。复杂度$O(n^2)$。 ## 1004 Senior's Fish 题目关键在于在x轴和y轴上，鱼的坐标变化都是单调的，因为$d$是正值。我们把在一个矩形内部有多少个点的询问拆分成四个在某个点的左下角有多少个点的询问，然后用一棵线段树维护鱼的x坐标，一棵线段树维护鱼的y坐标。对于移动操作，在对应的线段树上进行区间更新，更新完成后询问该区间内的最大值，若最大值超过了我们关心的值，那么这个点就可以删掉了，删除的方法可以通过在对应的线段树上把值设为$-INF$，同时继续询问直到最大值不大于我们关心的值为止。那么我们就可以实时维护当前在我们关心的点左下角的点有哪些了，这可以再借助于一个树状数组。这样子作四遍我们就能得到最终的答案了。由于每一次的过程中每个点只会被删除一次，所以复杂度是$O((n + q) * logn))$。

## 1001.YJC tricks time 因为要保证秒数是10的整数倍，所以可以直接枚举现在分针与水平成的角度，再算出时针判断是否符合。O(360T)（T表示数据组数） 不过也可以直接枚举所有时刻，算出成的角度，扔到map或hash表里直接查，好写又方便。O(Tlogm)或O(T)（m表示总时刻数） 注意计算的时候考虑两针的位置关系，并且成的角按劣角算，建议使用整型直接计算而不要转换成double。 ## 1002.YJC counts stars 首先针对大家提出的m的数据范围的问题，其实对于平面图来说有$m \le 3n-6$…… 首先五个点的团就是平面图判定中提到的$K_5$，包含子图$K_5$就不是平面图。所以答案只可能是$4$。 那么怎么统计答案呢？ 暴力枚举第一个点，再枚举第二个点，在枚举第三个，第四个，要求每个点都与前面其他点联通。你会发现这就过了，为什么呢？ 枚举第一个点是$O(n)$的，枚举第二个点是$O(n^2)$，但是注意$m=O(n)$，于是枚举第三个点只有$O(n)$次，总次数也是$O(n^2)$的。注意到平面图三元环的个数是$O(n)$的，因为把一个点的相邻点按照几角排序，那么这些点的连边相当于是若干个区间，而区间不能相交，所以总共就是$\sum deg_i=O(m)$（deg_i表示度数）的。于是枚举第四个点的次数也是$O(n)$的，总复杂度就是$O(n^2)$。对于$n=1000$来时完全够了。 标算是怎么写的呢，标算采用了特殊的技巧枚举三元环，先枚举边，然后枚举度数较少的点的相邻点，判断是否与另一个点相邻，这样可以证明是$O(n^{1.5})$的，至于第四个点，可以$16$个点压一位，预处理出$[0,2^{16})$每个数二进制1的个数，就可以统计了，复杂度是$O(n^{1.5}+\frac{n^2}{16})$，可以快速通过数据。 ## 1003.YJC plays automaton] 首先考虑一个YJC集$S$和题目所述的字符串$str$，根据YJC集的定义，一定存在两个元素$i,j\in S$满足i运行了str之后不为NULL，而j运行str之后为NULL。 同样对于两个元素$i,j\in S$若存在$str$满足i运行了str之后不为NULL，而j运行str之后为NULL，则$S$运行$str$就满足要求。 所以，$S$是YJC集当且仅当存在两个元素$i,j\in S$，$\{i,j\}$是YJC集。 我们可以对所有的二元组$<i,j>$预处理${i,j}$是不是YJC集。 预处理的过程可以用宽度优先搜索(BFS)，将所有的$<i,0>,<0,i>$加入初始队列，把图反向，每次枚举上一个转移的字符进行逆向转移，这一步是 $O(n^2m^2)$的。 计算答案呢：我们可以用所有非$NULL$状态集合的非空子集数目减去不合法的非空集合数目。问题变成统计满足以下条件的集合数目： $\forall i,j\in S,\{i,j\}$不是YJC集。 观察一个二元关系：${i,j}$不是YJC集。根据定义得知对于任意字符串$str$都有$i$和$j$运行$str$之后同为$NULL$或者同不为$NULL$。显然这个二元关系是一个等价关系(满足自反性，对称性，传递性) 于是我们使用并查集将$n$个元素分成若干个等价类$P_1,P_2,\cdots ,P_k$。 则不合法的集合数目为$\sum (2^{|P_i|}-1)$ 则$ans=2^n-1+k-\sum 2^{|P_i|}$ 2的方幂可以预处理也可以快速幂，复杂度不是瓶颈。 时间复杂度$O(n^2m^2)$，可以解决本题。 ## 1004.YJC plays Minecraft 就是让你求一个$n$个节点的大环，每个节点是一个完全图的生成森林个数。 设${f}_{n}$表示$n$个节点完全图生成树个数，${g}_{n}$表示$n$个节点完全图生成森林个数，${h}_{n}$表示$n$个节点完全图，点$1$和点$n$不在同一棵树中的生成森林个数。那么答案就是${2}^{n}\prod_{i=1}^{n}{g}_{{a}_{i}}-\prod_{i=1}^{n}({g}_{{a}_{i}}-{h}_{{a}_{i}})$。第一部分表示所有完全图生成森林个数乘起来再乘上大环上的边的每一种情况，第二部分表示大环上每一条边都不删，而每一个完全图中第一个点和最后一个点都在同一棵树里面的情况，这种情况是不合法的，要从答案里面减掉。 一个著名的定理是${f}_{n}={n}^{n-2}$，但${g}_{n}$和${h}_{n}$怎么算呢？ 再设$F(x)=\sum_{n}^{}{f}_{n}\frac{{x}^{n}}{n!}$，$G(x)=\sum_{n}^{}{g}_{n}\frac{{x}^{n}}{n!}$，$H(x)=\sum_{n}^{}{h}_{n}\frac{{x}^{n}}{n!}$。 我们把$1$号节点单独取出来，枚举哪些节点和$1$号节点在同一棵树里，则有： ${g}_{n}=\sum_{i=0}^{n-1}{f}_{i+1}{g}_{n-i-1}\frac{(n-1)!}{i!(n-i-1)!}$ $\frac{{g}_{n}}{(n-1)!}=\sum_{i=0}^{n-1}\frac{{f}_{i+1}}{i!}\frac{{g}_{n-i-1}}{(n-i-1)!}$ $G'(x)=F'(x)G(x)$ $\frac{G'(x)}{G(x)}=F'(x)$ 由$[\ln F(x)]'=\frac{F'(x)}{F(x)}$可得： $\ln G(x)=F(x)$ $G(x)={e}^{F(x)}$ 于是就可以算${g}_{n}$了。怎么算${e}^{F(x)}$？[http://picks.logdown.com/posts/209226-newtons-method-of-polynomial](http://picks.logdown.com/posts/209226-newtons-method-of-polynomial)。自己去看。反正知道是$O(nlogn)$的就行了。 接下来是${h}_{n}$。类似于$G(x)$： ${h}_{n}=\sum_{i=0}^{n-2}{f}_{i+1}{g}_{n-i-1}\frac{(n-2)!}{i!(n-i-2)!}$ $\frac{{h}_{n}}{(n-2)!}=\sum_{i=0}^{n-2}\frac{{f}_{i+1}}{i!}\frac{{g}_{n-i-1}}{(n-i-2)!}$ $H''(x)=F'(x)G'(x)$ $H(x)=\int \int F'(x)G'(x)$ 多项式求导、多项式积分都是$O(n)$的，多项式乘法用$NTT$是$O(nlogn)$的，于是总的时间复杂度就是$O(n+\max{{a}_{i}}\log\max{{a}_{i}})$的。

感谢BC管理员和验题人给我的不懈帮助。 这里特别感谢管理员hujie对我技术上的耐心帮助， 以及十分活跃、为我出题出谋划策的System Message。 本次的题目很简单，祝大家端午节快乐！ ## 1001 Dylans loves numbers 这道题就是按照题意模拟。 设读入的数是$N$，我们先把$N$分解成二进制形式放在数组$A$里。（正反顺序没有关系） 然后对A数组循环一边，如果当前位置是1而前一位是0那么计数器就++。注意一些小的细节。 时间复杂度为$O(T*log(N))$ ## 1002 Dylans loves sequence N只有$1000$，于是想怎么来就怎么来。 最容易想到的是枚举开头，然后$Nlog(N)$时间里去算逆序对，用一个树状数组维护。 （可惜BC不给卡。。。呜呜呜） 仔细一想发现可以很简单地做到$N^{2}$. 设$ans[l][r]$为$l \sim r$的逆序对数量。首先我们暴力地先算好$ans[1][1..N]$。 然后$i$从$2 \sim N$枚举，每次计算从$i$开始的逆序对。 那么$ans[i][j]$比$ans[i-1][j]$少了什么呢？没错，少了$a[i-1]$这个数的贡献。 我们再开一个累加器$cnt$。枚举$j$从$i \sim N$，如果$a[i-1]$和$a[j]$产生逆序对就$cnt[j]=-1$ 然后我们从右往左累加$cnt$(因为贡献是前缀和性质的) 最后$ans[i][j]=ans[i-1][j]+cnt[j]$。 预处理完所有的答案就可以$O(1)$的询问啦。 ## 1003 Dylans loves tree 题目里有一个很神奇的性质：路径上最多只有一个数出现奇数次。 这应该马上想到异或。因为异或两次和没异或是等价的。此外异或满足区间减性质。 因为有修改，我们很自然地想到用数据结构维护。 最无脑的就是直接上树链剖分或是Splay维护区间xor值即可。 仔细想一想，发现可以利用LCA消去“树上路径”，转化为根到x路径上求xor值。 我们可以很经典地直接使用线段树或树状数组维护dfs序。 （然而BC不给我卡$log^{2}$。。。呜呜呜） 有一个很强的trick就是权值可以为0！ 所以比如路径上有3个0，虽然他们xor值还是0，但是他们是出现了奇数次。 我特意把$A[i]$说成∈自然数集而不是$[0,100000]$，就是想尽量不被发现。 怎么避免呢？单独维护0的情况？ 有一个很简单的解决方案：直接把读入时所有权值+1，输出的时候再-1即可！ 时间复杂度为$O(N*log(N)^{2})$或者$O(N*log(N))$ ## 1004 Dylans loves polynomia n的范围$3000$。考虑多项式插值的方法。 因为是对子串进行插值，我们很自然地想到牛顿插值。（如果不会请自行百度）。 那么只需先预处理一个$3000*3000$的差商表，然后每次询问就能$O(N)$的读取对角线上的差商，那么问题就解决了。 时间复杂度为$O(N^{2}+NQ)$ 当然出完题后我还脑补出了一个n^2的拉格朗日的方法。 不过细节有点多，要搞一些前缀积、后缀积来维护，这里不再叙述。 吐槽：验题人说题目有点难，本次出题1002的idea换了好几次，然后基本是1002换成1003，1003换成了1004。（也就是说还有一道有趣的题目未能出出来） 然后大家在Clarification里大量询问C题是否有负和0点权，这给一些同学提了醒~