首页 > 其他分享 >CF808G Anthem of Berland

CF808G Anthem of Berland

时间:2024-10-01 17:23:35浏览次数:9  
标签:10 匹配 Berland int Anthem max include border CF808G

题意

给定字符串 \(s\),\(t\),求将 \(s\) 中的通配符赋值,\(t\) 在 \(s\) 中出现的最大次数。

\(n \times m \le 10 ^ 7\)。

Sol

考虑朴素 \(\texttt{dp}\),设 \(f_i\) 表示 \(i\) 之前的匹配出现的最大次数。

若当前的 \([i - m + 1, i]\) 可以直接匹配,或是由通配符匹配。

则 \(f_i = max(f_i, f_{i - m + 1} + 1)\)。

但是,显然可能出现使用上一次匹配的一个后缀。

显然这个一定是 \(t\) 的一个 \(border\),直接暴力枚举所有 \(border\) 即可。

最后还有一个问题,这种转移需要保证上一个位置一定是被匹配过的位置。

直接设 \(g_i\) 表示钦定最后一次匹配。

  • \(f_i = max(f_{i + 1}, g_i)\)。

  • \(g_i = max(max_{k \in border} g_{i - m + k}, f_{i - m}) + 1\)。

时间复杂度:\(O(n \times m)\)。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
int read() {
    int p = 0, flg = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') flg = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        p = p * 10 + c - '0';
        c = getchar();
    }
    return p * flg;
}
void write(int x) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    if (x > 9) {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}
bool _stmer;

const int N = 1e5 + 5;

char strbuf[N];

namespace Kmp {

array <int, N * 2> isl;

void prefix(string s, int n) {
    for (int i = 2; i <= n; i++) {
        isl[i] = isl[i - 1];
        while (isl[i] && s[i] != s[isl[i] + 1]) isl[i] = isl[isl[i]];
        if (s[i] == s[isl[i] + 1]) isl[i]++;
    }
}

} //namespace Kmp

array <int, N> f, g;

bool _edmer;
int main() {
    cerr << (&_stmer - &_edmer) / 1024.0 / 1024.0 << "MB\n";
    scanf("%s", strbuf); string s = strbuf; int n = s.size();
    scanf("%s", strbuf); string t = strbuf; int m = t.size();
    s = " " + s, t = " " + t;
    Kmp::prefix(t, m);
    for (int i = 1; i <= n; i++) {
        bool flg = (i >= m);
        for (int j = max(i - m + 1, 0); j <= i; j++)
            flg &= (s[j] == t[j - i + m] || s[j] == '?');
        f[i] = f[i - 1];
        if (!flg) continue;
        int res = 0;
        for (int j = m; j; j = Kmp::isl[j])
            res = max(max(g[i - m + j], f[i - m]) + 1, res);
        g[i] = max(res, f[i - m] + 1);
        f[i] = max(f[i], g[i]);
    }
    write(f[n]), puts("");
    return 0;
}

标签:10,匹配,Berland,int,Anthem,max,include,border,CF808G
From: https://www.cnblogs.com/cxqghzj/p/18442992

相关文章

  • CodeForces 1C - Ancient Berland Circus
    先通过三点确定一条直线,然后算出三条向量的夹角,与圆心角对比,如果呈倍数关系,说明可以接受。特别注意EPS1e-2和1e-7过不了全部数据,改成1e-4通过全部数据。点击查看代码#include<bits/stdc++.h>#definedoublelongdoubleusingnamespacestd;constdoublePI=acos(-1);......
  • 题解:CF644A Parliament of Berland
    本题题意有\(n\)个议员,编号为\(1\simn\),就坐在\(a\timesb\)的礼堂里,求如何安排座位能够使得任意两个相邻的座位上的议员奇偶性不相同。思路无解情况当\(n>a\timesb\)时,必定无法满足,则直接输出-1。有解情况打表找规律。我们发现,只要让奇数行正着就坐,偶数......
  • tryhackme-Anthem(国歌)
    根据题目描述,这是一个让我们练习的简单Windows机器信息收集首先对靶机进行端口扫描加入-Pn参数是因为Windows默认开启防火墙拒绝icmpping数据包根据开放端口80和3389猜测到后续可能会远程连接靶机接着访问80端口进行信息收集根据title和网页标题,可以看出网站的域名为Anth......
  • Ball in Berland
    ThisisaprogramingproblemonCodeforceswithadifficultyscoreof1400.ItssolutionisbasedontheInclusion-Exclusionprinciple.https://codeforces.com/problemset/problem/1475/Cvoidsolve(){ inta,b,k; cin>>a>>b>>k; m......
  • P9370 APIO2023 cyberland
    题面:https://www.luogu.com.cn/problem/P9370显然只有从\(0\)出发不经过\(H\)能到达的点是有用的。首先,考虑跑多源最短路,将\(arr=0\)的点都作为源点(当然\(0\)也是源点)。不难发现这样转化后,这些点即可视作\(arr=1\)。对于\(arr=2\)的点,由于能使用除以二技能的次数很......
  • [Codeforces] CF1475C Ball in Berland
    BallinBerland-洛谷题意在毕业典礼上,有\(a\)个男孩和\(b\)个女孩准备跳舞,不是所有的男孩和女孩都准备结伴跳舞。现在你知道\(k\)个可能的舞伴,你需要选择其中的两对,以便使没有人重复地出现在舞伴里,求可能的数量。思路暴力最朴素,也是简单的方法,就是通过暴力组合进行配对。......
  • CF1475C Ball in Berland
    CF1475CBallinBerlandBallinBerland-洛谷题意在毕业典礼上,有\(a\)个男孩和\(b\)个女孩准备跳舞,不是所有的男孩和女孩都准备结伴跳舞。现在你知道\(k\)个可能的舞伴,你需要选择其中的两对,以便使没有人重复地出现在舞伴里,求可能的数量。思路暴力最朴素,也是简单的方法,就......
  • [Codeforces] CF1475C Ball in Berland 题解
    BallinBerland-洛谷题意在毕业典礼上,有​个男孩和​个女孩准备跳舞,不是所有的男孩和女孩都准备结伴跳舞。现在你知道​个可能的舞伴,你需要选择其中的两对,以便使没有人重复地出现在舞伴里,求可能的数量。思路暴力最朴素,也是简单的方法,就是通过暴力组合进行配对。#include......
  • P9370 APIO2023 赛博乐园 / cyberland
    P9370APIO2023赛博乐园/cyberland。题目就是让我们求一个有各种优惠政策的单源点\(0\),单汇点\(H\)的最短路。优惠政策是:到达能力为\(2\)的点,可以让之前走过的距离除以\(2\)。到达能力为\(0\)的点,可以让之前走过的距离直接变成\(0\)。有限制:不能经过\(H\)多次......
  • CF1809F Traveling in Berland - 倍增 -
    题目链接:https://codeforces.com/contest/1809/problem/F题解:对一个点,考虑怎样在\(O(\logn)\)的时间复杂度内求出答案,联想到倍增但是,倍增合并的时候只能在两个状态相......