[ABC264G] String Fair Solution

• [ABC264G] String Fair Solution
  • 更好的阅读体验戳此进入
  • 题面
  • Solution
  • Code
  • UPD

更好的阅读体验戳此进入

题面

给定 $ n $ 条评分规则，每条存在字符串 $ T_i $ 和得分 $ P_i $。你需要构造一个任意长度但非空的字符串 $ S $，在 $ S $ 中每次出现 $ T_i $ 就会获得 $ P_i $ 得分。你需要最大化得分，输出最大值。若无限大则输出 Infinity。

Solution

一个十分精妙的图论。

关键的信息在 $ \lvert T_i \rvert \le 3 $，这样的话我们就可以考虑进行建边。我们令 $ P_{str} $ 表示字符串为 $ str $ 的时候的得分，如果没有该字符串的评分规则即为 $ 0 $。

于是考虑如对于从 $ ab $ 通过 $ c $ 可以有一条边到 $ bc $，边权即为 $ P_{abc} + P_{bc} + P_{c} $。同时注意一些细节，如从空字符串可以通过任意字符，如通过 $ a $ 连结到 $ a $，边权即为 $ P_a $，以及对于长度为 $ 1 $ 的字符串连结到长度为 $ 2 $ 的同理。

这样将图建完之后不难发现只需要 SPFA 跑一遍单源最长路，取最大的 $ dis $ 即可，如果存在正环那么显然无限大。

于是点数为 $ n = 26^2 + 26 + 1 $，边数即为 $ m = 26n $，于是 SPFA 最坏复杂度即为 $ O(nm) $，也就是 $ 26^5 $ 的级别，可以通过。

当然这里我们用 map 实现，手动实现一个 hash() 之后用 unorderer_map 即可去掉 map 的 $ \log $。

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(arr) void* Edge::operator new(size_t){static Edge* P = arr; 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);

struct Edge{
    Edge* nxt;
    int to;
    ll val;
    OPNEW;
}ed[21000];
ROPNEW(ed);
Edge* head[1100];

int N;
int cnt(0);
unordered_map < string, int > score;
map < pair < int, int >, int > mp;
unordered_map < int, pair < int, int > > rmp;
bitset < 1100 > inq;
int dep[1100];
ll dis[1100];
ll ans(LONG_LONG_MIN);

void SPFA(void){
    memset(dis, 0xc0, sizeof dis);
    queue < int > cur;
    cur.push(1); inq[1] = true; dep[1] = 1, dis[1] = 0;
    while(!cur.empty()){
        int p = cur.front(); cur.pop();
        inq[p] = false;
        for(auto i = head[p]; i; i = i->nxt){
            if(dis[p] + i->val > dis[SON]){
                dis[SON] = dis[p] + i->val;
                ans = max(ans, dis[SON]);
                dep[SON] = dep[p] + 1;
                if(dep[SON] > 26 * 26 + 26 + 1)printf("Infinity\n"), exit(0);
                if(!inq[SON])cur.push(SON), inq[SON] = true;
            }
        }
    }
}

int main(){
    N = read();
    for(int i = 1; i <= N; ++i){
        string S; cin >> S;
        score.insert({S, read()});
    }mp.insert({{0, 0}, ++cnt}), rmp.insert({cnt, {0, 0}});
    for(int i = 'a'; i <= 'z'; ++i)mp.insert({{0, i}, ++cnt}), rmp.insert({cnt, {0, i}});
    for(int i = 'a'; i <= 'z'; ++i)for(int j = 'a'; j <= 'z'; ++j)
        mp.insert({{i, j}, ++cnt}), rmp.insert({cnt, {i, j}});
    for(int i = 1; i <= cnt; ++i)for(int j = 'a'; j <= 'z'; ++j){
        ll tot(0); string S;
        if(rmp[i].first)S += (char)rmp[i].first;
        if(rmp[i].second)S += (char)rmp[i].second;
        S += j; tot += score[S];
        while(!S.empty()){
            S.erase(S.begin());
            tot += score[S];
        }
        head[i] = new Edge{head[i], mp[{rmp[i].second, j}], tot};
    }SPFA();
    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_03 初稿