02，03，04 来自 jiry_2，01，05 来自 ACS2013 ## Rikka with Chess 首先，如果先对偶数行取反，再对偶数列取反，可以得到一个$[n/2] + [m/2]$(下取整)的解, 只要说明这个这是答案的下界就可以了。 考虑第一列，每次操作最多使得两个第一列的相邻元素变得一样， 第一列有$n - 1$对相邻元素,这样使得第一列变成一样的次数就是$[(n - 1) / 2]$(上取整)，同理考虑第一行即可。 ## Rikka with Graph 让 $n$ 个点联通最少需要 $n-1$ 条边，所以最多只能删除两条边，我们可以枚举删除的这两条边（或者唯一的一条边），然后暴力BFS判断连通性就好了。时间复杂度 $O(n^3)$。 ## Rikka with Array 很明显这是一道数位DP的题目，状态 $dp[i][j][k]$ 表示当前考虑了最高的 $i$ 位，两个数目前数位和的差是 $j$，当前两个数以及给定的 $n$ 之间的大小关系是 $k$，然后暴力枚举这两个数的当前位的值，然后转移就好了。时间复杂度 $O(\log^2 n)$。 ## Rikka with Sequence 这是一道没什么思维含量的题，但是细节比较多。 首先答案不超过 $n$，因为我们可以直接在原来平均数的位置加入 $n$ 个数，这样中位数就等于平均数了。 其次，答案满足二分性（指第一问），因为如果存在加入 $i$ 个数的方案，我们可以把多出来的数都放在当前平均数的位置，显然还是满足要求的。 所以我们可以先二分答案，这样问题就转化成了加入 $K$ 个数，在满足平均数小于等于中位数的同时最小化平均数。 可以发现最开始给出的 $n$ 个数把 $[1,m]$ 分成了 $n+1$ 个区间，我们可以枚举中位数在哪一个区间内，当然这儿要进行分类讨论，大致的情况有这么多种： 1.总数是奇数，中位数是原来给出的数。 2.总数是奇数，中位数是加入的数。 3.总数是偶数，中位数是原来给出的两个数的平均数。 4.总数是偶数，中位数是一个加入的数和一个比它大的原来给出的数的平均数。 5.总数是偶数，中位数是一个加入的数和一个比它小的原来给出的数的平均数。 6.总数是偶数，中位数是两个新加入的数的平均数。 对于每种情况，我们可以把中位数设为 $x$，然后直接贪心，这样就能得到一个方程，解出这个方程然后再判断解是否合法并更新答案就行了。（当然，如果再加思考的话可以发现上述情况并不是都需要考虑，有两个是不会影响答案的） 时间复杂度 $O(n \log n)$ ## Rikka with Phi 注意到$10^7$之内的数最多phi $O(log(n))$ 次就会变成1， 因此可以考虑把一段相同的不为1的数缩成一个点，用平衡树来维护。每次求phi的时候就在平衡树上取出这个区间然后暴力求phi，如果一段数变成了$1$，就在平衡树里面删掉它，最后统计答案的时候只要把区间中被删去的1加回答案即可，时间复杂度$O((n + m)logn)$

## Clarke and chemistry 由于数目很小，我们可以直接枚举$a$和$b$。 ## Clarke and points 将$|x_A-x_B|+|y_A-y_B|$分成4种情况考虑可以知道这等价于$max(|(x_A+y_A)-(x_B+y_B)|, |(x_A-y_A)-(x_B-y_B)|)$，所以我们维护最大最小的$x_A+y_A$和$x_A-y_A$就行了。 ## Clarke and MST 我们贪心的从大到小枚举每一个位，如果一个位能取当且仅当所有权值这个位不为0的边能形成一棵生成树。是否能形成生成树我们简单的bfs一下就行了。 ## Clarke and math 其实这题可以做到$k$很大的= =由于太毒瘤我就不说了= =... 如果学过[Dirichlet卷积](https://en.wikipedia.org/wiki/Dirichlet_convolution)的话知道这玩意就是$g(n)=(f*1^k)(n)$，由于有结合律，所以我们快速幂一下$1^k$就行了。 当然，强行正面刚和式也是能搞的（反正我不会）。 一次Dirichlet卷积复杂度是$O(nlogn)$的，所以总时间复杂度为$O(nlognlogk)$. ## Clarke and tree 对于大小为$s$的树，我们考虑prufer数列，即我们只需要统计所有长度为$s-2$的满足的排列。也就是说，在所有长度为$s-2$的排列中，每个序号的出现次数要小于$a_i$。这个东西可以用指数型生成函数来统计。 由于还需要统计prufer序列中出现了多少个点（这样才能知道度数为1的点有多少个）。所以我们设$d(i, j)$表示前$i$个点取了$j$个点的生成函数，则$\displaystyle d(i, j) = d(i-1, j-1) \left( \sum_{k=1}^{a_i-1} \frac{1}{k!} x^k \right) + d(i-1, j) \ (\text{mod }x^{n-1}), \quad d(0, 0)=1$。 那么大小为$s$的树的方案数为$\displaystyle (s-2)! \sum_{j=1}^{s-2} \binom{n-j}{s-j} d(n, j)_{s-2}$，其中$d(n, j)_{s-2}$表示第$s-2$项系数，$\displaystyle \binom{i}{j}$表示从$i$中取$j$个的方案数。 如果用fft来求卷积则复杂度为$O(n^3logn)$。由于有点鬼畜，所以$O(n^4)$的也给过辣！（其实是因为fft常数太大了[嘿嘿嘿]）

## KK's Steel 已经忘记是哪一年的慈溪中学提前招生数学试卷里的题目了。 其实我们不去考虑N，我们只考虑最优切割策略： 首先肯定是尽量的小即1、2 既要不相等，又不能构成三角形，即每次为当前数列中最大的两项的和 那么，构成的数列为1,2,3,5,8,...... 这样我们只要求最接近且小于等于N的Fibonacci数的项数即可。 ## KK's Point 我们先撇开边界上的点不管，那么所有的点都是有两条线所构成的 手算得出N=4的时候，能形成一个点 那么，我们只要知道N个点可以构成几个四边形即可 即求${{C}^{4}_{N}}$ 最后我们再把边界上的N个点加上，最后的结果是${{C}^{4}_{N}}-N$ ## KK's Chemical 根据药品之间的相互关系，我们可以构建一张图，我们对相互会发生反应的药品连边 这个图的特征，是一个环加上一些“树”（可能有多个联通块） 一个环（1,2,3,4,5……，n）m染色的方案数：递推，设第一个点颜色为1 f[I,1]表示i点颜色为1的种数，f[I,0]为颜色不为1时(不考虑n与1颜色不同) 则F[I,0]=f[i-1,0]*(m-2)+f[i-1,1]*(m-1)，F[I,1]=f[i-1,0] 那么方案数为f[n,0]*m 一个根节点颜色固定且有k个孩子的树的m染色的方案数=${(m-1)}^{k}$,因为每个点的颜色只要与他的父亲颜色不同，即m-1种 因为乘法原理，一个联通块的方案数=环方案数*以环上每个点为根的树的积。多个联通块，再连乘即可。 ## KK's Number 显然，每个人的策略就是都会拿剩下的数中最大的某几个数 假如我们用f[i]表示当剩下i个数的时候先手得分-后手得分的最小值 那么得到$f[i]=max\left(a[j+1]-f[j] \right)(1<j\leq i)$ 但是这样做，是要超时的 我们不妨简单转换一下 f[i]=_max; _max=max(_max,a[i+1]-f[i]); ## KK's Reconstruction 首先，一种合法方案对应了原图的一棵生成树。 我们知道，最小生成树有一个性质是最大边最小。 因此，我们可以枚举生成树的最小边，去掉比该边小的边后对新图求最小生成树，那么我们所要的最优解一定包含在其中。 时间复杂度$O(M\log M+{M}^{2}\alpha (N))$，显然仅仅这个效率是不够的。 可以发现我们每次枚举后都重新求了最小生成树，事实上这是不必要的。 考虑从大到小枚举生成树的最小边，我们要做的实际上是每次加入一条边，维护当前图的最小生成树。 加入一条边时，我们需要判断这条边能否与之前的边构成环。 I 若能构成环，用该边替代环中最大边一定更优； II 若不能构成环，直接加入该边即可。 找环中最大边可以用DFS 实现。若图中现有的边数为$N-1$，我们就可以更新答案。 这样，事件复杂度就降到了$O(M\log M+MN)$。 更高的效率的方法，我们涉及的操作为加边、删边、查询路径最大边，因此可以使用LCT 来维护。

## Jam's math problem 第一道题比较简单，可以说是简单的模拟题，我们考虑到$a,b,c$都是$10^{9}$的，所以我们决定要把时间复杂度降下来，对于每一个数，因为考虑到都是正数，所以我们处理起来就方便很多，打个比方$32=2*16$，那么枚举到$2$的时候就可以得出$16$，这样子的话时间就变为$O(\sqrt{a}\sqrt{b})$，轻松解决这道题 ## Jam's balance 这道题可以放左边，可以放右边，$N=20$显然每种状态都枚举是不太现实的，因为每组砝码都可以变成很多种重量，当然也不排除有人乱搞过了这一题，其实这道题是一道贪心的思想，我们看到$w$不大，所以可以用$01$背包扫一次，当然这还是不够的，这只能放一边，考虑到可以放另一边，就是可以有减的关系，所以反着再背包一遍，注意要判断边界。 ## Jam's maze 这道题考虑的是回文串，有人会想到后缀数组自动机马拉车什么的，其实只要求方案数很多，所以我们应该想到动态规划，首先是状态的定义，我们可以想着从$(1,1)$和$(n,n)$开始走，然后走到相遇。所以我们定义状态可以定义为$f[x_1][y_1][x_2][y_2]$表示所对应的两个点$(x_1,y_1)(x_2,y_2)$，这样的话考虑到数据的范围，显然会爆空间，然后我们想一想就是走多少步和知道$x_1,x_2$的位置，就可以确定$y_1,y_2$的位置。于是我们把状态定义为$f[i][x_1][x_2]$即可，状态转移很显然，如果相等的话把四个方向都扫一下即可。因为还是会爆空间，所以我们把第一维改成滚动数组就解决问题 ## Jam's problem again 很显然让你找$(x,y,z)$都大于别的$(x,y,z)$,当然厉害的人可以用树套树水一下，但正解写的是CDQ分治，以$x$为第一关键字排序，以$y$为第二关键字来找，以$z$为第三关键字建一个树状数组找就好了，当然等于的情况可以实现前做一下。 ## Jam's store 这次肯定有人ak不用看了，第五题是道水题，当然也要看你有没有做过这类的经典题和懂不懂，一道经典的费用流的构图，我们想想，这个点排在另一个点后面的话，只是被另一个点影响了罢了。那么这个构图就巧妙了，因为N不大，所以我们可以把修电脑的人都拆成$N$个点，每个点表示是倒数第几个顾客修的。那大家试想一下，比如说我第一个修电脑的，我现在是倒数第二个来找这个人，那么我只影响我后面的一个和自己，所以的话修一条费用为$Tij*2$，流量为$1$的边流过去就好了。可能还有不明白的自己好好理一下，之后每个拆点都直接连到汇点。前面的话就是起点连到每个顾客，然后修电脑的人连到每个拆点，当流量满流的时候就表示每个顾客要做的都流完了，当然这样子还有保证准确性，因为时间都是正数，所以的话缩小流就保证了在每个人都会从流量小也就是倒数第一个留起。

## Baby Nero and Weight lifting 杠铃是成双出现的，然后只要枚举就可以了 ## Baby Nero and phone number 按照题目条件求解就行，注意输出需要$64$位整数。把读入的数据保存为字符串，取字符串第$[4~7]$个字符作为“年份”，第$[8~9]$个字符作为月份，第$[10~11]$个字符作为日期，日期判断闰年平年，特殊日期是闰年有2月29日，平年没有。取字符串第$[7~11]$数字，判断这$5$个数字是否相等，是否连续差$1$上升或者连续差$1$下降。要用$64$位整数输出。 ## Baby Nero and Matrix games 暴力枚举，枚举每一个表达式，当表达式矩阵为$5*9$的时候，最多有$14000$个表达式，单组复杂度为$O(14000*4)$，题目有精度误差，最好用分数做 ## Baby Nero and Binary image 枚举最左边一列的所有$2^{n-2}$种情况，然后递推到右边。因为上下两行不用考虑，所以对于每个枚举，递推过程中格子的状态是唯一的，因此对于每一种枚举判断一下是否能构成符合题意的二值图即可。 ## Baby Nero and Matrix tree 树链剖分, 由题意可知, 有$2$种类型的矩阵, 第一种类型的矩阵旋转循环节为$2$, 第二种类型的矩阵旋转循环节为$4$, 矩阵的状态一共$6$种。两种类型的矩阵之间转换一定是“替换”，每种类型内部转换一定是“旋转变换”。所以，对于每一组询问，首先找到$a$到$b$的路径，统计$a$到$b$的路径上每种状态的矩阵各有多少个（用$cnt[A_i]$表示$A_i$的矩阵有$cnt[A_i]$个），答案就是$sum(cnt[A_i]*cost[A_i][B])$。Cnt数组用树链剖分来维护，cost数组$6*6$自己打表。单组数据复杂度$O(qlogn*6)$