[Fortuna OJ]4605 – 排序 sort 题解

主要思路

这道题好有意思啊,提醒我在任何时候都要想到这种阈值+\(0/1\)转化的方式。

我们可以先二分出\(c\)位置的值,然后令所有大于等于\(c\)的值变成\(1\),小于的则变成\(0\)。然后排序的时候发现,其实就是重新组织零一的位置,所以用线段树区间修改就可以搞定了。最后判断\(c\)位是否为\(0/1\)决定要不要继续二分。

继续阅读[Fortuna OJ]4605 – 排序 sort 题解

LibreOJ 6003:「网络流 24 题」魔术球题解

思路

这道题其实跟 LOJ 6002 建模方式差不多,只是加了一个二分答案来进行动态建图。见代码:

代码

// LOJ6003.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e4 + 100, INF = 0x3f3f3f3f;
int head[MAX_N], current, s, t, dep[MAX_N], cur[MAX_N], n, tot, upward[MAX_N], tag[MAX_N], unit;
struct edge
{
    int to, nxt, weight;
} edges[500010];
void addpath(int src, int dst, int weight)
{
    edges[current].to = dst, edges[current].weight = weight;
    edges[current].nxt = head[src], head[src] = current++;
}
void add(int u, int v, int w) { addpath(u, v, w), addpath(v, u, 0); }
bool bfs()
{
    queue<int> q;
    q.push(s), memset(dep, 0, sizeof(dep));
    dep[s] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (edges[i].weight > 0 && dep[edges[i].to] == 0)
                dep[edges[i].to] = dep[u] + 1, q.push(edges[i].to);
    }
    return dep[t] != 0;
}
int dfs(int u, int flow)
{
    if (u == t || flow == 0)
        return flow;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (dep[edges[i].to] == dep[u] + 1 && (edges[i].weight > 0))
        {
            int to = edges[i].to, fl = dfs(to, min(flow, edges[i].weight));
            if (fl > 0)
            {
                upward[u] = to;
                if (u != s)
                    tag[edges[i].to - unit] = true;
                edges[i].weight -= fl, edges[i ^ 1].weight += fl;
                return fl;
            }
        }
    return 0;
}
int dinic()
{
    memset(tag, false, sizeof(tag));
    int ans = 0;
    while (bfs())
    {
        for (int i = 0; i <= tot; i++)
            cur[i] = head[i];
        while (int f = dfs(s, INF))
            ans += f;
    }
    return ans;
}
bool check(int num)
{
    unit = num;
    tot = (num << 1) + 2, s = tot - 1, t = tot;
    memset(head, -1, sizeof(head)), current = 0;
    for (int i = 1; i <= num; i++)
        add(s, i, 1), add(i + num, t, 1);
    for (int i = 1; i <= num; i++)
        for (int j = 1; j * j - i <= num; j++)
            if (i < j * j - i)
                add(j * j - i, i + num, 1);
    return num - dinic() <= n;
}
int main()
{
    scanf("%d", &n);
    int l = 1, r = MAX_N - 2000, ans;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
            l = mid + 1, ans = mid;
        else
            r = mid - 1;
    }
    printf("%d\n", ans);
    check(ans);
    for (int i = 1; i <= ans; i++)
        if (!tag[i])
        {
            int p = i;
            printf("%d ", p);
            while (upward[p] && upward[p] != t && upward[p] - ans >= 0)
                printf("%d ", upward[p] - ans), p = upward[p] - ans;
            puts("");
        }
    return 0;
}

POJ2018:Best Cow Fences 题解

思路

这道题目转换一下题意就可以分析出很多东西。其实这个问题就是在问一个给定的序列之中,求一个平均数最大、长度不少于\(F\)的字串。我们可以尝试考虑二分答案的做法。本题要二分的东西是平均数,而平均数是属于实数范围内的,所以我们必须在实数域中进行二分答案。我们要设定一个精度值为\(eps\),当\(r-l>eps\)时,说明还没有到比较准确的地步,然后继续二分,直到插值小于\(eps\)。

继续阅读POJ2018:Best Cow Fences 题解

P2898:[USACO08JAN]haybale猜测题解

思路

这又是一道抄题解的题目。我们先来简要分析一下触发矛盾的几种情况:

  • 给定两个区间\(A, B\),有\(A \cap B \neq \emptyset \),而\(A_{min} \neq B_{min}\),这种情况是矛盾的。
  • 给定两个区间\(A, B\),有\(A \subset B\),而\(A_{min} \neq B_{min}\),这种情况也是矛盾的。

之后我们就可以用并查集来进行集合操作。而数据范围非常的大,而答案只需要一个最早解,那么我们就可以尝试二分答案。

继续阅读P2898:[USACO08JAN]haybale猜测题解

P2678:跳石头题解&二分答案原理

暑假和小学神仙们集训的时候发过这道题,一直不知道如何去解决。一个月前crazydave大佬给我简述过二分答案的原理,而蒟蒻我今天才搞定这些。

我们先来看例题:洛谷P2678

这是一道NOIP提高组的简单题(我太菜了),主要是通过枚举答案,在每次枚举时检测能不能符合要求即可。先看代码:

// P2678.cpp
#include <iostream>

using namespace std;

const int maxn = 500020;
int L, N, M;
int D[maxn];

bool check(int num)
{
    int last = 0;
    int cnt = 0;
    for (int i = 0; i <= N; i++)
        if (D[i] - last < num)
            cnt++;
        else
            last = D[i];
    if (cnt > M)
        return false;
    return true;
}

void solve()
{
    int left = 0;
    int right = L;
    int ans = 0;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (check(mid))
            left = mid + 1, ans = mid;
        else
            right = mid - 1;
    }
    cout << ans;
}

int main()
{
    cin >> L >> N >> M;
    for (int i = 0; i < N; i++)
        cin >> D[i];
    D[N] = L;
    solve();
    return 0;
}

check函数就是验证答案num(也就是我们枚举出来的答案)是否符合要求,在这里便是检测当最小距离为num时,移走的石子会不会超过限制。如果超过了,返回false,二分便会把区间调为[left,mid-1],以降低最大值来试探限制;没有超过,则返回true,二分把区间调整为[mid+1,right],以追求更大的最大值。

抽象化分析结果

准备枚举一道题答案之前,请考虑二分答案。如果可以二分答案,那么时间复杂度会极度降低,从O(n^2)转变为O(n log n)。二分答案的结构就是二分代码和检验答案正确性代码。如果能通过正确性检查,那么追求更大(小)的答案并重新枚举;如果无法通过,则把区间调整,在较小(大)区间内追求更大(小)的答案。亦复如此。