专栏文章

MX Day 12

OOIer_ACMer
生活·游记参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mino7pmc
此快照首次捕获于
2025/12/02 05:38
3 个月前
此快照最后确认于
2025/12/02 05:38
3 个月前
查看原文

T1：

1759799690342.png
60分做法（自己想的）：
首先，我们从大往小考虑右边的数，选定后，再将视角迁移至左边，也是从大往小选择一个数依次减去，直到减为0，不过时间复杂度是n^2*logn，会超时，只能得60分。
muan分做法：
我们非常显然的发现，我们的答案就是{suma, sumb, max(ai)+max(bi)}，其实证明方法是网络流，而且金牌巨佬的证法还是太高深莫测了，但是在手玩样例时我们也不难发现这个特点，尤其是样例二，只不过，敢于尝试这种方法，需要莫大的勇气与毅力。

code：

CPP
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n, q;
ll sa[200005], sb[200005], a[200005], b[200005];
int sta[21][200005], stb[21][200005], lg[200005];
int Maxa(int x, int y)
{
    return a[x] > a[y] ? x : y;
}
int Maxb(int x, int y)
{
    return b[x] > b[y] ? x : y;
}
int Getmaxa(int l, int r)
{
    int len = lg[r - l + 1];
    return Maxa(sta[len][l], sta[len][r - (1 << len) + 1]);
}
int Getmaxb(int l, int r)
{
    int len = lg[r - l + 1];
    return Maxb(stb[len][l], stb[len][r - (1 << len) + 1]);
}
int main()
{
    freopen("max.in", "r", stdin);
    freopen("max.out", "w", stdout);
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]), sa[i] = sa[i - 1] + a[i];
    for (int i = 1; i <= n; i++)
        scanf("%lld", &b[i]), sb[i] = sb[i - 1] + b[i];
    for (int i = 1; i <= n; i++)
        sta[0][i] = stb[0][i] = i;
    for (int i = 2; i <= n; i++)
        lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= lg[n]; i++)
    {
        for (int j = 1; j + (1 << i) - 1 <= n; j++)
        {
            sta[i][j] = Maxa(sta[i - 1][j], sta[i - 1][j + (1 << (i - 1))]);
            stb[i][j] = Maxb(stb[i - 1][j], stb[i - 1][j + (1 << (i - 1))]);
        }
    }
    while (q--)
    {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        ll out = max(sa[r1] - sa[l1 - 1], sb[r2] - sb[l2 - 1]);
        int p1 = Getmaxa(l1, r1);
        out = max(out, a[p1] + b[l2 + (p1 - l1)]);
        int p2 = Getmaxb(l2, r2);
        out = max(out, b[p2] + a[l1 + (p2 - l2)]);
        printf("%lld\n", out);
    }
    return 0;
}

T2：

1759806945433.png
60分：
dij+n^2暴力，不过p=1的情况要用floyed另外考虑（如下）
1759806920404.png
muan分：
  1. 我们可以考虑线段树分治的做法，我们首先将一个区间[l, r]定义为f[id~][x][y]的存储数组，表示没有[l, r]范围内的数的情况下的邻接矩阵长啥样；
  2. 之后，我们就要进行关键的pushdown操作，我们首先要知道两个线段树数组的差别是什么：不同的删数区间，所以，我们在更新左儿子时只用将右儿子的那些点的距离更新到左儿子中，也就是连边跑最短路，之后更新邻接矩阵就可以了。

code：

CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    register int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
#define ls k << 1
#define rs k << 1 | 1
int n, q;
int mp[309][309];
int f[1025][309][309];
int dis1[1000009];
bool vis[1025][309], vis1[309];
int ps[1000009];
int id[1000009];
void add(int id, int x)
{
    if (vis[id][x])
    {
        return;
    }
    int tt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (vis[id][i])
        {
            ps[++tt] = i, dis1[i] = mp[i][x], vis1[i] = 0;
            // cout << "add " << i << " " << x << " " << dis1[i] << endl;
        }
    }
    for (int T = 1; T <= tt; T++)
    {
        int k = -1;
        for (int i = 1; i <= tt; i++)
        {
            if (vis1[ps[i]])
            {
                continue;
            }
            if (k == -1 || dis1[k] > dis1[ps[i]])
            {
                k = ps[i];
            }
        }
        if (k == -1)
        {
            break;
        }
        vis1[k] = 1, f[id][k][x] = dis1[k];
        for (int i = 1; i <= tt; i++)
        {
            dis1[ps[i]] = min(dis1[ps[i]], dis1[k] + mp[ps[i]][k]);
        }
    }
    for (int i = 1; i <= tt; i++)
    {
        dis1[ps[i]] = mp[x][ps[i]], vis1[ps[i]] = 0;
    }
    for (int T = 1; T <= tt; ++T)
    {
        int p = -1;
        for (int i = 1; i <= tt; i++)
        {
            if (vis1[ps[i]])
            {
                continue;
            }
            if (p == -1 || dis1[p] > dis1[ps[i]])
            {
                p = ps[i];
            }
        }
        if (p == -1)
        {
            break;
        }
        vis1[p] = 1, f[id][x][p] = dis1[p];
        for (int i = 1; i <= tt; ++i)
        {
            dis1[ps[i]] = min(dis1[ps[i]], dis1[p] + mp[p][ps[i]]);
        }
    }
    for (int i = 1; i <= tt; i++)
    {
        for (int j = 1; j <= tt; j++)
        {
            f[id][ps[i]][ps[j]] = min(f[id][ps[i]][ps[j]], f[id][ps[i]][x] + f[id][x][ps[j]]);
        }
    }
    vis[id][x] = 1;
}
void solve(int k, int l, int r)
{
    if (l == r)
    {
        id[l] = k;
        return;
    }
    int mid = (l + r) >> 1;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            f[ls][i][j] = f[rs][i][j] = f[k][i][j];
        }
        vis[ls][i] = vis[rs][i] = vis[k][i];
    }
    for (int i = l; i <= r; ++i)
    {
        // cout << "i=" << i << " mid=" << mid << endl;
        add((i <= mid ? rs : ls), i);
    }
    solve(ls, l, mid);
    solve(rs, mid + 1, r);
}
signed main()
{
    freopen("distance.in", "r", stdin);
    freopen("distance.out", "w", stdout);
    n = read();
    q = read();
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            mp[i][j] = read();
        }
    }
    solve(1, 1, n);
    for (int i = 1; i <= q; i++)
    {
        int s, p, t;
        s = read();
        t = read();
        p = read();
        // cout << "s=" << s << " t=" << t << " p=" << p << endl;
        cout << f[id[p]][s][t] << endl;
    }
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...