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

省选要来啦。。进入疯狂考试模式
这次做的好像是HNOI的day1试题

心路历程

打开第一题,发现这是前几周做过的一个很神的概率DP。。虽然方程忘了但是状态还是很记得的。。。
然后觉得这题一定能A！
很快就回忆+推出了DP方程,然后码完代码大约过了30min,发现答案怎么不对？
然后就拿着50行的超短代码输出中间结果开始调,结果

1h过去了。。还是奇怪地wa掉样例。。

然后我就很虚了。。去看第二题第三题,第二题好像暴力有50分的样子,第三题完全没思路啊。。
鉴于这题做过,我有必须A的信念,于是又跑回来继续第一题,对着方程一脸虚,怀疑搞错了但是又不知道哪里错了,于是开始玄学乱改+面相数据编程+手算概率。

然后。。过去了1h+,第一个规模为3的小样例还是没过。。。
要报警了。。时间只有1.5h,我貌似还一分没拿到。。。

悲哀,放弃第一题,十分钟码了个指数级状压暴力,看第二题

前20分好像是暴力分。。 O(N^2) 可以过吧,然后30分在链上好像可以离线+主席树莫队？
搞搞搞！
话10+min码了个20分的bitset暴力咦过不了样例？
先调试一波
没有问题呀啊我读错题辣
赶快改改改。。。
但是这样一来我发现我想不出20分 O(N^2) 的暴力了。。感觉考试接近尾声智商下线
没事。。码个 O(N^3) 可能还有十分。。要求不高了。。
码完过样例后只有30min不到了,想了一下30分感觉肯定也不好写,于是看最后一题

什么神奇的东西。。感觉没给部分分,这点时间想出来估计也写不出来
好像答案有Impossible,虽然多组数据还是输出撞个运气试试。。

然后就保存文件。。。然后就等着原地爆炸了。。

开始评测

第一题30分拿到后就Re完了。。
第二题貌似Tle? O(N^3) 果然过不了。。还是太天真
第三题拿到5分

事后

JeremyGuo说它考的好差只有270分辣(Hineven:$^#@&%)
SunIsMe貌似只写了第二题。。然后炸了,节哀
Ender写了第一题和第三题,据说有170分但是我发现他第三题好像题读错了然后炸了
JeremyGuo后来好像炸到了170分但还是强。。

后来发现第一题原来是预处理写错了,改改就AC了! 我￥#@$$&*$%#
和第一题搞了那么久还是没搞出来,害的后面两题没时间写啊。。但是感觉这个难度的话去写也很可能挂掉。
以后真的得给每道题分配好时间了。。时间分配问题从上次考试就有了。。。

题目以及解题报告

第一题

小 K 不慎被 LL 邪教洗脑了，洗脑程度深到他甚至想要从亚瑟王邪教中脱坑。
他决定，在脱坑之前，最后再来打一盘亚瑟王。既然是最后一战，就一定要打得漂
亮。众所周知，亚瑟王是一个看脸的游戏，技能的发动都是看概率的。作为一个非
洲人，同时作为一个前 OIer，小 K 自然是希望最大化造成伤害的期望值。但他已
经多年没写过代码，连 Spaly都敲不对了，因此，希望你能帮帮小 K，让他感受一
下当欧洲人是怎样的体验。
本题中我们将考虑游戏的一个简化版模型。
玩家有一套卡牌，共 n张。游戏时，玩家将 n 张卡牌排列成某种顺序，排列后
将卡牌按从前往后依次编号为 1 ~ n。本题中，顺序已经确定，即为输入的顺序。
每张卡牌都有一个技能。第 i 张卡牌的技能发动概率为 pi，如果成功发动，则会对
敌方造成di点伤害。也只有通过发动技能，卡牌才能对敌方造成伤害。基于现实因
素以及小K非洲血统的考虑，pi不会为 0，也不会为 1，即 0 < pi < 1。
一局游戏一共有 r 轮。在每一轮中，系统将从第一张卡牌开始，按照顺序依次
考虑每张卡牌。在一轮中，对于依次考虑的每一张卡牌：
1如果这张卡牌在这一局游戏中已经发动过技能，则
1.1 如果这张卡牌不是最后一张，则跳过之（考虑下一张卡牌）；
否则（是最后一张），结束这一轮游戏。
2否则（这张卡牌在这一局游戏中没有发动过技能），设这张卡牌为第 i 张
2.1将其以 pi的概率发动技能。
2.2如果技能发动，则对敌方造成 di点伤害，并结束这一轮。
2.3如果这张卡牌已经是最后一张（即 i 等于n），则结束这一轮；否则，
考虑下一张卡牌。
请帮助小 K 求出这一套卡牌在一局游戏中能造成的伤害的期望值

解题报告

很神很机智的概率DP
设状态 dp[i][j] 为
第i张牌获得j次发动技能的机会的概率
那么接下来分两种情况讨论
1.第i-1张牌获得了j次机会但是它很不争气没有发动技能,于是从dp[i-1][j]乘上[i-1]号牌j次都不发动技能的概率 (1-p[i])^j 转移到dp[i][j]
2.第i-1张牌获得了j+1次机会,然后在j+1轮中的某一轮终于发动了技能,于是剩下的j次为发动技能的机会向后轮到了i,于是从dp[i-1][j+1]乘上1-[i-1]号牌j+1次都不发动技能的概率 (1-(1-p[i])^(j+1)) 转移到dp[i][j]

计算答案就枚举i,j,乘以i号牌在获得j机会时能发动技能的概率再乘上权值累和即可。
复杂度ntr,比较有趣。。
注意精度有8位,开long double并且输出10位避免误差。

代码

#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <algorithm>
#include <iostream>
using std :: cin;
using std :: cout;
typedef long double LD;
LD f  [300][200];
LD fac[300][300];
LD p  [300], rev[300];
LD val[300];
int main () {
    int cas, N, R;
    scanf("%d", &cas);
    for(int tc = 1; tc <= cas; tc ++) {
        scanf("%d%d", &N, &R);
        for(int i = 1; i<=N; i++) {
            cin >> p[i] >> val[i];
            rev[i] = 1.0-p[i];
        }
        memset(f, 0, sizeof f);
        memset(fac, 0, sizeof fac);
        for(int i = 0; i<=N; i++)
            fac[i][0] = 1.0;
        for(int i = 0; i<=R; i++) // 注意这里需要赋值
            fac[0][i] = 1.0;
        for(int i = 1; i<=N; i++)
            for(int j = 1; j<=R; j++)
                fac[i][j] = fac[i][j-1]*rev[i];
        f[0][R] = 1.0;
        for(int i = 1; i<=N; i++)
            for(int j = 1; j<=R; j++) {
                f[i][j] = f[i-1][j]*fac[i-1][j] + f[i-1][j+1]*(1.0-fac[i-1][j+1]);
            }
        LD ans = 0;
        for(int i = 1; i<=N; i++)
            for(int j = 1; j<=R; j++)
                ans += f[i][j]*(1.0-fac[i][j])*(LD)val[i];
        printf("%.10lf\n", (double)ans);
    }
}

第二题

风见幽香非常喜欢玩一个叫做 osu!的游戏，其中她最喜欢玩的模式就是接水果。
由于她已经DT FC 了The big black, 她觉得这个游戏太简单了，于是发明了一个更
加难的版本。首先有一个地图，是一棵由 n 个顶点、n-1 条边组成的树（例如图 1
给出的树包含 8 个顶点、7 条边）。这颗树上有 P 个盘子，每个盘子实际上是一条
路径（例如图 1 中顶点 6 到顶点 8 的路径），并且每个盘子还有一个权值。第 i 个
盘子就是顶点a_i到顶点b_i的路径(由于是树，所以从a_i到b_i的路径是唯一的)，
权值为c_i。接下来依次会有Q个水果掉下来，每个水果本质上也是一条路径，第
i 个水果是从顶点 u_i 到顶点v_i 的路径。幽香每次需要选择一个盘子去接当前的水
果：一个盘子能接住一个水果，当且仅当盘子的路径是水果的路径的子路径（例如
图1中从 3到7 的路径是从1到8的路径的子路径）。这里规定:从a 到b的路径与
从b到 a的路径是同一条路径。当然为了提高难度，对于第 i 个水果，你需要选择
能接住它的所有盘子中，权值第 k_i 小的那个盘子，每个盘子可重复使用（没有使用次数
的上限：一个盘子接完一个水果后，后面还可继续接其他水果，只要它是水
果路径的子路径）。幽香认为这个游戏很难，你能轻松解决给她看吗？
N,P,Q<=40000

解题报告

代码题。。思路也很厉害
首先用dfs序(就是dfn)编号节点,
然后发现对于每个水果 (u, v) ,把节点编号用dfn替换后当成一个二维点点拍到笛卡尔平面上去
假设此时 dfn[u] < dfn[v] , 不满足该条件直接交换u和v即可
接下来对于每条盘子 (x, y) 分两类讨论(同样假设 dfn[x] < dfn[y] )
1. lca(x, y) != y && lca(x, y) != y
此时,如果有一个水果 (u, v) 要覆盖这个路径,那么u需要在x的子树内,y需要在v的子树内
用dfn序限制x和y的范围即可,那么这条路径转换成了矩形 [dfn[x], dlast[x]]\*[dfn[y], dlast[y]]
2. lca(x, y) == x || lca(x, y) == y
此时,如果有一个水果 (u, v) 要覆盖这个路径,那么u不能在 x的儿子中是y的祖先的节点 所代表子树内,y需要在v的子树内。
用dfn序限制x和y的范围类似,此时为了限制 不在某子树内 ,第一维需要和[1,N]取补集,转化成两个矩形,方法类似这里不在赘述。
接下来,问题就变成了

询问多次,每次询问包含一个点的所有矩形中权值第k小是多少

然后就可以强上数据结构了。。

离线所有点和矩形,离散化权值,点按x排序,建立平行于y轴的扫描线从左向右处理所有点,
维护一个权值线段树套y轴线段树,矩形动态插入和删除保证只有和扫描线有交的矩形存在于树套树上
然后查询直接在权值线段树上二分,可以把时间复杂度压掉一个log
然后就搞搞搞。。。
注意树套树第二层要动态开内存,数组别开太小会爆。。
PS: 这题离散化写错了调了我3h。。。心酸

代码

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
#include <cstdlib>
const int MAXN = 401000;
const int MAXE = 801000;
struct Node {
    int v, nxt;
} d[MAXE];
int head[MAXN], etot;
inline int addEdge (int a, int b) {
    etot ++;
    d[etot].v = b;
    d[etot].nxt = head[a];
    head[a] = etot;
    return etot;
}
int dfn[MAXN], dlast[MAXN], dfn_tot;
int fa[MAXN][21], dep[MAXN];
void getDfn (int u, int f) {
    if(dfn[u]) return;
    fa[u][0] = f, dep[u] = dep[f]+1;
    dfn[u] = ++dfn_tot;
    for(int e = head[u]; e; e = d[e].nxt)
        getDfn(d[e].v, u);
    dlast[u] = dfn_tot;
}
void stInit (int N) {
    for(int x = 1; x<=20; x++)
        for(int i = 1; i<=N; i++)
            fa[i][x] = fa[fa[i][x-1]][x-1];
}
int lca_last;
int getLCA (int a, int b) {
    if(dep[a] < dep[b]) std :: swap(a, b);
    lca_last = a;
    for(int i = 20; i>=0; i--)
        if(dep[fa[a][i]] >= dep[b]) a = fa[a][i];
    if(a == b) {
        for(int i = 20; i>=0; i--)
            if(dep[fa[lca_last][i]] > dep[b]) lca_last = fa[lca_last][i];
        return a;
    }
    for(int i = 20; i>=0; i--)
        if(fa[a][i] != fa[b][i]) a = fa[a][i], b = fa[b][i];
    return fa[a][0];
}
namespace hashtab {
    int yy[MAXN*4], tot;
    int bak[MAXN*4], *task;
    int rev[MAXN*4];
    bool cmp (int a, int b) {
        return task[a] < task[b];
    }
    void hash (int * arr, int len) {
        for(int i = 1; i<=len; i++)
            yy[i] = i, bak[i] = arr[i];
        task = arr;
        std :: sort(yy+1, yy+len+1, cmp);
        tot = 0;
        arr[yy[1]] = ++tot;
        rev[1] = bak[yy[1]];
        for(int i = 2; i<=len; i++)
            if(bak[yy[i]] != bak[yy[i-1]])
                arr[yy[i]] = ++tot, rev[tot] = bak[yy[i]];
            else arr[yy[i]] = tot;
    }
}
int N, P, Q;
namespace ibt2D {
    const int MEMPOOL = 25000000;
    struct Node {int ch[2], sum;} d[MEMPOOL];
    int dtot, uid[MAXN*4];
    int lb, rb, pos, val;
    int vtot;
    void insertY (int l, int r, int & u) {
        if(l > rb || r < lb) return ;
        if(!u) u = ++dtot;
        if(lb <= l && r <= rb) {d[u].sum += val; return ;}
        int mid = (l+r)>>1;
        if(l != r) insertY(l, mid, d[u].ch[0]), insertY(mid+1, r, d[u].ch[1]);
    }
    int queryY (int l, int r, int & u) {
        if(l > pos || r < pos) return 0;
        if(!u) {u = ++dtot; return 0;}
        int mid = (l+r)>>1, ret = d[u].sum;
        if(l != r) ret += queryY(l, mid, d[u].ch[0]) + queryY(mid+1, r, d[u].ch[1]);
        return ret;
    }
    void insert (int l = 1, int r = vtot, int u = 1) {
        if(pos > r || pos < l) return ;
        insertY(1, dfn_tot, uid[u]);
        int mid = (l+r)>>1;
        if(l != r) insert(l, mid, u<<1), insert(mid+1, r, (u<<1)+1);
    }
}

struct Path {
    int u, v, val;
} pas[MAXN];
struct Query {
    int a, b, k, id;
} qrs[MAXN];
bool operator < (Query a, Query b) {return dfn[a.a] < dfn[b.a];}
struct Rect {
    int x1, y1, x2, y2, val;
} rects[MAXN*4]; int rtot;
bool cmpRectX1Y(int a, int b) {return rects[a].x1 < rects[b].x1;}
bool cmpRectX2Y(int a, int b) {return rects[a].x2 < rects[b].x2;}
int tmp[MAXN*4];
int ryyx1[MAXN*4], ryyx2[MAXN*4];
int ans[MAXN];
int main () {
    scanf("%d%d%d", &N, &P, &Q);
    for(int i = 1; i<N; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        addEdge(a, b), addEdge(b, a);
    }
    getDfn(1, 0);
    stInit(N);
    for(int i = 1; i<=P; i++) {
        scanf("%d%d%d", &pas[i].u, &pas[i].v, &pas[i].val), tmp[i] = pas[i].val;
        if(dfn[pas[i].u] > dfn[pas[i].v]) std :: swap(pas[i].u, pas[i].v);
    }
    hashtab :: hash(tmp, P);
    ibt2D :: vtot = hashtab :: tot;
    for(int i = 1; i<=P; i++) {
        int u = pas[i].u, v = pas[i].v;
        int lca = getLCA(u, v);
        if(lca != u && lca != v) {
            rtot ++;
            rects[rtot].x1 = dfn[u];
            rects[rtot].x2 = dlast[u];
            rects[rtot].y1 = dfn[v];
            rects[rtot].y2 = dlast[v];
            rects[rtot].val = tmp[i];
        } else {
            rtot ++;
            rects[rtot].x1 = 1;
            rects[rtot].x2 = dfn[lca_last]-1;
            rects[rtot].y1 = dfn[v];
            rects[rtot].y2 = dlast[v];
            rects[rtot].val = tmp[i];
            if(dfn[lca_last]-1 < 1) rtot --;
            rtot ++;
            rects[rtot].x1 = dlast[lca_last]+1;
            rects[rtot].x2 = dfn_tot;
            rects[rtot].y1 = dfn[v];
            rects[rtot].y2 = dlast[v];
            rects[rtot].val = tmp[i];
            if(dlast[lca_last]+1 > dfn_tot) rtot --;
            else if(rects[rtot].x1 >= rects[rtot].y1){
                std :: swap(rects[rtot].x1, rects[rtot].y1);
                std :: swap(rects[rtot].x2, rects[rtot].y2);
            }
        }
    }
    for(int i = 1; i<=Q; i++) {
        scanf("%d%d%d", &qrs[i].a, &qrs[i].b, &qrs[i].k);
        if(dfn[qrs[i].a] > dfn[qrs[i].b])
            std :: swap(qrs[i].a, qrs[i].b);
        qrs[i].id = i;
    }
    std :: sort(qrs+1, qrs+Q+1);
    for(int i = 1; i<=rtot; i++) ryyx1[i] = ryyx2[i] = i;
    std :: sort(ryyx1+1, ryyx1+rtot+1, cmpRectX1Y);
    std :: sort(ryyx2+1, ryyx2+rtot+1, cmpRectX2Y);
    int x1pos = 1, x2pos = 1;
    for(int i = 1; i<=Q; i++) {
        Query q = qrs[i];
        while(x1pos <= rtot && dfn[q.a] >= rects[ryyx1[x1pos]].x1) {
            Rect rc = rects[ryyx1[x1pos]];
            ibt2D :: lb = rc.y1, ibt2D :: rb = rc.y2;
            ibt2D :: pos = rc.val, ibt2D :: val = 1;
            ibt2D :: insert();
            x1pos ++;
        }
        while(x2pos <= rtot && dfn[q.a] > rects[ryyx2[x2pos]].x2) {
            Rect rc = rects[ryyx2[x2pos]];
            ibt2D :: lb = rc.y1, ibt2D :: rb = rc.y2;
            ibt2D :: pos = rc.val, ibt2D :: val = -1;
            ibt2D :: insert();
            x2pos ++;
        }

        int u = 1, lef = 1, rig = ibt2D :: vtot;
        while(lef != rig) {
            int mid = (lef+rig) >> 1, t;
            ibt2D :: pos = dfn[q.b];
            if((t=ibt2D :: queryY(1, dfn_tot, ibt2D :: uid[u<<1])) >= q.k)
                u = u<<1, rig = mid;
            else u = (u<<1)+1, lef = mid+1, q.k -= t;
        }
        ans[q.id] = hashtab :: rev[lef];
    }
    for(int i = 1; i<=Q; i++)
        printf("%d\n", ans[i]);
    fclose(stdout);
}

后面一题题还没AC….AC后补题解