BZOJ 2299
题意：给出向量$(a,b), (a,-b), (-a,b), (-a,-b), (b,a), (b,-a), (-b,a), (-b,-a)$，请你判断是否能拼出向量$(x_0,y_0)$

观察发现只有$(2a,0), (2b,0), (0,2b), (0,2a), (b,a), (-b,-a), (-a,-b), (a,b)$种向量，并且后面的$4$种每种只会最多用一次。那么可以设方程

$$
\begin{cases}
2ax+2by=x_0 \\
2bx+2ax=y_0
\end{cases}
$$

根据裴蜀定理，有解的充要条件是

$$
gcd(2a,2b)|x_0 ,gcd(2a,2b)|y_0
$$

对于后面四种向量，由于每种最多用一次，分类讨论使用后再列方程判即可，因为$gcd$负数的绝对值和正数的相同，所以只需要讨论正数的即可。

Codeforces 1091D
题意：给定$n$，将$[1,n]$的排列按字典序接成$n \cdot n!$长的序列，求序列中有几个长度为$n$的区间和等于$\frac{n(n-1)}{2}$

显然这个区间是一个排列。那么我们可以统计每个排列的贡献。
对于一个合法的区间，他一定是一个排列的结尾接上一个排列的开头。所以可以将组合问题分解
对于一个排列有$n$种分解方法，所以有$n \cdot n!$种方案。
但是有不满足的情况，例如$(4, 2)$, $(1, 3, 5)$是不能接一起的。这样两个排列字典序大小不满足。
观察发现前面的是一个递减序列，所以我们要将这些递减序列构成的都删掉。选出$i$长递减序列有$C^{i}_{n}$种方法，对于每个递减序列他的第二个部分是随便填的，所以最后答案为

$$
n \cdot n! - \sum_{i=0}^n C^i_n \cdot (n-i)!
$$

找规律方法：
1、观察样例解释，发现和等于$\frac{n(n-1)}{2}$的有周期性
2、打表$4$的答案(顺序打印区间和)，发现确实有周期性，并且发现周期为$n!$
3、打表$3,5$的答案，发现答案有递推性
4、发现答案一定是两个数相乘，因为周期是$n!$，选择有$n \cdot n!$种，所以两个数中有一个是$n$
5、对另一个数分析，观察表可以发现$4$的每个周期都在$3$的基础上加上了$(n-1)!$个答案
6、对答案调整分析，上面的还要减一才行
7、写出递推式
$$
f(i)=i \cdot ((i-1)!+f(i-1)-1)
$$
其中$f(1)=1$

Codeforces 1095F
题意：给定字符串$s$，每个位有一个权值，删掉一个位代价为这个权值。请求出最小使得字符串不包含子序列hard的代价。

最优化问题想到DP，并且这题类似于 Bzoj 1030 AC自动机。
这里是一个匹配类状态的 DP，设$dp(i,j)$为前$i$位，$j=0$表示没有匹配，$j=[1,3]$表示匹配到了前缀h, ha, har的最小代价。

转移则

dp[0][0] = 0;
for (LL j = 0; j < 4; ++j) dp[i][j] = dp[i - 1][j];
for (LL i = 1; i <= n; ++i) {
  if (s[i] == 'h') {
      dp[i][0] = dp[i - 1][0] + a[i]; //  将 `h` 删去
      dp[i][1] = min(min(dp[i - 1][0], dp[i - 1][1]), dp[i - 1][1] + a[i]); // 不动或者将 `h` 删去
  }
  if (s[i] == 'a') {
      dp[i][1] = dp[i - 1][1] + a[i]; //  将 `a` 删去
      dp[i][2] = min(min(dp[i - 1][1], dp[i - 1][2]), dp[i - 1][2] + a[i]); // 不动或者将 `a` 删去
  }
  if (s[i] == 'r') {
      dp[i][2] = dp[i - 1][2] + a[i]; //  将 `r` 删去
      dp[i][3] = min(min(dp[i - 1][2], dp[i - 1][3]), dp[i - 1][3] + a[i]); // 不动或者将 `r` 删去
  }
  if (s[i] == 'd') {
      dp[i][3] = dp[i - 1][3] + a[i]; //  将 `d` 删去
  }
}

其实中间转移不需要dp[i - 1][3], dp[i - 1][3] + a[i]，因为$a_i \geq 0$，所以直接写即可。

Codeforces 1056B
题意：求$m | (x^2+y^2), 1 \leq x, y \leq n$的$(x,y)$个数。($m \leq 2000, n \leq 10^9$)

其实观察题目样例解释可以发现，互质对只有$(1,2), (1,3), (3, 4)$。其他的都是在$\leq n$范围类的倍数。特殊的$(5,5)$我们也将其列入。观察这些数对都是小于$m$的，不妨将$(5,5)$记为$(0,0)$，这些数对都满足$m | (x^2+y^2), 0 \leq x, y < m$，所以我们可以尝试在$m$范围内枚举这样的数对，然后再统计在$n$范围内的数量即可。

数学方法：
$m | (x^2+y^2) \Leftrightarrow (x^2+y^2) \mod m = 0 $
那么在$m​$范围类枚举这样的数对，然后在$n​$范围内统计个数即可。

Codeforces 1095F
题意：$n$点无向图最开始没有边，加一条边的代价为$A_x+A_y$, $A_i$为点权，现在有$m$个特殊方案$(x,y,w)$使得$x,y$连通，花费$w$。请问使图连通最小费用。

最开始我的思路：
考虑没有特殊方案，则就是个合并果子，必须保证每次都将两个连通块，并查集维护。
如果有特殊方案，那么每次操作要将两个连通块并起来。将方案按价值增序，那么堆中取出两个元素后和当前方案对比哪个方案连通最优。

其实更容易的：
考虑没有特殊方案，可以发现所有点都会连在一个最小价值的点上。
如果有，将所有点都会连在一个最小价值的点的操作一起并到特殊方案里排序取最优。

CH 46A
题意：见上。

容易发现可以用BFS从L开始一路下去找能吸附的。
关键是怎么找能吸附的，这里有两维$(m \leq p, dis \leq r)$这里可以用平衡树之类的去维护，比较麻烦
其实可以用分块来做。将原数组按$m$排序，然后就消除第一维影响
然后在块中按$dis$重新排序，然后就能满足块中$dis$单调，对于看作整体的块$m$单调。(分块处理二维的问题)
那么我们只需要查询，对于每个$m \leq p$整块，找$dis \leq r$的元素并且标记到当前位置，之后扫描从这里开始(前面都被挖走了)。对于$m$不完全小于$p$的一个不完整块，暴力统计。

这里分块可以简单写：$l,r$表示当前块的开始结束位置，不需要$bl$数组，询问也可以插到 BFS 里写。

模板及讲解

什么是CDQ分治

CDQ 分治就是将询问和修改(初值)都离线，然后对其分治的一种方法。
具体就是每次将区间一分为二，然后只统计左边修改对右边询问的影响，以此类推。

CDQ分治解决什么问题

CDQ 分治一般用来降维。比如有题需要树状数组套平衡树则可以降至只用树状数组解决。
CDQ 分治优点是将询问和修改隔离，即转为静态问题，且常数较小。缺点必须离线。
CDQ 分治的实现与归并排序类似。

CH 5105
题意：有$n$个人，每个人有一个$g_i$，现给$n$人分配$m$个饼干(每个人都要有饼干)，对于第$i$个人，比他饼干多的人数记为$a_i$，请最小化$\sum_{i=1}^n a_i g_i$

容易发现$g_i$大的$a_i$尽可能小，所以$g_i$单调递减时分配的饼干也单调递减。
对$g$降序排序后，设$dp(i,j)$为前$i$个人合分$j$块饼干的最小值。
则有
$$
dp(i,j)=min(dp(i,j-i), min_{0 \leq k < i}(dp(k, j - (i - k)) + k \cdot \sum_{x=k+1}^ig(x)))
$$

当第$i$位不填$1$时，前$i$个人分$j$块对应于前$i$个人分$j-i$块，因为每个人少拿一块，相对关系不变
否则，枚举前面有几个和它一样的，统计答案。

注意解的输出要按照dp意义来，注意递归输出在本题会好用些。

CH 4302
题意：给出一个$n$长序列，你要支持区间增加和查询区间$gcd$。

显然的线段树，但是区间增加对于$gcd$不好更新$lazy$标记。那么我们只能考虑一下能不能只单点修改，那么我们就想到了差分序列。
根据$gcd(a,b)=gcd(a, b-a)$推出$gcd(a,b,c)=gcd(a,b-a,c-b)$然后推广到更多数字可以发现，区间$gcd$值就等于区间第一个数和之后区间的差分序列的$gcd$相等。
所以只需要维护差分序列的$gcd$，线段树变为了单点修改区间查$gcd$。

因为要用到原数组，所以开一个 BIT 维护原数组的差分序列即可

「poj 2182」 Lost Cows
题意：有$n$头牛，编号为$[1, n]$。 乱序排成一列，已知每头牛前面有多少头牛比它的编号小（从第二头牛开始）。现在要求从前到后，每一头牛的编号。

考虑逆向思考，对于第$n$头牛如果前面有$a_i$头比他小，那他得编号就是$a_i+1$
对于第$n-1$头牛类似，只不过有可能编号在之前用过了，也就是在一个集合中找排名为$a_i+1$的数。
所以我们要维护一个集合支持删除一个数，查询$rnk$，显然线段树和Splay是可行的。
然而这里可以用编码量更小的树状数组+二分。
因为正数前缀和有单调性，所以我们将存在和不存在记为一个二进制01序列，然后可以通过前缀和判断当前为是排名多少的。然后就能二分了。