CF2023B

Info

给定一个正整数 $k$ 和数列长度为 $n$，$n$ 为奇数的数列 $a=[1,2,…,n]$，将其划分为 $m$ 个长度都为奇数的子序列，记划分后的第 $i$ 个子序列 $b_i$ 。定义对于数列 $arr$，$\text{median}(arr)$ 表示其中位数。令 $c_i=\text{median}(b_i),i\in[1,n]$，求一种划分方式使得 $\text{median}(c)=k$ 。

Solution

显然划分方式不唯一。若我们把每一个给出的序列都划分为三个长度为奇数的子序列 $b_1, b_2, b_3$。由于对于任意 $x_1\in b_1,x_2\in b_2,x_3\in b_3$，有 $x_1 < x_2 < x_3$ 恒成立，故 $\text{median}(b_1) < \text{median}(b_2) < \text{median}(b_3)$ 恒成立。只要令 $\text{median}(b_2)=k$，则 $\text{median}([\text{median}(b_1),\text{median}(b_2),\text{median}(b_3)])=k$ 成立，得到一种划分方案。

记 $b_i$ 的首项在 $a$ 中的位置为 $p_i$，则枚举 $p_2$, $p_3$ 。若存在一种划分满足题目条件，则输出此划分，否则输出 $-1$。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void solve() {
    int n, k;
    cin >> n >> k；
    ​if (n == 1) {
        cout << 1 << '\n' << 1 << '\n';
	    return;
    }
    int l = k, r = k + 1;
    bool ok = false;
    while (l >= 1 and r <= n) {
        if ((r - l) % 2 and (l - 1) % 2 and (n - r + 1) % 2) {
            ok = true;
            break;
        }
        l -= 1;
        r += 1;
    }
    if (ok) {
        cout << 3 << '\n' << 1 << ' ' << l << ' ' << r;
    } else {
        cout << -1;
    }
    cout << '\n';
}

CF2030B

Info

给定一个正整数 $n$，求一个由 $0$ 和 $1$ 组成的字符串 $s$，使得全由 $0$ 组成的子序列与存在 $1$ 的子序列的数目之差最小。

Solution

只要 $s$ 中存在 $1$，那么存在 $1$ 的子序列的个数至少为 $2^{n-1}$，为了使得全由零组成的子序列的个数与存在 $1$ 的子序列的个数接近，显然令 $0$ 的个数为 $n-1$，即存在 $2^{n-1}-1$ 个全 子序列，有我们期望的值最小。

Code

1
2
3
4
5
6
7
8

void solve() {
	int n;
	cin >> n;
	cout << 1;
	for (int i = 1; i < n; i ++)
		cout << 0;
	cout << '\n';
}

CF2027B

Info

定义斯大林排序为函数 $s(a)=[a_i|a_i\le a_1]$, $a$ 为任意数组。对于一个数组 $a$，若对数组 $a$ 的任意子数组（数组元素连续）进行任意次斯大林排序，最终操作后的数组 $a’$ 单调递减，那么认为这个数组是脆弱的。

给定一个具有 $n$ 个元素的数组 $a$，移除 $m$ 个元素使 $a$ 变成一个脆弱的数组。求 $m$ 的最小值。

Solution

我们首先考察对于一个数组 $a$ 如何变化为 $a’$。若 $a_1=\max(a)$，那么显然只需要对 $a$ 中的每一个逆序对加上一个顺序对的结构（即 $a_{i-1}>a_i,a_i<a_{i+1}$，这样就消除了一个顺序对，让 $a$ 的递减程度变高）进行斯大林排序，直到数组递减即可。

那么考虑对于数组 $a$ 中的任意一个元素 $a_i$，删去 $m_i$ 个元素使得 $a_i=a_1=\max(a)$，就能使得 $a$ 变成一个脆弱的数组。

只需要求出每一个 $m_i$，并统计其最小值即可。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i ++)
        cin >> a[i];
    int ans = n;
    for (int i = 0; i < n; i ++) {
        int stl = i;
        for (int j = i + 1; j < n; j ++) {
            if (a[j] > a[i])
                stl ++;
        }
        ans = min(ans, stl);
    }
    cout << ans << '\n';
}