牛客小白月赛13题解


A.小A的签到题

题目描述

这是一道签到题,主要考验比赛时的手速。接下来是一段很简单的代码,或许你提交它就可以AC。

#include<bits/stdc++.h>
using namespace std;
int main() {
    long long n;
    scanf("%lld",&n);
    long long f1=1,f2=1,f3;
    for(int i=3;i<=n;i++) {
        f3=f1+f2;
        f1=f2;
        f2=f3;
    }
    printf("%lld\n",f3*f3-f1*f1-f1*f3);
    return 0;
}

输入描述:

一行一个整数N

输出描述:

一行一个整数表示结果

示例1

输入

3

输出

1

备注:

$3≤N≤1e11$

思路

  • 确实是一道签到题啊!通过测试几组数据就可以发现规律:当N为奇数时,输出1;当N为偶数时,输出-1。

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    scanf("%lld",&n);
    if(n&1) printf("1\n");
    else printf("-1\n");
    return 0;
}

B.小A的回文串

题目描述

小A非常喜欢回文串,当然我们都知道回文串这种情况是非常特殊的。所以小A只想知道给定的一个字符串的最大回文子串是多少,但是小A对这个结果并不是非常满意。现在小A可以对这个字符串做一些改动,他可以把这个字符串最前面的某一段连续的字符(不改变顺序)移动到原先字符串的末尾。那么请问小A通过这样的操作之后(也可以选择不移动)能够得到最大回文子串的长度是多少。

输入描述:

一行一个字符串表示给定的字符串$S$

输出描述:

一行输出一个整数,表示通过这样的操作后可以得到最大回文子串的长度。

示例1

输入

dcbaabc

输出

7

说明

将前面的dcba移动到末尾变成abcdcba,这个字符串的最大回文子串就是它本身,长度为7

备注:

N表示字符串的长度,$1≤N≤5000$。

思路

题意简单概括就是:给你一个字符串,并赋予我们一项特异功能:将字符串从任意位置,一分为二,将第一段字符串(不改变顺序)接到第二段字符串的尾部,形成一个崭新的字符。求在有特异功能(也可选择不使用)的加持下,回文字穿的最大值。将前一部分移动到后一部分,用数组将字符串表示为环状。求回文子串,用马拉车(O(n))跑一遍就好了。这样复杂度就是$O(n^2)$了。

代码($O(n^2)$)

#include <bits/stdc++.h>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
const int MAXN = 1e5;
char str[MAXN];
char tmp[2*MAXN];
int len[2*MAXN];
int Manacher(char str[])
{
    tmp[0] = '$';
    tmp[1] = '#';
    int str_len = strlen(str);
    for(int i=1; i<=str_len; i++)
    {
        tmp[2*i] = str[i-1];
        tmp[2*i+1] = '#';
    }
    tmp[2*str_len+2] = '\0';
    //cout << tmp << endl;
    int mx = 0;
    int maxlen = -1;
    int mid;
    for(int i=1; tmp[i]; i++)
    {
        if(i < mx) len[i] = min(len[2*mid-i],mx-i);
        else len[i] = 1;
        while(tmp[i-len[i]] == tmp[i+len[i]]) len[i]++;
        if(len[i]+i > mx)
        {
            mx = len[i]+i;
            mid = i;
        }
        maxlen = max(maxlen,len[i]-1);
    }
    return maxlen;
}
char so[5010];
int main()
{
    scanf("%s",str);
    int len = strlen(str);
    for(int i=0; i<=len-1; i++)
    {
        str[i+len] = str[i];
    }
    int ans = 0;
    for(int i=0; i<=len-1; i++)
    {
        memset(so,0,sizeof(so));
        strncpy(so, str+i, len);
        // printf("%s\n",so);
        ans = max(ans,Manacher(so));
    }
    cout << ans;
    return 0;
}
Last modification:May 29th, 2019 at 09:32 am
有钱的捧个钱场,没带钱的捧个人场。

Leave a Comment