【Acwing】第58场周赛 题解

---

AcWing 4488. 寻找1  

AC代码

#include <iostream>
using namespace std;

int main()
{
    int n; cin >> n;
    bool f = false;
    while(n -- )
    {
        int num; cin >> num;
        if(num == 1) f = true;
    }
    if(f) puts("YES");
    else puts("NO");
    return 0;
}

---

AcWing 4489. 最长子序列 

输入样例1：

10
1 2 5 6 7 10 21 23 24 49

输出样例1：

4

输入样例2：

5
2 10 50 110 250

输出样例2：

1

输入样例3：

6
4 7 12 100 150 199

输出样例3：

3

---

要充分利用好题目中的 严格单调递增 这一条件

对于  ，其下一个满足的数应该要满足这两个条件 

1. 
2. 

由单调性可知， 的范围完全覆盖了  ，所以选择后面的数可以使选择的范围更大 

综上，当后面的数满足小于等于前面数的两倍时，必选这个数（贪心）

---

AC代码 

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 200010;

int a[N];

int main()
{
    int res = 0;
    int n; cin >> n;
    for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    
    for(int i = 0; i < n; i ++ )
    {
        int j = i + 1;
        while(a[j] <= 2 * a[j - 1] && j < n) j ++ ; j -- ;
        res = max(res, j - i + 1);
        i = j;
    }
    
    cout << res << endl;
    
    return 0;
}

---

AcWing 4490. 染色 

输入样例1：

6
1 2 2 1 5
2 1 1 1 1 1

输出样例1：

3

输入样例2：

7
1 1 2 3 1 4
3 3 1 1 1 2 3

输出样例2：

5

---

由于染色操作具有覆盖性，而且对于一棵（子）树的根节点只有在根节点这一点能够对其进行染色

如果从子节点进行染色的话，最后到达根节点时的染色将会覆盖之前的操作，不满足 最少操作 这一性质

所以我们需要从根节点开始进行染色，然后不断递归处理每个子节点直到叶节点（贪心思路）

1. 如果子节点和父节点的颜色相同，则不需要重复染色
2. 如果子节点和父节点的颜色不同，则需要多一次染色操作 ， ret ++ 

---

AC代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1000010;

int n;
int e[N], ne[N], h[N], idx;
int w[N];
int ret;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    if(u == 1) ret ++ ;
    
    // 叶节点
    if(h[u] == -1) return;
    
    for(int i = h[u]; ~i; i = ne[i])
    {
        // 是根节点
        int j = e[i];
        if(h[j] == -1)
        {
            if(w[j] != w[u]) ret ++ ;
        }
        else
        {
            // 不是根节点
            if(w[j] != w[u]) ret ++ ;
            dfs(j);
        }
    }
    return ;
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 2; i <= n; i ++ ) 
    {
        int p; cin >> p;
        add(p, i);
    }
    
    for(int i = 1; i <= n; i ++ )
    {
        cin >> w[i];
    }
    
    dfs(1);
    
    cout << ret << endl;
    
    return 0;
}