[ABC268F] Best Concatenation 题解

· · 题解

首先，我们定义一个函数 f(S) 表示字符串 S 的得分。

其次，本题的得分计算有一个性质：

对于字符串 S_i,S_j，用 + 表示字符串的连接操作，那么对于每两个相邻的字符串 S_i 和 S_j，如果 f(S_i+S_j)<f(S_j+S_i)，那么将 S_i 排在 S_j 前一定是优的。

::::info[证明] 定义 S_i\prec S_j 当且仅当 f(S_i+S_j)<f(S_j+S_i)，则需要证明 \prec 是一个全序。

记 X_i 为 S_i 中出现的 X 的数量，Y_i 为 S_i 中出现的数字的和。

根据定义容易得到 f(S_i+S_j)=f(S_i)+f(S_j)+X_iY_j，于是对于两个串 S_i\prec S_j\Rightarrow\frac{Y_i}{X_i}>\frac{Y_j}{X_j}（对于 X_i=0 的情况讨论发现仍然满足下面的条件），进而得到若对于 1\le i,j,k\le n，S_i\prec S_j\land S_j\prec S_k，那么 S_i\prec S_k。即 \prec 是一个全序。 ::::

进一步地，根据上面的证明，发现对于 S_i 和 S_j，直接比较 X_iY_j 和 X_jY_i 的大小就行了。可以利用 std::sort，按这个方法排个序再连接起来计算答案就行。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n; cin>>n;
  vector<string> s(n);
  for(auto &i:s)cin>>i;
  vector<int> x(n),y(n),p(n);
  for(int i=0;i<n;i++)
    for(char j:s[i])j=='X'?x[i]++:y[i]+=j-48;
  iota(p.begin(),p.end(),0);
  sort(p.begin(),p.end(),[&](int a,int b){
    return x[a]*y[b]>y[a]*x[b];
  }); // 按照上面所述的方法排序
  string g;
  for(int i:p)g+=s[i]; // 连接
  int cx=0,c=0;
  for(char i:g)i=='X'?cx++:c+=cx*(i-48); // 模拟题意计算答案
  cout<<c<<endl;
  return 0;
}