[POI2008]BLO

一眼可以了解到是一道割点题。对于不是割点的情况，那么被计算的点对一定包含此点本身，又因为有序，所以贡献就是\(2(n – 1)\)。如果是割点的话，就比较麻烦，分下面几个来算：

• 此点延伸出去的点对。
• 连通块之间的点对。
• 本身就无法互通的点对。

第一个很好算，是\(2(n – 1)\)。第二个，在 Tarjan 枚举搜索子树的时候计算子树大小和全图补集的乘积（注意，这里会多计算一遍与点\(u\)的点对，所以我们第一个改成算\(n – 1\)）；第三个，算「当前整颗搜索树与图的补集大小」与「搜索树的大小」的乘积。

综合起来就是，对于点\(u\)：

\[ ans_u = \sum_{k \in son(u)} (n – size(k)) \times size(k) + (n – 1) + (n – 1 – \sum_{k \in son(u)} size(k)) \times (1 + \sum_{k \in son(u)} size(k)) \]

// BZ1123.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int MAX_N = 100010, MAX_M = 500010;

struct edge
{
    int to, nxt;
} edges[MAX_M << 1];

int head[MAX_N], current, n, m, dfn[MAX_N], low[MAX_N], ptot, siz[MAX_N], root;
ll ans[MAX_N];
bool cut[MAX_N];

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

void tarjan(int u)
{
    ll flag = 0, sum = 0;
    dfn[u] = low[u] = ++ptot, siz[u] = 1;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (dfn[edges[i].to] == 0)
        {
            tarjan(edges[i].to), low[u] = min(low[edges[i].to], low[u]);
            siz[u] += siz[edges[i].to];
            if (low[edges[i].to] >= dfn[u])
            {
                flag++;
                ans[u] += 1LL * (n - siz[edges[i].to]) * siz[edges[i].to];
                // sum accumulated from cut;
                sum += siz[edges[i].to];
                if (u != 1 || flag > 1)
                    cut[u] = true;
            }
        }
        else
            low[u] = min(dfn[edges[i].to], low[u]);
    if (!cut[u])
        ans[u] = 2LL * (n - 1);
    else
        ans[u] += 1LL * (n - sum - 1) * (sum + 1) + (n - 1);
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= m; i++)
        scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
    tarjan(1);
    for (int i = 1; i <= n; i++)
        printf("%lld\n", ans[i]);
    return 0;
}

Codeforces Round #588 (Div. 2)

D – Marcin and Training Camp

考虑两种情况：

• 如果技能的 Code 相同，那么可以认为这两个合并了。这个用 map 维护就行。
• 如果技能的 Code 不同，那么在\(O(n^2)\)枚举的时候，找到一个\(S_i \subseteq S_j\)，进行标记即可。

// CF1230D.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 7070;

ll skills[MAX_N], val[MAX_N], n;
bool tag[MAX_N];
map<ll, int> cnt;

int main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &skills[i]), cnt[skills[i]]++;
    for (int i = 1; i <= n; i++)
        scanf("%lld", &val[i]);
    ll ans = 0;
    for (int i = 1; i <= n; i++)
        // set it as origin;
        if (cnt[skills[i]] > 1)
            for (int j = 1; j <= n; j++)
                if ((skills[i] & skills[j]) == skills[j])
                    tag[j] = true;
    for (int i = 1; i <= n; i++)
        if (tag[i])
            ans += val[i];
    printf("%lld", ans);
    return 0;
}

E – Kamil and Making a Stream

这道题太妙了！

考虑正常的暴力情况：\(O(n^2)\)条链，直接统计完事。但是，发现：一条链向下的\(gcd\)一定都是根部的一个因子，根据对\(\gcd\)复杂度的论证，可以知道最多只会存在\(\log\)级别的\(\gcd\)个数。知道这个性质之后，我们在 DFS 的时候可以把父亲的链的\(gcd\)拿出来进行合并，乘上出现次数就行了。这个做法真的太神仙了。

// CF1230E.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 100100, mod = 1e9 + 7;

int head[MAX_N], current;
ll val[MAX_N], ans, n;
map<ll, ll> mps[MAX_N];

struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

ll gcd(ll a, ll b)
{
    if (a == 0 && b == 0)
        return 0;
    if (a == 0)
        return b;
    return b == 0 ? a : gcd(b, a % b);
}

void dfs(int u, int fa)
{
    for (map<ll, ll>::iterator it = mps[fa].begin(); it != mps[fa].end(); it++)
        mps[u][gcd(val[u], it->first)] += it->second;
    mps[u][val[u]]++;
    for (map<ll, ll>::iterator it = mps[u].begin(); it != mps[u].end(); it++)
        ans = (1LL * ans + 1LL * it->second * it->first % mod) % mod;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            dfs(edges[i].to, u);
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &val[i]);
    for (int i = 1, u, v; i <= n - 1; i++)
        scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
    dfs(1, 0), printf("%lld", ans);
    return 0;
}

F – Konrad and Company Evaluation

题意翻译过来就是动态维护长度为三的链的个数。当然，给你的询问肯定会简化一点：所有的边的方向都取决于边两点动态点权的大小关系。官方题解用了一种非常日狗的方式证明了，这样的边比较少，所以可以直接暴力。真的是日狗。

// CF1230F.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 1e5 + 200;

list<int> l2r[MAX_N];
list<int> r2l[MAX_N];

int n, indeg[MAX_N], outdeg[MAX_N], salaries[MAX_N], m, q;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        if (u < v)
            swap(u, v);
        r2l[u].push_back(v), l2r[v].push_back(u);
        outdeg[v]++, indeg[u]++;
    }
    for (int i = 1; i <= n; i++)
        salaries[i] = i;
    ll ans = 0;
    for (int i = 1; i <= n; i++)
        for (list<int>::iterator it = r2l[i].begin(); it != r2l[i].end(); it++)
            ans += indeg[*it];
    printf("%lld\n", ans);
    scanf("%d", &q);
    int days = 0;
    while (q--)
    {
        int u;
        days++, scanf("%d", &u), salaries[u] = n + days;
        ll flip_num = 0;
        for (list<int>::iterator it = l2r[u].begin(); it != l2r[u].end();)
            // if there is a edge needs flipping;
            if (salaries[u] > salaries[*it])
            {
                int id = *it;
                flip_num++;
                indeg[id]--;
                ans -= outdeg[id] - indeg[id];
                outdeg[id]++;
                list<int>::iterator backup = it;
                backup++, l2r[u].erase(it), it = backup;
                l2r[id].push_back(u);
            }
            else
                it++;
        ans += 1LL * (outdeg[u] - flip_num) * (indeg[u] + flip_num) - (1LL * indeg[u] * outdeg[u]);
        indeg[u] += flip_num, outdeg[u] -= flip_num;
        printf("%lld\n", ans);
    }
    return 0;
}

线性时间建二叉树

一种方式是建笛卡尔树，但是我不会。另一种方式是「双端队列」：从后往前进行加边，且这个二叉树的中序遍历一定，所以合并的时候也要把序号的进行合并。可以看这道题：P1377 [TJOI2011]树的序。

// P1377.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200;

int seq[MAX_N], pos[MAX_N], lft[MAX_N], rig[MAX_N], n, lson[MAX_N], rson[MAX_N];

void dfs(int u)
{
    if (u == 0)
        return;
    printf("%d ", u);
    dfs(lson[u]), dfs(rson[u]);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &seq[i]), pos[seq[i]] = i;
        lft[i] = i - 1, rig[i] = i + 1;
    }
    for (int i = n; i >= 2; i--)
    {
        //  connect to the prev or back one;
        int l = lft[seq[i]], r = rig[seq[i]];
        if (pos[l] > pos[r])
            rson[l] = seq[i];
        else
            lson[r] = seq[i];
        lft[r] = l, rig[l] = r;
    }
    dfs(seq[1]);
    return 0;
}

出行预算

这道题也算是贪心的好题了。首先做好预处理，处理好\(n\)段的距离之类的东西。之后，我们一段一段来走：首先，我们要维护一个可以始终提供便宜油的节点，然后也需要知道之前在油箱里放了多少可供现在使用的油；知道这些之后，我们就可以贪心取，然后用线段树来维护油箱即可。

// B.cpp
#include <bits/stdc++.h>
#define pr pair<double, int>
using namespace std;

const int MAX_N = 500100;

int n;
double D, C, d0, nodes[MAX_N << 2], tag[MAX_N << 2], di[MAX_N], pi[MAX_N], segs[MAX_N];

#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)

void pushdown(int p)
{
    if (tag[p] != 0)
    {
        nodes[lson] += tag[p], nodes[rson] += tag[p];
        tag[lson] += tag[p], tag[rson] += tag[p];
        tag[p] = 0;
    }
}

void pushup(int p)
{
    nodes[p] = nodes[lson] + nodes[rson];
}

void update(int ql, int qr, int l, int r, int p, double val)
{
    if (ql <= l && r <= qr)
        return (void)(nodes[p] += val, tag[p] += val);
    pushdown(p);
    if (ql <= mid)
        update(ql, qr, l, mid, lson, val);
    if (mid < qr)
        update(ql, qr, mid + 1, r, rson, val);
    pushup(p);
}

double query(int ql, int qr, int l, int r, int p)
{
    if (ql <= l && r <= qr)
        return nodes[p];
    double ret = 0;
    if (ql <= mid)
        ret = max(ret, query(ql, qr, l, mid, lson));
    if (mid < qr)
        ret = max(ret, query(ql, qr, mid + 1, r, rson));
    return ret;
}

#undef lson
#undef rson
#undef mid

int main()
{
    scanf("%d%lf%lf%lf", &n, &D, &C, &d0);
    for (int i = 1; i <= n; i++)
        scanf("%lf%lf", &di[i], &pi[i]);
    for (int i = 1; i <= n - 1; i++)
        segs[i] = di[i + 1] - di[i];
    segs[n] = D - di[n];
    priority_queue<pr> pq;
    int lastpos = 0;
    double ans = 0;
    for (int i = 1; i <= n; i++)
    {
        pq.push(make_pair(-pi[i], i));
        double need = segs[i] / d0;
        while (need > 0)
        {
            if (pq.empty())
                puts("Poor Congcong"), exit(0);
            int pos = pq.top().second;
            if (pos <= lastpos)
            {
                pq.pop();
                continue;
            }
            double lft = C - query(pos, i, 1, n, 1);
            if (lft <= 0)
            {
                pq.pop();
                break;
            }
            if (need - lft <= 0)
            {
                ans += need * pi[pos];
                update(pos, i, 1, n, 1, need);
                need = 0;
            }
            else
            {
                ans += lft * pi[pos];
                need -= lft, update(pos, i, 1, n, 1, lft);
                lastpos = max(lastpos, pos);
                pq.pop();
            }
        }
    }
    printf("%.2lf", ans);
    return 0;
}

收作业

考场上切掉了。首先，最短路一定是不降路径；其次，不需要考虑具体的转移方式，所以可以直接找域内的点进行转移。二位偏序搞掉（第一次在考场上写这种玩意）。

// homework.cpp
#include <bits/stdc++.h>

using namespace std;

inline int read()
{
    int X = 0, w = 0;
    char ch = 0;
    while (!isdigit(ch))
    {
        w |= ch == '-';
        ch = getchar();
    }
    while (isdigit(ch))
        X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
    return w ? -X : X;
}

const int MAX_N = 2e5 + 200;

struct point
{
    int x, y, val, id;
    bool operator<(const point &pt) const { return x < pt.x || (x == pt.x && y < pt.y); }
} pts[MAX_N];

int n, m, k, dp[MAX_N], tree[MAX_N << 1], upper;
vector<int> mpx, mpy;

inline int lowbit(int x) { return x & -x; }

void update(int x, int d)
{
    if (x == 0)
        return;
    for (; x <= upper; x += lowbit(x))
        tree[x] = max(tree[x], d);
}

int query(int x)
{
    int ans = 0;
    for (; x > 0; x -= lowbit(x))
        ans = max(tree[x], ans);
    return ans;
}

int main()
{
    freopen("homework.in", "r", stdin);
    freopen("homework.out", "w", stdout);
    n = read(), m = read(), k = read();
    for (int i = 1; i <= k; i++)
    {
        pts[i].x = read(), pts[i].y = read(), pts[i].val = read(), pts[i].id = i;
        mpx.push_back(pts[i].x), mpy.push_back(pts[i].y);
    }
    pts[k + 1] = point{n - 1, m - 1, 0, k + 1}, k++;
    mpx.push_back(n - 1), mpy.push_back(m - 1);
    sort(mpx.begin(), mpx.end()), sort(mpy.begin(), mpy.end());
    mpx.erase(unique(mpx.begin(), mpx.end()), mpx.end());
    mpy.erase(unique(mpy.begin(), mpy.end()), mpy.end());
    upper = mpy.size();
    for (int i = 1; i <= k; i++)
    {
        pts[i].x = lower_bound(mpx.begin(), mpx.end(), pts[i].x) - mpx.begin() + 1;
        pts[i].y = lower_bound(mpy.begin(), mpy.end(), pts[i].y) - mpy.begin() + 1;
    }
    sort(pts + 1, pts + 1 + k);
    for (int i = 1; i <= k; i++)
    {
        int ans = query(pts[i].y);
        dp[pts[i].id] = ans + pts[i].val;
        update(pts[i].y, dp[pts[i].id]);
    }
    printf("%d", dp[k]);
    return 0;
}