AcWing周赛58比赛总结

总结

比赛链接：
AcWing第58场周赛 - AcWing
好久没打周赛了，开始恢复性训练，用的是小号（ACC学校号），第二题没特判wa了一发，第三题一开始想复杂了，突然灵光一闪，马上ac...
最终：排名：116/1386，过题数：3/3

A.寻找1

题意

给出长度为1的01序列，判断是否有1.

思路

...

代码

...（这次47s,应该是有史以来各大比赛第一次在1min内ac）

B.最长子序列（贪心）

题意

给出长度为n的数组，找出最大子序列长度满足：a_{j+1} \leq a_j\times 2
题目保证递增

思路

因为题目保证递增，所以直接扫一遍，它肯定满足:[1111111,1111,111111111,1111111,...]，这里有点抽象，意思就是有一段满足，然后断开，然后下一段又连起来，只需要扫一遍取max就好。

我没有注意特判（初始化）wa了一发

代码

inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    ans = 1;//一开始为0wa了一发，
    for (int i=1;i<=n;i++)
    {
        if (i==1) {tmp = 1;pre = a[i];continue;}//在这里加上ans = 1也可以
        if (pre*2>=a[i]) tmp++,pre = a[i];
        else tmp = 1,pre = a[i];
        ans = Max(ans,tmp);
    }
    cout<<ans;
}

C.染色（树形DP）

题意

给你一个树，并且告诉你每个点最后需要染成的颜色。染色的规矩是：对当前结点染色的话，包括它的子树都被染成该颜色。问你最少需要多少次能够达成

思路

一开始想错了，用vector存子结点颜色，还搞了set什么的，突然灵光一闪...
可以看出，如果子结点与父亲节点不一样，那么就需要+1染色，哪怕就只有你这个结点不一样，因为要严格按照最后的染色要求。
那么我每次存父亲节点，只需要判断不一样的时候就+1，最后递归完毕只后维护起来即可。

代码

inline void dfs(int x,int pre)
{
    if (col[x]!=col[pre]) val[x]++;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y = edge[i].to;
        dfs(y,x);
        val[x]+=val[y];
    }
}
inline void Case_Test()
{
    cin>>n;
    for (int i=2;i<=n;i++)
    {
        cin>>x;
        add(x,i);
    }
    for (int i=1;i<=n;i++)
        cin>>col[i];
    dfs(1,0);//一开始pre写0，这样第一次也必定染色
    cout<<val[1];
}