no11

周赛22 -3 构造数组

这个题目挺好的。
思路：

1. 1-n选取2m个数字。那么设$x_i$为$i$选了$x_1$次.考虑到$x_i$的取值可能为0，那么我们需要第二步变换
2. 将全部的解$x_i$+1，如此新的解的取值一定是为正整数。
3. 使用隔板法的思想，求解组合数~

我不喜欢一个拘泥于数据的算法，比如杨辉三角的小模板，我知道他写起来很简单，开一个数组模拟一下就完事，但是总是给我一个，万一数据题目开大了我就无所适从的无奈。
这里我使用逆元求组合数的方式，至少比起杨辉三角普世一点，而且它也不比杨辉三角难写呀~~

// 求逆元使用的是快速幂的方法，借用费马小定理
// 当然求逆元也可以借用扩展欧几里得算法，但是个人觉得不如上面推荐的，这里就不写了

LL fc[N] , ifc[N] ;

LL qmi(LL a , LL b) 
{
    LL res = 1 ;
    while(b) 
    {
        if(b&1) res = res * a % mod ;
        a = a * a % mod ;
        b >>= 1;
    }
    return res ;
}


fc[0] = ifc[0] = 1 ; 
for(int i = 1 ; i < N ; i ++ )
{
    fc[i] = fc[i-1]* i % mod ;
    ifc[i] = ifc[i-1] * qmi(i , mod -2) %mod ;
}

no12

周赛22-传送门

经验： 一道搜索题。题本身不难，想强调的是一些坑。
对于迷宫搜索题型，轻易还是不要写dfs来解决问题，这道题很好的佐证了这一点。我先对本题写了dfs代码，只能通过12-14个数据，换成bfs才能完整通过。两段代码是等价的，所以我们可以小心猜测两者之间的时间复杂度还是差着一个不可描述的距离~

no13

bash game 的解题思路 ： dp打表 + 找规律 –> if-else判断直接输出答案
抽时间我会系统整理这里的思路

no14

周赛25 - 3 染色

这道题目挺棒的。

思路：

题目的描述很有迷惑性。但是我们抓住以下就可以比较轻松的解决。

1. 最终的合法状态。这是一个被题目所规定的一个一个的集合。每一个集合都包含着相应下标（题目要求相应集合里面的下标的颜色相同）。

2. $res = \sum f_{i}$ , $f_{i}$被定义为，第$i$个集合需要进行染色的最小步骤。

3. $f_{i} = SIZE(i) - MAX(i)$ ; $SIZE(i)$是第$i$个集合的大小 ， $MAX(i)$是第$i$个集合中出现最多的颜色的个数。

no15

周赛29-2-线段覆盖

这个题目我觉得很有代表性。数据开的很大，巧用map解决了这个问题。
思路是差分的裸题思路。

思路

给出左右端点l,r , 表示这个区间被累加1。也即map[l] ++ , map[r+1] -- ; 最后对这个map的存储元素进行枚举。代码值得反复吸收。

no16

周赛30-2-最长合法括号子串

这个题目的思路当做模板来记下吧。

no17

周赛30-3-公约数

这道题目启发了我们一个定理，我们一定要记住它。
设命题$P$: 存在x整除a，x也整除b 命题$Q$:x整除gcd(a,b)
那么：P 和 Q 互为充分必要条件
人话，以上两个命题可以互推。

这道题目要求给出区间L,R之间的a，b的最大公约数。

思路

题目要我们求的是伪最大公约数，即有限制条件的最大公约数。但是无论怎么样，这个答案必定是a，b的公约数。我们如何求得两个数的所有公约数呢？

由以上命题，我们知道，gcd(a,b)的所有约数，就是a，b的公约数。

因此，获得gcd(a,b)之后，再把gcd(a,b)的约数求毕即可。存在一个vector里面。

在vector里面写一个简单的二分，轻松搞定~

no18

周赛33 - 括号序列

我对括号序列PTSD了

稍微简单总结一下下

1. 题目的括号序列只涉及一种括号，那么我们可以通过贪心的思想，比如这道题目的题解。具体来讲是，设计一个计数器，遇到左括号就加加，遇到右括号（并且当前计数器不是零）计数器减减，伪答案加加（伪答案记录配上的对数）。最终答案是二倍的伪答案。
2. 如果题目涉及了两种括号，（一般是小括号和中括号），那么就是区间DP了。当然这种 思路也是适用于上面的那种情况，但是上面的情况里面的数据会开得特别大。情况1适用于字符串长度1e6的，情况2适用于字符串长度不超过100的情况（单个测试样例）。
3. 特别注意的是，以上的贪心的思想不可以应用到情况2中来。以下是一个反例，正确答案是4 .

([[(])[[))

no19

周赛34 - 2 - 数字

知识点补充

补一个短除法的模板

int pth[N] , idx ;
int base(int n ,int b) 
{
    while(n) 
    {
        pth[idx++] = n % b ;
        n /= b ;
    }
}

no20

周赛36 -3- 机器人移动

做完这道题目之后，发现自己之前做的题目导致自己形成了一个思维定式——谈到代价都会不自禁去联系到数组元素本身如何如何。而这道题已经摆明了，代价只和修改区间长度有关，换言之，被修改的区间里如何如何都不会直接影响到代价取值。也就是说，我们可以二分区间长度来获得答案。

证明此题的二分可行性：
以下在有解的情况下讨论。
显然答案取值范围0-n，区间L。
不妨设答案取x，落在区间L上。x是最少修改的区间长度。
任何大于x的区间长度都是满足修改若干个指令可以到达终点的特点的。具体怎么改指令我们不用管。只需要知道可修改的长度越长，我们越是可能到达终点。当修改区间为x的时候都可以到达终点，那么任意大于x的长度一定是可以到达终点的。（注意。能否到达只取决于可修改的指令长度，随便改，长度够长，能到就行）
任何小于x是不可以满足以上讨论的性质的。会发现小于x的区间，怎么修改也无法到达，这是因为给定的指令长度已经决定了路途的大部分。