洛谷P5319 奥术神杖

短命女 2022-10-02 15:59 42阅读 0赞

题意：给你若干个串和一个填了一部分的串。补完这个串使得 (每个串的匹配次数 \* 权值) ^ (1 / 所有串匹配次数) 最大。

解：把这个东西随便取一个对数，就变成了分数规划。

二分。然后在AC自动机上DP判定。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
      2 
      3 const int N = 1510;
      4 const double INF = 1e10, eps = 1e-16;
      5 
      6 int tr[N][26], tot(1), cnt[N], g[N][N], gt[N][N], tans, fail[N], n;
      7 double ed[N], f[N][N];
      8 char str[N], ss[N];
      9 
     10 inline void getfail() {
     11 
     12     std::queue<int> Q;
     13     Q.push(1);
     14     fail[1] = 1;
     15     while(Q.size()) {
     16         int x = Q.front();
     17         if(x != 1) {
     18             ed[x] += ed[fail[x]];
     19             cnt[x] += cnt[fail[x]];
     20         }
     21         Q.pop();
     22         for(int f = 0; f < 10; f++) {
     23             if(tr[x][f]) {
     24                 int y = tr[x][f];
     25                 if(x == 1) fail[y] = 1;
     26                 else fail[y] = tr[fail[x]][f];
     27                 Q.push(y);
     28             }
     29             else {
     30                 if(x == 1) tr[x][f] = 1;
     31                 else tr[x][f] = tr[fail[x]][f];
     32             }
     33         }
     34     }
     35     return;
     36 }
     37 
     38 inline void insert(double v) {
     39     int len = strlen(ss), p = 1;
     40     for(int i = 0; i < len; i++) {
     41         int f = ss[i] - '0';
     42         if(!tr[p][f]) {
     43             tr[p][f] = ++tot;
     44         }
     45         p = tr[p][f];
     46     }
     47     ed[p] += v;
     48     cnt[p]++;
     49     return;
     50 }
     51 
     52 inline double check(double D) {
     53 
     54     /// f[i][j] means len i in node j , max value
     55 
     56     for(int i = 0; i <= n; i++) {
     57         for(int j = 1; j <= tot; j++) {
     58             f[i][j] = -INF;
     59         }
     60     }
     61 
     62     double ans = -INF;
     63     f[0][1] = 0;
     64     for(int i = 0; i < n; i++) {
     65         for(int j = 1; j <= tot; j++) {
     66             //if(sgn(f[i][j] + INF) == 0) continue;
     67             if(f[i][j] == -INF) continue;
     68             //printf("%lf ", f[i][j]);
     69             if(str[i + 1] != '.') {
     70                 int ff = str[i + 1] - '0';
     71                 int y = tr[j][ff];
     72                 if(f[i + 1][y] < f[i][j] + ed[y] - D * cnt[y]) {
     73                     f[i + 1][y] = f[i][j] + ed[y] - D * cnt[y];
     74                     g[i + 1][y] = j;
     75                     gt[i + 1][y] = ff;
     76                 }
     77             }
     78             else {
     79                 for(int ff = 0; ff < 10; ff++) {
     80                     int y = tr[j][ff];
     81                     //f[i + 1][y] = std::max(f[i + 1][y], f[i][j] + ed[y] - D * cnt[y]);
     82                     if(f[i + 1][y] < f[i][j] + ed[y] - D * cnt[y]) {
     83                         //printf("ff = %d  y = %d  \n", ff, y);
     84                         f[i + 1][y] = f[i][j] + ed[y] - D * cnt[y];
     85                         g[i + 1][y] = j;
     86                         gt[i + 1][y] = ff;
     87                     }
     88                 }
     89             }
     90         }
     91         //puts("");
     92     }
     93 
     94     for(int j = 1; j <= tot; j++) {
     95         if(ans < f[n][j] + eps) {
     96             ans = f[n][j];
     97             tans = j;
     98         }
     99     }
    100 
    101     return ans;
    102 }
    103 
    104 int main() {
    105 
    106     //freopen("my.out", "w", stdout);
    107 
    108     int m;
    109     double l = 0, r = 0;
    110     scanf("%d%d", &n, &m);
    111     scanf("%s", str + 1);
    112     double x;
    113     for(int i = 1; i <= m; i++) {
    114         scanf("%s%lf", ss, &x);
    115         //printf("i = %d \n", i);
    116         x = log(x);
    117         //printf(" h  21 1 1 \n");
    118         insert(x);
    119         //printf(" fdsgfdsfsdfsh  21 1 1  \n");
    120         r += x;
    121         int len = strlen(ss);
    122         memset(ss, 0, len * sizeof(char));
    123     }
    124     //printf("gfsiofdsfsdgfs\n");
    125 
    126     getfail();
    127 
    128     for(int T = 1; T <= 30; T++) {
    129         double mid = (l + r) / 2;
    130         //printf("mid %.10f \n", mid);
    131         double t = check(mid);
    132         //printf("l = %lf r = %lf mid = %lf \n", l, r, mid);
    133 
    134         if(t > 0) {
    135             l = mid;
    136         }
    137         else {
    138             r = mid;
    139         }
    140     }
    141 
    142     //printf("r = %.10f \n", r);
    143     /// output ways
    144 /*
    145 6 5
    146 2....2
    147 252 62
    148 5225 18
    149 25 7
    150 552 12
    151 2122 18
    152 
    153 */
    154 
    155     check(l);
    156     for(int i = n; i >= 1; i--) {
    157         //printf("ans : %d \n", gt[i][tans]);
    158         //printf("node : j = %d \n", tans);
    159         str[i] = gt[i][tans];
    160         tans = g[i][tans];
    161 
    162     }
    163 
    164     for(int i = 1; i <= n; i++) {
    165         putchar(str[i] + '0');
    166     }
    167     /*for(int i = 1; i <= n; i++) {
    168         printf("%d \n", str[i]);
    169     }*/
    170 
    171     /*puts("");
    172     for(int i = 1; i <= tot; i++) {
    173         printf("i = %d fail = %d | ", i, fail[i]);
    174         for(int j = 0; j < 10; j++) {
    175             printf("%d ", tr[i][j]);
    176         }
    177         puts("");
    178     }*/
    179 
    180     return 0;
    181 }

AC代码

输出答案前如果不加那一句check(l)，会WA第二个点。

转载于:https://www.cnblogs.com/huyufeifei/p/10884050.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220109/60ff10f88fd44bc69851e64e4e9ee931.png