Acwing game 58

4488. seek 1

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

Sign in

// Author: Changersh
// Problem:  seek 1
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4491/
// When: 2022-07-02 19:00:21
// 
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 


#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include<tr1/unordered_map>
#include <tr1/unordered_set>

using namespace std::tr1;
using namespace std;
typedef long long ll;
const int N = 5e4 + 50;
const int MOD = 1e9 + 7;



int main() {
    
	int n, a;
	bool flag = false;
	scanf("%d", &n);
	for (int i = 0; i < n; i ++) {
    
		scanf("%d", &a);
		if (a == 1) flag = 1;
	}
	if (flag) printf("YES");
	else printf("NO");
	return 0;
}

4489. The longest subsequence

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
sample input 3：
6
4 7 12 100 150 199
sample output 3：
3

greedy

The minimum length of subsequence is 1, It's convenient to start with the first number , Compare with the number after it , The conditions are met +1, Count the maximum length every time .
As long as there is dissatisfaction, return to zero , Count from the next digit
Then I put +1 The operation of is put at the end , I'm used to writing greedily

// Author: Changersh
// Problem:  The longest subsequence 
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4492/
// When: 2022-07-02 19:03:37
// 
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 


#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include<tr1/unordered_map>
#include <tr1/unordered_set>

using namespace std::tr1;
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const int MOD = 1e9 + 7;

int T;
void solve() {
    
	
}

ll n, s[N], cnt, ans;
int main() {
    
	// scanf("%d", &T);while (T--)solve();
	scanf("%lld", &n);
	for (int i = 0; i < n; i++)
		scanf("%lld", &s[i]);
	for (int i = 0; i < n - 1; i++) {
    
		if (s[i] * 2 >= s[i + 1]) {
    
			cnt++;
			ans = max(ans, cnt);
		}
		else {
    
			cnt = 0;
		}
	}
	ans++;
	printf("%lld", ans);
	return 0;
}

4490. dyeing

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≤104,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

Trees + greedy

If a node is different in color from its parent node ,namo You need to dye it again , And then , The parent node must be dyed first , Otherwise, the color of the parent node will overwrite the color of the child node .
It needs to be dyed at least once , As long as the color of the child node is different from that of the parent node , frequency +1

// Author: Changersh
// Problem:  dyeing 
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4493/
// When: 2022-07-02 19:16:35
// 
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 


#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include<tr1/unordered_map>
#include <tr1/unordered_set>

using namespace std::tr1;
using namespace std;
typedef long long ll;
const int N = 1e4 + 5;
const int MOD = 1e9 + 7;

int n, tree[N], col[N];
int main() {
    
	scanf("%d", &n);
	for (int i = 2; i <= n; i++) {
    
		scanf("%d", &tree[i]);
	}
	for (int i = 1; i <= n; i++) {
    
		scanf("%d", &col[i]);
	}
	int ans = 1;
	for (int i = 2; i <= n; i++) {
    
		if (col[i] != col[tree[i]]) {
    
			ans++;
		}
	}
	printf("%d", ans);
	return 0;
}