想来把当年的题目重新看一遍想一遍估计会比重新学一遍效率更高。虽然2020年也做了不少题，但是还是觉得手感不是很好。16 17两年的模拟题的题量应该足够我学不止一个寒假的了。加油！
7.10
牛宫
题意：给定一个200*200的矩阵，问矩阵中Sum>0的最大子矩阵多大。
解：先利用数据得出结论，$O(n^4)$暴力不可过，应该是$O(n^3\lg n)$或者$O(n^3)$可能性较大。通过研究可以发现，当已确定是从第几列到第几列的情况下，答案的产生是具有单调性的(这么说好迷惑，不过既然是写给自己看的，自己以后看懂应该毫无问题)，即起始行递增的情况下，末尾行不会在可行的基础上往前移动，只会往后移动，不然不符合答案最优性质。同时，如何确定是否有更后面的可行？毕竟当前末尾行不可行的情况下还是可能会有更优的末尾行。可以先做一下前缀和，那么可行的含义就变成了$sum[j]>sum[i]$.可以排序后直接查询做，具体实现随便想想就会了吧。
技能树
题意：给定一个最多50行的三角形“矩阵”，形成一个“方格取数”一般的倒三角形状，在其中选m(<200)个，要求选择的m个的和最大，且选择的每一个的左上及右上方格都已被选择(第一行除外)
解：怎么看都是DP.首先有比较直观的一个想法,类似方格取数的操作顺序.然而可以发现这样需要状压上一行的情况,这样转移对于50行就不可接受了.
题解给出了一个更加巧妙的想法:先画图发现最终答案其实就是个折线,让折线上方的权值和最大.把倒三角画成直角三角形的样子可以发现,每列的权值和即为1~选中的最下面的方格的权值和.如此,可以先对每列求前缀和后利用dp求解使得每列选一个的和结果最大的方案.设$f[i][j][k]$表示如果选中第$i$行第$j$列且总共选了$k$个的当前最大权值和.转移方程易得.注意要留取0个的一行即可.
最小密度路径
题意：给一个加权有向无环图,每个询问求x点到y点距离除以边数的最小值。其中$n\le 50,m\le 1000,q\le 100000,w\le 100000$.
解：首先联系题目和数据范围想到可能会和floyd有关,但显然不能直接做。考虑有向无环图中一个路径最多只有$n-1$条边，那显然可以在floyd基础上加上一维通过的边数来解决。但直接这样做算法是$O(n^5)$的。转移方程如下
$$
f[i][j][k]=min{f[i][h][g]+f[h][j][k]}
$$
考虑如何优化。可以发现在这个转移方程里面同一条路径会被转移很多次，从中途不同地方截断。显然可以优化一维。
$$
f[i][j][k]=min{f[i][h][k-1]+f[h][j][1]}
$$
正解，时间复杂度$O(n^4)$
7.11
T1
判断x是否y的原根,已经学了相关知识发在blog里了
T2 CF406A
题意：$n\times n(n\le1000)$的一个01矩阵，定义矩阵的值为第一行*第一列+第二行*第二列+…………………..的值&1。
有三种操作$(q\le1000000)$：
翻转一行的数
翻转一列的数
查询矩阵的值
解：容易发现矩阵的值事实上是
$$
\sum_{\oplus}{a[i][j]\land a[j][i]}
$$
因此当$i$和$j$反着取的时候，就会发现同样的式子又被加进异或和一次，那么显然计算了两次就是相当于没有加。于是只有对角线上的值才会影响矩阵的值。直接维护即可。
T3 找不到题面
7.12
绕橡皮
猜结论题(证明也不难)
道路网络
题意：无向图，$m\le300$个地铁线，连着$n\le100000$个站点，各个线路到各个站点之间距离为输入值，有$T\le2000$个询问，问两站之间最短距离。
解：首先显然可以把线路设点跑最短路。但这样只能拿部分分。然后我们可以把这个性质很强的图分成两部分看。首先对于$m\le300$，我们发现这个数据范围很适合floyd。那么其实考虑一下就可以发现可以利用floyd跑出所有站点之间的距离（初始值就是同一个站点连接的两个线路的距离和）。然后对于每个询问可以枚举出发先去的线路和最终的线路显然就做完了。复杂度$O(m^3+m\times l[i]+T\times m^2)$。
下十万层！
题面看起来很吃力，反正题目多得做不完，跳了。
7.13
小A的疑惑 (BZOJ3031理科男)
题意：给定p,q,k,问$\frac{p}{q}$是否有限小数，若有限则输出位数，若无限则给出混循环位数和循环节长度。
解：显然可以先约分。于是找规律可知，$(q,k)=1$时为纯循环小数。接下来考虑混循环问题。显然作为一个混循环位数为$b$混循环小数，乘$k^b$后取小数部分即为纯循环小数。其中$b$的值为不断操作$q/=gcd(q,k)$使得$(q,k)=1$的次数。也就是说，事实上分子（也就是该分数）每乘一个$k$，对于最终$(q,k)=1$的式子的满足情况而言，都相当于$q/=gcd(q,k)$。
然后计算循环节长度。显然这里可以取上面已经操作过的$p$和$q$形成的纯循环小数进行计算。我们发现循环节的含义实际上就是(设长度为$l$)
$$
A\cdot k^l\equiv A (mod\ q)
$$
其中$l$为最小满足本式的值。则由欧拉定理可知，$l$必定为$\phi(q)$的约数。求出后枚举即可。
树
题意：有$n\le200000$个盒子，进行$m\le200000$个放/拿球操作，其中放球操作指的是将$x$号球放到当前的某个空盒中，使得和它距离最近的有球盒子距离最远，如果有多个空格满足要求就放前面。（通俗来说就是放到最空的地方的中间，除了初始时候是两端）拿球就是将$x$号球从刚才放进的盒子中拿出。求每次放入的盒子的编号。
解：题目名字和内容怎么看都是个数据结构题吧。首先考虑首尾需要特判。其它的情况可以利用一个set和一个priority_queue来维护。priority_queue中存的是空区间，以区间长度为第一关键字降序，左端点为第二关键字升序排序；set中存删除节点时破坏掉的左右两个空区间。如果在priority_queue的栈顶元素在set中能被找到，则将两边的该区间都删除。貌似就可以了。但感觉应该有线段树/树状数组做法。一下子没想到，手头没数据，网上查不到。
限制
我为啥不去研究有题解有标程有数据的题目呢？
7.14
上班族
树上差分即可，貌似题解方法对dfs序建线段树过于复杂。
统计IV
要注意的就一个组合数的计算。看起来预处理阶乘和阶乘的逆元即可。但，p不保证是质数。因此需要CRT+快速阶乘。那么下一个知识点就学CRT。学完会发在blog上，然后接着做当年的模拟题（哦不，好像就得打训练赛了）
合法排列(这题还需要再看看！)
题意：假设有一个$1\cdots n$的数列，求有多少个它的错位排列，使得：假设$a_i$表示$i$点到$a_i$点存在一条有向边，则图中存在大小为$k$的环。求所有$1\le k\le n$的答案和%$(10^9+7)$。
解：我们可以枚举排列中存在几个长度为$k$的循环节，容斥求出答案。假设有$i$个，那么选出$i\cdot k$个数的方案数就是
$$
\frac{1}{i!}\sum_{i=1}^{k} C^k_{n−(i−1)\cdot k}
$$
因为每个循环都本质相同所以要除以$i!$。
由于循环之间互不影响，外面的$n−ik$个数的排列的方案数则为$D_{n−ik}$，其中$D_i$为长度为i的错位排列的方案数。而单个循环里面排列的方案数为$(k−1)!$，因为第一个数字可以是除了$1$之外的$k−1$个数字，第二个数字可以是除了$2$和第一个数字之外的$k−2$个数字，以此类推。
把阶乘、阶乘逆元和错位排列都预处理出来，就可以用$O(\frac{n}{k})$的时间回答一个询问了。注意当$k=1$时答案为$0$，因为错位排列中不存在长度为$1$的循环。