「杂题集」- 2019年9月25日

[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)) \]

继续阅读「杂题集」- 2019年9月25日

[Fortuna OJ]Aug 2nd – Group A 解题报告 / 集训队互测 2012 [李超]

A – Attack

这道题在 JZOJ 上面开 10s,遂 AC。

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

using namespace std;

const int MAX_N = 60100;

struct point
{
    int x, y, prop, id;
    bool operator<(const point &pt) const { return prop < pt.prop; }
} nodes[MAX_N], *cur[MAX_N];

int n, m;
char opt[10];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d", &nodes[i].x, &nodes[i].y, &nodes[i].prop), nodes[i].id = i;
    sort(nodes + 1, nodes + 1 + n);
    for (int i = 1; i <= n; i++)
        cur[nodes[i].id] = &nodes[i];
    while (m--)
    {
        scanf("%s", opt + 1);
        int x, y, x_, y_, k;
        if (opt[1] == 'Q')
        {
            scanf("%d%d%d%d%d", &x, &y, &x_, &y_, &k);
            bool flag = false;
            for (int i = 1; i <= n; i++)
                if (nodes[i].x <= max(x, x_) && nodes[i].x >= min(x, x_) && nodes[i].y <= max(y, y_) && nodes[i].y >= min(y, y_))
                {
                    k--;
                    if (k == 0)
                    {
                        printf("%d\n", nodes[i].prop), flag = true;
                        break;
                    }
                }
            if (!flag)
                puts("It doesn't exist.");
        }
        else
        {
            scanf("%d%d", &x, &y), x++, y++;
            swap(cur[x]->x, cur[y]->x), swap(cur[x]->y, cur[y]->y);
            swap(cur[x]->id, cur[y]->id), swap(cur[x], cur[y]);
        }
    }
    return 0;
}

继续阅读[Fortuna OJ]Aug 2nd – Group A 解题报告 / 集训队互测 2012 [李超]

[Fortuna OJ]Jul 5th – Group A 解题报告 / 集训队互测 2013

A – 家族

这道题真的是送分题(快要想出来直接暴力枚举+并查集的时候去看了题解,最后发现就是这么 sb)。

考虑枚举频段区间\([L, R]\)(将边进行排序,确定下界之后再枚举上界),这个地方是\(O(m^2)\)的。每次枚举下界的时候都要初始化并查集,然后合并两个集合的时候按照大小来修改答案就行了。

继续阅读[Fortuna OJ]Jul 5th – Group A 解题报告 / 集训队互测 2013