BruceJay's Blog

NOI2015 解题报告

| Comments

To start with

正在准备NOI2016的Bruce刚刚被2015的题虐了一发。

DAY1

prog

AC Algorithm

对所有的变量下标进行离散化,然后并查集处理所有相等关系,之后对所有不等关系进行判断,如果属于同一连通块,则说明该关系无法满足。

Code

#include <cstdio>
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1000100;
struct node{int x,y,opt;}a[N];
int f[N<<1],hash[N<<1];
set<int> S;
int T,n,m;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

inline int Find(int x){return f[x]==x?f[x]:f[x]=Find(f[x]);}

int main()
{
    freopen("prog.in","r",stdin);
    freopen("prog.out","w",stdout);
    T=read();
    while(T--){
        S.clear(); m=read(); n=0;
        for(int i=1;i<=m;i++){
            a[i].x=read(); a[i].y=read(); a[i].opt=read();
            if(!S.count(a[i].x)) S.insert(a[i].x),hash[++n]=a[i].x;
            if(!S.count(a[i].y)) S.insert(a[i].y),hash[++n]=a[i].y;
        }
        sort(hash+1,hash+n+1);
        for(int i=1;i<=m;i++){
            a[i].x=lower_bound(hash+1,hash+n+1,a[i].x)-hash;
            a[i].y=lower_bound(hash+1,hash+n+1,a[i].y)-hash;
        }
        for(int i=1;i<=n;i++) f[i]=i;
        for(int i=1;i<=m;i++) if(a[i].opt){
            if(Find(a[i].x)!=Find(a[i].y)) f[f[a[i].x]]=f[a[i].y];
        }
        bool flag=true;
        for(int i=1;i<=m;i++) if(!a[i].opt){
            if(Find(a[i].x)==Find(a[i].y)) flag=false;
        }
        if(flag) puts("YES");
        else puts("NO");
    }
    return 0;
}

manager

AC Algorithm

树链剖分,剖分后可以得到一个与重链有关的DFS序,线段树维护DFS序列区间“1”的个数。对于install x,将x到根的路径全部赋为“1”;对于uninstall x,将x的子树全部赋为“0”(子树在DFS序列上必然为连续一段)。每次操作完计算操作前与操作后整棵树(线段树的根节点)“1”的个数的差即可。

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100100;
struct Edge{int v,nxt;}e[N];
int head[N],L[N],R[N];
int fa[N],sz[N],top[N];
int tag[N<<2],sum[N<<2];
int n,m,cnt=0,time_block=0;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

void Addedge(int u,int v)
{
    e[++cnt]=(Edge){v,head[u]}; head[u]=cnt;
}

int Dfs(int u)
{
    sz[u]=1;
    for(int i=head[u];i;i=e[i].nxt)
        sz[u]+=Dfs(e[i].v);
    return sz[u];
}

void Dfs2(int u,int chain)
{
    int k=0; top[u]=chain;
    L[u]=++time_block;
    for(int i=head[u];i;i=e[i].nxt)
        if(sz[e[i].v]>sz[k]) k=e[i].v;
    if(k) Dfs2(k,chain);
    for(int i=head[u];i;i=e[i].nxt)
        if(e[i].v!=k) Dfs2(e[i].v,e[i].v);
    R[u]=time_block;
}

void Tag(int k,int l,int r,int x){tag[k]=x;sum[k]=(r-l+1)*x;}

void Pushup(int k){sum[k]=sum[k<<1]+sum[k<<1|1];}

void Pushdown(int k,int l,int r)
{
    int mid=(l+r)>>1;
    Tag(k<<1,l,mid,tag[k]);
    Tag(k<<1|1,mid+1,r,tag[k]);
    tag[k]=-1;
}

void Update(int k,int l,int r,int x,int y,int z)
{
    if(l==x && r==y){
        Tag(k,l,r,z);
        return;
    }
    int mid=(l+r)>>1;
    if(tag[k]!=-1) Pushdown(k,l,r);
    if(y<=mid) Update(k<<1,l,mid,x,y,z);
    else if(x>mid) Update(k<<1|1,mid+1,r,x,y,z);
    else Update(k<<1,l,mid,x,mid,z),Update(k<<1|1,mid+1,r,mid+1,y,z);
    Pushup(k);
}

void Modify(int x)
{
    for(;x;x=fa[top[x]])
        Update(1,1,n,L[top[x]],L[x],1);
}

int main()
{
    int x; char s[10];
    freopen("manager.in","r",stdin);
    freopen("manager.out","w",stdout);
    n=read();
    for(int i=2;i<=n;i++) fa[i]=read()+1;
    for(int i=2;i<=n;i++) Addedge(fa[i],i);
    Dfs(1); Dfs2(1,1);
    m=read();
    memset(tag,-1,sizeof(tag));
    for(int i=1;i<=m;i++){
        scanf("%s",s); x=read()+1;
        int tmp=sum[1];
        if(s[0]=='i'){
            Modify(x);
            printf("%d\n",sum[1]-tmp);
        }
        else{
            Update(1,1,n,L[x],R[x],0);
            printf("%d\n",tmp-sum[1]);
        }
    }
    return 0;
}

dinner

Force1

搜索打表。
期望得分:20~30。

Force2

对每个质因子分别考虑。30以内的质因子只有10个,考虑状压。
f[i][S][T]表示美味度为2~i的寿司,小G品尝的寿司包含质因子的状态为S(2进制),小W品尝的寿司包含质因子的状态为T的方案数。a[i]表示i所包含质因子的状态。转移方程:
f[i][S|a[i]][T]+=f[i-1][S][T];
f[i][S][T|a[i]]+=f[i-1][S][T]。
其实这是一个背包模型。对S和T倒序循环可以将空间优化至二维。
期望得分:30。

AC Algorithm

<=sqrt(n)的质数最多9个,每个数最多含有一个>sqrt(n)的质数。
所以对小质数进行状压,大质数再逐一考虑。
对小质数的考虑方法类似Force2,先处理不含有>sqrt(n)的质因子的数。
之后逐一考虑大质数,转移时枚举包含大质数p的所有整数x,考虑将其分给小G或小W(每个大质数最多分给一个人)。转移方程:
分给小G:g[0][S|a[x]][T]+=g[0][S][T]+f[S][T];
分给小W:g[1][S][T|a[x]]+=g[1][S][T]+f[S][T];
累加:f[S][T]+=(g[0][S][T]+g[1][S][T])。
同理,这是一个背包模型,对S和T倒序循环。

Code

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 510;
const int SIZE = 256;
ll f[SIZE][SIZE];
ll g[2][SIZE][SIZE];
int a[N]; bool b[N]; bool del[N];
int prime[N]; int near[N];
int n,cnt=0,cnt1=0,t; ll ans=0,mod;

void Linear_Shaker()
{
    for(int i=2;i<=n;i++){
        if(!del[i]) prime[++cnt]=i,near[i]=cnt;
        for(int j=1;j<=cnt && i*prime[j]<=n;j++){
            del[i*prime[j]]=true;
            near[i*prime[j]]=j;
            if(i%prime[j]==0) break;
        }
    }
}

void Calc(int x)
{
    for(int i=x;i!=1;i/=prime[near[i]]){
        if(prime[near[i]]<=t)
            a[x]|=(1<<(near[i]-1));
        else b[x]=true;
    }
}

void DP(int x)
{
    memset(g,0,sizeof(g));
    for(int i=x;i<=n;i+=x)
    for(int S=(1<<cnt1)-1;S>=0;S--)
    for(int T=(1<<cnt1)-1;T>=0;T--){
        (g[0][S|a[i]][T]+=g[0][S][T]+f[S][T])%=mod;
        (g[1][S][T|a[i]]+=g[1][S][T]+f[S][T])%=mod;
    }
    for(int S=0;S<(1<<cnt1);S++)
    for(int T=0;T<(1<<cnt1);T++)
        if(!(S&T)) (f[S][T]+=g[0][S][T]+g[1][S][T])%=mod;
}

int main()
{
    freopen("dinner.in","r",stdin);
    freopen("dinner.out","w",stdout);
    scanf("%d%lld",&n,&mod);
    t=sqrt(n);
    Linear_Shaker();
    for(int i=2;i<=n;i++) Calc(i);
    for(int i=1;i<=cnt;i++) if(prime[i]<=t) cnt1++;
    f[0][0]=1;
    for(int i=2;i<=n;i++) if(!b[i]){
    for(int S=(1<<cnt1)-1;S>=0;S--)
    for(int T=(1<<cnt1)-1;T>=0;T--){
        (f[S|a[i]][T]+=f[S][T])%=mod;
        (f[S][T|a[i]]+=f[S][T])%=mod;
    }
    }
    for(int i=cnt1+1;i<=cnt;i++)
        DP(prime[i]);
    for(int S=0;S<(1<<cnt1);S++)
    for(int T=0;T<(1<<cnt1);T++)
        if(!(S&T)) (ans+=f[S][T])%=mod;
    printf("%lld",ans);
    return 0;
}

DAY2

epic

AC Algorithm

N叉Huffman树。第一问类似合并果子。第二问只需在合并时优先合并深度较低的子树。

Code

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
struct node{ll x;int y;};
bool operator<(const node& a1,const node& a2)
{return a1.x==a2.x?a1.y>a2.y:a1.x>a2.x;}
priority_queue<node> q;
int n,k,ans=0; ll tot=0;

inline ll read()
{
    ll t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

int main()
{
    ll x; int y;
    freopen("epic.in","r",stdin);
    freopen("epic.out","w",stdout);
    n=read(); k=read();
    for(int i=1;i<=n;i++){
        x=read(); q.push((node){x,0});
    }
    if(k!=2) for(;n%(k-1)!=1;n++) q.push((node){0,0});
    for(int i=n;i!=1;i-=(k-1)){
        x=y=0;
        for(int j=1;j<=k;j++){
            node u=q.top(); q.pop();
            x+=u.x; y=max(y,u.y+1);
        }
        tot+=x; ans=max(ans,y);
        q.push((node){x,y});
    }
    printf("%lld\n%d",tot,ans);
    return 0;
}

savour

Force1

对后缀建立一个Trie树,在Trie树上进行统计。
期望得分:40~50。

Force2

字符串hash。
期望得分:0~50。

AC Algorithm1

后缀树,具体我也不知道怎么做。

AC Algorithm2

其实后缀数组+并查集的做法可以取代后缀树。
求出height数组,然后从大到小依次枚举height[i],将排名为i与排名为i-1的后缀并查集合并。并查集同时维护连通块内权值最大最小值和方案数。

AC Algorithm3

机房其他同学用到了高端的后缀自动机。
将字符串反过来建SAM,后缀就成了前缀。求两个后缀的相似度,就相当于求反串两个前缀的lcp。求lcp相当于求SAM的parent树上的lca。
所以问题就转化为在parent树上DP。

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 300100;
char s[N]; int c[N],t1[N],t2[N];
int a[N],sa[N],rk[N],h[N];
int f[N],sz[N],mx[N],mn[N];
int q[N]; ll ans[N],cnt[N];
bool cmp(int x,int y){return h[x]>h[y];}
int n; ll ANS=-3e18,CNT=0;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

void da(int m)
{
    int* x=t1; int* y=t2;
    for(int i=1;i<=m;i++) c[i]=0;
    for(int i=1;i<=n;i++) c[x[i]=s[i]]++;
    for(int i=1;i<=m;i++) c[i]+=c[i-1];
    for(int i=n;i;i--) sa[c[x[i]]--]=i;
    for(int k=1;k<=n;k<<=1){
        int p=0;
        for(int i=n-k+1;i<=n;i++) y[++p]=i;
        for(int i=1;i<=n;i++) if(sa[i]>k) y[++p]=sa[i]-k;
        for(int i=1;i<=m;i++) c[i]=0;
        for(int i=1;i<=n;i++) c[x[y[i]]]++;
        for(int i=1;i<=m;i++) c[i]+=c[i-1];
        for(int i=n;i;i--) sa[c[x[y[i]]]--]=y[i];
        p=1; swap(x,y); x[sa[1]]=1;
        for(int i=2;i<=n;i++)
            x[sa[i]] = y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k] ? p:++p;
        if(p>=n) break; m=p;
    }
}

void getheight()
{
    for(int i=1;i<=n;i++) rk[sa[i]]=i;
    int k=0;
    for(int i=1;i<=n;i++){
        if(k) k--;
        int j=sa[rk[i]-1];
        if(!j) continue;
        while(s[i+k]==s[j+k]) k++;
        h[rk[i]]=k;
    }
}

inline int Find(int x){return f[x]==x?f[x]:f[x]=Find(f[x]);}

inline void Merge(int u,int v)
{
    u=Find(u); v=Find(v);
    if(u==v) return;
    CNT+=(ll)sz[u]*sz[v];
    ANS=max(ANS,(ll)mx[u]*mx[v]);
    ANS=max(ANS,(ll)mn[u]*mn[v]);
    sz[u]+=sz[v]; f[v]=u;
    mx[u]=max(mx[u],mx[v]);
    mn[u]=min(mn[u],mn[v]);
}

int main()
{
    freopen("savour.in","r",stdin);
    freopen("savour.out","w",stdout);
    n=read(); scanf("%s",s+1);
    da(256);
    getheight();
    for(int i=1;i<=n;i++) a[rk[i]]=read();
    for(int i=1;i<=n;i++) q[i]=i;
    sort(q+1,q+n+1,cmp);
    for(int i=1;i<=n;i++) f[i]=i,sz[i]=1,mx[i]=mn[i]=a[i];
    for(int i=1;i<=n;i++){
        if(q[i]==1) continue;
        int u=q[i],v=q[i]-1;
        Merge(u,v);
        ans[h[q[i]]]=ANS;
        cnt[h[q[i]]]=CNT;
    }
    for(int i=0;i<n;i++){
        printf("%lld ",cnt[i]);
        if(cnt[i]) printf("%lld\n",ans[i]);
        else puts("0");
    }
    return 0;
}

farm

Force1

对于第一问,考虑5个方向离每个点最近的点,可以建出一张图。其实这张图是一张分层图。
层与层之间的转移显然,对于不同层的点i和j,如果j能转移到i,则可以用f[j]+1去更新f[i]。
层内的转移稍微复杂,对于同一层的点i和j,如果从j点进入该层,i点离开。若ji,则最优解一定是j到右端再到i。转移方程:
f[i]=max(f[j]+tot-i,i>j,f[j]+i-1,i<j)
这个其实可以用前后缀最值优化,所以单次转移的复杂度其实是O(1)。
期望得分:20。

Force2

对于第二问,需要统计第一问的方案。
为了避免同层点的相互影响,对每一个点,同时记录其从同层点与不同层点转移来的最大值,以及最大值的来源。同层点转移同Force1提到的方案,不同层点直接走。
期望得分:40。

AC Algorithm

有下界的网络流,我也没打。

Comments

comments powered by Disqus