「NOIP2016」天天爱跑步

RainAir

November 8, 2018

1714views

2 comments

3717 words

题解

题目链接

NOIP 史上最毒瘤的一个题目......花了 2h 总算肝出来了。

<h3>暴力测试点</h3>

大力枚举时间然后统计答案就可以了…….简单的模拟题目。

期望得分 $25$ 分。

考虑链情况的每一个人只能向左或向右走，也就是 $s \leq t$ 向右，否则向左。我们考虑点 $v$ 的观察员，不妨发现他能观察到的向右的玩家应满足 $ s + w_v = v $ ，即 $ s=v-w_v $。

同理，对于向左走的玩家有 $ s=v+w_v $。

排序或者用桶来维护这个东西即可。

时间复杂度 $ O(nlogn) \to O(n) $。

期望得分 $40$ 分。

我们钦定这个树的根是1，~~找一找规律~~ 发现点 $v$ 的观察员能够观察到的点当且仅当 $w_v= depth_v$，统计每个点的子树有多少个终点即可。

期望得分 $60$ 分。

依然钦定，考虑一个点 $v$ 能看到的路径，显然该路径的起点应该在 $j$ 的子树里而且满足条件 $w_v + depth_v = l$，其中 $l$ 为链的长度。这个我们开一个全局的桶，每一次我们 $dfs$ 后统计桶的增量即可。

期望得分 $80$ 分。

<h3>无特殊情况</h3>

~~你都80分了还不满足过分了啊~~

依然钦定，总体考虑 $i$ 点能看到谁。

把上面两种情况整合一下：发现对于一条路径 $u\to v$，相当于可以拆成两条路径 $u\to lca$ 和 $lca\to v$。这样的话对于向上走的玩家 $i$ 点能看见应满足 $depth_u - w_i = depth_i$，即 $ depth_u = w_i + depth_i $。

同理：向下的路径满足的条件是 $ depth_v -depth_i = l - w_i $，其中 $l$ 是链长，移项也可以得到 $ depth_v - len = depth_i - w_i $。

对着两种路径进行差分（我觉得不像是差分），我们用一个桶来统计，下标表示等式右边的表达式，记录的值是左边的表达式，如果出现负数，整体左移即可（对增量没有影响）。

我们来考虑 $lca$ 会被重复计算，那么我们减掉 $lca$ 的一次贡献即可。

具体可看代码，

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define RFOR(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

namespace fastIO{ 
    #define BUF_SIZE 100000 
    #define OUT_SIZE 100000 
    #define ll long long 
    bool IOerror=0; 
    inline char nc(){ 
        static char buf[BUF_SIZE],p1=buf+BUF_SIZE,pend=buf+BUF_SIZE; 
        if (p1==pend){ 
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin); 
            if (pend==p1){IOerror=1;return -1;} 
        } 
        return *p1++; 
    } 
    inline bool blank(char ch){return ch==' '||ch=='n'||ch=='r'||ch=='t';} 
    inline void read(int &x){ 
        bool sign=0; char ch=nc(); x=0; 
        for (;blank(ch);ch=nc()); 
        if (IOerror)return; 
        if (ch=='-')sign=1,ch=nc(); 
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; 
        if (sign)x=-x; 
    } 
    inline void read(ll &x){ 
        bool sign=0; char ch=nc(); x=0; 
        for (;blank(ch);ch=nc()); 
        if (IOerror)return; 
        if (ch=='-')sign=1,ch=nc(); 
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; 
        if (sign)x=-x; 
    } 
    #undef ll 
    #undef OUT_SIZE 
    #undef BUF_SIZE 
}; 
using namespace fastIO;

const int MAXN = 300000 + 5;

struct Node{
    struct Edge *firstEdge;
    int depth,ts,num; // ts = 题目中的 w
    bool vis;
}node[MAXN];

struct Edge{
    Node s,t;
    Edge *next;
}pool[MAXN2],frog = pool;

struct Person{
    int s,t;
    int lca,len;
}p[MAXN];

Edge New(Node s,Node *t){
    Edge *ret = ++frog;
    ret->s = s;ret->t = t;
    ret->next = s->firstEdge;
    return ret;
}

inline void add(int u,int v){
    node[u].firstEdge = New(&node[u],&node[v]);
    node[v].firstEdge = New(&node[v],&node[u]);
}

int N,M;
int fMAXN;
float log2N;

inline void init(){
    CLR(f,-1);
    FOR(i,1,N){
        node[i].num = i;
        node[i].depth = 0;
        node[i].vis = false;
    }
    log2N = log2(N);
    node[1].depth = 1;
    node[1].vis = true;
}

void dfs(Node *v){
    #define EFOR(i,v) for(Edge *i = v->firstEdge;i;i = i->next)
    FOR(i,1,log2N){
        if((1 << i) >= v->depth) break;
        fv->num = ff[v->num][i-1];
    }
    EFOR(e,v){
        if(!e->t->vis){
            e->t->vis = true;
            fe->t->num = v->num;
            e->t->depth = v->depth + 1;
            dfs(e->t);
        }
    }
    #undef EFOR
}

inline int lca(int x,int y){
    int dx = node[x].depth,dy = node[y].depth;
    if(dx != dy){
        if(dx < dy){
            std::swap(x,y);
            std::swap(dx,dy);
        }
        int d = dx - dy;
        FOR(i,0,log2N){
            if((1 << i) & d) x = fx;
        }
    }
    if(x == y) return x;
    RFOR(i,log2N,0){
        // if(nodef[x].depth < 0) continue;
        if(fx == fy) continue;
        else x = fx,y = fy;
    }
    return fx;
}

std::vector<int> cf[MAXN],cf1[MAXN],cf2[MAXN];
int max,t[MAXN],ans[MAXN],cnt[MAXN];
// cf: lca 为 i 的人起点深度

void dfs1(Node *v){
    #define EFOR(i,v) for(Edge *i = v->firstEdge;i;i = i->next)
    int now = v->depth + v->ts,pre; // now 记录右边，t 记录左边，pre 记录
    if(now <= max) pre = t[now];
    EFOR(e,v)
        if(v->depth < e->t->depth)
            dfs1(e->t);
    t[v->depth] += cnt[v->num];
    if(now <= max)
        ans[v->num] += t[now]-pre;
    int sz = cf[v->num].size()-1;
    RFOR(i,sz,0)
        tcf[v->num]--;
    #undef EFOR
}

void dfs2(Node *v){
    #define EFOR(i,v) for(Edge *i = v->firstEdge;i;i = i->next)
    int now = v->depth - v->ts + MAXN,pre; // 同上
    pre = t[now];
    EFOR(e,v)
        if(v->depth < e->t->depth) dfs2(e->t);
    int sz = cf1[v->num].size()-1;
    RFOR(i,sz,0)
        ++tcf1[v->num+MAXN];
    sz = cf2[v->num].size()-1;
    ans[v->num] += t[now] - pre;
    RFOR(i,sz,0)
        --tcf2[v->num+MAXN];
    // DEBUG(ans[v->num]);
    #undef EFOR
}

int main(){
    read(N);read(M);
    FOR(i,1,N-1){
        int u,v;read(u);read(v);
        add(u,v);
    }
    init();
    dfs(&node[1]);
    FOR(i,1,N){
        read(node[i].ts);
        max = std::max(max,node[i].depth);
    }
    // DEBUG(max);
    CLR(t,0);CLR(cnt,0);
    // puts("---------------------------");
    FOR(i,1,M){
        read(p[i].s);read(p[i].t);
        // node[p[i].s].cnt++;
        cnt[p[i].s]++;
        p[i].lca = lca(p[i].s,p[i].t);
        p[i].len = node[p[i].s].depth + node[p[i].t].depth - 2*node[p[i].lca].depth;
        cf[p[i].lca].push_back(node[p[i].s].depth); // 记录 lca 为 i 的人的深度
        // printf("%d %dn",p[i].lca,p[i].len);
    }
    dfs1(&node[1]); // 处理向上的路径
    CLR(t,0);
    FOR(i,1,M){
        int v = node[p[i].t].depth - p[i].len;
        cf1[p[i].t].push_back(v); // 记录终点为 i 的人的等式左边
        cf2[p[i].lca].push_back(v); // 记录 lca 为 i 的人的等式左边
    }
    dfs2(&node[1]);
    FOR(i,1,M)
        if(node[p[i].s].depth - node[p[i].lca].depth == node[p[i].lca].ts) --ans[p[i].lca];
    FOR(i,1,N)
        printf("%d%c",ans[i],(i == N) ? 'n' : ' ');
    return 0;
}

「NOIP2016」天天爱跑步

RainAir • 2018 年 11 月 08 日

题目链接

NOIP 史上最毒瘤的一个题目......花了 2h 总算肝出来了。

<h3>暴力测试点</h3>

大力枚举时间然后统计答案就可以了…….简单的模拟题目。

期望得分 $25$ 分。

同理，对于向左走的玩家有 $ s=v+w_v $。

排序或者用桶来维护这个东西即可。

时间复杂度 $ O(nlogn) \to O(n) $。

期望得分 $40$ 分。

我们钦定这个树的根是1，~~找一找规律~~ 发现点 $v$ 的观察员能够观察到的点当且仅当 $w_v= depth_v$，统计每个点的子树有多少个终点即可。

期望得分 $60$ 分。

期望得分 $80$ 分。

<h3>无特殊情况</h3>

~~你都80分了还不满足过分了啊~~

依然钦定，总体考虑 $i$ 点能看到谁。

同理：向下的路径满足的条件是 $ depth_v -depth_i = l - w_i $，其中 $l$ 是链长，移项也可以得到 $ depth_v - len = depth_i - w_i $。

我们来考虑 $lca$ 会被重复计算，那么我们减掉 $lca$ 的一次贡献即可。

具体可看代码，

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define RFOR(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

namespace fastIO{ 
    #define BUF_SIZE 100000 
    #define OUT_SIZE 100000 
    #define ll long long 
    bool IOerror=0; 
    inline char nc(){ 
        static char buf[BUF_SIZE],p1=buf+BUF_SIZE,pend=buf+BUF_SIZE; 
        if (p1==pend){ 
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin); 
            if (pend==p1){IOerror=1;return -1;} 
        } 
        return *p1++; 
    } 
    inline bool blank(char ch){return ch==' '||ch=='n'||ch=='r'||ch=='t';} 
    inline void read(int &x){ 
        bool sign=0; char ch=nc(); x=0; 
        for (;blank(ch);ch=nc()); 
        if (IOerror)return; 
        if (ch=='-')sign=1,ch=nc(); 
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; 
        if (sign)x=-x; 
    } 
    inline void read(ll &x){ 
        bool sign=0; char ch=nc(); x=0; 
        for (;blank(ch);ch=nc()); 
        if (IOerror)return; 
        if (ch=='-')sign=1,ch=nc(); 
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; 
        if (sign)x=-x; 
    } 
    #undef ll 
    #undef OUT_SIZE 
    #undef BUF_SIZE 
}; 
using namespace fastIO;

const int MAXN = 300000 + 5;

struct Node{
    struct Edge *firstEdge;
    int depth,ts,num; // ts = 题目中的 w
    bool vis;
}node[MAXN];

struct Edge{
    Node s,t;
    Edge *next;
}pool[MAXN2],frog = pool;

struct Person{
    int s,t;
    int lca,len;
}p[MAXN];

Edge New(Node s,Node *t){
    Edge *ret = ++frog;
    ret->s = s;ret->t = t;
    ret->next = s->firstEdge;
    return ret;
}

inline void add(int u,int v){
    node[u].firstEdge = New(&node[u],&node[v]);
    node[v].firstEdge = New(&node[v],&node[u]);
}

int N,M;
int fMAXN;
float log2N;

inline void init(){
    CLR(f,-1);
    FOR(i,1,N){
        node[i].num = i;
        node[i].depth = 0;
        node[i].vis = false;
    }
    log2N = log2(N);
    node[1].depth = 1;
    node[1].vis = true;
}

void dfs(Node *v){
    #define EFOR(i,v) for(Edge *i = v->firstEdge;i;i = i->next)
    FOR(i,1,log2N){
        if((1 << i) >= v->depth) break;
        fv->num = ff[v->num][i-1];
    }
    EFOR(e,v){
        if(!e->t->vis){
            e->t->vis = true;
            fe->t->num = v->num;
            e->t->depth = v->depth + 1;
            dfs(e->t);
        }
    }
    #undef EFOR
}

inline int lca(int x,int y){
    int dx = node[x].depth,dy = node[y].depth;
    if(dx != dy){
        if(dx < dy){
            std::swap(x,y);
            std::swap(dx,dy);
        }
        int d = dx - dy;
        FOR(i,0,log2N){
            if((1 << i) & d) x = fx;
        }
    }
    if(x == y) return x;
    RFOR(i,log2N,0){
        // if(nodef[x].depth < 0) continue;
        if(fx == fy) continue;
        else x = fx,y = fy;
    }
    return fx;
}

std::vector<int> cf[MAXN],cf1[MAXN],cf2[MAXN];
int max,t[MAXN],ans[MAXN],cnt[MAXN];
// cf: lca 为 i 的人起点深度

void dfs1(Node *v){
    #define EFOR(i,v) for(Edge *i = v->firstEdge;i;i = i->next)
    int now = v->depth + v->ts,pre; // now 记录右边，t 记录左边，pre 记录
    if(now <= max) pre = t[now];
    EFOR(e,v)
        if(v->depth < e->t->depth)
            dfs1(e->t);
    t[v->depth] += cnt[v->num];
    if(now <= max)
        ans[v->num] += t[now]-pre;
    int sz = cf[v->num].size()-1;
    RFOR(i,sz,0)
        tcf[v->num]--;
    #undef EFOR
}

void dfs2(Node *v){
    #define EFOR(i,v) for(Edge *i = v->firstEdge;i;i = i->next)
    int now = v->depth - v->ts + MAXN,pre; // 同上
    pre = t[now];
    EFOR(e,v)
        if(v->depth < e->t->depth) dfs2(e->t);
    int sz = cf1[v->num].size()-1;
    RFOR(i,sz,0)
        ++tcf1[v->num+MAXN];
    sz = cf2[v->num].size()-1;
    ans[v->num] += t[now] - pre;
    RFOR(i,sz,0)
        --tcf2[v->num+MAXN];
    // DEBUG(ans[v->num]);
    #undef EFOR
}

int main(){
    read(N);read(M);
    FOR(i,1,N-1){
        int u,v;read(u);read(v);
        add(u,v);
    }
    init();
    dfs(&node[1]);
    FOR(i,1,N){
        read(node[i].ts);
        max = std::max(max,node[i].depth);
    }
    // DEBUG(max);
    CLR(t,0);CLR(cnt,0);
    // puts("---------------------------");
    FOR(i,1,M){
        read(p[i].s);read(p[i].t);
        // node[p[i].s].cnt++;
        cnt[p[i].s]++;
        p[i].lca = lca(p[i].s,p[i].t);
        p[i].len = node[p[i].s].depth + node[p[i].t].depth - 2*node[p[i].lca].depth;
        cf[p[i].lca].push_back(node[p[i].s].depth); // 记录 lca 为 i 的人的深度
        // printf("%d %dn",p[i].lca,p[i].len);
    }
    dfs1(&node[1]); // 处理向上的路径
    CLR(t,0);
    FOR(i,1,M){
        int v = node[p[i].t].depth - p[i].len;
        cf1[p[i].t].push_back(v); // 记录终点为 i 的人的等式左边
        cf2[p[i].lca].push_back(v); // 记录 lca 为 i 的人的等式左边
    }
    dfs2(&node[1]);
    FOR(i,1,M)
        if(node[p[i].s].depth - node[p[i].lca].depth == node[p[i].lca].ts) --ans[p[i].lca];
    FOR(i,1,N)
        printf("%d%c",ans[i],(i == N) ? 'n' : ' ');
    return 0;
}

「NOIP2016」天天爱跑步

2 comments

Leave a Comment Cancel reply

NOI2021 退役记

I'm back

SDOI2020 退役记

点双连通分量 & 圆方树学习笔记

CSP2019 游记

「NOIP2017」列队

「CF76C」Mutation

「BZOJ3118」Orz The Mst

CF 1437 题解

20联赛集训day2 题解

「NOIP2016」天天爱跑步