头像

晓玲

重庆邮电大学




离线:1天前


最近来访(78)
用户头像
别吵好好打
用户头像
JavaBear
用户头像
yqG_G
用户头像
朱柏霖
用户头像
Lam4.
用户头像
277
用户头像
edgdcgxgbx
用户头像
莉亚
用户头像
wyc1996
用户头像
刷刷刷算法
用户头像
TheXX
用户头像
张大壮
用户头像
AcKing_HIT
用户头像
233333
用户头像
acwing_ydx
用户头像
zy23
用户头像
我舅是太阳
用户头像
1..
用户头像
fly668
用户头像
牧守流光


晓玲
30天前

题目描述

给定一个字符串s,求最大的前缀等于后缀等于中间缀

样例

//输入
2
fixprefixsuffix
abcdabc

//输出
fix
not exist

算法1

(KMP) $O(n)$

对于字符串s,我们可以处理处ne数组,ne[i]表示字符串s[1-i]最大的后缀等于前缀的长度
st[i]表示ne[2~n-1]中有=i的情况
先判断最大的后缀等于前缀p = ne[n]是否存在,即st[p],存在即说明2~n-1存在。
否则p = ne[p],这里保证了前缀=后缀=中缀,就是没想到这里导致一直过不去ORZ。

时间复杂度

KMP时间复杂度$O(n)$,然后依次枚举q,$O(n)$,总的时间复杂度$O(n)$.

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1000010;
char s[N], st[N];
int T, ne[N];

int main()
{
    scanf("%d", &T);
    while (T --) {
        scanf("%s", s + 1);
        int n = strlen(s + 1);
        for (int i = 2, j = 0; i <= n; i ++) {
            while (j && s[i] != s[j + 1]) j = ne[j];
            if (s[i] == s[j + 1]) j ++;
            ne[i] = j;
        }
        memset(st, 0, sizeof st);
        for (int i = 2; i < n; i ++)
            if (ne[i]) st[ne[i]] = 1;
        int ans = -1;
        int p = ne[n];
        while (p) {
            if (st[p]) ans = max(ans, p);
            p = ne[p];
        }
        // cout << n <<" " <<ans << endl;
        if (ans == -1) printf("not exist\n");
        else {
            for (int i = 1; i <= ans; i ++) printf("%c", s[i]);
            printf("\n");
        }

    }
}


新鲜事 原文

晓玲
1个月前
字节跳动-商业化技术 22校招正式启动! 字节跳动校招内推码: HZNW6UC 大数据开发工程师:https://jobs.toutiao.com/s/d87n6Rm 客户端开发工程师:https://jobs.toutiao.com/s/d87p8ur 算法工程师:https://jobs.toutiao.com/s/d876FNo 后端开发工程师:https://jobs.toutiao.com/s/d87G6SJ 前端开发工程师:https://jobs.toutiao.com/s/d87pwQn
图片


活动打卡代码 Linux 1.0. homework_0

晓玲
1个月前

ac terminal.png



活动打卡代码 AcWing 3799. 送糖果

晓玲
1个月前

注意读完题目

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int a, b;
int T;

int main()
{
    cin >> T;
    while(T--) {
        int flag = 1, num = 1;
        cin >> a >> b;
        while (a >= 0 && b >= 0) {
            if (flag) {
                a -= num;
            }
            else {
                b -= num;
            }
            num ++;
            flag = !flag;
            // cout << flag << endl;
        }
        if (a < 0) cout << "Vladik" << endl;
        else cout << "Valera" << endl;
    }
}


活动打卡代码 AcWing 3802. 消灭数组

晓玲
1个月前

类似二分的思想,记得用mid = l + r >> 1来划分!一开始直接写成r / 2,人傻了

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
int arr[N];
int n;
int ans;

bool check(int l, int r) {
    bool flag = true;
    for (int i = l; i < r; i ++) {
        if (arr[i] > arr[i + 1]) {
            flag = false;
            break;
        }
    }
    return flag;
}

void dfs(int l, int r) {
    if (l >= r) return;
    if (check(l, r)) {
        ans = max(ans, r - l + 1);
        // cout << "ans = " << ans << endl;
        return;
    } 
    int mid = l + r >> 1;
    dfs(l, mid);
    dfs(mid + 1, r);

}

int main()
{
    int T;
    cin >> T;
    while (T --) {
        ans = 1;
        cin >> n;
        for (int i = 0; i < n; i ++) cin >> arr[i];
        dfs(0, n - 1);
        cout << ans << endl;
    }
}



晓玲
1个月前

这里要想到算数平均数最大说明是数组最大的单个数,相当于找最大的数连续最长的长度即可

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
typedef long long LL;
int a[N];
int n;
int main()
{
    int T;
    scanf("%d", &T);
    while (T --) {
        scanf("%d", &n);
        int mx = 0;
        for (int i = 0; i < n; i ++) {
            scanf("%d", &a[i]);
            mx = max(mx, a[i]);
        }
        int res = 0;
        for (int i = 0; i < n; i ++) {
            if (a[i] == mx) {
                int j = i + 1;
                while (j < n && a[j] == mx) j ++;
                res = max(res, j - i);
                i = j - 1;
            }
        }
        printf("%d\n", res);

    }
}


活动打卡代码 AcWing 3798. 幸运年份

晓玲
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
    int T;
    cin >> T;
    while (T--) {
        long long n;
        cin >> n;
        string strn = to_string(n);
        // cout << "strn = " << strn << endl;
        int len = strn.size();
        // cout << "len = " << len << endl;

        if (strn[0] == '9') {
            long long num = pow(10, len);
            cout << num - n << endl;
        }
        else {
            long long num = (strn[0] - '0' + 1) * pow(10, len - 1);
            cout << num - n << endl;
        }
    }
}


活动打卡代码 AcWing 3781. 乘车问题

晓玲
2个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        int ans = 0;
        int nowm = m;
        for (int i = 0; i < n; i ++ ){
            int x;
            cin >> x;
            if (nowm < x) ans ++, nowm = m;
            nowm -= x;
        }
        ans ++;
        cout << ans << endl;
    }
}


活动打卡代码 AcWing 3773. 兔子跳

晓玲
2个月前

注意CF的题目代码都不难,所以要脑洞打开,这道题就是简单的几何,加油!

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T --) {
        int n, x;
        cin >> n >> x;
        int a = 0;
        int flag = 0;
        while (n --) {
            int t;
            cin >> t;
            if (t == x) flag = 1;
            a = max(a, t);
        }
        if (flag) cout << "1" << endl;
        else if (a > x) cout << "2" << endl;
        else cout << (x + a - 1) / a << endl;
    }
    return 0;
}


活动打卡代码 AcWing 3769. 移动石子

晓玲
2个月前
#include<bits/stdc++.h>
using namespace std;

int a[105];
int n, d;

int main() {
    int t;
    cin >> t;
    while (t --) {
        cin >> n >> d;
        for (int i = 0; i < n; i ++) cin >> a[i];
        for (int i = 1; i < n && d; i ++) {
            if (d >= i * a[i]) {
                d -= i * a[i];
                a[0] += a[i];
            }
            else {
                a[0] += d / i;
                d = 0;
            }
            // cout <<"a[0] = " << a[0] << endl;
            // cout << "d = " << d << endl;
        }
        cout << a[0] << endl;
    }
    return 0;
}

模拟即可