[acwing] solution of the 58th weekly match

---

AcWing 4488. seek 1  

AC Code

#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. The longest subsequence  

sample input 1：

10
1 2 5 6 7 10 21 23 24 49

sample output 1：

4

sample input 2：

5
2 10 50 110 250

sample output 2：

1

sample input 3：

6
4 7 12 100 150 199

sample output 3：

3

---

Make full use of   Strictly monotonically increasing   This condition

about   , The next satisfied number should meet these two conditions  

1. 
2. 

We can know from monotonicity ,  The scope of completely covers   , So choosing the following number can make the selection range larger  

Sum up , When the following number is less than or equal to twice the previous number , This number is required （ greedy ）

---

AC Code  

#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. dyeing  

sample input 1：

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

sample output 1：

3

sample input 2：

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

sample output 2：

5

---

Because the dyeing operation has Coverage , And for a tree （ Son ） Root node of tree Only at the root node This can dye it

If you dye from child nodes , Finally, the coloring when reaching the root node will overwrite the previous operation , dissatisfaction At least operation This is the nature of

So we need to dye from the root node , And then on and on Recursively process each child node to the leaf node （ Greedy thought ）

1. If the child node and the parent node Same color , There is no need to repeat dyeing
2. If the child node and the parent node Different colors , You need one more dyeing operation , ret ++ 

---

AC Code

#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 ++ ;
    
    //  Leaf nodes 
    if(h[u] == -1) return;
    
    for(int i = h[u]; ~i; i = ne[i])
    {
        //  Root node 
        int j = e[i];
        if(h[j] == -1)
        {
            if(w[j] != w[u]) ret ++ ;
        }
        else
        {
            //  Not the root node 
            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;
}