25暑排位1

发表于 分类于 ， 阅读次数： 作者 Pomelorin ， Cool-breeze

Problem A

有 \(n\) 个字符串，\(t_1,t_2,…,t_n\)，这些字符串只由字符 s 和 h 组成。 定义这些字符串的连接为 \(t_1,t_2,…,t_n\) 首尾相接。

可以对这 \(n\) 个字符串进行任意次重排，希望重排后字符串的连接之中 sh 子序列出现次数最多，并求出这个最大值。

\(1≤n≤10^5\)，总长度不超过 \(10^5\)。

点击查看题解

考虑排序后统计答案。按 h 占比排序即可，或者比较两个字符串不同顺序产生的贡献。

解法 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include  <bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>

bool cmp(pair<int,double> a,pair<int,double> b) {
    return a.second < b.second;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    string s[n];
    int ans = 0, a[n][2] = {}, sums = 0, sumh = 0; //s h
    vector<pair<int, double> > b; //index h-s
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        for (int j = 0; j < s[i].length(); j++) {
            if (s[i][j] == 's') sums++;
            else sumh++;
        }
    }
    for (int i = 0; i < n; i++) {
        int ss = 0;
        for (int j = 0; j < s[i].length(); j++) {
            if (s[i][j] == 's') ss++, a[i][0]++;
            else a[i][1]++, ans += ss;
        }
        double x;
        if (a[i][0] == 0) x = 1000000000000000;
        else x = ((double) a[i][1] / (double) a[i][0]);
        b.push_back({i, x});
    }
    sort(b.begin(), b.end(), cmp);
    int dp[n + 5];
    dp[n] = 0;
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = dp[i + 1] + a[b[i].first][1];
    }
    for (int i = 0; i < n; i++) {
        int x = b[i].first;
        ans += a[x][0] * dp[i + 1];
    }
    cout << ans;
    return 0;
}

解法 2：

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 100000 + 10;

struct str {
    string s;
    ll len;
} S[N];

ll n;
string tmp, ans = "";

bool cmp(str x, str y) {
    ll len = x.len + y.len, cnt1 = 0, cnt2 = 0, hcnt = 0, thcnt = 0;
    string t = x.s + y.s;
    for (ll i = 0; i <= len - 1; i++) {
        if (t[i] == 'h')
            hcnt++;
    }
    thcnt = hcnt;
    for (ll i = 0; i <= len - 1; i++) {
        if (t[i] == 's')
            cnt1 += thcnt;
        else
            thcnt--;
    }
    thcnt = hcnt;
    t = y.s + x.s;
    for (ll i = 0; i <= len - 1; i++) {
        if (t[i] == 's')
            cnt2 += thcnt;
        else
            thcnt--;
    }
    return cnt1 > cnt2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll hcnt = 0, cnt = 0, slen = 0, maxlen = 0;
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> tmp;
        ll len = tmp.size();
        maxlen = max(maxlen, len);
        S[i].s = tmp;
        S[i].len = len;
    }
    stable_sort(S + 1, S + 1 + n, cmp);
    for (ll i = 1; i <= n; i++)
        ans += S[i].s;
    slen = ans.size();
    for (ll i = 0; i <= slen - 1; i++) {
        if (ans[i] == 'h')
            hcnt++;
    }
    for (ll i = 0; i <= slen - 1; i++) {
        if (ans[i] == 's')
            cnt += hcnt;
        else
            hcnt--;
    }
    cout << cnt << endl;
    return 0;
}