Codeforces Round ＃722 (Div. 2)

2021.5.24

B

The question ： Give a length of n Sequence , Calculate the longest of the sequence “ strange ” What is the length of the subsequence ？ The definition of strange sequence is that the difference of any logarithm in the sequence is greater than or equal to the maximum value of the sequence .

Answer key ： Calculate the number of negative numbers in the sequence ans0,0 The number of ans1, The number of positive numbers ans2, When ans1>=2, So the answer is ans0+ans1, Otherwise, you can judge whether to take a positive number , It is easy to know that a positive number can be taken at most 1 individual , If the minimum value of a positive number is greater than the sum of a negative number and 0 The maximum value of the difference between , Then we can take the smallest positive number , Otherwise, you cannot take a positive number , We still need to judge ans0=0|ans1=0|ans2=0 The answer can be drawn from the situation of .

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#define INF 1e9
#define ll long long
using namespace std;
const int N=100005;
ll a[N];
int main()
{
    ios_base::sync_with_stdio(false);
    ll t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=0;i<n;i++)
            cin>>a[i];
        sort(a,a+n);
        vector<ll>vc;
        ll min1=1e12,min2=1e12,min3=1e12,ans0=0,ans1=0,ans2=0;
        for(int i=0;i<n;i++)
        {
            if(a[i]<0){
                ans0++;
                //min1=min(0-a[i],min1);
                vc.push_back(a[i]);
            }
            else if(a[i]==0)
                ans1++;

            else{
                min2=min(min2,a[i]);
                ans2++;
            }
        }
        if(ans1)
            vc.push_back(0);
        int len=vc.size();
        if(len>=2)
        {
            for(int i=1;i<len;i++)
            {
                //cout<<min3<<endl;
                min3=min(min3,vc[i]-vc[i-1]);

            }
        }
        if(ans1>=2)
            cout<<ans0+ans1<<endl;
        //else if(ans1>=2&&ans2)
            //cout<<ans1+1<<endl;
        else
        {
            if(ans1&&ans2)
            {
                if(!ans0)
                    cout<<2<<endl;
                else
                {
                    //cout<<min3<<' '<<min2<<endl;
                    if(min3>=min2)
                        cout<<ans0+2<<endl;
                    else
                        cout<<ans0+1<<endl;
                }
            }
            else if(ans1)
            {
                cout<<ans0+ans1<<endl;
            }
            else if(ans2)
            {
                if(!ans0)
                    cout<<1<<endl;
                else
                {
                    if(min3>=min2)
                        cout<<ans0+1<<endl;
                    else
                        cout<<ans0<<endl;
                }
            }
            else
                cout<<ans0<<endl;
        }

    }
    return 0;
}

C

The question ： Each vertex i It has a value range [li,ri], share n-1 side , All the points connect to form a tree , Calculate the sum of the maximum difference between all points after taking values .

Answer key ： For each vertex av∈[lv,rv], set up p As with the v Adjacent vertices u The number of , bring au> av,q As with the v Adjacent vertices u The number of , bring au <av

p>q av=lv But it turns out

p<q av=rv But it turns out

p=q av=lv|rv But it turns out

Available tree dp, Calculate the value of each connection point from the first point , All the way down to the leaf node

av=lv,dp[v][0] Represents the sum of the maximum difference at the connection point

av=rv,dp[v][1] Represents the sum of the maximum difference at the connection point

u As with the v Connected points

dp[v][0]+=max(dp[u][0]+abs(l[v]-l[u]),dp[u][1]+abs(l[v]-r[u]))

dp[v][1]+=max(dp[u][0]+abs(r[v]-l[u]),dp[u][1]+abs(r[v]-r[u]))

Because it's from the vertex 1 Start recursing back , So the obvious answer is max(dp[1][0],dp[1][1]).

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
#define INF 1e9
#define ll long long
using namespace std;
const int N=100005;
int l[N],r[N];
ll dp[N][2];
vector<int>G[N];
void dfs(int v,int p)
{
    dp[v][0]=dp[v][1]=0;
    for(int i=0;i<G[v].size();i++)
    {
        int u=G[v][i];
        if(u==p)
            continue;
        dfs(u,v);
        dp[v][0]+=max(dp[u][0]+abs(l[v]-l[u]),dp[u][1]+abs(l[v]-r[u]));
        dp[v][1]+=max(dp[u][0]+abs(r[v]-l[u]),dp[u][1]+abs(r[v]-r[u]));
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    int t,n,u,v;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>l[i]>>r[i];
            G[i].clear();
        }
        for(int i=1;i<n;i++)
        {
            cin>>u>>v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs(1,0);
        cout<<max(dp[1][0],dp[1][1])<<endl;
    }
    return 0;
}

D

The question ： stay [0,2n] Any two pairs of points are required on the number axis of A,B, bring length(A)=length(B) perhaps A Included in B

Answer key ： linear dp,

Including the situation ： When point pair [1,2*i] Even on , middle [2,2*i-1] You can choose according to the rules , That is to say dp[i-1], When point pair [1,2*i-1],[2,2*i] Even on , middle [3,2*i-2] You can choose at will , That is to say dp[i-2], And so on

Isometric condition ： Can be 2*n Equal length is equal , Then you just need to n The number of positive divisors of can determine the classification category

linear equation dp[i]=(dp[1]+...+dp[i-1])+v[i](i The number of positive divisors of )

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
#define INF 1e9
#define mod 998244353
#define ll long long
using namespace std;
const int N=1000005;
int n,dp[N],s;
int main()
{
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j+=i)
            dp[j]++;
    s=0;
    for(int i=1;i<=n;i++)
    {
        dp[i]=(dp[i]+s)%mod;
        s=(s+dp[i])%mod;
    }
    cout<<dp[n]<<endl;
    return 0;
}