2017.10.21 NOIP模拟赛

题解 套题

目录

• 2017.10.21 NOIP模拟赛
  • 最长不下降子序列
    • 思路
    • 代码
  • 完全背包问题
    • 思路
    • 代码
  • 最近公共祖先
    • 思路
    • 代码

最长不下降子序列

思路

• $D$很小，显然要求循环节搞事，但是只求出一个是不行的；
• 我们考虑，由于不下降子序列结尾的值有后效性，我们需要补齐一部分循环节；
• 设循环部分长$len$；
• 考虑循环节中元素互异，我们只能是在非循环部分选一些，在循环部分最多从$len$个循环中每一个选一个，之后再剩下的循环每个选一个和之前不下降子序列末尾值相同的；
• 那么我们只需要构造一个序列：不循环部分、$len$个循环节、余下的一个不完整的循环，求最长不下降子序列（对于有些，可以加上余下的循环个数）。
• 复杂度就是$O(D^2 \log D)$。

代码

#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 <algorithm>
#include <cstring>
using std::max;
using std::min;
using std::upper_bound;
const int MAXN=350;
int t,A,B,C,D,len,last,first;
int a[MAXN*MAXN],pos[MAXN];
long long n;
inline void prod_seq(){
    a[1]=t;
    pos[t]=1;
    for(int i=2;;++i){
        t=(A*t*t%D+B*t%D+C)%D;
        if(pos[t]){
            first=pos[t];
            last=t;
            len=i-1;
            return;
        }
        pos[t]=i;
        a[i]=t;
    }
}
inline long long DP(){
    static int dp[MAXN*MAXN];
    int nocir=first-1;
    int cir=len-nocir;
    int pre=len;
    len+=cir*(cir-1)-nocir;
    long long now=nocir+len+(n-len-nocir)%len;
    if(now>n) now=n;
    for(int i=pre+1;i<=now;++i)
        a[i]=a[i-cir];
    long long rest= (n-len-nocir)/len>0 ? (n-len-nocir)/len:0;
    rest*=cir;
    memset(dp,0x7f,sizeof(dp));
    long long ret=0,tmp;
    for(int i=1;i<=now;++i){
        tmp=upper_bound(dp+1,dp+now+1,a[i])-dp;
        dp[tmp]=min(dp[tmp],a[i]);
        if(i>nocir) tmp+=rest;
        ret=max(ret,tmp);
    }
    return ret;
}
int main(){
    setIO("lis");
    read(n);
    read(t),read(A),read(B),read(C),read(D);
    prod_seq();
    write(DP());
    return 0;
}

完全背包问题

思路

• 这种题的套路似乎就是取模然后用最短路进行有循环的DP；
• 先考虑$v_{min} \geq l$的特殊情况：
  
  1. 此时，可行的$w_{max} \leq c \times v_{max}$；
  2. 我们直接DP即可，设$dp(i)$为装满容量为$i$的背包的最少物品个数；
  3. 则，$dp(i)=\min_{v_j \leq i}\{dp(i-v_j)+1\}$；
  4. 直接递推复杂度有些卡，这是因为有很多状态并不足够优来更新其它状态，而且有很多不可行状态；
  5. 但是，可以发现这个是个最短路（起点为$0$，边权都为$1$），我们用BFS就可以高效求出了。
• 再考虑$v_{min}<l$的情况：
  
  1. 如果$w$可行，$w+k \times v_i$都可行；
  2. 我们将其放到模$v_{min}$意义下，也就是若$w' \bmod v_{min}$可行，并且$w' \leq w$，则$w$可行；
  3. 所以DP方程就是（用了$i$个大物品，总体积为$w,w \bmod v_{min}=j$的最小$w$）：
     $$dp(i,j)=\min_{k=1}^n\{dp(i-[v_k \geq l],(w-v_k)\bmod v_{min})+v_k\}$$
  4. 这个DP显然是环形的，我们考虑用最短路（这种拓扑性质的图SPFA常数会小一些）。

代码

#include <cstdio>
#include <algorithm>
#include <bitset>
#include <cstring>
#include <queue>
using std::sort;
using std::min;
using std::queue;
const int MAXN=55;
int n,l,c;
long long w[MAXN];
namespace solve1{
    const int MAXW=3000005;
    int dp[MAXW];
    inline void DP(){
        static queue<int> que;
        memset(dp,0x7f,sizeof(dp));
        dp[0]=0;
        que.push(0);
        int u,v;
        while(que.size()){
            u=que.front();
            que.pop();
            if(dp[u]>=c) continue;
            for(int i=1,d;i<=n;++i){
                v=u+w[i],d=dp[u]+1;
                if(dp[v]>d){
                    dp[v]=d;
                    que.push(v);
                }
            }
        }
    }
    inline bool jud(long long v){return v<=MAXW && dp[v]<=c;}
}
namespace solve2{
    const int MAXC=35,MAXW=20005;
    long long dp[MAXC][MAXW];
    struct node{
        int c;
        long long w;
    };
    inline void DP(){
        static bool inQ[MAXC][MAXW];
        static queue<node> que;
        memset(dp,0x7f,sizeof(dp));
        dp[0][0]=0;
        que.push((node){0,0});
        inQ[0][0]=true;
        node u,v;
        while(que.size()){
            u=que.front();
            que.pop();
            inQ[u.c][u.w%w[1]]=false;
            for(int i=1,d;i<=n;++i){
                v.w=u.w+w[i];
                v.c=u.c;
                if(w[i]>=l) ++v.c;
                if(v.c>c) continue;
                else if(dp[v.c][v.w%w[1]]>v.w){
                    dp[v.c][v.w%w[1]]=v.w;
                    if(!inQ[v.c][v.w%w[1]]){
                        que.push(v);
                        inQ[v.c][v.w%w[1]]=true;
                    }
                }
            }
        }
        for(int i=1;i<=c;++i){
            for(int j=0;j<w[1];++j)
                dp[i][j]=min(dp[i][j],dp[i-1][j]);
        }
    }
    inline bool jud(long long v){return dp[c][v%w[1]]<=v;}
}
int main(){
    freopen("bag.in","r",stdin);
    freopen("bag.out","w",stdout);
    int m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%lld",&w[i]);
    scanf("%d%d",&l,&c);
    sort(w+1,w+n+1);
    bool (*jud)(long long);
    if(w[1]>=l){
        solve1::DP();
        jud=solve1::jud;
    }
    else{
        solve2::DP();
        jud=solve2::jud;
    }
    long long v;
    for(int i=1;i<=m;++i){
        scanf("%lld",&v);
        if(jud(v)) puts("Yes");
        else puts("No");
    }
    return 0;
}

最近公共祖先

思路

• 考虑到一个点被染黑会有什么影响，显然，其子树所有点的答案都可以用该点点权更新，我们将树用DFS序在线段树上维护即可；
• 设该点为$u$，其父亲为$fa$，则$subt(fa)-subt(u)$这部分点可以用$w(fa)$更新；
• 继续向上跳，每次如是更新；
• 但是每次这样肯定会T，不过考虑有些情况是不需要重复更新的；
• 如果有个标记$mdf(u)$，那么当用$fa$更新完时，如果发现$mdf(fa)$被标记了，那么说明从$fa$向上这条链被从$fa$这个方向向上更新过，就可以结束了；
• 为什么是更新$fa$后再判断，因为有可能$fa$被标记过，但是是从$fa$另一个儿子上来标记的，更新的点和这次不同，不这样会少更新；
• 这样均摊下来，每个点被更新了常数次（貌似是两次），复杂度就是$O((n+m)\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 <algorithm>
using std::max;
const int MAXN=100005;
int n;
class segT{
    private:
        struct node{int ls,rs,l,r,max;}d[MAXN<<2];
        int new_nd(){
            static int cnt=1;
            return ++cnt;
        }
        void push_d(int u){
            int ls=d[u].ls,rs=d[u].rs;
            int &tag=d[u].max;
            d[ls].max=max(d[ls].max,tag);
            d[rs].max=max(d[rs].max,tag);
        }
        void mdf(int u,int lp,int rp,int x){
            if(lp<=d[u].l && d[u].r<=rp){
                d[u].max=max(d[u].max,x);
                return;
            }
            push_d(u);
            int mid=d[u].l+d[u].r>>1;
            if(lp<=mid) mdf(d[u].ls,lp,rp,x);
            if(rp>mid) mdf(d[u].rs,lp,rp,x);
        }
        int qry(int u,int pos){
            if(d[u].l==d[u].r) return d[u].max;
            push_d(u);
            int mid=d[u].l+d[u].r>>1;
            if(pos<=mid) return qry(d[u].ls,pos);
            else return qry(d[u].rs,pos);
        }
        void build(int u,int l,int r){
            d[u].max=-1;
            d[u].l=l,d[u].r=r;
            if(l==r) return;
            int mid=l+r>>1;
            d[u].ls=new_nd();
            build(d[u].ls,l,mid);
            d[u].rs=new_nd();
            build(d[u].rs,mid+1,r);
        }
    public:
        void build(){build(1,1,n);}
        void mdf(int lp,int rp,int x){
            if(lp>rp) return;
            mdf(1,lp,rp,x);
        }
        int qry(int pos){return qry(1,pos);}
};
class TP{
    private:
        struct node{
            int w,he,fa,top,id,sz,hson,lpos;
            bool blk,mdf;
        }d[MAXN];
        struct line{int to,nex;}ed[MAXN<<1];
        segT T;
        void addE(int u,int v){
            static int cnt;
            ed[++cnt]=(line){v,d[u].he};
            d[u].he=cnt;
        }
        void DFS(int u,int 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;
                if(v!=fa){
                    d[v].fa=u;
                    DFS(v,u);
                    d[u].sz+=d[v].sz;
                    if(d[v].sz>d[hson].sz) hson=v;
                }
            }
        }
        void link(int u,int fa){
            static int cnt;
            d[u].id=++cnt;
            d[u].top= d[fa].hson==u ? d[fa].top:u;
            int hson=d[u].hson;
            if(hson) link(hson,u);
            for(int i=d[u].he,v;i;i=ed[i].nex){
                v=ed[i].to;
                if(v!=fa && v!=hson) link(v,u);
            }
            d[u].lpos=cnt;
        }
    public:
        void init(){
            for(int i=1;i<=n;++i)
                read(d[i].w);
            for(int i=1,u,v;i<n;++i){
                read(u),read(v);
                addE(u,v),addE(v,u);
            }
        }
        void build(){
            DFS(1,0);
            link(1,0);
            T.build();
        }
        void mdf(int u){
            if(d[u].blk) return;
            T.mdf(d[u].id,d[u].lpos,d[u].w);
            d[u].blk=true;
            int fa;
            while(d[u].fa){
                fa=d[u].fa;
                T.mdf(d[fa].id,d[u].id-1,d[fa].w);
                T.mdf(d[u].lpos+1,d[fa].lpos,d[fa].w);
                if(d[fa].mdf) break;
                d[fa].mdf=true;
                u=fa;
            }
        }
        int qry(int u){return T.qry(d[u].id);}
}T;
int main(){
    setIO("lca");
    int m;
    read(n),read(m);
    T.init();
    T.build();
    char cmd[10];
    for(int i=1,v;i<=m;++i){
        scanf("%s%d",cmd,&v);
        if(cmd[0]=='Q') write(T.qry(v),'\n');
        else T.mdf(v);
    }
    return 0;
}