Acwing: Game 58 of the week

AcWing： The first 58 Weekly match

4488. seek 1 - AcWing Question bank

Given a length of n Of 01 Sequence a1,a2,…,an.

Please judge , Whether it contains 1.

Input format

The first line contains an integer n.

The second line contains n It's an integer a1,a2,…,an.

Output format

If the sequence contains 1, The output YES, Otherwise output NO.

Data range

The first three test points meet 1≤n≤3.
All test points meet 1≤n≤100,0≤ai≤1.

sample input 1：

3
0 0 1

sample output 1：

YES

sample input 2：

1
0

sample output 2：

NO

Problem analysis

Traversal array , find 1 It outputs yes end , If it has not been output yes, It outputs no.

AC Code

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin>>n;
    int x;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        if(x==1)
        {
            cout<<"YES"<<endl;
            return 0;
        }
    }
    cout<<"NO"<<endl;
    return 0;
}

4489. The longest subsequence - AcWing Question bank

Given a length of n Strictly monotonically increasing sequence of integers a1,a2,…,an.

Sequence a The subsequence of can be expressed as ai1,ai2,…,aip, among 1≤i1<i2<…<ip≤n.

We hope to find one a The subsequence , Make the subsequence satisfy ： about j∈[1,p−1],aij+1≤aij×2 Hang up .

We think , The length is 1 The subsequence of always satisfies the condition .

Please calculate and output the maximum possible length of the subsequence that meets the conditions .

Input format

The first line contains an integer n.

The second line contains n It's an integer a1,a2,…,an.

Output format
An integer , Represents the maximum possible length of the subsequence that meets the condition .

Data range

front 5 Test points meet 1≤n≤10.
All test points meet 1≤n≤2×105,1≤a1<a2<…<an≤109.

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

Problem analysis

At first glance , Like finding the longest increasing subsequence nlogn practice , Just change the judgment conditions .

But it's not that complicated （ And I didn't write two points correctly ）, The first sequence we are looking for is , The current digit is twice or less than the previous digit . Then the title said that the given array is strictly increasing , that , If we are looking for this sequence , The current element of the array is greater than twice the previous element , Then we don't have to go back to the previous elements , Because arrays are incrementing , If twice the number of the previous element is smaller than the current element , Then there is no need to think about the later element that is smaller than this element . So this question is not so much a sequence , It's more like a subarray .

We directly traverse the array , If the current element is less than or equal to twice the previous element , Let's treat him as the last element of the sequence , At the same time, the sequence length ++. If this element is not satisfied , Then let's assume that this element is the beginning of the sequence , Restore the sequence length to 1. In this process, maintain the maximum value of the sequence .

AC Code

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    vector<int>v(n), f(n + 2,0);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    int res = 0,ans=0;
    for (int i = 0; i < n; i++)
    {
        if (f[ans] * 2 >= v[i])
        {
            f[ans + 1] = v[i];
            res = max(res, ++ans);
        }
        else
        {
            f[1] = v[i];
            ans = 1;
            res = max(res, ans);
        }

    }
    cout << res << endl;
    return 0;
}

4490. dyeing - AcWing Question bank

Given a n Tree of nodes , Node number is 1∼n.

1 Node number is the root node of the tree .

At the beginning , The color of all nodes is 0.

Now? , You need to re dye the tree , Where nodes i The target color of is ci.

The specific process of each dyeing operation is as follows ：

Select a node v And a color x.
Will be in the form of nodes v All nodes in the subtree of the root node （ Including nodes v） All dyed in color x.
Please calculate , In order to make each node be dyed into the target color , At least how many dyeing operations are needed .

Input format

The first line contains integers n.

The second line contains n−1 It's an integer p2,p3,…,pn, among pi Representation node i The parent node number of .

The third line contains n It's an integer c1,c2,…,cn, among ci Representation node i Target color of .

Ensure that the input given graph is a tree .

Output format

An integer , Indicates the minimum number of dyeing operations required .

Data range

The first three test points meet 2≤n≤10.
All test points meet 2≤n≤10^ 4,1≤pi<i,1≤ci≤n.

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

Problem analysis

First of all, let's think about the dyeing , Because we dye a root node and its subtree in the same color at one time . Then if the color of the subtree is different from the root node , Then it must have dyed the root node first , Then dye the subtree . So our coloring step is to start from the root node , Gradually dyed .

Then we can dfs To deal with it , If the current color of this node is different from the target color , We will dye the whole subtree into its target color , Dyeing times ++, Then traverse all its children , And the target color of this node is the new color of their children . Then when the child's target color is different from this color , Just keep dyeing .

Finally, output the dyeing times .

AC Code

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;
unordered_map<int, int>color;
unordered_map<int, vector<int>>mymap;

int cnt = 0;
//x Is the value of the current node ,y Is the color of the parent node of this node 
void dfs(int x,int y)
{
    if (y != color[x])cnt++;
    for (auto i : mymap[x])
    {
        dfs(i, color[x]);
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, x;
    cin >> n;
    for (int i = 2; i <= n; i++)
    {
        cin >> x;
        mymap[x].push_back(i);
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> x;
        color[i] = x;
    }
    dfs(1,0);
    cout << cnt << endl;
    return 0;
}