近年NOI题目总结

时间：2019-06-10 19:45:07 阅读：181 评论：0 收藏：0 [点我收藏+]

题目大意：有 $n$ 个字符串，第 $i$ 个在文章中出现了 $w_i$ 次。现在要把每个字符串替换成一个 $k$ 进制字符串（每个字符都是 $0$ 到 $k-1$ 的整数）。假设第 $i$ 个字符串被替换成了 $s_i$，那么要求对于任意 $i\ne j$ 都有 $s_i$ 不是 $s_j$ 的前缀。现在请求出替换后文章最小的长度（$\sum w_i|s_i|$），在此基础上求出 $\max(|s_i|)$ 的最小值。

$1\le n\le 10^5,2\le k\le 9,0\le w_i\le 10^{11}$。

实际上就是哈夫曼树的定义。那么求个 $k$ 进制哈夫曼树即可。

时间复杂度 $O(k+n\log n)$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100010;
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
    char ch=getchar();ll x=0,f=0;
    while(ch<‘0‘ || ch>‘9‘) f|=ch==‘-‘,ch=getchar();
    while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();
    return f?-x:x;
}
int n,k;ll ans;
struct hhh{
    ll w;int h;
    bool operator<(const hhh &h)const{
        if(w!=h.w) return w>h.w;
        return this->h>h.h;
    }
};
priority_queue<hhh> pq;
int main(){
    n=read();k=read();
    FOR(i,1,n) pq.push((hhh){read(),1});
    if((n-1)%(k-1)!=0) FOR(i,1,k-1-(n-1)%(k-1)) pq.push((hhh){0,1});
    while(pq.size()!=1){
        ll sum=0;int hei=0;
        FOR(i,1,k){
            hhh h=pq.top();pq.pop();
            sum+=h.w;hei=max(hei,h.h);
        }
        pq.push((hhh){sum,hei+1});ans+=sum;
    }
    printf("%lld\n%d\n",ans,pq.top().h-1);
}

View Code

NOI2015D2T2

题目大意：有一个长度为 $n$ 的小写字母字符串 $s$，第 $i$ 个字符有权值 $a_i$。对于这个字符串的任意两个不同后缀 $p,q$，定义 $lcp(p,q)$ 为两个后缀的最长公共前缀的长度。现在对于每个 $0\le i\le n-1$，求出对于所有 $lcp(p,q)\ge i$ 的 $p,q$，$a_p\times a_q$ 的和和最大值。

$1\le n\le 3\times 10^5,|a_i|\le 10^9$。

之前没过的又臭又长又慢的做法的题解

（想看并查集做法的看别人的题解吧……）

NOI2016D1T1

题目大意：如果一个字符串可以被拆分为

$$1\le n\le 30000,1\le T\le 10$。$

$$a_i$），以 $i$ 开头的 $AA$ 有多少个（设为 $b_i$），答案即为 $\sum a_ib_{i+1}$。$

$$a_i$ 为例。枚举 $A$ 的长度 $l$，然后考虑 $l,2l,3l\dots\lfloor\frac{n}{l}\rfloor l$ 这些位置。$

$$x+y\ge l$ 时：$ 技术分享图片

发现粉色和棕色的都是合法的 $AA$ 串。也就是说会对绿色荧光笔部分的每一个 $a$ 都产生 $1$ 的贡献。（这个区间是 $[(i+1)l-y+l-1,(i+1)l+x-1]$）

$b$ 同理。

求 $x,y$ 可以用后缀数组做到 $O(1)$，区间加可以用差分做到 $O(1)$。

$$O(Tn\log n)$。$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=30030;
#define PB push_back
#define MP make_pair
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
    char ch=getchar();int x=0,f=0;
    while(ch<‘0‘ || ch>‘9‘) f|=ch==‘-‘,ch=getchar();
    while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();
    return f?-x:x;
}
struct Suffix_Array{
    char s[maxn];
    int n,m,cnt[maxn],sa[maxn],rak[maxn],tmp[maxn],h[maxn][17],logt[maxn];
    void radix_sort(){
        MEM(cnt,0);
        FOR(i,1,n) cnt[rak[tmp[i]]]++;
        FOR(i,1,m) cnt[i]+=cnt[i-1];
        ROF(i,n,1) sa[cnt[rak[tmp[i]]]--]=tmp[i];
    }
    void build(char s[]){
        MEM(sa,0);MEM(rak,0);MEM(tmp,0);MEM(h,0);
        n=strlen(s+1);m=26;
        FOR(i,1,n) rak[tmp[i]=i]=s[i]-‘a‘+1;
        radix_sort();
        for(int d=1,p=1;p<n;m=p,d<<=1){
            p=0;
            FOR(i,1,d) tmp[++p]=n-d+i;
            FOR(i,1,n) if(sa[i]>d) tmp[++p]=sa[i]-d;
            radix_sort();swap(rak,tmp);
            rak[sa[1]]=p=1;
            FOR(i,2,n) rak[sa[i]]=(tmp[sa[i]]==tmp[sa[i-1]] && tmp[sa[i]+d]==tmp[sa[i-1]+d])?p:++p;
        }
        int k=0;
        FOR(i,1,n){
            if(k) k--;
            for(int j=sa[rak[i]-1];s[i+k]==s[j+k];k++);
            h[rak[i]][0]=k;
        }
        logt[1]=0;FOR(i,2,n) logt[i]=logt[i>>1]+1;
        FOR(j,1,logt[n]+1) FOR(i,1,n-(1<<j)+1) h[i][j]=min(h[i][j-1],h[i+(1<<j-1)][j-1]);
    }
    int LCP(int x,int y){
        x=rak[x];y=rak[y];
        if(x>y) swap(x,y);
        x++;
        int k=logt[y-x+1];
        return min(h[x][k],h[y-(1<<k)+1][k]);
    }
}nor,rev;
int n;
char str[maxn];
ll ans,a[maxn],b[maxn];
int main(){
    for(int t=read();t;t--){
        scanf("%s",str+1);n=strlen(str+1);
        nor.build(str);
        for(int i=1,j=n;i<j;i++,j--) swap(str[i],str[j]);
        rev.build(str);
        MEM(a,0);MEM(b,0);ans=0;
        FOR(l,1,n/2){
            for(int i=l,j=l<<1;j<=n;i+=l,j+=l){
                int x=min(l,nor.LCP(i,j)),y=min(l-1,rev.LCP(n-i+2,n-j+2));
                if(x+y>=l){
                    a[j+x-(x+y-l+1)]++;a[j+x]--;
                    b[i-y+(x+y-l+1)]--;b[i-y]++;
                }
            }
        }
        FOR(i,1,n) a[i]+=a[i-1],b[i]+=b[i-1];
        FOR(i,1,n-1) ans+=a[i]*b[i+1];
        printf("%lld\n",ans);
    }
}