2017.10.30 NOIP模拟赛

题解 套题

目录

• 2017.10.30 NOIP模拟赛
  • 赛跑
    • 思路
    • 代码
  • 暗中观察
    • 思路
    • 代码
  • 占领
    • 思路
    • 代码

赛跑

思路

• 拓展欧几里得模板题；
• 就是求不定方程$ai+(-c)j=d-b$的最小正整数解。

代码

#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::__gcd;
int a,b,c,d;
void exgcd(int a,long long &x,int b,long long &y){
    if(b==0){
        x=1,y=0;
        return;
    }
    exgcd(b,y,a%b,x);
    y-=a/b*x;
}
inline long long solve(){
    int gcd=__gcd(a,c);
    if((d-b)%gcd!=0) return -1;
    long long i,j;
    exgcd(a,i,c,j);
    i*=(d-b)/gcd;
    int tmp=c/gcd;
    i=(i%tmp+tmp)%tmp;
    return b+a*i;
}
int main(){
    setIO("run");
    read(a),read(b);
    read(c),read(d);
    write(solve());
    return 0;
}

暗中观察

思路

• 考虑直接模拟的话，时间精度可以无限小，不可做；
• 而速度的话，由于起点的不同，因素太多；
• 我们不妨考虑求出每个人进入可被观察区域（$x_i \leq 0 \leq x_i+1$）的开始和结束时间$t_l,t_r$；
• 我们按$y$升序处理每个人，那么这个人能被观察到，当且仅当目前$[t_l,t_r]$这个时间区间没有被完全覆盖；
• 这个我们可以在线段树上维护，但是需要离散化；
• 而离散化中有一个要注意的是离散化出来的区间是原区间的左闭右开即$[t_l,t_r)$，因为如果不这样，对于一个时间为$10$~$12$另一个为$13$~$14$，离散化后并覆盖完会认为$12$~$13$之间没有空区间了。

代码

#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::sort;
using std::unique;
using std::lower_bound;
const int MAXN=50005;
int n,tot;
int x[MAXN],y[MAXN],d[MAXN];
struct people{
    int y,lp,rp;
    long long l,r;
    static bool cmp_y(const people &a,const people &b){return a.y<b.y;}
}p[MAXN];
class segT{
#define ls (u<<1)
#define rs (ls|1)
    private:
        bool cov[MAXN<<2],tag[MAXN<<2];
        void upd(int u){cov[u]=cov[ls]&cov[rs];}
        void add_tag(int u){cov[u]=tag[u]=true;}
        void push_d(int u){
            if(!tag[u]) return;
            add_tag(ls),add_tag(rs);
            tag[u]=false;
        }
        void ist(int u,int l,int r,int lp,int rp){
            if(lp<=l && r<=rp){
                add_tag(u);
                return;
            }
            push_d(u);
            int mid=l+r>>1;
            if(lp<=mid) ist(ls,l,mid,lp,rp);
            if(rp>mid) ist(rs,mid+1,r,lp,rp);
            upd(u);
        }
        bool qry(int u,int l,int r,int lp,int rp){
            if(lp<=l && r<=rp) return cov[u];
            push_d(u);
            int mid=l+r>>1;
            bool ret=true;
            if(lp<=mid) ret=qry(ls,l,mid,lp,rp);
            if(rp>mid) ret&=qry(rs,mid+1,r,lp,rp);
            return ret;
        }
    public:
        void ist(int lp,int rp){ist(1,1,tot,lp,rp);}
        bool qry(int lp,int rp){return qry(1,1,tot,lp,rp);}
#undef ls
#undef rs
}T;
inline void deal(){
    for(int i=1;i<=n;++i){
        p[i].l=(long long)d[i]*(0-x[i]-1);
        p[i].r=(long long)d[i]*(0-x[i]);
        p[i].y=y[i];
    }
}
inline void decrete(){
    static long long tmp[MAXN<<1];
    for(int i=1;i<=n;++i){
        tmp[++tot]=p[i].l;
        tmp[++tot]=p[i].r;
    }
    sort(tmp+1,tmp+tot+1);
    tot=unique(tmp+1,tmp+tot+1)-tmp-1;
    for(int i=1;i<=n;++i){
        p[i].lp=lower_bound(tmp+1,tmp+tot+1,p[i].l)-tmp;
        p[i].rp=lower_bound(tmp+1,tmp+tot+1,p[i].r)-tmp;
    }
}
inline int solve(){
    sort(p+1,p+n+1,people::cmp_y);
    int ret=0;
    for(int i=1;i<=n;++i){
        if(!T.qry(p[i].lp,p[i].rp)) ++ret;
        T.ist(p[i].lp,p[i].rp);
    }
    return ret;
}
int main(){
    setIO("watch");
    read(n);
    for(int i=1;i<=n;++i)
        read(x[i]),read(y[i]),read(d[i]);
    deal();
    decrete();
    write(solve());
    return 0;
}

占领

思路

• 考虑将链放到最顶端，即端点的$lca$上；
• 设$dp(u)$是以$u$为根的子树的最大价值，那么显然$dp(u)=\sum_{v \in son(u)}dp(v)$；
• 而我们还要考虑处理放在$u$上的链，但是这样，子树中有些点就会不能用了，导致之前的$dp(u)$不能直接加上这个链的价值；
• 怎么办呢？我们记录一下每个点$u$，以它为根的子树中用和不用$u$的最大价值，最后在这个点记录一下这两者之差，也就是不用$u$的损失；
• 刚刚那个$dp(u)$其实就是不用$u$的；
• 我们枚举过$u$的链时，就是用之前的$dp(u)$减上这条链上点的损失总和加上这条链的价值来更新$dp(u)$；
• 至于求链上的和，就是树剖基本功了；
• 总复杂度$O(m \log n^2)$。

代码

#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 <vector>
using std::max;
using std::swap;
using std::vector;
const int MAXN=100005,MAXM=MAXN;
int n,m;
vector<int> vec[MAXN];
struct chain{int val,u,v;}ln[MAXM];
class BIT{
    private:
        int c[MAXN];
        int lowbit(int x){return x&-x;}
        int qry(int r){
            int ret=0;
            for(;r;r-=lowbit(r))
                ret+=c[r];
            return ret;
        }
    public:
        void add(int l,int x){
            for(;l<=n;l+=lowbit(l))
                c[l]+=x;
        }
        int qry(int l,int r){return qry(r)-qry(l-1);}
};
class TP{
    private:
        int dp[MAXN];
        struct node{int lp,rp,de,top,hson,he,sz,fa;}d[MAXN];
        struct line{int to,nex;}ed[MAXN<<1];
        BIT ta;
        void DFS(int u){
            d[u].sz=1;
            int fa=d[u].fa;
            d[u].de=d[fa].de+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);
                    if(d[hson].sz<d[v].sz) hson=v;
                    d[u].sz+=d[v].sz;
                }
            }
        }
        void link(int u){
            static int cnt;
            d[u].lp=d[u].rp=++cnt;
            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!=fa && v!=hson) link(v);
            }
            d[u].rp=cnt;
        }
        int qry(int u,int v){
            int ret=0;
            int *now;
            while(d[u].top!=d[v].top){
                now= d[d[u].top].de>d[d[v].top].de ? &u:&v;
                ret+=ta.qry(d[d[*now].top].lp,d[*now].lp);
                *now=d[d[*now].top].fa;
            }
            if(d[u].de>d[v].de) swap(u,v);
            ret+=ta.qry(d[u].lp,d[v].lp);
            return ret;
        }
        void add(int u,int x){ta.add(d[u].lp,x);}
        void treeDP(int u,int fa){
            int tmp=0;
            for(int i=d[u].he,v;i;i=ed[i].nex){
                v=ed[i].to;
                if(v!=fa){
                    treeDP(v,u);
                    tmp+=dp[v];
                }
            }
            dp[u]=tmp;
            for(int i=0,j,lim=vec[u].size();i<lim;++i){
                j=vec[u][i];
                dp[u]=max(dp[u],qry(ln[j].u,ln[j].v)+tmp+ln[j].val);
            }
            add(u,tmp-dp[u]);
        }
    public:
        void addE(int u,int v){
            static int cnt;
            ed[++cnt]=(line){v,d[u].he};
            d[u].he=cnt;
        }
        void build(){DFS(1),link(1);}
        int LCA(int u,int v){
            int *now;
            while(d[u].top!=d[v].top){
                now= d[d[u].top].de>d[d[v].top].de ? &u:&v;
                *now=d[d[*now].top].fa;
            }
            return d[u].de<d[v].de ? u:v;
        }
        int treeDP(){
            treeDP(1,0);
            return dp[1];
        }
}T;
int main(){
    setIO("occupy");
    read(n),read(m);
    for(int i=1,u,v;i<n;++i){
        read(u),read(v);
        T.addE(u,v),T.addE(v,u);
    }
    T.build();
    for(int i=1;i<=m;++i){
        read(ln[i].u),read(ln[i].v),read(ln[i].val);
        vec[T.LCA(ln[i].u,ln[i].v)].push_back(i);
    }
    write(T.treeDP());
    return 0;
}