Acwing week 58

The longest subsequence

The longest subsequence

This is a greedy question , Greedy heel dp It's very similar , That is, we can also divide all subsets into several categories , If proved , The answer must be in a certain category , This is greed , If you find that the answer is not in a certain category , If each category requires , Namely dp

This topic is not difficult to understand , The fun part is , Its proof , How to prove that the answer must be continuous

hypothesis $a_i$ and $a_k$ In the subsequence of answers , however $a_j$ be not in , Prove whether it is true


That's how it turns out , The result is $a_j$ eligible , You can put it in the answer , Then contradict the assumption , So the answer must be a large continuous segment , Then double pointer scan once

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

const int N = 200010;
int n;
int w[N];

signed main()
{
    
	cin >> n;
	for(int i=1; i<=n; i++) cin >> w[i];

	int res = 0;
	for(int i=1; i<=n; i++)
	{
    
		int j = i + 1;
		while(j <= n && w[j] <= w[j - 1] * 2) j++;// Here is the enumeration to the j individual , The first j If not, quit , So let's go straight to i - j
		res = max(res, j - i);
		i = j - 1;
	}

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

dyeing

dyeing
It means , Dye a tree with the specified color , How many steps does it take to ask , When dyeing , One point , Including its subtree will be dyed , therefore , Whenever a root node is dyed , All operations before its subtree are invalid , So it must be from top to bottom , Dye the root node first , Then check whether the color of the child node is consistent with that of the root node , If not, dye , If you agree, look at the child nodes

So there are two ways , The first is to build drawings , Then record the color of the parent node every time , If it is different from the child node, dye it , In this way
The second is not to build a map , Directly see how many points are different from the color of child nodes , So you have to dye once , Finally, add an operation of the root node , That's the answer.

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 10010;

int n;
int p[N], c[N];

signed main()
{
    
	fast;
	cin >> n;
	for(int i=2; i<=n; i++) cin >> p[i];
	for(int i=1; i<=n; i++) cin >> c[i];
	int res = 0;
	
	for(int i=1; i<=n; i++)
		if(c[i] != c[p[i]]) res ++;

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

D - Trophy

D - Trophy

Write a handy abc, It's all about water , The reason for writing is because , There are some small points , I didn't notice before , such as ,long long The maximum range of is 9e18 many

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <cstring>
#include <cmath>
#include <stack>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define sc(a) scanf("%lld",&a)
#define pf(a) printf("%d",a) 
#define endl "\n"
#define int long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define LL long long 
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define x first
#define y second
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
int a[N], b[N];
int suma[N], sumb[N];
int res[N];
signed main()
{
    
	fast;
	int n, x;
	cin >> n >> x;
	int ans = 8e18;
	for(int i=1; i<=n; i++)
	{
    
		cin >> a[i] >> b[i];
		suma[i] = suma[i-1] + a[i];
		sumb[i] = sumb[i-1] + b[i];
		res[i] = suma[i] + sumb[i] + b[i] * (x - i);
	}
	for(int i=1; i<=n; i++)
	{
    
		if(i > x) break;// Note that if x Than i Big to break, Because I can't go so far 
		ans = min(ans, res[i]);
	}
	cout << ans << endl;
	return 0;
}