[ABC264G] String Fair Solution

更好的阅读体验戳此进入

题面

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

Solution

一个十分精妙的图论。

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

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

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

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

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

Code

xxxxxxxxxx
104
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

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

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22

23

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

27
struct Edge{
28
    Edge* nxt;
29
    int to;
30
    ll val;
31
    OPNEW;
32
}ed[21000];
33
ROPNEW(ed);
34
Edge* head[1100];
35

36
int N;
37
int cnt(0);
38
unordered_map < string, int > score;
39
map < pair < int, int >, int > mp;
40
unordered_map < int, pair < int, int > > rmp;
41
bitset < 1100 > inq;
42
int dep[1100];
43
ll dis[1100];
44
ll ans(LONG_LONG_MIN);
45

46
void SPFA(void){
47
    memset(dis, 0xc0, sizeof dis);
48
    queue < int > cur;
49
    cur.push(1); inq[1] = true; dep[1] = 1, dis[1] = 0;
50
    while(!cur.empty()){
51
        int p = cur.front(); cur.pop();
52
        inq[p] = false;
53
        for(auto i = head[p]; i; i = i->nxt){
54
            if(dis[p] + i->val > dis[SON]){
55
                dis[SON] = dis[p] + i->val;
56
                ans = max(ans, dis[SON]);
57
                dep[SON] = dep[p] + 1;
58
                if(dep[SON] > 26 * 26 + 26 + 1)printf("Infinity\n"), exit(0);
59
                if(!inq[SON])cur.push(SON), inq[SON] = true;
60
            }
61
        }
62
    }
63
}
64

65
int main(){
66
    N = read();
67
    for(int i = 1; i <= N; ++i){
68
        string S; cin >> S;
69
        score.insert({S, read()});
70
    }mp.insert({{0, 0}, ++cnt}), rmp.insert({cnt, {0, 0}});
71
    for(int i = 'a'; i <= 'z'; ++i)mp.insert({{0, i}, ++cnt}), rmp.insert({cnt, {0, i}});
72
    for(int i = 'a'; i <= 'z'; ++i)for(int j = 'a'; j <= 'z'; ++j)
73
        mp.insert({{i, j}, ++cnt}), rmp.insert({cnt, {i, j}});
74
    for(int i = 1; i <= cnt; ++i)for(int j = 'a'; j <= 'z'; ++j){
75
        ll tot(0); string S;
76
        if(rmp[i].first)S += (char)rmp[i].first;
77
        if(rmp[i].second)S += (char)rmp[i].second;
78
        S += j; tot += score[S];
79
        while(!S.empty()){
80
            S.erase(S.begin());
81
            tot += score[S];
82
        }
83
        head[i] = new Edge{head[i], mp[{rmp[i].second, j}], tot};
84
    }SPFA();
85
    printf("%lld\n", ans);
86
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
87
    return 0;
88
}
89

90
template < typename T >
91
inline T read(void){
92
    T ret(0);
93
    int flag(1);
94
    char c = getchar();
95
    while(c != '-' && !isdigit(c))c = getchar();
96
    if(c == '-')flag = -1, c = getchar();
97
    while(isdigit(c)){
98
        ret *= 10;
99
        ret += int(c - '0');
100
        c = getchar();
101
    }
102
    ret *= flag;
103
    return ret;
104
}

UPD

update-2023_01_03 初稿