[总结]2017年3月29日的考试

ryz是谁?

心路历程

拿到题发现好像不是HNOI了,一阵开心

第一题先看错了数据规模,觉得这题不是可以直接下凸壳离线搞么
还好机智地有看了一遍数据规模,发现 t < 10e9 而不是 t < 1e6
然后又想了两分钟,觉得可以lct乱搞
感觉会有更简单的方法啊。。再想一下
果然傻逼了。。用倍增就可以了
感觉好简单,很可做啊!但是不忙,先看下其他两题

第二题俄罗斯方块?那么恶心的dp?
第三题好像飞常神的样子。。想了十分钟暴力都想不出来,果断放弃吧。。

回头开始第一题,此时已经过去30min
花了45min才写完。。写的时候才发现暴多细节,导致写的超慢。。
10min调过样例,但感觉样例好弱啊细节那么多好怂啊。。
写个对拍吧
然后惨不忍睹。。我的智商好像这次下线得特别早。。暴力程序和数据生成器连续写错。。在考场上生无可恋地调拿来对拍的暴力什么感觉。。
45min过去才把对拍写好。。
边拍边做第二题

离考试结束还有1h10min了。。
第二题感觉只能写暴力啊。。
写个40分吧,20分大力搜索+20分特殊情况
特殊情况写到一半感觉思路很不对啊。。鉴于前面写对拍智商下线感觉一阵怂,就把写20分特殊情况的计划给咔嚓掉了。。
回去看第一题,对拍拍出错了,细节改改改。
然后只有40min了
赶快写大力!
在程序里手动暴力了俄罗斯方块15种情况。。痛苦啊
15min写完发现wa了？
智商下线严重啊。。暴力都各种写错,调调调!
15min过去了发现俄罗斯方块少搞了4种情况。。应该是19种,果然犯傻了
暴力好过了,还有大约15min

第一题又出错了???
还好快速发现细节错误,改掉。

检查文件。。
还有几分钟继续拍,玩一下俄罗斯方块放松一下心情。。。
咦不是10点了么不收卷？
应该快收了吧。。反正现在肯定干什么也来不及了。。

最后发现原来10点20才收,第一题到收卷都没拍出错,感觉120稳了(flag)

开始评测

第一题疯狂爆炸!!爆炸!!爆炸!!!wa完只有10分什么情况啊。。
第二题拿了20分然后就开始卡评测了。。
第三题没得说输出0wa完。。出题人没良心。。

120抢救无效30分滚。。

事后

Ender表示他第一题觉得lct搞,写完后发现好像可以直接倍增。。 鸡汁的我 🙂
然后我和Ender第一题写了类似的算法,然而两人都爆了。。只有10分
SunIsMe表示他第一题疯狂乱搞然后拿了50分???
Ender,SunIsMe第二题写了m=4的60分然后爆0了?
JeremyGuo表示爆炸了。。第一题没搞出来,然后好像杠上了?然后就炸了。。
最后SunIsMe用第一题搞到的50分(满分300)碾压我们。。

后来翻了一下第一题题解,发现思路差不多,但好像有更好写,细节更少的写法
还是有点慌了。。应该在写题前多想想
代码正确率实在不行。。写个暴力都写不好还要调试浪费1h+也是醉了

后来发现我的第一题数据生成器略有砒毒,导致正确答案几乎全是1个数字,所以比较弱。。改改参数发现还能拍出错。。败了
对题目的理解还是不到位就开始写题或生成数据还是会爆的啊

题目以及解题报告

第一题

小 R 种了一棵苹果树，这棵树上有 n 个节点（标号从 0 到 n-1），有 n-1 条树枝连接这
n 个节点，这 n 个节点相互连通。每条树枝的长度为 1。
苹果树上的每一个节点上生长着一个苹果，这个苹果散发着香味。在 0 时刻，第 i 个
节点的苹果散发香味的浓郁度为 s[i]，以后每过一个单位时间，香味的浓郁度就会增加 a[i]。
苹果树上还有一只蚂蚁，在 0 时刻时，这只蚂蚁在 0 号节点，在第 i 时刻，它会朝着
第 i 时刻时香味最浓郁的节点方向走 1 个单位长度。（如果两个节点的浓郁度相同，则标号
较大的节点被认为是香味更浓郁的）。如果在第 i 时刻，蚂蚁所处的位置已经是香味最浓郁
的节点了，那么它会选择在原地休息。
现在，小 R 有 m 个问题，他想知道在第 t[i]个时刻蚂蚁的位置。
对于100%的数据 n<=100000,m<=100000，0<=a[i]<=10^6，0<=s[i]<=10^15，0<=t[i]<=10^9

解题报告

首先每个节点作为最香的节点必然是一段连续的时间区间
把每个节点的一次函数在二维平面上画出来然后那二维平面与每个节点上方的平面交出一个向右下方凸出的凸壳
凸壳上每条边所在直线集合就是最香的节点集合。
我在考场上做法是保存凸壳的时间分割点,预处理每个时间分割点时蚂蚁所在位置,然后询问在线回答,在保存的时间分割点上二分一下时间段然后用树上倍增模拟一下就可以了。。
然后这么搞会有一些神奇的细节(现在还没调出来。。弃坑了)
正解好像是离线询问然后扔到时间分割点内一起顺序处理一样。。貌似更好些
写了正解的写法。。比较类似的思路,只是离线答案后再模拟而已
一堆细节坑死我。。。

#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
const int MAXN = 110000;
const int MAXM = 110000;
const LL  LIMT = 1000000000;
int N, M;
struct Pos {
    LL s, a;
    int id;
} inp[MAXN], tmp[MAXN];
int ttot;
bool cmpPos (Pos a, Pos b) {
    if(a.a == b.a) {
        if(a.s == b.s) return a.id > b.id;
        return a.s > b.s;
    }
    return a.a < b.a;
}
LL calt (Pos a, LL x) {return (LL)a.s + (LL)a.a * (LL)x;}
struct Node {
    int v, nxt;
} d[MAXN*2];
int head[MAXN], etot;
inline void addEdge (int a, int b) {
    etot ++;
    d[etot].v = b;
    d[etot].nxt = head[a];
    head[a] = etot;
}
int dep[MAXN], fa[MAXN][16];
void dfs (int u, int f) {
    dep[u] = dep[f] + 1;
    fa[u][0] = f;
    for(int e = head[u]; e; e = d[e].nxt)
        if(d[e].v != f) dfs(d[e].v, u);
}
void st_install () {
    for(int lvl = 1; lvl<=15; lvl++)
        for(int i = 1; i<=N; i++)
            fa[i][lvl] = fa[fa[i][lvl-1]][lvl-1];
}
int jump (int u, int times) {
    for(int i = 15; i>=0; i--)
        if((1<<i) <= times) times -= (1<<i), u = fa[u][i];
    return u;
}
int getLCA (int a, int b) {
    if(dep[a] < dep[b]) std :: swap(a, b);
    a = jump(a, dep[a] - dep[b]);
    if(a == b) return a;
    for(int i = 15; i>=0; i--)
        if(fa[a][i] != fa[b][i]) a = fa[a][i], b = fa[b][i];
    return fa[a][0];
}
struct Query {
    int tick, id;
} qrs[MAXM];
inline bool operator < (Query a, Query b) {return a.tick < b.tick;}
int lbnd[MAXN], rbnd[MAXN];
Pos goals[MAXN]; int gtot;
int ans[MAXM];
int main () {
    scanf("%d%d", &N, &M);
    for(int i = 1; i<=N; i++)
        scanf("%I64d", &inp[i].s);
    for(int i = 1; i<=N; i++)
        scanf("%I64d", &inp[i].a), inp[i].id = i;
    for(int i = 1; i<N; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        addEdge(a+1, b+1);
        addEdge(b+1, a+1);
    }
    std :: sort(inp+1, inp+N+1, cmpPos);
    inp[0].a = -1;
    for(int i = 1; i<=N; i++)
        if(inp[i].a != inp[i-1].a)
            tmp[++ttot] = inp[i];
    goals[++gtot] = tmp[1];
    lbnd[gtot] = 0, rbnd[gtot] = LIMT;
    for(int i = 2; i<=ttot; i++) {
        Pos p = tmp[i];
        while(gtot) {
            if(calt(p, lbnd[gtot]) > calt(goals[gtot], lbnd[gtot])) gtot --;
            else if(calt(p, lbnd[gtot]) == calt(goals[gtot], lbnd[gtot])
                    && p.id > goals[gtot].id) gtot --;
            else break;
        }
        LL intersect = 0;
        if(gtot) {
            int lef = lbnd[gtot], rig = LIMT;
            intersect = lbnd[gtot]+1;
            while(lef <= rig) {
                int mid = (lef+rig) >> 1;
                if(calt(p, mid) < calt(goals[gtot], mid) ||
                   (calt(p, mid) == calt(goals[gtot], mid) && goals[gtot].id > p.id))
                    lef = mid + 1;
                else rig = mid - 1, intersect = mid;
            }
        }
        if(intersect > TLIM) continue ;
        rbnd[gtot] = intersect - 1;
        goals[++gtot] = p;
        lbnd[gtot] = intersect;
        rbnd[gtot] = LIMT;
    }
    dfs(1, 0);
    st_install();
    for(int i = 1; i<=M; i++) {
        scanf("%d", &qrs[i].tick);
        qrs[i].id = i;
    }
    std :: sort(qrs + 1, qrs + (M+1));
    LL now = 0;
    int intv = 1, pos = 1;
    for(int i = 1; i<=M; i++) {
        while(rbnd[intv] <  qrs[i].tick) {
            int goal = goals[intv].id;
            int lca = getLCA(goal, pos);
            int llen = dep[pos] - dep[lca], rlen = dep[goal] - dep[lca];
            int len = rbnd[intv] - now + 1;
            if(llen >= len) pos = jump(pos, len);
            else if(llen + rlen >= len) pos = jump(goal, llen+rlen - len);
            else pos = goal;
            now = rbnd[intv]+1, intv ++;
        }
        int goal = goals[intv].id;
        int lca = getLCA(goal, pos);
        int llen = dep[pos] - dep[lca], rlen = dep[goal] - dep[lca];
        int len = qrs[i].tick - now;
        if(llen >= len) pos = jump(pos, len);
        else if(llen + rlen >= len) pos = jump(goal, llen+rlen - len);
        else pos = goal;
        now = qrs[i].tick;
        ans[qrs[i].id] = pos - 1;
    }
    for(int i = 1; i<=M; i++)
        printf("%d\n", ans[i]);
}