2017.10.8 NOIP模拟赛

题解 套题

目录

• 2017.10.8 NOIP模拟赛
  • 逗你玩
    • 思路
    • 代码
  • 简单题
    • 思路
    • 代码
  • 采矿
    • 思路
    • 代码

逗你玩

思路

• 考虑到可以走回头路，还可以停在原位，直接BFS一定会炸；
• 那么我们考虑什么样的状态是可以继续走的；
• 显然，若设$f(x,y,vis,rest)$为走到$(x,y)$处，访问状态为$vis$（可以压到int里），剩余能量为$rest$的最短时间，那么若当前状态小于之前的历史记录，则可以继续走，否则舍弃；
• 所以，这题就是个BFS加一些剪枝，复杂度较为玄学，但数量级不会超过$f$数组大小。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <queue>
#include <cstring>
using std::queue;
const int MAXN=5,all=(1<<9)-1;
int dirx[]={0,1,0,-1,0},diry[]={0,0,1,0,-1};
int G[MAXN][MAXN],id[MAXN][MAXN],his[MAXN][MAXN][1<<9][200];
struct state{
    int x,y,rest,tm,vis;
    state(){x=y=rest=tm=vis=0;}
};
inline bool inG(state &u){
    return 1<=u.x && u.x<=3 && 1<=u.y && u.y<=3;
}
inline bool jud(state &u){
    if(u.tm<his[u.x][u.y][u.vis][u.rest]){
        his[u.x][u.y][u.vis][u.rest]=u.tm;
        return true;
    }
    else return false;
}
inline int BFS(){
    static queue<state> que;
    memset(his,0x7f,sizeof(his));
    state u,v;
    u.x=1,u.y=1;
    u.rest=G[1][1];
    u.tm=1;
    u.vis=1;
    que.push(u);
    while(que.size()){
        u=que.front();
        que.pop();
        if(u.rest<0) break;
        for(int i=0;i<5;++i){
            v.x=u.x+dirx[i],v.y=u.y+diry[i];
            v.rest=u.rest+G[v.x][v.y];
            v.tm=u.tm+1;
            if(!inG(v) || v.rest<0) continue;
            v.vis=u.vis;
            v.vis|=id[v.x][v.y];
            if(jud(v)){
                if(v.vis==all) return v.tm;
                que.push(v);
            }
        }
    }
    return -1;
}
int main(){
#ifdef DEBUG
    setIO("a");
#endif
    for(int i=1,cnt=0;i<=3;++i){
        for(int j=1;j<=3;++j){
            read(G[i][j]);
            id[i][j]=1<<cnt++;
        }
    }
    write(BFS());
    return 0;
}

简单题

思路

• 这和之前考试的一道题一样，数据量还小了。。。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <queue>
#include <algorithm>
#include <cstring>
using std::queue;
using std::max;
const int MAXN=505,MAXM=3005;
int n,m,s1,t1,s2,t2,l1,l2;
int he[MAXN],dis[MAXN][MAXN];
struct line{int to,nex;}ed[MAXM<<1];
inline void addE(int u,int v){
    static int cnt=0;
    ed[++cnt]=(line){v,he[u]};
    he[u]=cnt;
}
inline void BFS(int s){
    static queue<int> que;
    memset(dis[s],-1,sizeof(dis[s]));
    int *d=dis[s];
    d[s]=0;
    que.push(s);
    int u;
    while(que.size()){
        u=que.front();
        que.pop();
        for(int i=he[u],v;i;i=ed[i].nex){
            v=ed[i].to;
            if(d[v]==-1){
                d[v]=d[u]+1;
                que.push(v);
            }
        }
    }
}
inline void cal_dis(){
    for(int i=1;i<=n;++i) BFS(i);
}
inline int solve(){
    if(dis[s1][t1]>l1 || dis[s2][t2]>l2 || dis[s1][t1]==-1 || dis[s2][t2]==-1)
        return -1;
    int ret=m-dis[s1][t1]-dis[s2][t2];
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(dis[s1][i]==-1 || dis[i][j]==-1 || dis[j][t1]==-1 || dis[s2][i]==-1 || dis[j][t2]==-1)
                continue;
            if(dis[s1][i]+dis[i][j]+dis[j][t1]<=l1 && dis[s2][i]+dis[i][j]+dis[j][t2]<=l2)
                ret=max(ret,m-dis[s1][i]-dis[s2][i]-dis[i][j]-dis[j][t1]-dis[j][t2]);
        }
        for(int j=1;j<=n;++j){
            if(dis[s1][j]==-1 || dis[i][j]==-1 || dis[i][t1]==-1 || dis[s2][i]==-1 || dis[j][t2]==-1)
                continue;
            if(dis[s1][j]+dis[j][i]+dis[i][t1]<=l1 && dis[s2][i]+dis[i][j]+dis[j][t2]<=l2)
                ret=max(ret,m-dis[s1][j]-dis[s2][i]-dis[i][j]-dis[i][t1]-dis[j][t2]);
        }
    }
    return ret;
}
int main(){
#ifdef DEBUG
    setIO("b");
#endif
    read(n),read(m);
    read(s1),read(t1),read(l1);
    read(s2),read(t2),read(l2);
    for(int i=1,u,v;i<=m;++i){
        read(u),read(v);
        addE(u,v),addE(v,u);
    }
    cal_dis();
    write(solve());
    return 0;
}

采矿

思路

• BZOJ原题。。。题目太长了吧。。。
• 考虑正常树形DP只能有40分，因为每次修改后都要去算一遍；
• 但是容易发现，$m$很小，每次枚举DP时复杂度很小，我们不妨试图维护DP的内容，即$subt(u,i)$以$u$为根的子树中布置$i$个人采矿的最大收益；
• 这是子树带修改的问题，很容易想到要用树剖；
• 但还可以在$v \to u$的链上的某一点布置人采矿，显然应布置到点权最大的地方（对于每种$i$），那么树剖也顺带维护链上点权最值即可；
• 树剖后，线段树维护子树恰好是个区间，那么DP很好转移，$subt(u,i)=\max_{v \in son(u)}\{subt(u,j)+subt(v,i-j)\}$，现在就是$subt(u,i)=\max\{subt(ls,j)+subt(rs,i-j)\}$；
• 虽然有些线段树节点$u$维护的区间不只是一个的子树的内容，但是查询时也不会访问，所以不用担心；
• 那么修改就是单点下去暴力修改好了，查询时也很简单，就是个DP，枚举选两边哪些；
• 代码长但是很容易明白，总复杂度有些卡，$O(m^2 n \log n+Cm^2 \log n)$。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <cstring>
#include <climits>
#include <algorithm>
using std::max;
using std::sort;
const int MAXN=20005,MAXM=55;
int n,m,A,B,Q;
int data[MAXN][MAXM],id[MAXN],subt[MAXM],edge[MAXM];
class segT{
#define ls (u<<1)
#define rs (ls|1)
    private:
        struct node{int subt[MAXM],edge[MAXM];}d[MAXN<<2];
        void upd(int u){
            for(int i=1;i<=m;++i){
                d[u].subt[i]=d[u].edge[i]=max(d[ls].edge[i],d[rs].edge[i]);
                for(int j=0;j<=i;++j)
                    d[u].subt[i]=max(d[u].subt[i],d[ls].subt[j]+d[rs].subt[i-j]);
            }
        }
        void build(int u,int l,int r){
            if(l==r){
                for(int i=1;i<=m;++i)
                    d[u].subt[i]=d[u].edge[i]=data[id[l]][i];
                return;
            }
            int mid=l+r>>1;
            build(ls,l,mid),build(rs,mid+1,r);
            upd(u);
        }
        void mdf(int u,int l,int r,int pos){
            if(l==r){
                for(int i=1;i<=m;++i)
                    d[u].subt[i]=d[u].edge[i]=data[id[l]][i];
                return;
            }
            int mid=l+r>>1;
            if(pos<=mid) mdf(ls,l,mid,pos);
            else mdf(rs,mid+1,r,pos);
            upd(u);
        }
        void qry_subt(int u,int l,int r,int lp,int rp){
            if(lp<=l && r<=rp){
                for(int i=m;i;--i){
                    for(int j=0;j<i;++j)
                        subt[i]=max(subt[i],subt[j]+d[u].subt[i-j]);
                }
                return;
            }
            int mid=l+r>>1;
            if(lp<=mid) qry_subt(ls,l,mid,lp,rp);
            if(rp>mid) qry_subt(rs,mid+1,r,lp,rp);
        }
        void qry_edge(int u,int l,int r,int lp,int rp){
            if(lp<=l && r<=rp){
                for(int i=1;i<=m;++i)
                    edge[i]=max(edge[i],d[u].edge[i]);
                return;
            }
            int mid=l+r>>1;
            if(lp<=mid) qry_edge(ls,l,mid,lp,rp);
            if(rp>mid) qry_edge(rs,mid+1,r,lp,rp);
        }
    public:
        void build(){build(1,1,n);}
        void qry_subt(int l,int r){qry_subt(1,1,n,l,r);}
        void qry_edge(int l,int r){qry_edge(1,1,n,l,r);}
        void mdf(int pos){mdf(1,1,n,pos);}
#undef ls
#undef rs
};
class TP{
    private:
        struct node{int he,hson,top,lpos,sz,fa,id;}d[MAXN];
        struct line{int to,nex;}ed[MAXN];
        segT T;
        void addE(int u,int v){
            static int cnt=0;
            ed[++cnt]=(line){v,d[u].he};
            d[u].he=cnt;
        }
        void DFS(int u){
            int fa=d[u].fa;
            d[u].sz=1;
            for(int i=d[u].he,v,&hson=d[u].hson;i;i=ed[i].nex){
                v=ed[i].to;
                DFS(v);
                if(d[v].sz>d[hson].sz) hson=v;
                d[u].sz+=d[v].sz;
            }
        }
        void link(int u){
            static int cnt=0;
            d[u].id=++cnt;
            id[cnt]=u;
            int fa=d[u].fa;
            d[u].top= d[fa].hson==u ? d[fa].top:u;
            int hson=d[u].hson;
            if(hson) link(hson);
            for(int i=d[u].he,v;i;i=ed[i].nex){
                v=ed[i].to;
                if(v!=hson) link(v);
            }
            d[u].lpos=cnt;
        }
    public:
        void init(){
            for(int i=2;i<=n;++i){
                read(d[i].fa);
                addE(d[i].fa,i);
            }
        }
        void build(){
            DFS(1);
            link(1);
            T.build();
        }
        void mdf(int u){T.mdf(d[u].id);}
        int qry(int u,int v){
            memset(subt,0,sizeof(subt));
            memset(edge,0,sizeof(edge));
            T.qry_subt(d[u].id,d[u].lpos);
            if(u!=v){
                u=d[u].fa;
                while(d[u].top!=d[v].top){
                    T.qry_edge(d[d[u].top].id,d[u].id);
                    u=d[d[u].top].fa;
                }
                T.qry_edge(d[v].id,d[u].id);
            }
            int ret=0;
            for(int i=0;i<=m;++i)
                ret=max(ret,subt[i]+edge[m-i]);
            return ret;
        }
}T;
inline int getint(){
    static const int X=1<<16,Y=INT_MAX;
    A=((A^B)+B/X+B*X)&Y;
    B=((A^B)+A/X+A*X)&Y;
    return (A^B)%Q;
}
inline void prod_data(int a[]){
    for(int i=1;i<=m;++i)
        a[i]=getint();
    sort(a+1,a+m+1);
}
int main(){
#ifdef DEBUG
    setIO("c");
#endif
    read(n),read(m);
    read(A),read(B),read(Q);
    T.init();
    for(int i=1;i<=n;++i)
        prod_data(data[i]);
    T.build();
    int C;
    read(C);
    for(int i=1,type,p,u,v;i<=C;++i){
        read(type);
        if(type==0){
            read(p);
            prod_data(data[p]);
            T.mdf(p);
        }
        else{
            read(u),read(v);
            write(T.qry(u,v),'\n');
        }
    }
    return 0;
}