没有过的题QAQ

佚名 6年前 (2019-04-24) 随笔 1710人围观抢沙发百度已收录

持续更新。。。纪念一下我的高分暴力。。。（好丢人啊qwq）

NOI2014 动物园
80pts
用倍增暴力跳nxt数组

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 1000010
#define MOD 1000000007
#define ull unsigned long long
using namespace std;
int T,len,ans;
int nxt[MAXN],fp[22][MAXN];
char s[MAXN];
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    scanf("%d",&T);
    while(T--)
    {
        ans=1;
        memset(nxt,0,sizeof(nxt));
        scanf("%s",s+1);
        len=strlen(s+1);
        int p=0;
        for(int i=2;i<=len;i++)
        {
            while(p&&s[p+1]!=s[i]) p=nxt[p];
            if(s[p+1]==s[i]) p++;
            nxt[i]=p;
        }
        for(int i=2;i<=len;i++) fp[0][i]=nxt[i];
        for(int k=1;k<=21;k++)
            for(int i=2;i<=len;i++)
                fp[k][i]=fp[k-1][fp[k-1][i]];
        for(int i=2;i<=len;i++)
        {
            int now=i;
            for(int j=21;j>=0;j--)
                if(fp[j][now]*2>i)
                    now=fp[j][now];
            int cur_ans=0;
            for(int j=21;j>=0;j--)
                if(fp[j][now])
                    cur_ans+=(1<<j),now=fp[j][now];
            ans=1ll*ans*(cur_ans+1)%MOD;
        }
        printf("%d\n",ans);
    }
    return 0;
}

NOI2016 优秀的拆分
95pts
hash直接水,\(n^2\)判断字符串是否相同

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 1000010
#define ull unsigned long long
using namespace std;
int T,n,m;
int base[MAXN],kkk[MAXN];
long long ans;
char s[MAXN];
const int prime=233;
inline void init()
{
    base[0]=1;
    for(int i=1;i<=n;i++)
    {
        base[i]=base[i-1]*prime;
        kkk[i]=kkk[i-1]*prime+s[i]-'a';
    }
}
inline ull query(int l,int r){return kkk[r]-kkk[l-1]*base[r-l+1];}
inline bool check(int l,int r)
{
    if((r-l+1)&1) return false;
    int mid=(l+r)>>1;
    if(query(l,mid)==query(mid+1,r)) return true;
    return false;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    scanf("%d",&T);
    while(T--)
    {
        ans=0;
        scanf("%s",s+1);
        n=strlen(s+1);
        init();
        for(int i=1;i<=n;i++)
        {
            int st=0,en=0;
            for(int j=1;j<=i;j++)
                if(check(j,i)) en++;
            for(int j=i+1;j<=n;j++)
                if(check(i+1,j)) st++;
            ans+=1ll*en*st;
        }
        printf("%lld\n",ans);
    }
    return 0;
}