2019.4.18
t1:给出不定方程ax+by+c=0，求x在x1~x2并且y在y1~y2时的解个数。考场上想的是一个扩欧板子敲下去，然后构造出x>=x1的最小解，同时得出y，然后通过通项来枚举x1~x2之间的x，判断y是否合法，然后累计答案即可。但正解并不需要枚举，因为x的通项是x=x0+kb，y是y=y0-kb，现在得出了x0,y0，也知道b，直接解一组不等式就好了：x1<=x0+kb<=x2,y1<=y0-kb<=y2，若k算出来不是整数：a<=k<=b，则下界上取整，上界下取整。考场用时：30min，得分50。
t2:给出一个圆的方程x2+y2=r2，求圆上有多少个坐标为整数的点。考场上先想了个暴力，两边先模上一个大质数p，然后转化为x2+y2Ξr2(mod p) => y2Ξr2-x2，枚举x，然后解出y2，判断y是否为整数，然后累加答案。而光是枚举就会超时。正解是，把圆方程看成一组勾股数，然后通过勾股数的特性来解。考场用时：2h(扩欧一直写挂)，得分0。(数据真的强)
t3:定义函数f(n)=11*22*33*...*nn，一共q次询问，对于每次询问给出的r，求f(n)/(f(r)*f(n-r)) mod m。但是考试时给下来的题目把分母的括号吞了，就是：f(n)/f(r)*f(n-r) mod m，照着这个写就挂了。。。我的思路是(当然是求后面这个错式子的思路)，离线处理，先线性算出f(i)%m，然后询问时求出f(r)的逆元就可以回答了。顺便写了个记忆化，把f(r)的逆元存了起来。但是好像一组数据之后忘了memset。。。当然那时的思路也是错的，因为f(r)不一定与m互质，不能够求逆元。正解是，把m分解质因数，分别计算对答案的贡献。考场用时:30min(先做的t1,t3)，得分0(题目没错的话应该能拿一点)。
2019.5.7
t1:列车调度。考场思路：暴力+贪心，每次找后面第一个小于当前编号的值，并把找出的序列打好标记，以后不再使用。时间复杂度O(n2)，期望得分40，实际100(滑稽)因为数据很水......但正解还是要敲的。实际上这道题类似于luoguP1020 导弹拦截的第一问，直接求最长不上升子序列即可。求法可以O(n2)，但可以用二分优化一下，复杂度为O(nlogn)，期望得分100.
t2:Learning Languages。考场思路：并查集动态求连通块个数。当出现新语言时cnt+1，并判断能否并入其它集合中，若可以则cnt-1，最后答案就是cnt-1。时间复杂度O(n*α(n))，期望得分91(AC分).然而手残把n打成m，只有41......
t3:[Noip模拟题]序列。考场思路：贪心。先选最低温度，能不降就不降。然而是个错贪心，像：4 2 4 1 3 1 1 1 1此类的hack数据随便造......期望得分：30，实际得分80(哦哟)。正解是，用单调队列维护一段单调不上升序列，找出最长的一段。
2019.5.8
t1:最大子序列之和2。考场思路：动态规划，设dp1[i]表示1~i的最大子序列和，dp2[i]表示i~n的最大子序列和，求出来之后枚举分界点，ans=max(ans,dp[i-1]+dp[i+1])。时间复杂度为O(n)，期望得分:100，实际得分50......原因是求dp数组的地方写爆了。正确的写法是：
for i = 1 to n do sum+=a[i]; if(sum>dp[i-1]) then dp[i]=sum; else if(sum<0) then sum=0,dp[i]=dp[i-1]; else dp[i]=dp[i-1];
两个dp数组都是类似这种方法来求。因为子序列和为负数的话还不如不选，所以将sum清零。
t2:Vijos1617 超级教主。考场思路：动态规划+单调队列。设dp[i]表示拿完了高度<=i*100的所有能量球可以剩下的最大能量，可以列出式子：dp[i]=max(c[i]-c[j]+dp[j]-i*100)，其中c数组为前缀和，1<=j<i。可以双重循环求得答案，时间复杂度为O(n2)，期望得分40。考虑优化——显然对于每个i，我们只需要dp[j]-c[j]最大的即可。设f(x)=dp[x]-c[x]，我们可以用单调队列维护max{f[j]}。当队首元素的dp值不足以跳到i的高度时，将它出队即可。时间复杂度为O(n)，期望得分100。实际得分10......原因是把代价的式子写错了......
t3:[Nwerc 2006]escape。考场思路：二分答案求出最大距离，然后在保证与敌人距离的前提下广搜求得最小步数。时间复杂度为O(X2*logANS)，这是上界，期望得分100，实际得分15......原因有很多：
1.每次搜索之后队列没有清空就再次使用。
2.对于与敌人的距离是用双重循环标记的，是个不小的常数，最后三组会超时。更好的做法是从所有敌人开始往外搜索，求出所有点与最近的一个敌人的距离是多少。这样在二分+搜索时直接判断当前的距离是否大于等于二分出来的值即可。
3.当出发点与敌人的距离小于当前的二分值时应特判一下。
2019.5.18
t1:射击。考场思路：暴力搜出第一行全部边凹的方案，然后对于每种全凹的状态都模拟推出2~n-1行全部变凹的步数，最后判断最后一行是否全凹。期望得分70，实际得分40.原因是：搜重了很多状态，为了剪枝还剪多了很多。正解思路：用二进制数枚举射击第一行的哪些地方，然后在2~n行模拟，如果上一行某个位置为1就射击此行这个位置，时间复杂度为O(2N*N)。
t2: 八中生成树。没有思路，连暴力也没想到，太弱了。只有敲了一个最小生成树上去骗分，看能不能拿到次小生成树等于最小生成树或者输出-1的情况。期望得分10，实际得分10.正解思路：先求出最小生成树，然后枚举树外的每条边。对于枚举到的边E(u,v)，不难想到如果把它加入生成树就必定会断开路径u->LCA(u,v)->v之间的一条边。由于要求次小生成树，所以我们希望加入生成树时影响尽量小，而其影响为：
加入的边-删去的边
前者我们枚举已经得到，后者当然越大越好。所以问题转变为：求生成树上两个点之间边权的最大值，用倍增做复杂度为O((N+M)logN)，总复杂度为O(M((N+M)logN+logM))；还可以树剖直接做，总复杂度为O(M(Mlog2N+logM))。
t3:[Usaco2017 Feb]Why Did the Cow Cross the Road II。考场思路：动态规划。设dp[i][j][0]表示A序列的第i位和B序列的第j位不连接的最大连接数，dp[i][j][1]表示A序列的第i位和B序列的第j位连接的最大连接数，转移方程：
dp[i][j][0]=max(max(dp[i-1][j][0],dp[i][j-1][0]),max(dp[i-1][j][1],dp[i][j-1][1]));
dp[i][j][1]=max(dp[i-1][j][0],dp[i][j-1][0])+1;
似乎是这样...时间复杂度就是O(N2)，期望得分40，实际得分20，数据太强，并且NlogN级别才是正解。正解思路：把每个点能连的位置降序排序，求LIS。
2019.6.5
t1:整数区间。考场上没有思路，写了错贪心骗分，得了10分。正解是贪心，尽量选右边的数。具体是对区间按照右端点排序，枚举每个区间，看这个区间有多少个数在集合中，不足两个就用右边的数不足。时间复杂度为O(N3)，不过常数很小可以过。
t2:[Usaco2010 Mar]gather 奶牛大集会。考场思路：树形动规的换根法，把每个节点的不方便值算出来求最小值。时间复杂度为O(N)，期望得分100，实际得分90，原因是递归爆栈了(std也爆了)。正解和考场思路一致。
t3:[USACO14OPEN]GPS的决斗Dueling GPS's。考场上没看懂题和样例，写了个错贪心上去，加了个随机化，得分20。正解是对于每个GPS都建个反图跑最短路，再计算每条边有几个GPS的最短路图没包含它，作为新图的边权。最后在新图上再从起点往终点跑最短路即可。时间复杂度为O((N+M)log(N+M))。
2019.6.7
t1:[Noip模拟题]血色敢死队。考场思路：广搜，时间复杂度O(N^2)，期望得分100，实际得分100。
t2:[Noip模拟题]兴建高铁。考场思路：分层图最短路，时间复杂度为O((N+M)log(N+M))，期望得分100，实际得分56。原因是没有判题目要求的最优值。正解用深搜就可以过，只要判了最优值。
t3:[Noip模拟题]珠光宝气阁。考场思路：广搜+启发式，期望得分60，实际得分27?(不记得了)。正解是状压后加广搜。
2019.6.10
t1:[Noip模拟题]poker。考场思路：抽屉原理+贪心，时间复杂度O(N)，期望得分100，实际得分50。原因是算式子时多算了一项。看到别人用NlogN过了真心不爽...
t2:工业时代。考场思路：单调队列优化dp，时间复杂度为O(N^2)，期望得分100，实际得分100.
t3:[Noip模拟题]杀蚂蚁。考场思路：动态规划，时间复杂度O(n^3)，期望得分40，实际得分40。正解是再优化一维的N^2动规。
2019.6.11
t1:Gift。考场思路：没有思路，写了骗分程序，得了27分。正解是二维的最小生成树，枚举第一维求第二维。
t2:Coin。考场思路：暴力求n次背包，期望得分40，实际40。正解是利用背包的性质直接算。
t3:[Noip模拟题]小Y的炮。考场思路：没有思路，写了错贪心，得分5。正解是贪心。
2019.6.13
t1:POJ1639 Picnic Planning。考场思路：错贪心+随机化，得分80。正解是枚举Party点连哪些边。
t2:Poj3585 Accumulation Degree。考场思路：树形dp，期望100，实际80，原因是转移错了。正解也是树形dp。
t3:POJ1179 Polygon。考场思路：错区间dp，得分0。正解是区间dp。
2019.6.17
t1:[Noip模拟题]Seq。考场思路：错贪心，得分14。正解是贪心优化的dp。
t2:photo。考场思路：区间dp+状压，也是错的，得分20.正解是状压dp。
t3:[noip模拟]分组行动。考场思路：求出最大生成树然后倍增求路径最小边，得分100。正解类似，但是是离线，不优。