您的位置: 首页  >  IT文章  >  牛客练习赛42（A,B）

牛客练习赛42（A,B）

分类: IT文章 • 2022-02-28 19:17:03

牛客练习赛42（A,B）

A：链接：https://ac.nowcoder.com/acm/contest/393/A

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

给定两个等长的由小写字母构成的串 A,BA,B，其中 |A|=|B|=n 。

现在你需要求出一个子区间 [l,r]使得 LCP(A[l,r],B[l,r])×LCS(A[l,r],B[l,r])+LCP(A[l,r],B[l,r])+LCS(A[l,r],B[l,r]) 最大，并输出这个值。

LCS(S,T)表示S和T的最长公共后缀。

输入描述:

第一行一个字符串 B 。

输出描述:

一行一个整数，表示答案。
示例1

输入

aaabbbcccddd
aaaddddddddd

输出

15

说明

选择  是一种可行的最优解。

备注:

对于所有数据，保证 n≤200000 ，串 A,B仅由小写字母构成。

思路：一眼看是最长公共前缀和最长公共后缀。但是稍微想一下，其实只需要求一次最长公共前缀就行了，因为无论怎么样对于一段连续字符串来说，最长前缀和最长后缀是一样的。
　　　　比如说aaabab和aaaccc，最优情况是选前三个字母aaa。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 100000007;
int dp[200000];
int main(){
    string s1,s2;
    cin>>s1>>s2;
    memset(dp,0,sizeof(dp));
    int a = 0,b = 0;
    for(int i = 1 ; i <= s1.size() ; i ++){
        if(s1[i-1] == s2[i-1]){
            dp[i] = dp[i-1]+1; 
        }else{
            dp[i] = 0;
        }
        a = max(a,dp[i]);
    }
    LL ans = a*a*1LL + 2LL*a;
    printf("%lld
",ans);
}/*
aaabbbddccdd
aaaddddddddd
*/

B：链接：https://ac.nowcoder.com/acm/contest/393/B
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

注意本题有模数
给定一个 长度为 n 的序列 { a } ，求：

其中  表示异或

输入描述:

第一行一个整数 n 。
第二行 n 个整数，表示  。

输出描述:

一行一个整数 ans ，表示答案。
示例1

输入

3
1 2 3

输出

6

说明

我们  。

备注:

对于所有的数据，保证  。

样例：想不到吧，你的做法至少能过样例！

思路：没啥好说的，对于一个数a_i，即使前面出现过a_i这个数，大不了就是异或等于0，但是会再加上a_i，对ans贡献肯定是增大的。所以选所有数就好啦。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 100000007;
int main(){
    int n;
    scanf("%d",&n);
    LL s1 = 0,s2 = 0;
    for(int i = 0 ; i < n ; i ++){
        LL x;
        scanf("%lld",&x);
        s1 += x;
        s1 %=mod;
        s2 ^= x;
        s2 %= mod;
    }
    printf("%lld
",(s1+s2+mod)%mod);
}

C：链接：https://ac.nowcoder.com/acm/contest/393/C
来源：牛客网

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

给定m个长为n的序列

相关推荐