MX Day 12
OIer_ACMer · · 生活·游记
T1：
60分做法（自己想的）：
首先，我们从大往小考虑右边的数，选定后，再将视角迁移至左边，也是从大往小选择一个数依次减去，直到减为0，不过时间复杂度是n^2*logn，会超时，只能得60分。
muan分做法：
我们非常显然的发现，我们的答案就是{suma, sumb, max(ai)+max(bi)}，其实证明方法是网络流，而且金牌巨佬的证法还是太高深莫测了，但是在手玩样例时我们也不难发现这个特点，尤其是样例二，只不过，敢于尝试这种方法，需要莫大的勇气与毅力。
code：
#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：
60分：
dij+n^2暴力，不过p=1的情况要用floyed另外考虑（如下）
muan分：
- 我们可以考虑线段树分治的做法，我们首先将一个区间[l, r]定义为f[id~][x][y]的存储数组，表示没有[l, r]范围内的数的情况下的邻接矩阵长啥样；
- 之后，我们就要进行关键的pushdown操作，我们首先要知道两个线段树数组的差别是什么：不同的删数区间，所以，我们在更新左儿子时只用将右儿子的那些点的距离更新到左儿子中，也就是连边跑最短路，之后更新邻接矩阵就可以了。
code：
#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;
}