[Fortuna OJ]Jul 5th – Group A 解题报告 / 集训队互测 2013

A – 家族

这道题真的是送分题(快要想出来直接暴力枚举+并查集的时候去看了题解,最后发现就是这么 sb)。

考虑枚举频段区间\([L, R]\)(将边进行排序,确定下界之后再枚举上界),这个地方是\(O(m^2)\)的。每次枚举下界的时候都要初始化并查集,然后合并两个集合的时候按照大小来修改答案就行了。

继续阅读[Fortuna OJ]Jul 5th – Group A 解题报告 / 集训队互测 2013

[Fortuna OJ]Jul 4th – Group A 解题报告

A – 非回文数字

这道题还没写,是一道数位 DP,推荐记忆化搜索。

B – 管道

这道题是一道相当好的题目。

首先对于\(m = n – 1\)的情况,也就是树的形态下,可以考虑自下向上推,也就是从叶子节点开始推起,参考代码中 Toposort 的写法。然后,对于\(m > n\)的情况可以直接输出\(0\),因为这个方程组并不存在唯一的解:\(m\)个未知数仅提供\(n\)个条件,这样是不成立的。

最后考虑\(m = n\)的情况。这种情况就是基环树了。首先,Toposort 会把支链上的答案全部统计完毕,并且合并到环上的点。最后,我们唯一要多做的事情,就是处理环上的方程组。考虑一个这样的环:

继续阅读[Fortuna OJ]Jul 4th – Group A 解题报告

[Fortuna OJ]Mar 5th – Group A 解题报告

A – 旷野大计算

嗯,是我这种菜鸡不会的类型。

这个题主要的思路就是用离线莫队算法,这个算法是我本人第一次打,所以我会尝试一处一处讲清楚。首先大致分析一下,这道题的本质其实就是查询区间最大的加权众数。那么,根据题解上讲的,有一个这样的结论:

给定集合\(A,B\),则\(mode(A \cup B) \to mode(A) \cup B\)这两玩意本质一样。

所以就可以考虑进行区间增大的莫队了。首先,离散化后简单的分个块,把问答离线下来排个序搞一搞。针对每一个询问,如果可以从上个区间进行转移,就进行快速转移;否则,重新开始。

莫队算法的精髓就是:暴力的进行转移。

// A.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 1e6 + 2000;
int n, m, arr[MAX_N], blockId[MAX_N];
int currentId[MAX_N], bucket[MAX_N];
ll cnt[MAX_N], leftBucket[MAX_N], answer, anses[MAX_N];
struct query
{
    int l, r, id;
    bool operator<(const query &qu) const
    {
        return blockId[l] < blockId[qu.l] ||
               (blockId[l] == blockId[qu.l] && r < qu.r);
    }
} queries[MAX_N];
void update_left(int x)
{
    leftBucket[currentId[x]]++;
    answer = max(answer, (leftBucket[currentId[x]] + cnt[currentId[x]]) * 1LL * arr[x]);
}
int main()
{
    scanf("%d%d", &n, &m);
    int siz = sqrt(n * 1.0);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]), bucket[i] = arr[i], blockId[i] = (i - 1) / siz + 1;
    sort(bucket + 1, bucket + 1 + n);
    int buckTot = unique(bucket + 1, bucket + 1 + n) - bucket;
    for (int i = 1; i <= n; i++)
        currentId[i] = lower_bound(bucket + 1, bucket + 1 + buckTot, arr[i]) - bucket;
    for (int i = 1; i <= m; i++)
        scanf("%d%d", &queries[i].l, &queries[i].r), queries[i].id = i;
    sort(queries + 1, queries + 1 + m);
    // Previous Information:
    int L = 1, R = 0, tmd;
    ll tmp = 0;
    answer = 0;
    queries[0].l = 0, blockId[0] = 0;
    for (int i = 1; i <= m; i++)
    {
        // Validiate if this interval is able to be calced by the previous one;
        if (blockId[queries[i - 1].l] != blockId[queries[i].l])
        {
            memset(cnt, 0, sizeof(cnt));
            R = tmd = blockId[queries[i].l] * siz;
            answer = tmp = 0;
        }
        L = min(tmd + 1, queries[i].r + 1);
        // Calc;
        while (L > queries[i].l)
            update_left(--L);
        while (R < queries[i].r)
        {
            R++;
            tmp = max((++cnt[currentId[R]]) * 1LL * arr[R], tmp);
            answer = max(answer, (cnt[currentId[R]] + leftBucket[currentId[R]]) * 1LL * arr[R]);
        }
        // Set the answer;
        anses[queries[i].id] = answer;
        // Set the bucket back;
        for (int j = L; j <= queries[i].r && j <= tmd; j++)
            leftBucket[currentId[j]]--;
        answer = tmp;
    }
    // Print the answer;
    for (int i = 1; i <= m; i++)
        printf("%lld\n", anses[i]);
    return 0;
}

B – 爬山

这是一道傻逼题,然后我强行搞了个拓扑序 DP 就 GG 了。现在想想非常后悔。

显然,把环全部缩成点就会形成一个 DAG (有向无环图),之后直接暴力 DP,然后再取出标记过的答案进行最大值比较即可。很傻逼的一道题。

哦,对了,记得开栈。(JZOJ 万年卡栈)

// B.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 602000;
extern int theMain(void) __asm__("theMain");
int head[MAX_N << 1], current, n, m, dfn[MAX_N], low[MAX_N], aff[MAX_N];
int tot, stk[MAX_N], cur, afftot, indeg[MAX_N << 1], tmpx, tmpy, s;
ll cnt[MAX_N << 1], dp[MAX_N << 1], answer;
bool inst[MAX_N], mark[MAX_N];
struct edge
{
    int to, nxt;
} edges[MAX_N << 1];
void addpath(int src, int dst)
{
    edges[current].to = dst;
    edges[current].nxt = head[src], head[src] = current++;
}
void tarjan(int u)
{
    dfn[u] = low[u] = ++tot, stk[++cur] = u, inst[u] = true;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (dfn[edges[i].to] == 0)
            tarjan(edges[i].to), low[u] = min(low[u], low[edges[i].to]);
        else if (inst[edges[i].to])
            low[u] = min(low[u], dfn[edges[i].to]);
    if (low[u] == dfn[u])
    {
        int j, nd = ++afftot;
        do
        {
            j = stk[cur], inst[j] = false;
            aff[j] = nd;
        } while (stk[cur--] != u);
    }
}
void toposort()
{
    queue<int> q;
    q.push(aff[s]), dp[aff[s]] = cnt[aff[s]];
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != -1; i = edges[i].nxt)
        {
            dp[edges[i].to] = max(dp[edges[i].to], dp[u] + cnt[edges[i].to]);
            q.push(edges[i].to);
        }
    }
}
int theMain()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d%d", &tmpx, &tmpy), addpath(tmpx, tmpy);
    afftot = n;
    for (int i = 1; i <= n; i++)
        if (aff[i] == 0)
            tarjan(i);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &cnt[i]);
    for (int u = 1; u <= n; u++)
    {
        cnt[aff[u]] += cnt[u];
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (aff[u] != aff[edges[i].to])
                addpath(aff[u], aff[edges[i].to]), indeg[aff[edges[i].to]]++;
    }
    scanf("%d%d", &s, &tmpx);
    for (int i = 1; i <= tmpx; i++)
        scanf("%d", &tmpy), mark[aff[tmpy]] = true;
    toposort();
    for (int i = 1; i <= n; i++)
        if (mark[aff[i]])
            answer = max(answer, dp[aff[i]]);
    printf("%lld", answer);
    return 0;
}

int main()
{
    int size = 64 << 20;
    char *p = (char *)malloc(size) + size;
    __asm__ __volatile__("movq  %0, %%rsp\n"
                         "pushq $exit\n"
                         "jmp theMain\n" ::"r"(p));
    return 0;
}

C – 货仓选址 运输妹子

如题,然后秒切。

// C.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 101000;
ll n, l, w, pos[MAX_N], prefix[MAX_N], answer;
bool validiate(int l, int r)
{
    int mid = (l + r) >> 1;
    ll ans = pos[mid] * (mid - l + 1) - (prefix[mid] - prefix[l - 1]) + (prefix[r] - prefix[mid]) - pos[mid] * (r - mid);
    return ans <= w;
}
int main()
{
    scanf("%lld%lld%lld", &n, &l, &w);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &pos[i]), prefix[i] = prefix[i - 1] + pos[i];
    ll lcur = 1, rcur = 0;
    while (rcur < n && lcur <= n)
    {
        rcur++;
        while (lcur <= rcur && !validiate(lcur, rcur))
            lcur++;
        answer = max(rcur - lcur + 1, answer);
    }
    printf("%lld", answer);
    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;
}