# 比赛总结
## 牛客多校第一场 1/4/13
> 通过：D
> 补题：H，J，K
### 总结
回来之后打的第一场组队赛，状态还是不太好；三个人提前讨论过分工，开题时候先读到签到的那个人直接写；这次签到是个小思维的博弈论，陈市和王永峰讨论了一会才猜到了结果，交一发a了；之间石在想J题，a了签到之后我们就一直卡在J和K上，基本没啥思路，期间石主要负责K，想到了一些关于环的解法，最后都被推翻了；王永峰负责J，最后已经写出正解了，码力没有跟上。

总的来说回来之后还是要尽快进入状态，很多题都是思维题，没有用到很高深的算法，应该加强这部分，我的方法只有多做题，很多时候在潜移默化中就能培养一些套路。还有就是代码能力，这个更应该通过多写代码来增强。
### 题解
+ D：博弈论，比赛的时候，通过几个例子的检查，大胆的猜测出了答案，然后就A了
+ H：在比赛的时候想了很久，没有思路，最后通过讲解，学到了正序相交，正序包络，正序不交，反序包络，反序不交，反序相交之间的关系，重要的是把这里搞清楚，这道题基本就差不多了
+ K：比赛时候想了好多思路，最后发现没有一个是对的。先生成bfs树，将非树边和树边分开讨论，如果非树边可以无限制加点，树边不加点，这里要特判叶子结点是否连接非树边，如果没连可以加点。整体的大思路就是如果加点在树边上，肯定会顶掉一些叶子节点，就算叶子足够浅，也是在叶子边上加点最优。
+ J：比赛时已经想出了思路，跟题解完全一致，但是不够坚定，在写代码的时候因为区间的边界混乱导致没能全部通过样例。在debug的时候也一直因为担心这个思路不对而心不在焉。结束后看到题解和我们的思路一样立刻就修改完通过了。思路就是考虑每一轮能赢钱的概率，即是不能连输到本金输光为止——如果现在有 *x* 元，找到最大的 *r* 满足 $2^{r}$-1*≤* *x*，则概率为 1 *−* $(\frac{1}{2})^{r}$。最后找枚举r，找寻对应的区间[$2^{r}$-1，$2^{r+1}$-2],在这一段获胜的概率是一样的，结合快速幂即可通过。

    long long exgcd(long long a,long long b,long long &x,long long &y)
    {
        if (!b)
        {
            x = 1, y = 0;
            return a;
        }
        long long  d = exgcd(b, a % b, x, y);
        long long  z = x;
        x = y;
        y = z - a / b * y;
        return d;
    }

## 牛客多校第二场 2/5/13
> 通过：E，I
> 补题：D，F，K
### 总结
我们仨人同时开了E、I题，石和王讨论了一会I之后有了思路，石负责码，王去和陈讨论E，石很快码完I之后加入讨论并想出了一个可行解，码了发发现总是wa，然后石和陈开始找bug，这期间王开了F，最后经过漫长的尝试发现边界条件写错，改过来交一发，a了E；之后王和陈卡在了F博弈论，石卡在了K，一直到结束也没想出正确解法

在关于边界条件上，还是要慎重，石这次尝试的是以long long溢出为限界，但不到万不得已不要用这种，就像这次的E，用<=$10^8$就能过就别用溢出这种；博弈论中运用了李国鸿在比赛前一天分享的那个找对应的思想，但是我们都没想到，另外，团队的dp能力也需要加强，起码在这次比赛中，王先入为主的认为K不能用dp，不满足最优子结构，需要后记状态等等，其实如果dp学的好，能一眼看出dp的状态和方程，所以还是要加强dp的理解，滚动数组、状态的定义，转移方程的构建等等；另外就是本场有歪榜题，石在比赛之后想了一小会就把D题a了，这说明读题时候不应该仅仅读题，而是边读边思考，否则就会按照通过人数做题，被榜带着走。
### 题解
+ E：思维题，枚举x的位数，开方上取整和y比较就行
wa点在于x位扩张的终止条件：一开始感觉输出y是10^9^，应该把x扩张到溢出即可，但是可能有些太大了，改成10^18^就对了

    while(x <= 1e18) { // 这里如果是(x > 0)就会wa
        int ans = check(x, cnt);
        if(ans > 0 && ans < 1e9) {
            std::cout << ans << endl;
            return ;
        }
        else {
            x *= 10;
            cnt *= 10;
        }
    }

+ I：构造，水题，判断总共是奇数行还是偶数行，偶数行每行4x4o交替放就行，奇数行要在最后一行1x1o交替放
+ F：博弈论的思维题。跟本周第一队分享的思维题中的博弈论题的思路是相同的。就是去找两两匹配。对于三元组可以放到三元空间中。若边长为偶数，则对于空间中每一个点，都可以找到对应的匹配，也就是后手必胜。若边长是奇数，则需要考虑三元组的起始状态，通过奇偶性进行判断先手必胜还是先手必败。
+ K：dp题。比赛时考虑到可以将后面的1移至前面使用，所以我们认为这个题不符合dp的最优子结构和无后效性的性质，想了一段时间dp之后就一直在尝试其他的思路，最后又绕回到dp上，但是没能定义合适的状态表示，也没有推出正确的状态转移方程。对于dp的状态转移思考还是比较混乱，需要多练习。该题的状态定义和转移方程如下：

    f[0][0]=f[0][2]=-0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        if(b[i])
        {
            // 剩余1
            f[i][0]=max(f[i-1][1],f[i-1][0]+a[i]);
            // 1没剩余
            f[i][1]=max(f[i-1][2],f[i-1][1]+a[1]);
            // 抢了前面的1
            f[i][2]=f[i-1][2]+a[i];
        }
        else 
        {
            f[i][0]=-0x3f3f3f3f;
            f[i][1]=max(f[i-1][1],f[i-1][0]+a[i]);
            f[i][2]=f[i-1][1]+a[i];
        }
    }

+ D：本场最大歪榜题，因为每次人不会选择后面肯定会选择的，反过来想就是最后一个人没得选择，只能选自己最喜欢吃的，因此倒过来贪心就行；比赛时候看了一眼没细想，补题时候发现应该挺简单的
## 杭电多校第一场 2/4/12
> AC：1005，1009
> 补题：1002，1012
### 总结
首先签到题wa了两发，主要是有点慌张，情况没有讨论完全；之后王开了1005，瞬间想到思路，然后就是漫长的T，最后陈跳出原有思路才在最后冲的几发里面a了一发。期间，负责图论的石抽空把1002开了，然后就是漫长的wa，其实题目就是简单的找最小点覆盖，一眼树形dp板子题，不知道为啥过不了，最后用标程对拍，发现最大的两个样例出错，进而发现dp转移计算部分写的有点问题，爆int就wa。

这场比赛其实主要就是卡在了1005，最开始的思路就有问题，在复杂度分析上面出了差错，导致一直wa，中期才看出来给的数据会卡T，后期换思路才过，这就说明了在一开始，还是要冷静，即使是简单题，也应该细致讨论每一种情况，仔细分析每一个循环的复杂度，这样能避免今天这种签到wa2发、简单题T飞的情况；而另一道wa题1002，主要是负责开题的石没有考虑大数的边界情况，其实已经开了long long，但是在这道题中，还应该更仔细的手动模拟，以防wa点；另外，在图论部分，只有石能开，其他两人不太能进行参与，之后陈和王也要分出一部分精力学习简单的图论知识，比如树上dp、变种的图搜索以及树形的数据结构。
### 题解
+ 1009：水题，直接粘个代码

    scanf("%d%d%d", &n, &m, &d);
    int num = m / n + (m % n > 0);
    if(num >= d) printf("Yes\n");
    else printf("No\n");

+ 1005：先利用map映射会出现的字符串种类，然后并查集将可以互相转化的字符串标记连通，最后根据题目的询问回答即可，O(1)复杂度。比赛的时候刚开始没特别在意复杂度，直接用的find函数，T了，然后修改，根据长度进行kmp匹配，还是T。最后用map进行映射后使用并查集，TLE+MLE俱现。最后经过不断优化才通过。不是很理解。
+ 1002：比赛时候wa了好多发，不知道哪里错了，最后拿官方数据对拍，一共1000组错了2组...感觉是被卡了；题目是一眼dp求最大点覆盖，标程是个无向图直接dp，我是先bfs一遍转化为有根树，然后dfs跑的树形dp，其实跟答案也大同小异，真不知道wa点在哪...
+ 1012：先计算出一个根节点的SG，先计算出为根时，各个子树的SG和1自己的SG,然后通过换根的方法得到所有节点的SG函数。之前也有出现过这种结论性的问题。比赛的时候确实没有想到可以这么推，上了图的博弈论第一次见到，之后会进行针对性的训练。

## 杭电多校第二场 4/5/12
> AC：1001，1002，1004，1009
> 补题：1007
## 总结
这次打得算是不错，罚时比较少而且基本把会的都a了；开场先是T了一发签到，然后石把1002读错了，wa了一发；然后石接着想1002，陈和王去开了1004，半个小时给他a了；这边1002总体也有了思路，最后王提供了关键点，石直接开码，一发就a了；之后王开了1001，石和陈开1007，感觉思路完全没问题，就是有一个点需要优化，但是到最后都没优化出来；不过王猜了结论a了1001，也是意料之外的惊喜。

补题时候发现1002可以用bitset优化，这种优化之前在很多题中都有，不过之前都没总结，因此有很多小技巧，小数据结构需要随手记下来，不定时看一看，并尽量在日常训练做题中应用，这样也能顺带提高自己解题的套路思维，也能在关键时候多a几道题；另外，一些博弈论可能没有想想的那么复杂，其中只要找出关键量进行先手后手讨论，猜结论验证就行；这几场中基本都有博弈论和dp，而且作为中等题出现，还是要好好总结，好好练习的。
## 题解
+ 1001：博弈论题。九次方数据量显然不能通过推SG来进行判断。而是找寻两方都遵循的最优策略，根据题目的询问进行O(1)的回答。最后推导出0-k先手必胜，k+1先手必败，再到3k是先手必胜，3k+1是先手必败。每次对输入取余（4k+2）后进行对应的判断即可。
+ 1002：记录下所有的连续1的区间数。特判全1和cnt=0的情况，对于区间数少于可操作数的情况，出来必然是全1.对于区间数大于可操作数的情况，从前往后以此翻转即可。
+ 1004：跟汉诺塔类似。递推公式$a_{i}$=2$a_{i-1}$+1。然后推出来通项公式，根据查询O(1)回答即可。
+ 1009：水题。找寻所有长度大于1的连续1串，得到答案。
+ 1007：给一个图，找出“永恒图”有多少个；枚举出度为6的点，然后枚举找长度为2的点，用排列组合数算，比赛时候的思路没问题，不知道找长度为2的路径如何优化，看题解发现可以用bitset优化
# 课程总结
## 陈市
### 学习情况
+ 主要巩固了一些数学知识，和一些简单的数据结构，并且在补之前没有上的一些算法的基础课程。
+ 对于根号算法和线段树，只是粗浅的在课上跟着学习了一遍，还需要继续在课下深入的学习学习，
### 题目练习
+ 带权并查集：HDU3038，经典模板题

    int find(int x){
        if(fa[x] == x) return x;
        else{
            int tmp = fa[x];
            fa[x] = find(fa[x]);
            val[x] += val[tmp];
            return fa[x];
        }
    }
    void union(int x, int y, int d){
        // x, y 之间建立权为d的父亲边
        int fx = find(x);
        int fy = find(y);
        if(fx != fy){
            fa[fx] = fy;
            val[fx] = -val[x] + val[y] + d;
        }
        // 验证 x，y 之间的权值是否为 d
        else{
            if(val[x] - val[y] != d){
                cnt++; // 不符合要求的个数
            }
        }
    }

## 石珂安
### 学习情况
初步学习分块思想，完成了一些例题，其中的代码还是比较有规律可言的，基本上做题需要记录块的编号以及每一块第一个元素的下标，难点在于拿到一道算法题可以想到用分块的思路
### 题目练习
+ 课上例题：[弹飞绵羊](https://www.cnblogs.com/marti88414/p/17579204.html)
+ 思维题：[Ntarsis' Set](https://www.cnblogs.com/marti88414/p/17581045.html)
+ 其他的没重点写，下面有做题记录截图
## 王永峰
### 学习情况
复习基础，大部分是dp方面内容，并做了大量练习，不过题目难度并不大，没有特意写题解
### 题目练习
[](https://imgse.com/i/pCq1MdA)
# 自由学习情况
## Codeforces Round 886 (Div. 4)
> 比赛比较简单，基本都是一眼题
> 简单说一下最后三个
+ [F - We Were Both Children](https://codeforces.com/contest/1850/problem/F)
本道题的数据范围10^5^，一直在考虑O(nlogn)算法，但是没啥思路，最后发现O(n^2^/k)直接过了，应该是没有卡常之类的
+ [G. The Morning Star](https://codeforces.com/contest/1850/problem/G)
考的map应用，算是个小思维题，不过也没啥难度，用4个map记维度，再开4个map打标记就行
+ [H. The Third Letter](https://codeforces.com/contest/1850/problem/H)
本场最难的题，考图论建模搜索，还没补，蹲一个题解，youtube上有个印度人讲的，实在是听不懂

## 王永峰：博弈论和dp的专项练习
[](https://imgse.com/i/pCq1QII)
博弈论总结见[博客地址](https://www.cnblogs.com/marti88414/p/17572150.html)
## 石珂安：dp专题练习 + 打了一场cf
[](https://imgse.com/i/pCq3kwj)
[](https://imgse.com/i/pCq1vFI)
[](https://imgse.com/i/pCq1xYt)
## 陈市：数论 + 数据结构
并查集总结见[博客地址](https://www.cnblogs.com/marti88414/p/17572418.html)
# 材料整理
线性同余方程

long long exgcd(long long a, long long b, long long &x, long long &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    long long  d = exgcd(b, a % b, x, y);
    long long  z = x;
    x = y;
    y = z - a / b * y;
    return d;
}

[动态规划基础](https://www.cnblogs.com/marti88414/p/17581724.html)
# 整体总结
## 学习情况
+ 本周的学习情况总体来说不让人足够满意，还需要加强训练，把训练的强度提升上来。
+ 三个人的基础都不太好，去年也没有什么训练效果，因此本周基本上是学习一些比较基础的算法，尽快把进度赶一赶
+ 最后就是感觉比较迷茫，感觉自己已经掌握算法原理，但是遇到题还是不会做，不知道一道平时的练习题如果多长时间想不出来才需要去看题解
## 学习目标
+ 将之前没听课的一些基础知识尽快学懂学透，并且找一些思维题来锻炼一下思维能力，在比赛期间发现自己的思维不够发散，这方面需要加强。
+ 每个人都补一补基础知识，尤其是dp相关的知识，然后大量做题，短期内不考虑过于进阶的算法和数据结构