25寒省赛排位

发表于 更新于 分类于 ， 阅读次数： 作者 Pomelorin

Problem C

给长度为奇数 \(n\) 的数组 \(a\)。最多执行 \(k\) 次操作，每次任意选定一个元素，其值加一。最大化中位数。

\(1≤n≤2\times 10^5\)，\(n\) 为奇数，\(1≤k≤10^9,1≤a_i≤10^9\)。

点击查看题解

思维题 对不如中位数大的数操作是多余的。排序，一层一层地对中位数及其之后的数加一，看可以加几层。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll,ll>
const ll N = 200000 + 50, inf = 1145141919810;

ll n, k, a[N], ans;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> k;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
    ans = a[n / 2 + 1];
    for (ll i = n / 2 + 1; i <= n - 1; i++) {
        while (a[i] == a[i + 1] && i + 1 <= n)
            i++;
        if (i >= n)
            break;
        ll need = a[i + 1] - ans;
        ll len = i - n / 2;
        ll serv = k / len;
        if (serv >= need) {
            k -= need * len;
            ans += need;
        } else {
            k = 0;
            ans += serv;
            break;
        }
    }
    if (k == 0)
        cout << ans << endl;
    else
        cout << ans + k / (n / 2 + 1) << endl;
    return 0;
}

Problem E

问长度为 \(n\) 的交替数列的子数列有多少个为交替数列。

单个 0 或 1 为交替数列。若某交替数列 \(a\) 最后一个数为 \(x\)，则在 \(a\) 后面加入元素 \(1-x\)，也为交替数列。

\(1≤n≤10^6\)。

点击查看题解

动态规划 设 \(f(i,j)\) 表示长度为 \(i\)，最后一个元素为 \(j\) 的交替数列数量。则 \(f(1,1)=f(1,0)=1\)。

若 \(i\) 为偶数： \[ f(i,0)=f(i-1,1)+f(i-1,0)+1 \]

\[ f(i,1)=f(i-1,1) \]

奇数情况类似。答案为 \(f(n,0)+f(n,1)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll,ll>
const ll N = 1000000 + 50, inf = 1145141919810, mod = 1000000000 + 7;

ll n, f[N][2];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n;
    f[1][1] = 1;
    f[1][0] = 0;
    for (ll i = 2; i <= n; i++) {
        if (i % 2 == 0) {
            f[i][0] = (f[i - 1][1] + f[i - 1][0] + 1) % mod;
            f[i][1] = f[i - 1][1] % mod;
        } else {
            f[i][0] = f[i - 1][0] % mod;
            f[i][1] = (f[i - 1][1] + f[i - 1][0] + 1) % mod;
        }
    }
    cout << (f[n][0] + f[n][1]) % mod << endl;
    return 0;
}

Problem F

给 \(n\) 个字符串，问有多少对索引不同的字符串拼接并重排后，可以成为回文串。

\(1≤n≤100000\)，所有字符的总数将小于 \(1000000\)。

点击查看题解

状态压缩 成为回文串的条件是字符串拼接后，各种字母出现次数最多有一个奇数。利用状压和 map 计数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll,ll>
const ll N = 100000 + 50, inf = 1145141919810, mod = 1000000000 + 7;
const ll M = 100000 + 50;

ll n, a[50], b[M], ans = 0;
string s;
map<ll, ll> f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> s;
        s = ' ' + s;
        ll len = s.size() - 1;
        for (ll j = 1; j <= 26; j++)
            a[j] = 0;
        for (ll j = 1; j <= len; j++) {
            a[s[j] - 'a' + 1]++;
        }
        for (ll j = 1; j <= 26; j++) {
            if (a[j] % 2)
                b[i] += (1ll << (j - 1));
        }
    }
    for (ll i = 1; i <= n; i++) {
        if (f.count(b[i]))
            ans += f[b[i]];
        for (ll j = 1; j <= 26; j++) {
            if (f.count(b[i] + (1ll << (j - 1))) && (((b[i] >> (j - 1)) & 1) == 0))
                ans += f[b[i] + (1ll << (j - 1))];
        }
        for (ll j = 1; j <= 26; j++) {
            if (f.count(b[i] - (1ll << (j - 1))) && (((b[i] >> (j - 1)) & 1) == 1))
                ans += f[b[i] - (1ll << (j - 1))];
        }
        if (f.count(b[i]) == 0)
            f[b[i]] = 1;
        else
            f[b[i]] += 1;

    }
    cout << ans << endl;
    return 0;
}

Problem H

对于数组 \(h[1..n]\)，我们按如下方式定义其 Lipschitz 常数 \(L(h)\)：

  • 若 \(n<2\)，则 \(L(h)=0\)；

  • 若 \(n≥2\)，则 \(L(h)=\max⌈\dfrac{|h[j]−h[i]|}{j−i}⌉\)，其中最大值取自所有 \(1≤i<j≤n\)。

给定一个长度为 \(n\) 的数组 \(a\) 和 \(q\) 个形式为 \([l,r]\) 的查询。对于每个查询，考虑子数组 \(s=a[l..r]\)，需要计算 \(s\) 的所有子数组的 Lipschitz 常数之和。

点击查看题解

诈骗题 单调栈 对于开区间可导，闭区间连续的函数，要使得平均斜率大于等于区间内任意一点处的斜率，区间内斜率必然处处相等，且等于平均斜率（拉格朗日中值定理可得）。所以，\(L(h)\) 的值只会被某两个相邻的数贡献。（理解性表述）

问题被缩小范围，转化为求区间内所有子区间的最大值之和。

考虑每个数 \(a_i\) 对以 \(i\) 为开头的区间的贡献，贡献范围为 \([i,j)\)，其中 \(j\) 为第一个大于 \(a_i\) 的数的位置。此后，由 \(a_j\) 取代 \(a_i\) 的贡献。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll,ll>
const ll N = 100000 + 50, inf = 1145141919810, mod = 1000000000 + 7;
const ll M = 100000 + 50;

ll n, a[N], nxt[N], top = 0, num[N];
PII stk[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll q, ans, l, r;
    cin >> n >> q;
    for (ll i = 1; i <= n; i++)
        cin >> a[i];
    for (ll i = 1; i <= n - 1; i++) {
        a[i] = abs(a[i + 1] - a[i]);
    }
    a[n] = inf;
    for (ll i = 1; i <= n - 1; i++) {
        while (stk[top].first < a[i] && top >= 1) {
            nxt[stk[top--].second] = i;
        }
        stk[++top] = (PII){a[i], i};
    }
    for (ll i = 1; i <= q; i++) {
        cin >> l >> r;
        ans = 0, r--;
        for (ll j = l; j <= r; j++) {
            num[j] = 1;
        }
        for (ll j = l; j <= r; j++) {
            if (nxt[j] <= r && nxt[j] != 0) {
                ans += a[j] * (nxt[j] - j) * num[j];
                num[nxt[j]] += num[j];
            } else {
                ans += a[j] * (r - j + 1) * num[j];
            }
        }
        cout << ans << endl;
    }
    return 0;
}