Codeforces Beta Round #87.. .

(在网吧做 CF 的寂寞你们不懂!!!)

这盘是 TC 题妈 dolphinigle 的场。。

A 开始没有注意 p[i] > i 的情况。。耽搁了一些时间在调试上。
B 略。。

之后先读了 D,是一个给定一个表达式,问加括号数目的题目,
对于普通的情况,我们知道解是 Catalan 序列,但是这题中有
+-+- A +-+- B
类似这样的表达式存在,影响了我作出判断,想了 12 分钟没有什么有意义的结果于是跳。。

C 是一个插头DP,但是感觉对我可能是个坑。。于是再看了一下 E。。

E 是说给定一个长度为 N 的赛道(数轴),以及 M 场比赛,
每场比赛占用一段连续的区间,每个单位赛道如果要使用的话,有一个修复的代价,每场比赛有一个收益,最大化收益。。

目测了一下准备上最大权闭合子图,但是有一个问题。。

。。N 和 M 都等于 2 * 10^5,这样如果每场比赛都依赖整段区间的话,边可能存不下。想了一下优化建图。。或者能不能离散掉什么的,但是没有什么结果。。
于是我赌它不稠密。。。。
(中间果然被 cha 了)

在 E 被 cha 这前我 yy 了一下 D。。。。
最后 C 的没调出来。。

------
解题报告出来了。。D, E 都挂了。。。等下次吧。。。

----------
补:
好吧。。首先 C 只有 那 4 种插头。。于是只是一道找 Invariants 的题目。。
。。。然后补一下 E 。。目前知道三种作法。。其中网络流的方法仍然有问题。。但我认为应该以后可以想出改进的办法。。

首先是动态规划。。

。。我们用 dp[i] 表示 到前 i 个位置为止所能取得的最大收益,第 i 个位置可以修也可以不修。

那么 dp[i] = max{dp[j] + w(j, i)} | j < i} 其中 w(j, i) 表示及所有日程包含于 [j, i] 这段的赛事所能取得的收益和 减去 修复这段路的代价。 。。这是 第 i 个位置必须要修德,所以再 checkMax(dp[i], dp[i-1]) .. . 这个转移方程的复杂度似乎是 O(n2) 而且看起来得到 w() 也不是很好写。。 。。正确的做法是,将 w() 函数连同 dp[] 一起放到线段树中维护,于是得到一个 O(nlogn) 的方法。 。。。然后。。这题还有一种贪心方法 Orz。 。贴在 Editorial 下面了。。

(据说这个题是出到 今年 IOI 然后被 Ban 掉了。。因为。。 IOI 不喜欢纯数值输出的题目。。)

/* .................................................................................................................................. */

const int N = 200009;
int C[N], L[N], R[N], V[N];
VI events[N];

LL key[4 * N], delay[4 * N];
int a, b; LL v;
int n, m; LL res;

#define root 1, 0, n
#define lx (x << 1)
#define rx (lx + 1)
#define lc lx, l, m
#define rc rx, m+1, r

void Inc(int x, LL d){
    key[x] += d, delay[x] += d;
}

void Release(int x){
    if (delay[x] != 0){
        key[lx] += delay[x], key[rx] += delay[x];
        delay[lx] += delay[x], delay[rx] += delay[x];
        delay[x] = 0;
    }
}

void Update(int x){
    key[x] = max(key[lx], key[rx]);
}

void Insert(int x, int l, int r){
    if (a <= l && r <= b){
        Inc(x, v);
    }
    else {
        Release(x);
        int m = ((l + r) >> 1);
        if (a <= m) Insert(lc);
        if (m < b) Insert(rc);
        Update(x);
    }
}

int main(){

    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    RD(n, m); REP_1(i, n) RD(C[i]);
    REP_1(i, m) RD(L[i], R[i], V[i]), events[R[i]].PB(i);

#define it events[i][j]

    REP_1(i, n){
        REP(j, SZ(events[i])){
            a = 0, b = L[it] - 1, v = V[it];
            Insert(root);
        }

        a = 0, b = i - 1, v = -C[i];
        Insert(root);

        checkMax(res, key[1]);
        a = i, b = i, v = res;
        Insert(root);
    }

    OT(res);
}

/* .................................................................................................................................. */

const int N = 200009;

int Lef[N], Rgt[N], Def[N];
int Att[N]; VI events[N];
int n, m; LL res;

struct comp{
    bool operator() (const int &lhs, const int &rhs) const{
        return Rgt[lhs] > Rgt[rhs];
    }
};

priority_queue<int, vector<int>, comp > Q;

int main(){
    RD(n, m); REP_1(i, n) RD(Att[i]);
    REP_1(i, m) RD(Lef[i], Rgt[i], Def[i]), events[Lef[i]].PB(i);

#define it events[i][j]

    REP_1(i, n){
        while (!Q.empty() && Rgt[Q.top()] < i) res += Def[Q.top()], Q.pop();
        REP(j, SZ(events[i])) Q.push(it);

        while (!Q.empty() && Att[i]){
            int delta = min(Att[i], Def[Q.top()]);
            Att[i] -= delta, Def[Q.top()] -= delta;
            if (!Def[Q.top()]) Q.pop();
        }
    }
    while (!Q.empty()) res += Def[Q.top()], Q.pop();

    OT(res);
}

HDU 4010. Query on The Trees

Brief description :

... 动态维护一组森林,要求支持以下操作:

  • Link(a, b) 如果 a,b 不在同一颗子树中,则通过在 a,b 之间连边的方式,连接这两棵子树。
  • Cut(a, b) 如果 a,b 在同一颗子树中、且 a != b,则将 a 视为这棵子树的根之后,切断 b 与其父亲结点的连接。
  • Modify(w, a, b) 如果 a, b 在同一颗子树中,则将 a, b 之间路径上所有的点权增加 w。
  • Query(a, b) 如果 a, b 在同一颗子树中,返回 a, b 之间路径上点权的最大值。

ゆっくり読んでください ...