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;
}

B – Contra

这道题是一道很有意思的概率 DP 题，需要先二分出一个概率\(p\)，再用期望 DP 加上矩阵快速幂进行优化。

我们先来考虑正常 DP 的写法。考虑一个状态\(g[i][j][k]\)代表到达第\(i\)局游戏、剩下\(j\)条命且连续\(k\)局这样的局势的概率，转移非常的好想：

\[ \begin{cases} g[i + 1][min(j + 1, Q)][min(k + 1, R)] += g[i][j][k] \times p \\ g[i + 1][j – 1][0] += g[i][j][k] \times (1 – p) \end{cases} \]

然而在这里\(g\)仅仅是概率，我们要求的是期望：我们可以发现，向\(answer\)中直接累加每个状态对答案的「单独贡献」即可，也就是：

\[ answer += g[i][j][k] \times k \]

这样就可以拿到 50 分了。接下来的 50 分则需要用非常厉害的矩阵快速幂了。我们发现，转移中，每一个状态只跟\(i-1\)有关，所以可以使用矩阵快速幂；且，\(j, k\)组合起来的情况很少，所以我们可以直接暴力压缩\(j, k\)的状态到一个数组\(mapper[j][k] = zippedCode\)，最后发现不超过\(100\)，所以可以直接过\(O(n^3)\)的矩阵乘法。

现在考虑三个矩阵：\(f\)是最终答案需要用的矩阵，\(a_1\)是概率矩阵，\(a_2\)是贡献矩阵，那么显然，\(a_1 * a_2\)就是期望矩阵。

回顾一下矩阵乘法：

\[ matrix[i][j] = \sum_{k = 1}^m{matrix_{size}} f[i][k] * g[k][j] \]

发现这个很像转移的形式：\(i\)行表示原来的\(S_i\)（状态），\(j\)列表示现在要转移到的\(S_j\)（状态），那么矩阵中第\(i\)行\(j\)列的元素代表的就是从\(S_i\)到\(S_j\)的概率。这个概率连续乘起来就可以得到第\(n\)轮的所有状态两两之间的概率。具体矩阵设置见代码，很好理解。

我们的初始状态是\(S = 1\)，终止状态是\(S = stat_tot\)，也就是最后一个状态。所以我们设置\(f\)的时候设置前两个状态之间直接概率为\(1\)即可。然后\(\log n\)快速幂就完了。

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

using namespace std;

const int MAX_Q = 6, MAX_R = 21;
const double eps = 1e-8;

int N, R, Q, mat_siz, stat_siz, mapper[MAX_Q][MAX_R];
ll S;

struct matrix
{
    double mat[155][155];

    void clear() { memset(mat, 0, sizeof(mat)); }
    matrix operator*(const matrix &target) const
    {
        matrix ans;
        ans.clear();
        for (int i = 1; i <= mat_siz; i++)
            for (int j = 1; j <= mat_siz; j++)
                for (int k = 1; k <= mat_siz; k++)
                    ans.mat[i][j] += mat[i][k] * target.mat[k][j];
        return ans;
    }
} f, a1, a2, b;

double DP(double p)
{
    f.clear(), a1.clear(), a1.clear();
    for (int lives = 1; lives <= Q; lives++)
        for (int conseq = 0; conseq <= R; conseq++)
            if (lives >= conseq || lives == Q)
            {
                // this is how the probability matrix is set.
                a1.mat[mapper[lives][conseq]][mapper[min(lives + 1, Q)][min(conseq + 1, R)]] = p;
                a1.mat[mapper[lives][conseq]][mapper[lives - 1][0]] = 1.0 - p;
            }
    a1.mat[stat_siz][stat_siz] = 1;
    // this is how the Expectation works.
    for (int lives = 0; lives <= Q; lives++)
        for (int conseq = 0; conseq <= R; conseq++)
            if (lives >= conseq || lives == Q)
                a2.mat[mapper[lives][conseq]][stat_siz] = conseq;
    for (int i = 1; i <= mat_siz; i++)
        a2.mat[i][i] = 1;
    b = a1 * a2;
    f.mat[1][mapper[Q][0]] = 1;
    int tim = N;
    while (tim)
    {
        if (tim & 1)
            f = f * b;
        b = b * b;
        tim >>= 1;
    }
    return f.mat[1][stat_siz];
}

int main()
{
    scanf("%d%d%d%lld", &N, &R, &Q, &S);
    // zip the status up!
    for (int lives = 0; lives <= Q; lives++)
        for (int conseq = 0; conseq <= R; conseq++)
            if (lives >= conseq || lives == Q)
                mapper[lives][conseq] = ++stat_siz;
    // as the end status;
    ++stat_siz, mat_siz = stat_siz;
    if (DP(1.0) <= S)
        puts("Impossible.");
    else
    {
        double l = 0, r = 1.0;
        while (l < r - eps)
        {
            double mid = (l + r) / 2;
            if (DP(mid) > S)
                r = mid;
            else
                l = mid;
        }
        printf("%.6lf", l);
    }
    return 0;
}

C – Bomb

这也是一道思维上的好题目。

最大贡献的求法

我们先求最大的三点距离和。发现三个点\((x_1, y_1), (x_2, y_2), (x_3, y_3)\)最后对答案的贡献形如（长得像）：

\[ \frac{answer}{2} = \begin{cases} x_1 + y_1 – x_2 – y_3 \\ x_1 + y_1 – x_3 – y_3 \end{cases} \]

所以我们只需要维护最大最小的\(x, y\)，和最大最小的\(x + y, x – y\)就行了。

最小贡献的求法

这个就相对难了很多了。我们发现，这道题的数据范围大概可以过\(O(n \log n)\)或者是\(O(n)\)，而时间是 4s。所以我们可以考虑\(O(n \log n)\)的方式。考虑将整个点序列按\(x\)为关键字进行排序，然后上 CDQ 分治。在这里，CDQ 分治有个好处：区间长度小的时候直接暴力\(O(n^3)\)，比较好写；区间长了之后，那么再次筛选点集进行暴力的时候，因为区间长度小的已经对答案进行了贡献，所以小区间按\(y\)排序之后可能成为答案的点数非常的少，所以也是符合综合复杂度的。具体见代码。

代码

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

using namespace std;

const int MAX_N = 101000;

int n, ans = 0x3f3f3f3f;

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

bool compareByY(const point &pt1, const point &pt2) { return pt1.x < pt2.x || (pt1.x == pt2.x && pt1.y < pt2.y); }
int get(point A, point B, point C) { return max(A.x, max(B.x, C.x)) - min(A.x, min(B.x, C.x)) + max(A.y, max(B.y, C.y)) - min(A.y, min(B.y, C.y)); }

void solve(int l, int r)
{
    if (r - l < 15)
    {
        // brute force;
        for (int i = l; i <= r; i++)
            for (int j = i + 1; j <= r; j++)
                for (int k = j + 1; k <= r; k++)
                    ans = min(ans, get(pts[i], pts[j], pts[k]));
        return;
    }
    int mid = (l + r) >> 1, tot = 0;
    solve(l, mid), solve(mid, r);
    for (int i = mid; i <= r; i++)
        if (ans > abs(pts[i].x - pts[mid].x))
            tmp[++tot] = pts[i];
        else
            break;
    for (int i = mid - 1; i >= l; i--)
        if (ans > abs(pts[i].x - pts[mid].x))
            tmp[++tot] = pts[i];
        else
            break;
    sort(tmp + 1, tmp + 1 + tot);
    for (int rig = 3, lft = 1; rig <= tot; rig++)
    {
        while (abs(tmp[rig].y - tmp[lft].y) >= ans)
            lft++;
        for (int i = lft; i < rig; i++)
            for (int j = i + 1; j < rig; j++)
                ans = min(ans, get(tmp[rig], tmp[i], tmp[j]));
    }
}

int main()
{
    scanf("%d", &n);
    // largest module;
    int xmin, ymin, xmax, ymax, xpymax, xpymin, xmymax, xmymin;
    xmin = ymin = xpymin = xmymin = 1 << 30;
    xmax = ymax = xpymax = xmymax = -(1 << 30);
    for (int i = 1, x, y; i <= n; i++)
    {
        scanf("%d%d", &x, &y), swap(x, y);
        pts[i].x = x, pts[i].y = y;
        xmin = min(xmin, x), xmax = max(xmax, x);
        ymax = max(ymax, y), ymin = min(ymin, y);
        xpymax = max(xpymax, x + y), xpymin = min(xpymin, x + y);
        xmymax = max(xmymax, (x - y)), xmymin = min(xmymin, (x - y));
    }
    printf("%d\n", 2 * max(max(xpymax - xmin - ymin, xmax + ymax - xpymin), max(xmymax - xmin + ymax, xmax - xmymin - ymin)));
    // using the CDQ Division And Conquerence;
    sort(pts + 1, pts + 1 + n, compareByY);
    solve(1, n);
    printf("%d", 2 * ans);
    return 0;
}