既然考完NOIP了，那就来补下题吧>_<。
Day1 T1
Solution
30%这个随便瞎搞应该都能A，没有细想。
60%
题目其实就是要求最大的不能满足$ax+by=k, \, x,y \in N$的数字。
由于$gcd(a,b)=1$，因此必定存在$ax+by=1$的解，假设这对解为$(x_0,y_0)$。扩展到任意正整数$k$的话，解就为$(kx_0,ky_0)$。
又由于$x,y \in N$，所以我们需要调整答案使得$0 \leq kx_0+pb,0\leq ky_0-pa$，而且$p \in Z$。
由此可以解出关于$p$的不等式$-\frac{kx_0}{b} \leq p \leq \frac{ky_0}{a}$。
使得$p$存在整数解的充要条件为$1 \leq \lfloor \frac{ky_0}{a} \rfloor -\lfloor -\frac{kx_0}{b} \rfloor$。
高斯函数怎么解啊，反正考场上我是一脸懵逼的。
这个不等式无法解决，但是我们可以得到更为宽松的上界。
即令$1 \leq \frac{ky_0}{a} +\frac{kx_0}{b}$，这个不等式可解得$ab \leq k$。
也就是说，我们要求的答案必定是$< ab$。
这样的话，就可以直接做个背包来判断整数$k$是否能被凑出来了。
时间复杂度$O(ab)$。
100%
我们可以观察到$ab$必定只能被$a$或$b$凑出来，因此$ab-a-b$必定是不能被凑出来的。
然后再利用反证法证明$(ab-a-b,ab)$内的数字都能被凑出来即可。
或者我们可以参照一下墨墨的等式(BZOJ2118)这题。
首先考虑模$a$下的一个同余类。如果$x$能够被凑出来，那么$x+ka$都能够被凑出来。
由于$a$和$b$互质。因此，我们可以构造出一个完系，即$\{0,b,2b,3b,…,(a-1)b\}$。显然这个完系中的每个数为对应同余类下的最小的能够被凑出来的数字。
所以，对于每个同余类，最大的不能够被凑出来的数字分别为$b-a,2b-a,3b-a….(a-1)b-a$。
因此，答案为$(a-1)b-a$。
时间复杂度$O(1)$。
CODE
CODE - Click Here
Day1 T2
Solution
30%由于$x<y$，且仅有$y$可能为$n$。
因此时间复杂度只有$O(1)$和$O(n)$两种情况。
若$y$为$n$，则时间复杂度为$O(n)$，否则时间复杂度为$O(1)$。
直接统计判断即可。
50%
时间复杂度情况同$30\%$。
但是允许存在循环并列的情况。
因此，对于每个循环，需要找到被哪个循环嵌套。
这个可以利用栈来维护，$F$代表入栈，$E$代表出栈。对于每个循环而言，被嵌套的循环必定为栈顶元素。
然后利用$30\%$做法统计判断即可。
70%
$x$和$y$没有限制。
分析一下所有可能的情况。
$x$为$n$，$y$为$n$，时间复杂度为$O(1)$。
$x$为$n$，$y$为整数，时间复杂度为$O(0)$。
$x$为整数，$y$为$n$，时间复杂度为$O(n)$。
$x$为整数，$y$为整数，且$x\leq y$，时间复杂度为$O(1)$。
$x$为整数，$y$为整数，且$y < x$，时间复杂度为$O(0)$。
然后利用$50\%$做法统计判断即可。
100%
存在语法错误。
语法错误有两种，$F$与$E$不匹配和变量重复。
对于情况一，出栈时判断是否为空栈，结束时判断是否为空栈即可。
对于情况二，开个$bool$数组来判断某个变量是否占用即可。
然后利用$70\%$做法统计判断即可。
CODE
CODE - Click Here
Day1 T3
Solution
10%随便暴力，应该能A。
30%(K=0)
就是一个最短路计数。
跑最短路后用DP求方案即可。
时间复杂度$O((N+M)logN \, + \, N + M)$
70%(无0边)
无0边表明必定有解。
因此可以首先跑出$1$至所有点的最短路。
然后显然可得DP方程式，$f(i,j)$表示到点$i$且与最短路距离相差为$j$的方案数。
如何转移DP？
有两种写法。
一是对于每个点$i$将其拆成$K+1$个节点，然后在新图上连边。由于必定有解，因此新图肯定是DAG。直接拓扑排序转移即可。
二是以第二维为转移顺序，对于每个$j$从$n$开始倒着dfs转移。并利用记忆化搜索加速。
两种时间复杂度均为$O((N+M)(logN+K))$。
100%
答案可能存在无解情况。
考虑如何判断无解，有三种方法。
一是考虑图中的每个0环，如果$1$至0环的最短路距离+0环至$n$的最短路距离小于$1$至$n$的最短路距离+K，则答案是无解的。
二是考虑构造出新图，并在新图上判断。如果这个新图有环，并且这个环会对$n$造成影响(这个有两个条件，连通性和存在答案)。那么答案是无解的。
三是在记忆化搜索的时候，如果出现一个环，那么答案是无解的。
判断完答案之后合法后，再套用$70\%$做法即可。
由于方法三是最好写且空间是最小的，因此给出的代码为方法三的做法。(其实是码了方法一结果跑得贼慢)
CODE
CODE - Click Here
Day2 T1
Solution
20%由于只有一个球，因此判断该球是否和上下表面相交即可。
40%
暴力枚举路径，判断是否能从下表面走到上表面。
80%
并不是很懂这个部分分用来干嘛的。。。
用来卡sqrt和double？
100%
考虑两个球之间是否相交，即判断不等式$dis(P_i,P_j)^2 \leq 4R^2$是否成立。
由于距离可能爆long long，因此可以移项来避免。即判断$(x_i-x_j)^2+(y_i-y_j)^2 \leq 4R^2 - (z_i-z_j)^2$是否成立。
构出图后再判断是否联通即可。
时间复杂度$O(N^2)$。
CODE
CODE - Click Here
Day2 T2
Solution
20%保证是一棵树，也就是说方案唯一。
DFS一遍求出答案即可。
40%
所有$v$都相等，因此决定答案大小的是深度。
枚举一个根，然后跑最小生成树即可。
70%
注意到边看起来很多，然而实际上有用的边只有$\frac{n(n-1)}{2}$条。
因此可以暴力枚举选取哪些边，然后$N^2$暴力检验答案。
时间复杂度$O(N^2 \times C_{\frac{n(n-1)}{2}}^{n-1})$。
由于不是所有选取方案都能够构成一棵树，因此这个时间复杂度下界是很宽松的。
100%
听说原范围就是$N \leq 8$？
还好吉老师改了范围，不然我就没有半点优势了。
我们需要构造出一棵树，使得其总代价最小，而且总代价与节点深度有关。
因此可以得到一个DP方程，用$f(i,S)$表示到第$i$层深度总共选了$S$集合的点的最小代价。
然后易得转移方程，$f(i,S)=f(i-1,S-S’)+i \times cost(S’,S-S’),S’ \subset S$。
$cost(S’,S-S’)$代表$S’$和$S-S’$的最小连边花费，虽然不能保证$S’$都能和上一层的节点连边，但是这并不影响答案，因为若和非上一层节点连边，答案必定是偏大的。
若在每次转移都计算$cost$，那么时间复杂度将为$O(N^3 \times 3^N)$。
若对$cost$进行预处理，那么时间复杂度将为$O(N^2 \times 3^N)$。
对于此题而言，两种实现方法时限都很危险，因此需要进一步优化。
由于时间是花费在$cost$的预处理上，因此优化预处理成为了时限关键。
注意到一个节点多次计算了和某个集合的最小连边，因此可以定义$g(i,S)$表示，$i$节点向集合$S$的最小连边。这个可以在$O(N^2 \times 2^N)$内完成。
计算出$g$后，再利用$g$来处理$cost$，则能够将时间复杂度降至$O(N \times 3^N)$。
总时间复杂度为$O(N^2 \times 2^N+N \times 3^N)$。
CODE
CODE - Click Here
Day2 T3
Solution
30%(n=1000)这个暴力模拟就好了，没什么技巧。
40%(q=500)
$q \leq 500$表明有许多行完全没有进行过操作。
因此可以离线后，对每行暴力处理。
时间复杂度$O(nq)$。
30%(x=1)
$x=1$时，受到影响的只有第一行和最后一列。
然后每次出队，都相当于删除一个元素，添加一个元素。
线段树或平衡树都可以实现。
时间复杂度$O(q log \,n)$。
100%
从$x=1$处很容易可以推出正解。
由于每次操作，只有当前行和最后一列执行了删除元素，添加元素操作。
因此套用$x=1$做法同样可以解决，不过要动态开点。
因为写平衡树还要维护原来行的元素，所以我直接码了线段树。
对于每行都建一个$m+q$的线段树，对于最后一列则建一个$n+q$的线段树。
然后删除元素就标记上$-1$，询问就在线段树上二分即可，很好码的。
时空间复杂度$O(qlog(m+q))$。
CODE
CODE - Click Here