CERC2013 Problem E 勇者斗恶龙

地址:http://codeforces.com/gym/100299(要登录了点进gym才能成功传送)
很有意思的一个Problem。

一棵树上,勇者在1号点,初始血量是0。每个点有一个权值,踩上去血量会加上$$delta_i$$,这个值可正可负。勇者任何时候血量不能低于0。问勇者能否到达某个目标点T。
国际惯例$$1 \leq n \leq 10^5, -10^6 \leq delta_i \leq 10^6$$

看了solution以后才写出来的。
其实看之前已经有一些零零碎碎的idea。就是组织不起来。

  1. 按道理可以把结果组织成带拓扑关系的pair的形式。pair的第一个元素表示至少要多少血量才能进去,第二个元素表示进去以后能增加多少血量。通俗说就是每个血泉的门槛。
  2. 进去以后血量会更亏的地方没有必要走进去
  3. 应该转化成最多能获得多少血量的问题。

先看最后一点,转化的方法是从需要到达的点连一条边到一个新的点,这个新的点值是无穷。最后只要看最多能获得的血量是不是达到无穷就行了。

然后剩下的就是solution最神棍的地方。在求解“最多能获得多少血量”的前提下,因为最优性的原则可以把一棵树化归为一种理想结构:拓扑关系为一条链的pair。并且满足上面提到的第2条(即每对pair里加血总比扣血多),以及依赖越浅的pair,门槛越低。也就是说,把他看成数组的话,门槛递增。

证明分两步。

  1. 证明:假设是一条链的依赖关系,那么可以视作以上提到理想结构。

    1. 显然一条链上相邻的正值和相邻的负值可以合并。于是必然正负交错,可以构成pair。
    2. 依赖关系最深的pair(就是最后一个),如果first >= second,那么可以直接扔掉。因为根据最优性,永远不会选它。
    3. 对于相邻的pair,如果previous.first >= previous.second(扣血比补血多),那么这个pair必然可以和后面一个合并。原因是根据最优化目标的原则,不可能取了previous就不取next。所以previous和next要么同取要么同不取,所以理应合并。
    4. 对于相邻的pair,如果previous.first >= next.first(伤血门槛不递增),那么previous和next必然可以合并。原因是:根据前面两条,所有的pair都满足first < second,所以根据最优性能取都取掉最好。所以都是贪心去取就好了。如果next门槛比previous还低,那么做完previous肯定顺便做掉next。其实这里条件可以更紧一点,取previous.first >= preivous.first – previous.second + next.first作为合并条件也可以AC的,但是前面那个已经足够了。
  2. 证明:假如每个分支下的子树都是链,那么该子树也可以看成链。
    其实就是数学归纳法的意思。然后这个只要把每个分支下的pair按first顺序列成一行就可以了。

综上,用multiset<pair <long long, long long>>维护链就可以了。

#include <cstdio>
#include <vector>
#include <set>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> PLL;
typedef multiset <PLL> MS;
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define foreach(it,v) for (__typeof((v).end()) it = (v).begin(); it != (v).end(); it++)
const int N = 200005;
const ll INF = 1e15;
int Tc, n, m;
vector <int> E[N];
MS pool[N];
ll a[N];

MS* merge(MS *a, MS *b) {
    if (a->size() < b->size()) swap(a, b);
    foreach (it, *b) a->insert(*it);
    b->clear();
    return a;
}

MS* dfs(int u, int fa) {
    MS *res = &pool[u];
    rep (i, E[u].size())
        if (E[u][i] != fa)
            res = merge(dfs(E[u][i], u), res);
    PLL cur = a[u] > 0 ? PLL(0, a[u]) : PLL(-a[u], 0);
    while (!res->empty() && (cur.second < cur.first || cur.second >= res->begin()->first)) {
        PLL tmp = *res->begin();
        res->erase(res->begin());
        cur = tmp.first > cur.second ? PLL(cur.first - cur.second + tmp.first, tmp.second) : PLL(cur.first, cur.second - tmp.first + tmp.second);
    }
    if (cur.second > cur.first) res->insert(cur);
    return res;
}

int main() {
    scanf("%d", &Tc);
    while (Tc--) {
        scanf("%d%d", &n, &m);
        rep (i, n + 1) E[i].clear();
        rep (i, n) {
            int x;
            scanf("%d", &x);
            a[i] = x;
        }
        rep (i, n - 1) {
            int u, v;
            scanf("%d%d", &u, &v);
            u--; v--;
            E[u].push_back(v);
            E[v].push_back(u);
        }
        --m;
        E[m].push_back(n);
        E[n].push_back(m);
        a[n++] = INF;
        MS *res = dfs(0, -1);
        ll hp = 0;
        bool flag = 0;
        foreach (it, *res) if (hp >= it->first) {
            hp += it->second - it->first;
            if (hp >= INF / 2) flag = 1;
        }
        res->clear();
        puts(flag ? "escaped" : "trapped");
    }
    return 0;
}

Low

长春比完一直都很low,直到现在还是……
以这样的姿态结束自己最后一场Regional,实在是很遗憾吧。
大三这一个学期自己也不明白怎么熬到现在的。33的学分,每周来回ZJG训练4场。算一算路上花费1个半小时,每次训练5个小时,那么就是6.5*4 = 26个小时。也没算训练后补题的时间,其实根本就算不清楚……
这么多场训练下来,可以清晰地感受到今年1队比上一年要强上了太多了。结果Regional和网络赛打得都没上一年好。
感觉现在我或多或少看明白了一些原因,不过小结还是等我不怎么带情绪的时候写吧。
痛苦只是因为没有达到自己的预期
不在圈内的人知道结果只会跟你说:“又拿了块金牌,不错哦。”
在圈内的人只会觉得:“唔,ZJU今年还没有上一年强。”
嘛,上一年我带的1队在final打成那样……今年也没多少人看好我们吧。
\
历史总是惊人地相似。
\
4年前我准备NOI的时候亦是如此。
\
为何感觉从小到大我都是这样,无论小学初中还是高中……
前面尝到一点小甜头;在最后的关键时刻前一直被打成马,勉强晋级……;最后放手一搏,然后得到出乎自己意料的结果。
希望这回也不例外吧。
2014.6.25 ACM/ICPC World Finals 不远了。

SRM 598

250pt

给定100 \leq a[i] \leq 300,每个桶容量300,问最少多少个桶能装完给定的a[i]。

看到过的有两种做法,一种把数字从小到大排序,然后从大到小每次贪心装。我的做法是因为只有三个100能放进一个桶里,其它至多两个,那么就枚举有多少组100是三个三个叠在一起的,剩下用sort,每次小的值,找一个尽量大的值来匹配。

550pt

有两个剑士一开始距离为d,A剑士一回合可以移动mov1,攻击范围为rng1。B剑士一回合可以移动mov2,攻击范围为rng2。A、B轮流动,问最优策略下,谁赢或者平局。

先把双方第一步能秒杀的情况排除掉,然后就是看谁mov + rng大,这个值小的必定不能赢(反证一下)。然后这个值大的要看能不能追上另外一个人,如果追的mov比较小,必定平局。mov比较大的条件下,最近是追到对方的mov+rng+1,否则再近一步对方就要反扑了。于是判断mov_op+rng_op+1+mov_op(这是因为追到最近以后,对方可以后退一步才轮到进攻方攻击)这个值是否小于等于mov_me + rng_me,如果是,就是可以赢,否则不行。

写的时候想当然了,几行的代码就写挂了-。-

    string WhoCanWin(int mov1, int mov2, int rng1, int rng2, int d)  {
        if (mov1 + rng1 >= d) return WIN;
        if (mov1 + d <= mov2 + rng2) return LOSE;
        if (mov1 + rng1 > mov2 + rng2) {
            if (mov1 > mov2) {
                return mov2 + rng2 + 1 + mov2 <= mov1 + rng1 ? WIN : DRAW;
            } else {
                return DRAW;
            }
        } else if (mov2 + rng2 > mov1 + rng1) {
            if (mov2 > mov1) {
                return mov1 + rng1 + 1 + mov1 <= mov2 + rng2 ? LOSE : DRAW;
            } else {
                return DRAW;
            }
        } else {
            return DRAW;
        }
    }

1000pt

给定一棵边长为1的树,问最少在多少个点上添加信号塔,使得每个点对信号塔的距离序列互不相同。

枚举一个放信号塔的树根,然后dfs下去,统计没有填信号塔的子树数目(记为cnt)。里面最多只能有一个子树子树不填信号塔,所以ans += cnt – 1。比赛的时候也想到这个了,但是只证出他是必要条件,充分性没证出来- -b,于是就弄了个按覆盖个数的贪心果断跪了。再仔细想想怎么证吧。

[update]
-。-想了一下,充分性好像也是显然的,这样每个节点的不同分叉都可以分辨……也是充分的。

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template <class T> void checkmin(T &t, T x) { if (x < t) t = x; }
const int N = 55;
int n;
vector <int> E[N];

int dfs(int u, int fa) {
    int res = 0, cnt = 0;
    rep (i, E[u].size()) {
        int v = E[u][i];
        if (v == fa) continue;
        int tmp = dfs(v, u);    
        if (tmp == 0) {
            cnt++;
        } else {
            res += tmp;
        }
    }
    if (cnt > 1) {
        res += cnt - 1;
    }
    return res;
}

class TPS { 
    public: 
    int minimalBeacons(vector <string> linked)  { 
        n = linked.size();
        rep (i, n) E[i].clear();
        if (n == 1) return 0;
        rep (i, n) rep (j, n) if (linked[i][j] == 'Y')
            E[i].push_back(j);
        int ans = 0x7FFFFFFF;
        rep (i, n)
            checkmin(ans, dfs(i, -1));
        return ans + 1;
    }
};

弦图

今天在gym上被一题疑似弦图的题目卡了一下,后来猛犸随便乱搞就搞过去了。看了一下gcj上的solution,发现有用完美消除序列过的,于是就去温习了一下弦图。结果最后发现其实那个图根本不是弦图……只是碰巧那个最大势的方法求出来的顺序是靠谱的染色顺序罢了。写一下今天温习的内容吧。

  • 弦图的定义。任意size>3的环都存在弦。弦即环上不相邻两点之间的边。
  • 完美消除序列。$$v_i$$和$$v_{i+1}, … , v_n$$构成的诱导子图里,把和$$v_i$$相连的点拿出来,会成为一个团。
  • 完美消除序列的求法。令$$d_i = 0$$,然后每次选取d值最大的一个点拿出来放进序列,再枚举该点的出边,把他们的d值加1。如此反复。
  • 完美消除序列的性质

    1. 按序列从后往前染色可得图的色数。在弦图里,色数等于最大团的size。
    2. 按序列从前往后贪心取可得最大独立集。在弦图里,最大独立集额等于最小团覆盖。
    3. 按上面最大势方法求出这个序列顺序以后,如果想知道该图是不是弦图,那么枚举每个点$$v_i$$,假设他在$$v_{i+1}, …, v_n$$里有边直接相连的点集为$$S = {x_1, x_2, … , x_m}$$然后只需判定$$x_1$$是不是和$$x_2, x_3, … , x_m$$都有边就可以了。
  • 完美图的定义。所有诱导子图满足色数等于最大团size的图。
  • 伴完美图的定义。所有诱导子图满足最大独立集等于最小团覆盖的图
  • 区间图总是弦图。并且按r排序就是他的完美消除序列。
  • 其实感觉很多不是弦图的题要求色数都可以用最大势的方法求出顺序然后贪心染……说不定就凑出正解的顺序过了……比如GCJ2009 R3 C