[ABC268F] Best Concatenation Solution

• [ABC268F] Best Concatenation Solution
  • 更好的阅读体验戳此进入
  • 题面
  • Solution
  • Code
  • UPD

更好的阅读体验戳此进入

题面

给定 $ n $ 个由 X 和数字构成的字符串，你需要对其进行排列并拼接成新的字符串 $ T $ 以最大化其分数。定义其分数为对于字符串中每一个数字，使数字对应的数值乘上其之前 X 的数量，并求和。输出分数最大值。

Solution

首先一个显然的结论即为对于题目定义的分数，同一字符串内部的 X 对其数字的贡献，与字符串在排列中的顺序无关。

于是我们考虑其它字符串的 X 对字符串数字的贡献，我们考虑字符串 $ S_i, S_j $，令 $ cnt_i $ 表示字符串 $ i $ 中 X 的数目，令 $ sum_i $ 表示字符串 $ i $ 中所有数字数值之和。显然若 $ S_i $ 在 $ S_j $ 之前，$ j $ 对 $ i $ 无贡献，$ i $ 对 $ j $ 的贡献为 $ cnt_i \times sum_j $。反之则为 $ cnt_j \times sum_i $。

则不难想到若我们要将 $ S_i $ 放在 $ S_j $ 之前，那么一定有这样的贡献更大一些，即 $ cnt_i \times sum_j \gt cnt_j \times sum_i $。

所以我们直接考虑对字符串进行排序，比较规则则按照刚才的式子跑一下即可。

同时我们也可以从意义上感性理解，显然只有前面的 X 对后面的数字产生贡献，所以我们将 X 更多数字更少的放在前面，则 $ \dfrac{cnt_i}{sum_i} $ 可以作为一个类似估价函数的作用进行排序，转换一下即我们刚才证明的上式。

同时对于此贪心的证明，考虑若满足偏序关系 $ S_1, S_2 $ 和 $ S_2, S_3 $，那么一定也有 $ cnt_1 \times sum_3 \gt cnt_3 \times sum_1 $，所以也有偏序关系 $ S_1, S_3 $，也就是 $ S_1, S_2, S_3 $，扩展到整个序列依然满足。

存在双倍经验 LG-P1080 [NOIP2012 提高组] 国王游戏。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

template < typename T = int >
inline T read(void);

int N;
struct Node{string S; int sum, cnt;}d[210000];
ll ans(0);

int main(){
    N = read();
    for(int i = 1; i <= N; ++i){
        cin >> d[i].S;
        for(auto c : d[i].S)
            if(c == 'X')++d[i].cnt;
            else d[i].sum += c - '0';
    }sort(d + 1, d + N + 1, [](const Node &a, const Node &b)->bool{return (ll)a.sum * b.cnt < (ll)b.sum * a.cnt;});
    ll cur(0);
    for(int i = 1; i <= N; ++i)
        for(auto c : d[i].S)
            if(c == 'X')++cur;
            else ans += cur * (c - '0');
    printf("%lld\n", ans);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2023_01_18 初稿