A – 数学题

这道题二次函数的暴力分有 60 分，正解来自于论文。

这道题的主要是利用了一个结论，并且运用了辗转相除法的一种思想来对问题进行化简。首先，我们把向量调整至同向，且使\(|\vec{a}| < |\vec{b}|\)，然后再来推导一个结论：

结论   对于\(\vec{a}, \vec{b}\)，如果\(<\vec{a}, \vec{b}> \geq \frac{\pi}{3}\)，那么答案就是\(min\{|\vec{a}|, |\vec{b}|\}\)。

这个结论的证明参见《欧几里得算法的应用》。所以，我们就可以大概知道，我们可以将较长的向量分解：\(\vec{b} = k\vec{a} + \vec{b’} \)。由于我们知道，这道题可以笑掉这个\(k \vec{a}\)，所以就可以用辗转相除法的套路进行处理。具体见代码：

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

using namespace std;

void solve(ll a, ll b, ll c, ll d, ll &x, ll &y)
{
    ll dot = a * c + b * d;
    if (dot < 0)
    {
        solve(a, b, -c, -d, x, y);
        y = -y;
        return;
    }
    ll lenA = a * a + b * b, lenB = c * c + d * d;
    if (lenA > lenB)
        return solve(c, d, a, b, y, x);
    if (((dot * dot) << 2) <= lenA * lenB)
    {
        x = 1, y = 0;
        return;
    }

    ll k = dot / lenA;

    if (dot + dot <= lenA * (k + k + 1))
    {
        solve(a, b, c - k * a, d - k * b, x, y);
        x -= k * y;
    }
    else
    {
        solve(a, b, c - (k + 1) * a, d - (k + 1) * b, x, y);
        x -= (k + 1) * y;
    }
}

ll pow2(ll bas) { return bas * bas; }

int main()
{
    int x1, y1, x2, y2;
    ll ans1, ans2;
    while (scanf("%d%d%d%d", &x1, &y1, &x2, &y2) != EOF)
        solve(x1, y1, x2, y2, ans1, ans2), printf("%lld\n", pow2(ans1 * x1 + ans2 * x2) + pow2(ans1 * y1 + ans2 * y2));
    return 0;
}

B – 挖宝藏

我们把所有的块都变成点，发现每一层路径图一定是树状的，每一层的树会有交集点。且发现宝藏的数量非常少，可以想到 Steiner Tree 。这个东西可以解决关键点最小生成树的问题，这样，我们就进行状压和 SPFA，完成这道很好的题目。

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

using namespace std;

const int MAX_N = 15;

const int dirx[4] = {1, 0, -1, 0}, diry[4] = {0, 1, 0, -1};

int weight[MAX_N][MAX_N][MAX_N], h, n, m, ki[MAX_N], tag[MAX_N][MAX_N][MAX_N];
int f[MAX_N][MAX_N][1 << MAX_N], g[MAX_N][MAX_N][1 << MAX_N];
bool vis[MAX_N][MAX_N][1 << MAX_N];
struct node
{
    int x, y, status;
};
queue<node> q;

int main()
{
    /*
	freopen("treasure.in", "r", stdin);
	freopen("treasure.out", "w", stdout);
    */
    scanf("%d%d%d", &h, &n, &m);
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= m; k++)
                scanf("%d", &weight[i][j][k]);

    for (int i = 1; i <= h; i++)
    {
        scanf("%d", &ki[i]);
        for (int k = 1, x, y; k <= ki[i]; k++)
            scanf("%d%d", &x, &y), tag[i][x][y] = k;
    }

    int ans = 0x3f3f3f3f;

    for (int i = 1; i <= h; i++)
    {
        memcpy(g, f, sizeof(g));
        memset(f, 60, sizeof(f)), memset(vis, false, sizeof(vis));
        int INF = f[0][0][0];
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= m; k++)
            {
                f[j][k][1] = g[j][k][(1 << (ki[i - 1] + 1)) - 1] + weight[i][j][k];
                // printf("DBG : making f[%d][%d][%d] to %d, %d\n", j, k, 1, g[j][k][(1 << (ki[i - 1] + 1)) - 1] + weight[i][j][k], weight[i][j][k]);
                if (tag[i][j][k])
                {
                    f[j][k][1 << (tag[i][j][k])] = weight[i][j][k];
                    // printf("DBG : Tag[%d][%d][%d] is activated, f[%d][%d][%d] is %d\n", i, j, k, j, k, 1 << (tag[i][j][k]), f[j][k][1 << (tag[i][j][k])]);
                }
            }
        for (int stat = 1; stat < (1 << (ki[i] + 1)); stat++)
        {
            while (!q.empty())
                q.pop();
            for (int j = 1; j <= n; j++)
                for (int k = 1; k <= m; k++)
                {
                    for (int x = stat & (stat - 1); x; x = stat & (x - 1))
                        if (f[j][k][x] + f[j][k][stat ^ x] - weight[i][j][k] < f[j][k][stat])
                            f[j][k][stat] = f[j][k][x] + f[j][k][stat ^ x] - weight[i][j][k];
                    if (f[j][k][stat] < INF)
                        vis[j][k][stat] = true, q.push(node{j, k, stat});
                }
            while (!q.empty())
            {
                node curt = q.front();
                q.pop();
                int x = curt.x, y = curt.y, status = curt.status;
                for (int dir = 0; dir < 4; dir++)
                {
                    int dx = x + dirx[dir], dy = y + diry[dir];
                    if (dx != 0 && dy != 0 && dx <= n && dy <= m)
                    {
                        if (f[x][y][status] + weight[i][dx][dy] < f[dx][dy][status])
                        {
                            f[dx][dy][status] = f[x][y][status] + weight[i][dx][dy];
                            if (!vis[dx][dy][status])
                                vis[dx][dy][status] = true, q.push(node{dx, dy, status});
                        }
                    }
                }
                vis[x][y][status] = false;
            }
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            ans = min(ans, f[i][j][(1 << (ki[h] + 1)) - 1]);
    printf("%d", ans);
    return 0;
}

C – 理想城市

这道题也是一道很好的题目。

我们先算纵向的贡献，也就是算点与点之间纵向路径之和。根据题目的信息，我们可以试图把一长条连续的区块缩成一个点，然后上下之间有交集的点进行连边，可知对于一条边，他的贡献就是：

\[ E(u, v), ans(E(u, v)) = val[u] * (global – val[v]), dep[v] < dep[u] \]

也就是，两个大子树的内部权值之积。做列与列时就把\(x, y\)交换下即可。

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

using namespace std;

const int MAX_N = 2e5 + 2000, mod = 1e9;

int head[MAX_N], current, n, tot;
ll global_sum = 0, ans = 0;
struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

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

struct node
{
    int x, y1, y2, val;
} vec[MAX_N];

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

void swap()
{
    for (int i = 1; i <= n; i++)
        swap(pts[i].x, pts[i].y);
}

void build_tree()
{
    memset(head, -1, sizeof(head));
    current = 0;
    sort(pts + 1, pts + 1 + n);
    tot = 0;
    int cursor = 1;
    while (cursor <= n)
    {
        int nd = ++tot;

        int endpoint = cursor + 1;
        while (pts[endpoint].x == pts[cursor].x && pts[endpoint].y == pts[endpoint - 1].y + 1)
            endpoint++;
        endpoint--;

        vec[tot] = (node{pts[cursor].x, pts[cursor].y, pts[endpoint].y, endpoint - cursor + 1});
        cursor = endpoint + 1;
    }

    int cursor1 = 0, cursor2 = 1;
    while (cursor2 <= tot)
    {
        while (vec[cursor1].x < vec[cursor2].x - 1 || (vec[cursor1].x == vec[cursor2].x - 1 && vec[cursor1].y2 < vec[cursor2].y1))
            cursor1++;
        bool flag = false;
        while (vec[cursor1].x == vec[cursor2].x - 1 && vec[cursor1].y1 <= vec[cursor2].y2)
        {
            flag = true;
            addpath(cursor1, cursor2), addpath(cursor2, cursor1);
            cursor1++;
        }
        if (flag)
            cursor1--;
        cursor2++;
    }
}

ll dfs(int u, int fat)
{
    ll answer = vec[u].val;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fat)
            (answer += dfs(edges[i].to, u)) %= mod;
    ans = (ans + answer * (global_sum - answer)) % mod;
    return answer;
}

ll calc()
{
    global_sum = 0, ans = 0;
    for (int i = 1; i <= tot; i++)
        (global_sum += vec[i].val) %= mod;
    dfs(1, 0);
    return ans;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &pts[i].x, &pts[i].y);
    ll answer = 0;
    build_tree(), answer += calc();
    answer %= mod;
    swap();
    build_tree(), answer += calc();
    answer %= mod;
    printf("%lld", answer);
    return 0;
}