16年的模拟题里面许多是缺少数据之类的东西的，不如先搞17年的吧。
6.28
悄然苏醒
好题
题意：设有序列以L,R两种元素构成，其中L的重量为97.05276，R的重量是128.05858，序列的重量指所含所有L的重量加上R的重量。现在有一个序列，数据给出一组重量，其中最大的重量就是原序列的重量，其它重量可能是原序列前缀或后缀的重量。问匹配最多的组内重量的情况下可能的原序列是什么。若有多个答案输出任意一个。保证重量组中元素不超过100000个，原序列长度不超过400。
解：首先考虑去除不合法重量。这里根据我的垃圾数学会想是否能靠扩展欧几里得来算，事实证明是可以的，但这里不需要。考虑原序列长度不超过400，则乘100000转化为整数后即可枚举合法重量。重量不合法的第一种情况是不能由两种成分的重量加和得出，第二种情况是包含的某种元素多于原序列。处理结束后，就可以愉快地开始dp了。
我们先把合法碎片的情况存在一个二维数组中。设B[i][j]表示由i个L、j个D组成的合法碎片的数量。
dp时从两端向中间放置。设f[k][i][j]表示已确定目标序列中的前k个和后k个，其中左端(前缀)使用了i个L，右端(后缀)使用了j个L时能取到的最大匹配数。则转移过程为
$$
f[k][i][j]=max{f[k-1][i][j],f[k-1][i-1][j],f[k-1][i][j-1],f[k-1][i-1][j-1]}\\
if\ (i!=j)\ f[k][i][j]+=B[i][k-j]+B[j][k-i]\\
else f[k][i][j]+=B[i][k-i]
$$
其中第一行表示从都放D、左L右D、左D右L、左右都L的状态转移过来。
显然每次转移都可以确定两个位置，且答案需要加上两个前缀(一个我们逐步确定的短前缀和一个利用后缀减出来的长前缀)和两个后缀。于是注意一下把方案存一下就做完了
犹在镜中
$O(n)$算法nth_element的应用
乘风而归
即16年模拟题中小A的疑惑的改动版。求k进制下循环小数情况，求出混循环长度和循环节长度。数据范围调整到了$10^{12}$所以要开__int128或者用快(慢)速乘。
6.29
女神的微笑
题意：给定$s$，$n$个$f_i$，其中$n\le 20$，$f_i\le 10^{12}$。
问
$$
\sum_{0\le x_i\le f_i}x_i=s
$$
的解的数量$% 10^9+7$。
解：组合数学。首先考虑直接正着算，不会。正难则反，容斥。显然最终答案数量相当于假设全都没限制的情况下的答案-其中一个有限制的答案的和+其中两个有限制的答案的和……利用隔板法可以求出公式。具体哪个有限制哪个没限制可以进行状态压缩。$2^{20}$并不大。这里注意算组合数时可能会爆long long。开__int128或慢速乘解决。或者利用卢卡斯定理。
$$
lucas(n,m)=C(n\ mod\ p,m\ mod\ p)*lucas(n/mod,m/mod)
$$
凤舞六幻
题意：5000000个数，保证众数出现次数大于一半。找到它。保证答案只有一个。空间限制1M
解：Boyer-Moore 投票算法。众数次数必须超过一半才是对的。定义cnt，若某数和前数相同则cnt++，反之cnt–。当cnt=0时更新ans。其实就是一个抵消。设众数为x，若要最终答案并非x，则必须至少有相同数量的别的数来抵消x，但x有超过一半个，因此x为最终答案。优秀在空间复杂度$O(1)$。
题目描述有问题，题面写的是大于等于一半，那么上面的做法就挂了。
若空间限制不紧且众数出现次数可能正好等于一半
解：考虑这样的众数必然是中位数之一。可以利用$O(n)$的nth_element求出两个中位数。显然如果n为奇数那么直接求中位数即可。若n为偶数那么仅有一种特殊情况，即最小的$1\to n/2$项都是该众数，或相反。所以找出最小值判一判和哪个中位数相等即可。但空间限制挂了。
A.T.力场
题意：200000个三维点，问切比雪夫距离下的最小生成树
解：分别按不同坐标排序，对相邻点加边，Kruskal
6.30
长沙漫展
简单思维题 当时就过了 现在又过了遍
重庆广场
题意：最大$8\times 8$的方阵中有至多$5$种颜色的格子，每次可以把左上角所在的连通块变颜色，问最少几步可以把所有格子变成同一个颜色。
解：迭代加深。注意每次选择改变的颜色只需要是边界上有的颜色。同时如果剩余格子+已走步数<答案那么就直接剪掉。可以加一点启发式，比如说先搞边界上最多的颜色。
中亚酒吧
小题1：求$n\le8$条由字母组成的长度$\le10$的信息的最长公共子序列（不是子串）
解：考虑状压DP，设$g[len_1+len_2\times 11^1+len_3\times 11^2+\cdots+len_k\times 11^{k-1}]$表示第$i$段信息的前$len_i$个的最长公共子序列长度。转移方程显然。状压dp入门题。
小题2：三条$len\le500$的信息，问公共子序列有多少个
解：
首先思考一下如果只有两条的话怎么做。设$f[i][j]$表示第一条处理到$i$，第二条处理到$j$时的方案数。则分类讨论
若$a[i]!=b[j]$
$$
f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]
$$
若$a[i]==b[j]$
$$
f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+f[pre_a[i]-1][pre_b[i]-1]
$$
其中$pre_a[i]$表示在$a$数组前距离$i$最近的$a[i]$相同字母的位置。
事实上变成三条的话一样，就是容斥的式子变长了点罢了。
7.1
公主的工作
好题
题意：n个数，问m次，每次询问上升子序列长度为x的高度的字典序最小的方案是什么。（注：字典序并非12比113大，而是把12看做整体的）
解：首先我们考虑普遍而又简单的最长上升子序列怎么做。设$f[i]$表示从$i$开始的到结束位置间的最长上升子序列长度，设$g[i]$表示处理到目前的长度为$i$的上升子序列的首端最大值。则$f[i]=BinarySearch(a[i],g)$。再把$a[i]$放进$g$里面。
这样操作完之后如果需要输出以下标值字典序排序的方案，则只要判断$f[i]$的值是否能达到目标值以及上一个选中的是否与当前$a[i]$大小关系符合，贪心选择即可。
对于这题要输出的以高度字典序最小的方案。我们首先来发现一个性质：由于最长上升子序列要求下标上升、值上升，两个指标事实上是可以交换的。因此如果有一个数组以值的rank为下标，以原下标为值，得到的最长上升子序列其实是一样的。那么，我们可以在程序开始就将值离散化之后转化为上一段的问题求解。
公主的朋友
题意：1-n(100000)的数列 颜色区间覆盖，一共有300种可能的颜色。100000次操作，每次覆盖同时询问区间内有多少个位置与要覆盖的颜色相同。
解：维护300个线段树是60分。考虑直接利用数据结构维护整个区间的颜色情况。可以发现，由于每次询问与修改是绑定的，且修改结束会使得区间成为同一种颜色，那么某次的询问操作越多，以后的询问就操作越少。利用分块或者线段树都可解。分块更好写，线段树更熟练。
公主的游戏
田忌赛马 贪心
7.2
小澳的方阵
题意：$1000^2$的棋盘，每一次操作都是选一种颜色和一个位置，把位置所在行和列都染成该颜色。$10^6$次操作，问最终棋盘的颜色情况
解：可以发现操作之间有很多的完全叠加现象，其实最终有用的操作数只有最多两千次。倒着暴力修改判断即可。
小澳的坐标系
好题
题意：二维平面，原点开始，上左右三个方向，不能走已走位置，问走$n\le 10^9$步有多少走法
解：设$f[i][0]$为走了$i$步，最后一步向上的方案数，$f[i][1]$向左，$f[i][2]$向右。则
$$
f[i][0]=f[i-1][0]+f[i-1][1]+f[i-1][2]\\
f[i][1]=f[i-1][0]+f[i-1][1]\\
f[i][2]=f[i-1][0]+f[i-1][2]\\
$$
矩阵乘法优化即可将复杂度减至$O(\lg n)$
小澳的葫芦
题意：DAG，边数$2000$以内，问从$1$号点出发到$n\le 200$的点的最小密度路径的密度。
解：01分数规划 二分答案（密度）ans，跑spfa。spfa的距离定义为dis[to]=min(dis[to],dis[now]+edge.w-ans)，因为每走一步都要消耗ans。最终答案大于等于0则可行，小于等于0则不行。
7.3
打印收费
小学数学题
最长合法括号序列
题意：求最长合法括号序列的长度和数量。1000000
解：用stack模拟一下即可，要注意()()的情况是可以连起来的就行
钻石游戏
题意：$500^2$的矩阵，有各种数字。每一步交换其中两个位置上的数字（保证不同），问因为此次交换形成的新的同色子矩阵中最大面积是多少。共1000次交换。
解：首先发现找最大同色矩阵可以用经典的广告牌问题 单调栈解决。然后发现这种方法需要维护的四个方向最大延伸长度在本题交换时可以快速维护。复杂度$O(n\cdot q)$
7.5
钱仓
题意：一个圈上有$n\le100000$个点，每个点上有一些钱，总量为$n$，要使每一个点上的钱都为1，而搬运钱的代价为搬运的量乘搬运距离的平方，每一个钱都只能被搬运一次。问只顺时针搬运钱的最小代价。
解：首先注意到必须顺时针搬运。那么必然有一个位置使得所有的搬运都不会跨越。找规律或推导可知该处为前缀和最低处。由于搬运代价为平方，所以搬运时必定会靠把钱搬到此处再把此处钱搬走的方式。模拟即可。
种树
题意：给定一棵树，称一个点为好的当且仅当将它删除时原图成为一棵树。问好点分别是哪几个。$n,m\le100000$
解：树是什么？是边数=点数-1的联通图。那么要删除的点只要保证删除后边数=点数-1且非割点即可。tarjan求割点
自然数
题意：设$mex(x,y)$表示数列的$x$到$y$项中未出现的最小自然数。给定数列，$n\le200000$，求$\sum _ {i=1} ^ {n} \sum _ {j=i} ^ {n} mex(i,j)$。
解：首先考虑容易想到的$O(n^2)$做法，枚举左端$i$，一个一个推进$j$，统计答案。然后考虑如何优化。我们可以发现，当$i$确定时，答案相对于$j$具有单调性(单增)；当$j$确定时，答案相对于$i$具有单调性(单减)。考虑先把$i=1$的情况的答案全部统计出来。这时候形成一个答案数列$mex(1,j)$。可以发现，每当$i$增加$1$时，答案数列中从$i$到下一个与$a_i$相等的值处的答案都将变为$a_i$，而其它答案不变。因此我们可以利用线段树维护，只需提供区间覆盖和算总和的功能即可。
7.6
Exhibit
简单思维题
国家宝藏
简单DFS/BFS/并查集
Lcm
好题
题意：与20年某模拟题一样。给定$n$，将$n$以和的方式分解成任意个整数，问分解后数列的最小公倍数的最大值。
解：可以发现，当分解出的数互质时答案最大。若不互质，则可以将其中大的那个除以公因数，将多出来的列为新数或加到别的地方使得别的数变成更大的互质的数。因此，最终答案必定为各质数的幂次相加。考虑这样的条件与多重背包相似。设$f[i][j]$为用到前$i$个质数，和为$j$的最大答案。转移显然。
7.7
Blue
简单贪心
Weed
好题！！！
题意：有$200000$个两种操作，一种是将$v_i$入栈，一种是将栈顶$v_i$个元素弹出。有$200000$个询问，每个询问会将一个操作更改(值不变，操作1和操作2互换)，问最终在栈中的元素和。
解：首先可以看出必须要用数据结构维护。从线段树的角度思考。可以发现，排在前面的操作不会对后面的操作有影响。对于线段树的每一个节点，可以记录最终节点需要删除几个、插几个、插入的和这三个值。在合并时需要到左儿子中减去删除的那几个。因此总复杂度是两个log的。操作相对复杂，思路和一般线段树不太一样，不是非常显然，好题！
Drink
好题！！！
题意：一个1000的0~9矩阵，1000次操作，每次将其中的一个子矩阵顺时针旋转。问最终的矩阵情况。
解：
暴力：从值域很小来思考。容易想到对两个方向分别维护压位的矩阵情况，旋转时截取其中的贴过去。这样大约是$1000^3/8$，2s的时限可能能过(特别如果是现代机器)
正解：假设初始所有位置的元素方向都向上，记录每个元素的前后左右分别是谁。在每次修改时，只会改变一圈的前后左右信息。于是就做完了。妙！妙！妙！
7.8
神奇的数字
题意：输入两个长度小于等于100000的01串，表示一个$\frac{\sqrt{5}+1}{2}$进制的数字，判断大小。（提示：100=11）
解：看到$\frac{\sqrt{5}+1}{2}$可以想到跟Fibonacci可能有关，（这一段是我突然sb了，这玩意不是特别显然吗？）但是不能显然地看出来，于是先进行推导。可以发现
$$
1=1\\
10=10\\
100=11\\
1000=21\\
10000=32\\
$$
显然有Fibonacci性质，直接干即可。
证据
题意：给一张图，点十万，边二十万。边权值100以内。一部分点为无效点。要求在图中选出一部分边使得所有点构成k个连通块。问所有没有无效点的连通块内边权之积的最大值。
解：首先想一想如果没有无效点怎么做。可以发现边权100以内，且结果是靠乘的，那么自然可以想到可以取对数跑最小生成树。然后考虑加上无效点怎么做。推几组数据可以发现，贪心地先连有效点和有效点之间的边，再连无效点和无效点之间的边，再按照连通块大小贪心地连有效点和无效点的边即可。证明还是方便的，重点是发现可贪的性质。
讯息
题意：比较复杂，算了，跳过
7.9
计算几何
简单计算几何+二分查找
花花的聚会
题意：有一棵$n$个节点的有根树，在某些节点$v_i$，可以选择花费$w_i$的代价，向上跳$[1,k_i]$步。$q$个询问，某节点跳到根的最少代价。 100000
解：套链剖板子啥的都行，不过最容易想到的还是倍增吧。
文本编辑器
题意：两个光标移动，好多种操作，但是光标每次最多移动一格。
解：不需要平衡树，这道题只要链表就可以了。
7.10
进制
题意：给定a，b，c，问十进制下的a*b转换成什么进制会等于c这个字符串。若答案在2到16间则输出，否则输出0。
解：直接看当然可以模拟+高精度做，其实更方便可以哈希。
置换
置换 环 的大小的最小公倍数
24点
题意：给定n个n（n<=30），其中部分数可以不用，问怎样能24点。
解：首先把十几以内的都可以暴力出来。然后考虑，如果k个任意数通过某些操作必定能达到24点，那么其实k个数以外的数就可以浪费掉。问题就在于如何构造。构造还是比较好想的。
7.11
小麦亩产一千八
简单数学题
休息
找规律+树状数组求逆序对
军训
DP 不会