79练习赛D

回文字D

https://ac.nowcoder.com/acm/contest/11169/D

题目:https://ac.nowcoder.com/acm/contest/11169/D

正解 —— 字符串 hash
比赛的时候用贪心感觉可以,但是没弄出来,赛后正解对拍瞎弄弄出来了。

大概思路:

要使每个长度为的字串都是回文串仅存在两种情况:

  1. 每个字母相同 即:aaaaa...
  2. 为奇数且仅含两个字母重复循环 即:abababababab..

只有以上情况所截取的字符串长度大于
截取字符串长度等于时,该字符串只能为回文串。

之后便可贪心,具体详见代码及注释。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 7;
char s[N];
int l, r = -1, n, d, tot;
inline bool chk() {
    // 每次考虑截取的长度 l-r
    l = r + 1, r = l + d - 1;
    if (r > n - 1)
        return 0;
    // 取前两个字符 判断是否为 aaaaaa... 或 ababababab...的这种形式
    char a = s[l], b = s[l + 1];
    bool flag = 0;
    // 判断长度为D的是否为回文串
    for (int i = 0; i <= tot; ++i) {
        // 不是回文串 只能截取长度 d-1
        if (s[i + l] != s[r - i])
            return --r, 1;
        // 判断是否是以abababab..循环
        if (!((i & 1 && s[i + l] == b) || (i % 2 == 0 && s[i + l] == a)))
            flag = 1;
    }
    // aaaa....
    if (a == b) {
        for (int i = l; i <= r; ++i)
            if (s[i] != a)
                return 1;
        while (!(r + 1 >= n || s[r + 1] != s[r]))
            ++r;
        return 1;
    }
    // abababab....
    if (a != b) {
        // 如果不是abababa.. 则就是一个简单回文串
        if (flag)
            return 1;
        while (!(r + 1 >= n || (s[r + 1] != a && s[r + 1] != b) ||
                 s[r + 1] == s[r]))
            ++r;
        return 1;
    }
    return 0;
}
int solve() {
    // 每个字符串不考虑特殊情况简单拆分最大长度 d-1
    int maxn = n / (d - 1) + 1, ans = 0;
    tot = d / 2;
    // 循环考虑截取长度
    while (chk())
        ans++;
    // 剩下点小尾巴 也要单独分一段
    if (l < n)
        ans++;
    return min(ans, maxn);
}
int main() {
    scanf("%d%d%s", &n, &d, s);
    // 如果d=1则每个长度为d的字串都是字符串 既不用拆分
    if (n < d || d == 1)
        puts("1");
    else
        printf("%d\n", solve());
    return 0;
}
全部评论

相关推荐

吐泡泡的咸鱼:我也工作了几年了,也陆陆续续面试过不少人,就简历来说,第一眼学历不太够,你只能靠你的实习或者论文或者项目经历,然后你没有论文,没有含金量高的比赛和奖项,只能看实习和项目,实习来说,你写的实习经历完全不清楚你想找什么工作?行研?数据分析?且写的太少了,再看项目,这些项目先不说上过大学读过研究生的都知道很水,然后对你想找的岗位有什么帮助呢?项目和实习也完全不匹配啊,你好像在努力将你所有的经历都放在简历里想表现你的优秀,但是对于你想找的岗位来说,有什么用呢?最后只能获得岗位不匹配的评价。所以你需要明白你想要找的岗位要求是什么,是做什么的,比如产品经理,然后再看你的经历里有什么匹配的上这个岗位,或者对这个岗位以及这个岗位所在的公司有价值,再写到你的简历上
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务