Kalorona

「Fortuna OJ」Jul 6th – Group B 解题报告

A – 调整 Tweak

这道题我在考场上打了一个错解，还骗到了 30 分。

正常的思路是：在最短路图上找到几个边进行修改。然而，最优的解决方案并不一定出现在最短路图上的边上，也可以通过修改次优边进行解决。所以，这道题其实跟最短路没什么太大关系，即使后面会用到 Djisktra 来求最短路。

我们可以把一个\(G(V, E), |V| = n, |E| = m\)复制\(n\)份，然后对于第\(k\)份图中的有向边\((u_k, v_k, w_k)\)，可以生成一个副本来连接下一层的目标点，也就是每一条边会派生出\((u_k, v_{k + 1}, 0)\)，当最后求最短路时，经过这样的一条边可以被认为是修改一条边，且，这个边是单向向下的，所以不会出现同一层修改多次的情况。最后只需要求这张图的最短路，然后判定满足\(dist[n_k] \leq c\)的最小\(k\)就行了。

Continue reading →

「Fortuna OJ」Feb 15th – Group B 解题报告

A – 魏传之长坂逆袭

一道水的不得了的题目，两边线性的深搜合并距离即可。

// A.cpp
// Complexity: O(n)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 500200;
int head[MAX_N], current, n, tmpx, tmpy, paths[MAX_N];
ll tmpz, goal = 0, answer;
struct edge
{
    int to, nxt;
    ll weight;
} edges[MAX_N << 1];
void addpath(int src, int dst, ll weight)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    edges[current].weight = weight, head[src] = current++;
}
void dfs_1(int u, int fa, ll dis)
{
    ll ans = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            dfs_1(edges[i].to, u, dis + edges[i].weight), ans = max(paths[edges[i].to] + edges[i].weight, ans);
    goal = max(goal, dis), paths[u] = ans;
}
void tune(int u, int fa)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            tune(edges[i].to, u), answer += paths[u] - paths[edges[i].to] - edges[i].weight;
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
        scanf("%d%d%lld", &tmpx, &tmpy, &tmpz), addpath(tmpx, tmpy, tmpz), addpath(tmpy, tmpx, tmpz);
    dfs_1(1, 0, 0), tune(1, 0);
    printf("%lld", answer);
    return 0;
}

B – 蜀传之单刀赴会

这道题有点失误，写了一个暴力忘记判断不能超过\(t\)这个限制然后就送掉了 30 分，暴力状压 DFS 可拿到 60 分。正解其实就是最短路缩图 + 状压 DP，方程非常好想，设\(f[stat][i]\)为要经过\(stat\)集合中的点且最后一次经过了点\(i\)的最短路径，显然可以得出：

\[ f[stat \cup j][j] = min\{ f[stat][i] + map[i][j] \}, i \in stat, j \not\in stat \]

// B.cpp
// Complexity: O(n log m + 2^(k+1)*k^2) = O(2^(k+1)*k^2)
#include <bits/stdc++.h>
#define ll long long
#define pr pair<ll, int>
using namespace std;
const int MAX_N = 10010, MAX_M = 50010;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m, k, t, head[MAX_N], current, tmpx, tmpy, tmpz, mp[20];
ll dist[20][MAX_N], neomap[20][20], f[(1 << 17)][20];
bool vis[MAX_N];
struct edge
{
    int to, nxt, weight;
} edges[MAX_M << 1];
void addpath(int src, int dst, int weight)
{
    edges[current].to = dst, edges[current].weight = weight;
    edges[current].nxt = head[src], head[src] = current++;
}
int getOnBit(int num)
{
    int ans = 0;
    while (num)
        if (num & 1)
            ans++, num >>= 1;
        else
            num >>= 1;
    return ans;
}
void djisktra(int u)
{
    memset(vis, false, sizeof(vis));
    priority_queue<pr> q;
    int org = mp[u];
    q.push(make_pair(0, org)), dist[u][org] = 0;
    while (!q.empty())
    {
        int curt = q.top().second;
        q.pop();
        if (vis[curt])
            continue;
        vis[curt] = true;
        for (int i = head[curt]; i != -1; i = edges[i].nxt)
        {
            int to = edges[i].to;
            if (dist[u][to] > dist[u][curt] + edges[i].weight)
                dist[u][to] = dist[u][curt] + edges[i].weight, q.push(make_pair(-dist[u][to], to));
        }
    }
}
int main()
{
    memset(dist, 0x3f, sizeof(dist)), memset(head, -1, sizeof(head));
    scanf("%d%d%d%d", &n, &m, &k, &t);
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d", &tmpx, &tmpy, &tmpz), addpath(tmpx, tmpy, tmpz), addpath(tmpy, tmpx, tmpz);
    for (int i = 0; i < k; i++)
        scanf("%d", &tmpx), mp[i] = tmpx;
    mp[k] = n, mp[k + 1] = 1;
    for (int i = 0; i <= k + 1; i++)
        djisktra(i);
    for (int i = 0; i <= k + 1; i++)
        for (int j = 0; j <= k + 1; j++)
            neomap[i][j] = dist[i][mp[j]];
    memset(f, 0x3f, sizeof(f));
    for (int i = 0; i <= k; i++)
        for (int j = 0; j <= k; j++)
            f[(1 << i)][j] = neomap[k + 1][i];
    for (int stat = 1; stat < (1 << (k + 1)); stat++)
        for (int i = 0; i <= k; i++)
            for (int j = 0; j <= k; j++)
                if ((((stat >> i) & 1) == 1) && (((stat >> j) & 1) == 0))
                    f[stat | (1 << j)][j] = min(f[stat | (1 << j)][j], f[stat][i] + neomap[i][j]);
    ll ans1 = 0, ans2 = INF;
    for (int stat = 1; stat < (1 << (k + 1)); stat++)
    {
        if (getOnBit(stat) < ans1 || ((stat >> k) & 1) == 0)
            continue;
        ll tmp = INF;
        for (int i = 0; i <= k; i++)
            if (((stat >> i) & 1) == 1)
                tmp = min(tmp, f[stat][i] + neomap[i][k + 1]);
        if (tmp != INF && tmp <= t)
            ans2 = (ans1 < getOnBit(stat)) ? tmp : min(ans2, tmp), ans1 = getOnBit(stat);
    }
    printf("%lld %lld", ans1 - 1, ans2);
    return 0;
}

最后一直卡在 80 分，发现忘了判断\(t\)的限制，凉飞了。

C – 吴传之火烧连营

心态崩了，这道题本身 trie 树空间开对了，最后标记的空间忘了开大就凉了，亏我还特意计算了要有多少各节点。

这道题就是一道傻* Trie 树摸板题，贪心沿着树走即可。

// C.cpp
// Complexity: O(32n + 32m)
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 100;
int trie[MAX_N * 64][2], mark[MAX_N * 64], tot = 1, tmp;
void insert(int num, int mk)
{
    int p = 1;
    for (int i = 31; i >= 0; i--)
    {
        int bit = (num >> i) & 1;
        if (trie[p][bit] == 0)
            trie[p][bit] = ++tot;
        p = trie[p][bit];
    }
    mark[p] = mk;
}
int query(int num)
{
    int p = 1;
    for (int i = 31; i >= 0; i--)
    {
        int bit = (num >> i) & 1, desire = bit ^ 1;
        if (trie[p][desire] != 0)
            p = trie[p][desire];
        else
            p = trie[p][bit];
    }
    return mark[p];
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &tmp), insert(tmp, i);
    for (int i = 1; i <= m; i++)
        scanf("%d", &tmp), printf("%d\n", query(tmp));
    return 0;
}

P1522:牛的旅行 Cow Tours 题解

主要思路

先用 Floyed 算出初始最短路，然后再枚举两个不在同一连通块内的点进行连边并且更新当前最短路然后用 DFS 求出最长链。这道题我的垃圾做法没有\(O2\)无法 AC，时间复杂度\(O(n^4)\)。（这可能是我写过最慢的代码了）

// P1522.cpp
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#define pr pair<int, int>
#define dpr pair<double, int>
using namespace std;
const int MX_N = 200, INF = 0x3f3f3f3f;
int n;
char mat[MX_N][MX_N];
double G[MX_N][MX_N], ripe[MX_N][MX_N];
pr points[MX_N];
bool vis[MX_N];
double pow2(double num) { return num * num; }
double getDist(pr a, pr b) { return sqrt(pow2(a.first - b.first) + pow2(a.second - b.second)); }
double dfs(int u)
{
    if (vis[u])
        return 0;
    vis[u] = true;
    double res = 0;
    for (int i = 1; i <= n; i++)
        if (ripe[u][i] != INF && i != u)
            res = max(res, max(ripe[u][i], dfs(i)));
    return res;
}
int main()
{
    scanf("%d", &n);
    int x, y;
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &x, &y), points[i] = make_pair(x, y);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", mat[i] + 1);
        for (int j = 1; j <= n; j++)
            if (mat[i][j] == '1')
                G[i][j] = getDist(points[i], points[j]);
            else if (i != j)
                G[i][j] = (double)INF;
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
    double ans = (double)INF;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            if (i != j && G[i][j] == INF)
            {
                memcpy(ripe, G, sizeof(G));
                memset(vis, false, sizeof(vis));
                ripe[i][j] = ripe[j][i] = getDist(points[i], points[j]);
                for (int a = 1; a <= n; a++)
                    for (int b = 1; b <= n; b++)
                        ripe[a][b] = min(ripe[a][b], ripe[a][i] + ripe[i][j] + ripe[j][b]);
                double res = dfs(i);
                ans = min(ans, res);
            }
    printf("%.6f", ans);
    return 0;
}