Codeforces Round ＃722 (Div. 2)

2021.5.24

B

题意：给一个长度为n的序列，计算该序列的最长“奇怪”子序列长度为多少？其中奇怪序列的定义为序列里的任何一对数的差值大于等于序列的最大值。

题解：计算一下序列里负数个数ans0，0的个数ans1，正数的个数ans2，当ans1>=2，那么答案为ans0+ans1，否则可以判断是否拿正数，易知正数最多拿1个，如果正数的最小值大于负数和0之间差值的最大值，那么就可以取那个最小的正数，否则不能取正数，还需判断一下ans0=0|ans1=0|ans2=0的情况即可得出答案。

#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

题意：每个顶点i具有一个取值范围[li,ri]，共有n-1条边，所有点连成一棵树，计算所有点取值后之间最大差值的和。

题解：对于每个顶点av∈[lv,rv]，设p为与v相邻的顶点u的数量，使得au> av，q为与v相邻的顶点u的数量，使得au <av

p>q av=lv可得结果

p<q av=rv可得结果

p=q av=lv|rv可得结果

可用树型dp，从第一个点计算每个连接点的取值，一直往叶子结点以下

av=lv，dp[v][0]代表连接点的最大差值和

av=rv，dp[v][1]代表连接点的最大差值和

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]))

因为是从顶点1开始往后递归的，所以答案很明显是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

题意：在[0,2n]的数轴上要求任意两个点对A，B，使得length(A)=length(B)或者A包含于B

题解：线性dp，

包含情况：当点对[1,2*i]连上，中间[2,2*i-1]就可以随意按规则选取，即为dp[i-1]，当点对[1,2*i-1]，[2,2*i]连上，中间[3，2*i-2]就可以随意选取，即为dp[i-2]，以此类推

等长情况：可以将2*n进行等分即为等长，那么只需求出n的正约数个数就可确定划分种类

线性方程dp[i]=(dp[1]+...+dp[i-1])+v[i](i的正约数个数)

#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;
}