A.

如果一个序列含有0或有两个相同的数，那么答案是0。
可以通过玄学证明或打表得到如果 \(n\geq 6\) 答案一定是0。
对剩下的数据直接爆搜即可。

Code

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int n,a[300003],ans;
void dfs(int x){
    if(ans==0)return;
    if(x==1){
        ans=min(ans,a[1]);
        return;
    }
    for(int i=1;i<=x;i++){
        for(int j=i+1;j<=x;j++){
            int tmp1=a[i],tmp2=a[j];
            for(int k=j;k<x;k++)a[k]=a[k+1];
            a[i]=tmp1+tmp2;
            dfs(x-1);
            a[i]=abs(tmp1-tmp2);
            dfs(x-1);
            a[i]=tmp1*tmp2;
            dfs(x-1);
            for(int k=x-1;k>=j;k--)a[k+1]=a[k];
            a[i]=tmp1,a[j]=tmp2;
        }
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",a+i);
        if(n>8){puts("0");continue;}
        ans=INF;
        dfs(n);
        printf("%d\n",ans);
    }
    return 0;
}

B.

答案=总数-重复计算次数。
考虑所有可能的答案 \(c\) 。设 \(a\) 是 \(s\) 的一个前缀， \(b\) 是 \(t\) 的一个前缀，\(a+b=c\) 。取 \(a\) 最长的作为代表串，则 \(|a|>|a_1|,|b|<|b_1|\) ，那么 \(b_1\) 是 \(b\) 的一个border（既是前缀又是后缀） 。统计时，枚举 \(b\) ，取其最长的border（如果不取的话会重复统计），从后面把这个border删掉，然后剩余的字符串在 \(s\) 中作为非前缀出现的次数作为答案。
用kmp匹配一遍，然后累加后缀和。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long D;
const int maxn=100003;
int kmp[maxn],sum[maxn];
char s[maxn],t[maxn];
int main(){
    scanf("%s%s",s+1,t+1);
    int n=strlen(s+1),m=strlen(t+1);
    int pos=0;
    for(int i=2;i<=m;i++){
        while(pos&&t[i]!=t[pos+1])pos=kmp[pos];
        if(t[i]==t[pos+1])pos++;
        kmp[i]=pos;
    }
    pos=0;
    for(int i=2;i<=n;i++){
        while(pos&&s[i]!=t[pos+1])pos=kmp[pos];
        if(s[i]==t[pos+1])pos++;
        sum[pos]++;
    }
    for(int i=m;i>=1;i--)sum[kmp[i]]+=sum[i];
    D ans=0;
    for(int i=1;i<=m;i++)if(kmp[i])ans+=sum[i-kmp[i]];
    printf("%lld\n",1ll*n*m-ans);
    return 0;
}

20191005

原文：https://www.cnblogs.com/BlogOfchc1234567890/p/11631513.html