2017 计蒜之道初赛第五场题解

比赛链接：2017 计蒜之道初赛第五场

A:水题，WA了三次。。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        vector<int> a(m);
        for(auto &v:a) cin>>v;
        sort(a.begin(),a.end(),[](int a,int b){ return a>b; });
        int k=,ans=;
        bool ok=false;
        if(n>)
        for(int i=;i<m&&a[i];i++)
        {
            k+=a[i]-;
            ans=i+;
            if(k>=n)
                break;
        }
        if(k>=n) cout << ans << endl;
        else cout << "Impossible" << endl;
    }
    return ;
}
           

B,C:

类似XDOJ的1175。

动态维护s上一个长度为k的区间内不同数字的个数及其数量。

复杂度为 O(nm)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=;
int s[N],t[N],tmp[N],n,m,c1[N],c2[N];
int main()
{
    int T;
    scanf("%d",&n);
    for(int i=;i<=n;i++) scanf("%d",&s[i]);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&m);
        for(int i=;i<=m;i++) scanf("%d",&t[i]);
        memset(c2,,sizeof(c2));
        memset(c1,,sizeof(c1));
        int ans=,num=,res=;
        for(int i=;i<=m;i++)
        {
            if(!c2[t[i]]) ++num;
            ++c2[t[i]];
        }
        for(int i=;i<=m;i++)
        {
            if(c1[s[i]]==c2[s[i]]) --res;
            ++c1[s[i]];
            if(c1[s[i]]==c2[s[i]]) ++res;
        }
        if(res==num) ++ans;
        for(int i=m+;i<=n;i++)
        {
            if(c1[s[i]]==c2[s[i]]) --res;
            ++c1[s[i]];
            if(c1[s[i]]==c2[s[i]]) ++res;
            if(c1[s[i-m]]==c2[s[i-m]]) --res;
            --c1[s[i-m]];
            if(c1[s[i-m]]==c2[s[i-m]]) ++res;
            if(res==num) ++ans;
        }
        printf("%d\n",ans);
    }
    return ;
}
           

D:

考虑到 ∑k<200000 ，且有 m 个询问，那么这 m 个询问中，最多有 m−−√ 中不同的 k 。

因此离线处理，先读入所有的询问，然后对于长度 l ，将所有长度为 l 的 t 丢入哈希表中， hashvalue(t)=∑ti 。然后对 s 中所有长度为 l 的子串求出哈希值，然后放到哈希表里查找。

判断 substr(s) 于 t 相等，这里用了两个 vis 来处理。

维护 substr(s) 的哈希值： hash[l,r]=hash[l−1,r−1]−s[l−1]+s[r] 。

把哈希表的复杂度看成 O(1) 的话，算法时间复杂度是 O(nm−−√+∑k) 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=+,N=+;
const int mod=M;
typedef vector<int> vi;
vector<int> s,t[M];
vector<int> T[N];
int ans[M],vis1[N],vis2[N],vs=,c1[N],c2[N];
int n,m,L;

vector<vi> ht[mod];

bool iseq(vi &a,vi &b,int l)
{
    int cnt1=,cnt2=;
    for(auto &c : a)
    {
        if(vis1[c]!=vs)
        {
            vis1[c]=vs;
            c1[c]=;
            ++cnt1;
        }
        else ++c1[c];
    }
    for(int i=;i<a.size();i++)
    {
        int c=b[i+l];
        if(vis2[c]!=vs)
        {
            vis2[c]=vs;
            c2[c]=;
        }
        else ++c2[c];
        if(vis1[c]==vs)
        {
            if(c1[c]==c2[c]) ++cnt2;
            else if(c1[c]==c2[c]-) --cnt2;
        }
    }
    ++vs;
    return cnt1==cnt2;
}

void update(int hv,int l)
{
    for(auto &vec:ht[hv])
    {
        int j=vec[];
        if(iseq(t[j],s,l))
        {
            for(auto &v:vec)
                ++ans[v];
            return ;
        }
    }
}
void insert(int id)
{
    int hv=;
    for(int i=;i<t[id].size();++i) hv=(hv+t[id][i])%mod;
    vi v;
    for(auto& vec:ht[hv])
    {
        int x=vec[];
        if(iseq(t[x],t[id],))
        {
            vec.push_back(id);
            return ;
        }
    }
    v.push_back(id);
    ht[hv].push_back(v);
}
int main()
{
    scanf("%d",&n);
    s=vector<int>(n);
    for(int i=;i<n;i++)
        scanf("%d",&s[i]);
    scanf("%d",&m);
    for(int i=;i<m;i++)
    {
        int k;
        scanf("%d",&k);
        t[i]=vector<int>(k);
        for(int j=;j<k;++j) scanf("%d",&t[i][j]);
        T[t[i].size()].push_back(i);
    }
    for(int i=;i<=n;++i)
    {
        if(!T[i].size()) continue;
        for(int j=;j<mod;++j) ht[j].clear();
        for(auto j:T[i]) insert(j);
        int hv=;
        L=t[T[i][]].size();
        for(int j=;j<L;++j) hv=(hv+s[j])%mod;
        update(hv,);
        for(int j=L;j<n;++j)
        {
            hv=(hv-s[j-L]+mod)%mod;
            hv=(hv+s[j])%mod;
            update(hv,j-L+);
        }
    }
    for(int i=;i<m;i++)
        printf("%d\n",ans[i]);
    return ;
}