BruceJay's Blog

NOI2014 解题报告

| Comments

To start with

感觉NOI无望,又被2014的题虐了。

DAY1

sleep

AC Algorithm

NOI经典试机题。按二进制位从高到低依次考虑每一位的取值情况。在保证最终伤害尽量高的前提下,还应同时使初始攻击力尽量低。

Code

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

const int N = 100100;
struct node{char s[5]; int x;}a[N];
int n,m,ans=0,now=0;

int main()
{
    freopen("sleep.in","r",stdin);
    freopen("sleep.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s%d",a[i].s,&a[i].x);
    for(int i=30;i>=0;i--){
        int t0=0,t1=1,t;
        for(int j=1;j<=n;j++){
            t=(a[j].x>>i)&1;
            if(a[j].s[0]=='A') t0&=t,t1&=t;
            else if(a[j].s[0]=='X') t0^=t,t1^=t;
            else t0|=t,t1|=t;
        }
        if(t0) ans+=(1<<i);
        else if(t1 && now+(1<<i)<=m){
            now+=(1<<i),ans+=(1<<i);
        }
    }
    printf("%d",ans);
    return 0;
}

forest

Force1

枚举路径上a值的最大值amax,然后对ai<=amax的边做关于b值的MST,1~n的“瓶颈”就是bmax,用amax+bmax更新答案。
期望得分30~50分。

AC Algorithm

延续Force1的思路,还是枚举amax,然后用LCT维护ai<=amax的边的关于b值的MST。
将边按a值排序,依次加入,对于边(u,v)的大致操作如下:
1.查询(u,v)是否相连;
2.若不相连,则加入(u,v);
3.若相连,查询当前MST上路径(u,v)上的最大b值bmax,b(u,v)<bmax,则割去b=bmax的边,加入(u,v);
4.若1与n已经相连,当前MST上路径(1,n)上的最大b值bmax查询,用a(u,v)+bmax更新答案。

Code

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

const int N = 50100;
const int M = 100100;
const int INF = 0x3f3f3f3f;
struct Edge{int u,v,x,y;}e[M];
bool operator<(const Edge& e1,const Edge& e2)
{return e1.x<e2.x;}
int tr[N+M][2],fa[N+M];
bool rev[N+M],rt[N+M];
int val[N+M],mx[N+M],st[N+M];
int n,m,ans=INF;

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 Pushup(int x)
{
    int l=tr[x][0],r=tr[x][1];
    mx[x]=x;
    if(val[mx[l]]>val[mx[x]]) mx[x]=mx[l];
    if(val[mx[r]]>val[mx[x]]) mx[x]=mx[r];
}

void Pushdown(int x)
{
    int l=tr[x][0],r=tr[x][1];
    if(rev[x]){
        rev[x]^=1; rev[l]^=1; rev[r]^=1;
        swap(tr[x][0],tr[x][1]);
    }
}

void Rotate(int x)
{
    int y=fa[x],z=fa[y];
    int t=tr[y][0]==x?0:1;
    if(rt[y]) rt[x]=true,rt[y]=false;
    else{
        if(tr[z][0]==y) tr[z][0]=x;
        else tr[z][1]=x;
    }
    fa[x]=z; fa[y]=x; fa[tr[x][t^1]]=y;
    tr[y][t]=tr[x][t^1]; tr[x][t^1]=y;
    Pushup(y); Pushup(x);
}

void Splay(int x)
{
    int top=0;
    for(int i=x;i;i=fa[i]) st[++top]=i;
    for(int i=top;i;i--) Pushdown(st[i]);
    while(!rt[x]){
        int y=fa[x];
        if(!rt[y]){
            int z=fa[y];
            if(tr[y][0]==x^tr[z][0]==y) Rotate(x);
            else Rotate(y);
        }
        Rotate(x);
    }
}

void Access(int x)
{
    int t=0;
    for(;x;x=fa[x]){
        Splay(x);
        rt[tr[x][1]]=true;
        rt[tr[x][1]=t]=false;
        Pushup(x); t=x;
    }
}

void Reverse(int x)
{
    Access(x); Splay(x); rev[x]^=1;
}

void Link(int x,int y)
{
    Reverse(x); Access(y); Splay(y);
    tr[y][1]=x; fa[x]=y; rt[x]=false;
    Pushup(y);
}

void Cut(int x,int y)
{
    Reverse(x); Access(y); Splay(y);
    tr[y][0]=fa[x]=0; rt[x]=true;
    Pushup(y);
}

int Query(int x,int y)
{
    Reverse(x); Access(y); Splay(y);
    return mx[y];
}

int Find(int x)
{
    Access(x); Splay(x);
    for(;tr[x][0];x=tr[x][0]);
    return x;
}

int main()
{
    int u,v,x,y;
    freopen("forest.in","r",stdin);
    freopen("forest.out","w",stdout);
    n=read(); m=read();
    for(int i=1;i<=m;i++){
        u=read(); v=read(); x=read(); y=read();
        e[i]=(Edge){u,v,x,y};
    }
    sort(e+1,e+m+1);
    for(int i=1;i<=n+m;i++) rt[i]=true;
    for(int i=1;i<=m;i++){
        int u=e[i].u,v=e[i].v;
        if(Find(u)==Find(v)){
            int tmp=Query(u,v);
            if(e[i].y<val[tmp]){
                Cut(tmp,e[tmp-n].u);
                Cut(tmp,e[tmp-n].v);
            }
            else continue;
        }
        mx[i+n]=i+n; val[i+n]=e[i].y;
        Link(i+n,e[i].u); Link(i+n,e[i].v);
        if(Find(1)==Find(n)) ans=min(ans,e[i].x+val[Query(1,n)]);
    }
    if(ans==INF) puts("-1");
    else printf("%d",ans);
    return 0;
}

game

一道提答,表示懵逼。

DAY2

zoo

AC Algorithm

很明显要用到KMP。
KMP求出next数组之外,求出一个cnt数组,cnt[i]表示前缀1~i-1中有cnt[i]个是前缀i的后缀。所以有:cnt[i]=cnt[next[i]]+1。
再做一遍类似KMP的东西,记录下Next数组,Next[i]表示在长度限制(Next[i]*2<=i)的情况下,最长匹配长度。题目中的num数组就可以求出来了:num[i]=num[Next[i]]+1。

Code

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

typedef long long ll;
const int N = 1000100;
const int mod = 1e9+7;
char s[N]; int fail[N];
ll num[N];
int T,n; ll ans;

int main()
{
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
    scanf("%d",&T);
    while(T--){
        scanf("%s",s+1);
        n=strlen(s+1);
        num[1]=1;
        for(int i=2,j=0;i<=n;i++){
            while(j && s[i]!=s[j+1]) j=fail[j];
            if(s[i]==s[j+1]) j++;
            fail[i]=j; num[i]=num[j]+1;
        }
        ans=1;
        for(int i=2,j=0;i<=n;i++){
            while(j && s[i]!=s[j+1]) j=fail[j];
            if(s[i]==s[j+1]) j++;
            while(j && (j<<1)>i) j=fail[j];
            ans=ans*(num[j]+1)%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

random

AC Algorithm

首先要看懂题目,然后就发现,那一系列的变换其实可以直接模拟。
然后贪心求最佳路径。依次枚举1~n*m,每次找到当前枚举的i所在的位置,然后判断其是否可行,如果可行,将其输出,再将该位置左下和右上方向的格子删去(标记为不可行)。
对每一行来考虑,每次删去的要么是从最左边到中间某个点,要么是中间某个点到最右边,所以第i行的可取范围可以用[Li,Ri]来表示,每次删去格子时,O(n)去更新所有的Li和Ri。

Code

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

typedef long long ll;
const int N = 5010;
int L[N],R[N],a[N*N],pos[N*N];
ll A,B,C,D,X; int n,m,q,u,v,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;
}

inline ll f(int x)
{
    return (A*x%D*x%D+B*x%D+C)%D;
}

int main()
{
    freopen("random.in","r",stdin);
    freopen("random.out","w",stdout);
    X=read();
    A=read(); B=read(); C=read(); D=read();
    n=read(); m=read(); q=read();
    for(int i=1;i<=n*m;i++) a[i]=i;
    for(int i=1;i<=n*m;i++){
        X=f(X); swap(a[i],a[X%i+1]);
    }
    for(int i=1;i<=q;i++){
        u=read(); v=read(); swap(a[u],a[v]);
    }
    for(int i=1;i<=n*m;i++) pos[a[i]]=i;
    for(int i=1;i<=n;i++) L[i]=1,R[i]=m;
    for(int i=1;i<=n*m;i++){
        int x=(pos[i]-1)/m+1,y=(pos[i]-1)%m+1;
        if(L[x]>y || R[x]<y) continue;
        cnt++;
        if(cnt!=n+m-1) printf("%d ",i);
        else printf("%d\n",i);
        for(int j=1;j<x;j++) R[j]=min(R[j],y);
        for(int j=x+1;j<=n;j++) L[j]=max(L[j],y);
    }
    return 0;
}

ticket

Force1

简单粗暴。对每个点,依次考虑可以走到的祖先。复杂度大约是O(n^2)的。
期望得分30分。

Force2

对于一条链(就当这条链是1,2,3....,n),很显然可以推出有关斜率的式子:
f[i]=min{f[j]-dis[j]*a[i]}+dis[i]*a[i]+b[i],j<i且dis[i]-limit[i]<=dis[j]
如果没有距离限制可以直接斜率DP,维护一个关于点集(dis[i],f[i])的凸包,在凸包上二分求出每个点的答案。
如果有距离限制,用CDQ分治可以解决问题。
期望得分40分。

Force3

Force1+Force2。
期望得分50分。

AC Algorithm1

Force2中提到了CDQ分治,准确点说是关于序列的CDQ分治,现在就考虑如何将CDQ分治的思想用到树上。
考虑点分治。对于每一个分治块,这么处理:
1.求出分治块重心,通过重心将分治块分为几个部分;
2.对分治块根节点所在的部分和重心一起分治,求出这一部分所有点和重心的答案。
3.用CDQ分治的思想,对将2中求出的点一次插入凸包,同时对分治块中其他点,在凸包上二分更新答案。
4.对每个部分继续分治(除了2中的那一部分)。
这样可以达到O(nlog^2n)的复杂度。

AC Algorithm2

和zzd交流时听他说了一个树剖的做法。
线段树维护树剖序列每个区间的凸包。
对于每一个点,能走到的点在树上就是一条链,然后用树剖可以将这条链分为log个部分,在线段树上就是log^2个区间,将这些区间的凸包合并,然后在凸包上二分可以求出答案。
复杂度为O(nlog^3n)。没点分治快,而且应该比点分治难打(我也没打)。

Code

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

typedef long long ll;
const int N = 200100;
const int INF = 0x3f3f3f3f;
ll a[N],b[N],dis[N],f[N],limit[N];
int fa[N],head[N],nxt[N];
int sz[N],mx[N],q[N],st[N];
double sl[N]; bool vis[N];
int n,T,cnt;

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

inline double slop(int x,int y)
{
    return (double)(f[x]-f[y])/(dis[x]-dis[y]);
}

inline bool cmp(int x,int y)
{
    return dis[x]-limit[x]>dis[y]-limit[y];
}

void Find(int u,int all,int& G)
{
    sz[u]=1; mx[u]=0;
    for(int v=head[u];v;v=nxt[v])
        if(!vis[v]){
            Find(v,all,G); sz[u]+=sz[v];
            mx[u]=max(mx[u],sz[v]);
        }
    mx[u]=max(mx[u],all-sz[u]);
    if(mx[u]<=mx[G]) G=u;
}

void Get(int u)
{
    q[++cnt]=u;
    for(int v=head[u];v;v=nxt[v])
        if(!vis[v]) Get(v);
}

void Calc(int u,int top)
{
    int l=1,r=top,res=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(sl[mid]>=a[u]) l=mid+1,res=mid;
        else r=mid-1;
    }
    int v=st[res];
    f[u]=min(f[u],f[v]+a[u]*(dis[u]-dis[v])+b[u]);
}

void Solve(int rt,int all)
{
    int G=0;
    if(all==1) return;
    Find(rt,all,G);
    for(int v=head[G];v;v=nxt[v]) vis[v]=true;
    Solve(rt,all-sz[G]+1);
    cnt=0;
    for(int v=head[G];v;v=nxt[v]) Get(v);
    sort(q+1,q+cnt+1,cmp);
    int top=0;
    for(int i=1,v=G;i<=cnt;i++){
        int u=q[i];
        for(;v!=fa[rt] && dis[u]-dis[v]<=limit[u];v=fa[v]){
            while(top>1 && slop(v,st[top])>=slop(st[top],st[top-1])) top--;
            st[++top]=v;
            if(top!=1) sl[top]=slop(st[top],st[top-1]);
            else sl[top]=1e15;
        }
        if(top) Calc(u,top);
    }
    for(int v=head[G];v;v=nxt[v]) Solve(v,sz[v]);
}

int main()
{
    freopen("ticket.in","r",stdin);
    freopen("ticket.out","w",stdout);
    n=read(); T=read();
    for(int i=2;i<=n;i++){
        fa[i]=read(); dis[i]=dis[fa[i]]+read();
        nxt[i]=head[fa[i]]; head[fa[i]]=i;
        a[i]=read(); b[i]=read();
        limit[i]=read();
    }
    memset(f,INF,sizeof(f)); f[1]=0;
    mx[0]=n; Solve(1,n);
    for(int i=2;i<=n;i++) printf("%lld\n",f[i]);
    return 0;
}

Comments

comments powered by Disqus