Codeforces Round #722 (Div. 2)

A. Eshag Loves Big Arrays

题意:
给定一个长度为 n 的序列,可以选择一段区间将其中严格大于区间平均数的数删掉,可以执行任意多次,问最多可以删除多少次。

Soulution:
删到最后一定只剩下数组中的最小值,因为最小值是永远小于等于区间平均值, 所以统计最小值的个数 cnt, 答案就是 n - cnt

Code:

int t, n;
map<int, int> mp;

int main(){
    __;
    cin >> t;
    while(t --){
        cin >> n;
        int x;
        mp.clear();
        for(int i = 1; i <= n; i ++)    cin >> x, mp[x] ++;
        if(mp.size() == 1)  puts("0");
        else{
            int f = 0;
            int ans = 0;
            for(auto i : mp){
                if(f){
                    ans += i.se;
                }
                f = 1;
            }
            printf("%d\n", ans);
        }

    }
    return 0;
}

B. Sifid and Strange Subsequences

题意:
给定一个长度为 n 的序列,要求选择出其最长的序列满足 \left| a_i-a_j \right|\geqslant MAX , MAX 为子序列最大值。

Soulution:
负数和零肯定是必须选的,因为它们之间任意的差的绝对值必然大于它们两个数。
两个正数之间的差的绝对值必然小于它们两个数,所以我们最后判断一下第一个正数即可。

Code:

int t, n;
ll a[N];

int main(){
    __;
    cin >> t;
    while(t --){
        cin >> n;
        for(int i = 1; i <= n; i ++)    cin >> a[i];
        if(n == 1){
            puts("1");
            continue;
        }
        sort(a + 1, a + n + 1);
        int p = 0;
        ll ans = 0, res = 3e9;
        for(int i = 1; i <= n; i ++){
            if(a[i] <= 0){
                p = i;
                ans ++;
                if(i >= 2) {
                    res = min(res, abs(a[i] - a[i - 1]));
                }
            }
        }
        if(p == 0)  ans = 1;
        else{
            p ++;
            if(p <= n){
                if(res >= a[p]){
                    ans ++;
                }
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

C. Parsa's Humongous Tree

题意:
给定一棵树,树上每个节点 i 都包含一个值域 [l_i, r_i] 要求每个节点在其值域中选择一个数 a_i ,使得所有的边 (u,v)\sum_{i=1}^n{\left| a_u-a_v \right|} 最大。

Soulution:
显然,选择边界时最大的,我们就可有两个点转移到三个点,再转移到更多点,树形DP。

Code:

int n, t;
int l[N], r[N];
ll f[N][2];
vector<int> G[N];

void dfs(int u, int fa){
    for(int i = 0; i < G[u].size(); i ++){
        int v = G[u][i];
        if(v == fa) continue;
        dfs(v, u);
        f[u][0] += max(f[v][0] + abs(l[u] - l[v]), f[v][1] + abs(l[u] - r[v]));
        f[u][1] += max(f[v][0] + abs(r[u] - l[v]), f[v][1] + abs(r[u] - r[v]));
    }
}

int main(){
    __;
    cin >> t;
    while(t --){
       cin >> n;
       for(int i = 1; i <= n; i ++){
           G[i].clear();
           f[i][0] = 0;
           f[i][1] = 0;
       }
       for(int i = 1; i <= n; i ++){
           cin >> l[i] >> r[i];
       }
       for(int i = 1; i < n; i ++){
           int u, v;
           cin >> u >> v;
           G[u].pb(v);
           G[v].pb(u);
       }
       dfs(1, 0);
       printf("%lld\n", max(f[1][0], f[1][1]));
    }
    return 0;
}

D. Kavi on Pairing Duty

题意:
对于 2n 个点,可以选择不重复的 n 对点连接,要求任意两个点对 A,B 满足 len(A)=len(B) 或者 A \subset B,求出点对的选择的方案。n

Soulution:
f[i]n=i 的可行解数量
显然 f[1]=1
考虑 i > 1 的情况
我们依据题目条件分两类考虑:n

1.包含情况:
对于区间 [1,2i],当我们将两边点按等长都选择上之 n 后,我们中间的点就可以随便选取。
例如
选择一个点对 (1,2n),则中间的区间 [2,2n−1] 可以随便选取即 f[n−1]

选择两个点对 (1, 2n−1)、(2, 2n),则中间的区间 [3,2n−2] 可以随便选取即 f[n-2]

依次类推,可推得共有 \sum_{i=1}^{n-1}{f_i}种方案

2.相等情况: 只有在线段长度为 n 的因子时才存在方案

递推公式:

f_i=\sum_{j=1}^{n-1}{f_j+}\pi \left( i \right), 其中\pi \left( i \right)表示i的因子个数

Code:

int n;
ll f[N], D[N];

int main(){
    __;
    for(int i = 1; i < N; i ++){
        for(int j = i; j < N; j += i){
            D[j] ++;
        }
    }
    f[1] = 1, f[2] = 3;
    ll res = f[1] + f[2];
    cin >> n;
    for(int i = 3; i <= n; i ++){
        f[i] = (res + D[i]) % mod;
        res = (res + f[i]) % mod;
    }
    printf("%lld\n", f[n]);
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注