CCPC湖北省赛游记

在学长说这是CCPC湖北省赛之前，我一直以为这是武大校赛。。。。。所以我全场实际上是在一直划水的。。。。。结果看起来也并没有达到预期的希望。不过就是那种得不到的东西，才能称之为希望吧。

开场不知所措，三人胡乱看题，几分钟后有人交了D，我一看，水题啊，想到犹豫就会败北，果断胡写一发，然后就白给了发WA，再看了一下，发现个sb错误，顺手改掉后AC。

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+50;
int a[N];
int main()
{
    int T,n,k;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        for(int i=0;i<n;i++)
            scanf("%d",a+i);
        map<int,int> mp;
        for(int i=0;i<n;i++)
            mp[a[i]]++;
        long long ans=0;
        for(auto ite=mp.begin();ite!=mp.end();++ite)
            ans+=1ll*( ite->second)*mp[ite->first-k];
        printf("%lld\n",ans);
    }
    return 0;
}

之后去做F，发现没有数据范围，问了一波出题人，然后全场被提示F题暂时不可做，于是愉快的换题，看到队友们在看G，抢过来一看，发现显然做过（很类似的），（在队友们的懵逼中）随手拍了个Python就1A了。

mp={}
mp['1']=2
mp['2']=5
mp['3']=5
mp['4']=4
mp['5']=5
mp['6']=6
mp['7']=3
mp['8']=7
mp['9']=6
mp['0']=6
mp['+']=2
mp['-']=1


T=int(input())
while T:
    T-=1
    n=int(input())
    e=input()
    cnt=0
    symcnt=0
    for ch in e:
        cnt+=mp[ch]
        if ch in ['+','-']:
            symcnt+=1
    #print(cnt,symcnt)
    cnt-=symcnt*3
    ans=0
    if cnt %2 ==1:
        ans=7
        cnt-=3
    else:
        ans=1
        cnt-=2
    while cnt:
        ans=ans*10+1
        cnt-=2
    ans-=symcnt
    print(ans)

接着是H题，简短的了解了题意后（同样是在队友的懵逼之中）快速口胡了一个算法，瞎jb写了一发，然后wa了，又是个sb错误，感谢题目提示，一个数虽然最大能到$2^{31}-1$，但是都是由两个$[0,32768)$的数乘起来得到的，所以质因子不会大于32768，于是迅速打表（还写了个树状数组，最后发现直接前缀和就好了），验了几组数据没毛病，一交，MLE了。。。。sizeof一下发现用了1300+MB内存，只好想办法改进，不知为何我突然想到了奇怪的做法，我把计算改成离线的，每次处理一个质因子，这样就将内存用量降到了原来的$\frac{1}{3000}$，这次终于AC了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+50;
int a[N];
ll ps[N],pcnt;
bool notPrime[1<<15];
const ll mod=35808247 ;
int C[N];
struct query{
    int l,r;
    ll ans;
}Q[N];
int main()
{
    for(ll i=2; i<(1<<15); i++)
        if(!notPrime[i])
        {
            ps[pcnt++]=i;
            for(ll j=i*i; j<(1<<15); j+=i)
                notPrime[j]=true;
        }
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
        scanf("%lld",a+i);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&Q[i].l,&Q[i].r);
        Q[i].ans=1;
    }
    for(int i=0;i<pcnt;i++)
    {
        memset(C,0,sizeof(C));
        for(int j=1;j<=n;j++)
        {
            int cnt=0;
            for(ll x=a[j];x%ps[i]==0;x/=ps[i])
                cnt++;
            C[j]=cnt+C[j-1];
        }
        for(int j=0;j<m;j++)
        {
            query&q=Q[j];
            q.ans=q.ans*(C[q.r]-C[q.l-1]+1)%mod;
        }
    }
    for(int j=0;j<m;j++)
        printf("%lld\n",Q[j].ans);
    return 0;
}

之后感觉J题可做的样子，但是显然我不会后缀数组来求本质不同的子串数量，于是当然要用字符串哈希大法啊！然后就WA了！这时佬蒋出了一组数据把我卡住了，非常好，然后愉快的改了一发再交，TLE了。。。。。又改了一发还是TLE，只是从test11变成了test21，想想这不行啊，时间复杂度应该够了，只是常数上的问题。情急之下，想到了昨天研究的pb_ds，但是！我刚写完heap的部分，还没写hash_table的部分，只好凭着记忆写了一堆，竟然编译通过了，先是试着用cc_hash_table，用cf的自测发现1300+ms，改成gp_hash_table就竟然只用560+ms了！果断交了一发，结果AC了，可以说是非常玄学了。

#include <bits/stdc++.h>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll calc(char *s,ll len)
{
    __gnu_pbds::gp_hash_table<ull,__gnu_pbds::null_type> S;
    for(ll i=0; i<len; i++)
        for(ll j=i,h=1; j<len; j++)
            h=h*131+s[j],S.insert(h);
    return S.size();
}
char str[2050];
int main()
{
    ll k;
    while(~scanf("%s%lld",str,&k))
    {
        ll len=strlen(str);
        memcpy(str+len,str,len);
        memcpy(str+len+len,str,len);
        ll a2=calc(str,len*2);
        ll a3=calc(str,len*3);
        ll ans=0;
        if(k==0) ans=0;
        else if(k==1) ans=calc(str,len);
        else if(k==2) ans=a2;
        else ans=a2+(a3-a2)*(k-2);
        printf("%lld\n",ans);
    }
    return 0;
}

最后是AB题，没有什么思路，A是怎么都过不了样例，B是佬蒋写了个搜索一直WA。最后听着华科一个队连连过题的欢呼，超级不爽，md为什么人家队就有妹子，还是能做题的妹子，还能一直过题，我们却什么都做不出来。

最后靠着不太高的罚时获得了金牌三等奖，只能算差强人意吧。