赛后总结

再见，Pupil。

• 虽然是Pupil，但是Div3-4水上去的，含金量不高，被刷下来也是理所应当。
• 没有及时根据Div2调整自己的做题节奏和思维方式是一大黑洞。而且在没有音乐平衡自己心态的时候，遇到题目卡了就会变成while(1)。
• CodeForces似乎进入了比赛淡季，需要适时地给自己加赛，原来我还是预备队啊，那就积极参与每周两次的线上训练罢。主要回血方向应放在Div2的1500及以下，然后适度冲一下2000的题目。
• D和E静一静也能想出来，但比赛的时候精神状态已经崩溃了，甚至没有往下滚动界面看那些一看就懂的注释。

A | Factorise N+M

数论题做多了是这样的。因为题目保证了输入的数是素食，直接乘个2。

namespace lovelive{
    typedef long long LL;
    LL n;
    void init(){

    }
    void main(){
        cin>>n;
        cout<<n<<endl;
    }
}

B | Jumbo Extra Cheese 2

第二题就被卡了，心理状态可想而知。

考试的时候想到了需要保证最后的组合体是一个凸多边形，这个组合体的高只能是所有边的最高值和次高值。但是考试的时候码力大减，没有处理好。

考完之后才发现，其实样例的4*5横着放还是竖着放对于样例的最终答案没有影响！心态太菜惹的祸，给自己加了一堆没用的活。

最终答案为（最长边） （所有最短边的和） 2

int main(){
    long long _t,n,a,b,ans;
    vector<pair<long long,long long>> ai;
    cin>>_t;
    while (_t--){
        cin>>n;
        ai.clear();
        for(int i=1;i<=n;i++){
            cin>>a>>b;
            if(a<b){long long c = a;a = b;b = c;}
            ai.push_back(make_pair(a,b));
        }
        sort(ai.begin(),ai.end());
        ans = ai[ai.size()-1].first + ai[ai.size()-1].second;
        for(int i=0;i<n-1;i++)ans += ai[i].second;
        cout<<ans*2<<endl;
    }
}

C | Bricks and Bags

构造很明显，利用中学的绝对值思想，最小值一组，最大值一组，然后其他的一组（从全部数字的次小值到次大值），答案就变成了：

$$|max\left({a_i}\right)-min\left({a_i}\right)| + max\left(|max\left({a_i}\right)-submax\left({a_i}\right)|,|min\left({a_i}\right)-submin\left({a_i}\right)|\right) $$

思路很简单，但是代码实现的时候乱套了，结果就变成了比赛时的自暴自弃。其实只要将数组排一下序再遍历元素就OK了。

namespace lovelive{
    typedef long long LL;
    LL n,ai[200005],ans;
    void main(){
        cin>>n;ans = 0;
        for(int i=1;i<=n;i++){
            cin>>ai[i];
        }
        sort(ai+1,ai+n+1);
        for(int i=3;i<=n;i++){
            ans = max(ans,abs(ai[i]-ai[i-1])+abs(ai[i]-ai[1]));
        }
        for(int i=n-2;i>=1;i--){
            ans = max(ans,abs(ai[i]-ai[i+1])+abs(ai[i]-ai[n]));
        }
        cout<<ans<<endl;
    }
}

D | Knowledge Cards

经典只看上面不看下面，但凡看一眼下面就算只看动态图都能猜到这道题想讲什么。

这题就像是小时候玩的滑块游戏，因为填满棋盘之前的状态是可以自己调的，所以只要填上一张牌之后，棋盘上还有一个空位，就可以通过填满之前的调度和填上之后在这一个空白格附近牌的移动，让刚被放下去的牌有机会被推到终点。所以，题目就变成了处理到每一个号码的牌时，棋盘上是否还有空位。

namespace lovelive{
    typedef long long LL;
    LL n,m,k,ai[100005],cnt;
    bool settled[100005];
    void main(){
        cin>>n>>m>>k;cnt = 0;
        memset(settled,0,sizeof(settled));
        for(int i=1;i<=k;i++){
            cin>>ai[i];
        }
        for(int i=k,j=1;i>=1;i--){
            while(!settled[i]){
                    settled[ai[j]]=true;
                    cnt++;j++;
            }
            if(cnt>n*m-3){
                cout<<"TIDAK"<<endl;
                return;
            }
            settled[i]=true;
            cnt--;
        }
        cout<<"YA"<<endl;
    }
}

但我的代码实现又寄了（，调了好几次才过。

E | Hanging Hearts

在考试的时候，考虑到当时全线崩溃的情绪，能看出来这是一棵树，并且能判断出深度在答案上取到的作用都很不容易了。

详细的思路在程序的注释里，但感觉还是有点精神混乱。

//一失足成千古恨

namespace lovelive{
    typedef long long LL;
    LL lca[20][100005],fa[100005],n,ans1,ans2;
    vector<LL> childs[100005];
    LL dp[2][100005];
    void dfs(LL cur){
        //对于当前节点，所有的子节点有两种选择：
        //1. 其子树根的值会上传，同时子树节点可由其深度影响父节点（主要是对于叶子结点的特殊处理）；
        //2. 不上传子树根值，这样就只能直接继承子树的最大子序列。

        //dp作为推导式子，代表的是其对父亲节点的影响
        //dp[1][cur] 记录该子树的答案
        //dp[0][cur] 记录深度

        LL ans = 0,dep = 0;
        for(vector<LL>::iterator i=childs[cur].begin();i!=childs[cur].end();i++){
            dfs(*i);
            ans += max(dp[0][*i],dp[1][*i]);
            dep = max(dep,dp[0][*i]);
        }
        dp[0][cur] = dep + 1;
        dp[1][cur] = ans;
    }
    void main(){
        cin>>n;
        for(int i=2;i<=n;i++){
            cin>>fa[i];
            childs[fa[i]].push_back(i);
            lca[0][i] = fa[i];
        }ans1 = ans2 = 0;
        dfs(1);
        cout<<max(dp[0][1],dp[1][1])<<endl;
    }
}