Acwing game 58 (AK)

2022-07-19 06:05:00 【lovesickman】

4489. The longest subsequence

The question ： Given a length of $n$ Of Strictly monotonically increasing Integer sequence of $a_1,a_2,…,a_n$ .

Sequence $a$ The subsequence of can be expressed as $a_{i1},a{i2},…,a{ip}$ , among $1≤i_1<i_2<…<i_p≤n$ .

We hope to find one $a$ The subsequence , Make the subsequence satisfy ： about $ j \in[1,p−1] $,$ a_{i_{j+1}}≤a_{i_{j×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 $a_1,a_2,…,a_n$ .

Output format

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

intuition ： Two points answer , But it is found that the sequence is strictly monotonically increasing , There is no repeating element , So you can consider greed . Just be greedy with the idea similar to double pointer ,（ The details are not well written , For a while ）

/* A: 10min B: 20min C: 30min D: 40min */ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#define pb push_back 
#define all(x) (x).begin(),(x).end()
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){
    for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){
    j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){
    for(auto c:v)os<<c<<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>&v){
    for(auto c:v)os<<c.first<<" "<<c.second<<endl;return os;}
template<typename T>inline void rd(T &a) {
    
    char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {
    if (c == '-')f = -1; c = getchar();}
    while (isdigit(c)) {
    x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}

typedef pair<long long ,long long >PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=2e5+10,M=1e9+7;

ll n,a[N];
ll ans=1;
void solve(){
    
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;){
    
		int j = i+1;
		int p = i , q = j;
		bool flag=0;
		while(q<=n && a[q]<=a[p]*2){
    
			p++,q++;
			flag=1;
		}
		if(flag){
    
		  // cout<<i<<" "<<q<<endl;
		    ans = max(ans,(1ll)*(q-i));
		}
			
		i = q;
	}
	cout<<ans;
}

int main(){
    
    solve();
	return 0;
}

4490. dyeing

Given a $n$ Tree of nodes , Node number is $1 \sim 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 $c_i$ .

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 $p_2,p_3,…,p_n$ , among $p_i$ Representation node $i$ The parent node number of .

The third line contains $n$ It's an integer $c_1,c_2,…,c_n$ , among $c_i$ 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 .

All test points meet $2≤n≤10^4$ , $1≤p_i<i$ , $1≤c_i≤n$ .

intuition ：dfs Traverse , Not a tree dp.

It is found that if the color of a child node is different from that of its parent node , It must be dyed once .

Dye down from the parent node . First, dye the currently traversed node , If the node is dyed to the desired color, it is the same as the parent node . Then you don't need another operation , If different surfaces need to be dyed down from this node .

therefore dfs You need to pass in the color that each parent node needs to be dyed , You also need the color that each node wants to become , Initial color .

At the beginning, the first step was not dyeing , It led to a period of adjustment , Lack of proficiency .

/* A: 10min B: 20min C: 30min D: 40min */ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#define pb push_back 
#define all(x) (x).begin(),(x).end()
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){
    for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){
    j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){
    for(auto c:v)os<<c<<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>&v){
    for(auto c:v)os<<c.first<<" "<<c.second<<endl;return os;}
template<typename T>inline void rd(T &a) {
    
    char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {
    if (c == '-')f = -1; c = getchar();}
    while (isdigit(c)) {
    x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}

typedef pair<long long ,long long >PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=1e5+10,M=1e9+7;

int h[N],e[N],ne[N],idx;
int n,fa[N];
int pre[N],col[N],ans;
void add(int a,int b){
    
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

void dfs(int u,int Fa,int Col){
     //  take u The node and its subtree are dyed col[u] 
	bool flag=1; 
	pre[u] = Col;
	if(pre[u] != col[u]){
     //  The color of the current node is different from the color that needs to be changed  
		pre[u] = col[u];
		ans++;
		if(col[u] == Col){
     //  If the color you need to change is the same as that of your ancestors  
			; 
		}
		else{
      
			flag=0;
		}
	}
    for(int i=h[u];~i;i=ne[i]){
    
        int j=e[i];
        if(j==Fa)continue;
        if(flag){
    
        	dfs(j,u,Col);
		}
		else
        	dfs(j,u,pre[u]);
    }
}

void solve(){
    
    cin>>n;
    memset(h,-1,sizeof h);
    fa[1]=1;
    for(int i=2;i<=n;i++){
    
        cin>>fa[i];
        add(i,fa[i]);
        add(fa[i],i);
    }
    for(int i=1;i<=n;i++)cin>>col[i];
    dfs(1,-1,col[1]);
    cout<<ans+1;
}

int main(){
    
    solve();
	return 0;
}