【2019】0711 的 C 组模拟赛总结 + 感想

· · 个人记录

比赛状况

比赛地址

分数（实际/估分）：91.7 / 120

排名：并列 29$

这次的比赛是之前一次模拟赛的原题，一模一样。考虑到过去我的博客很丑，所以我不推荐各位点进去看。（但我也不会重新详细地写题解）然而，即便是 “原题” “印象深刻” 的一次比赛，我居然也打爆了 …… 话说说来，今天也是大凶。

总结

（简单概括：预处理时 “原点” 加，越界一个的点减，越界两个的点加；累计答案时往前偏移一个的点加，往前偏移两个的点减）

T1 GCD 与 LCM

本题很容易想到朴素做法 —— 显然， lcm * gcd = a * b ，枚举 lcm * gcd 的每一对 a 和 b ，在 GCD(a,b)=gcd （这里用 GCD 表示求最大公因数） 时将其考虑进答案。这个思路没有问题，但就是 lcm * gcd 太大了 —— 10^{18} ！即使只枚举到 \sqrt{n} ，也有 10^9 级别的时间复杂度，怎么优化呢？

可以发现，上面的枚举如果同时除以 gcd ，依然是等价的，详细一点就是 —— 枚举 lcm 的每一对 a 和 b ，在 GCD(a,b)=1 时将其考虑进答案。这样，我们的时间复杂度就只是 10^4 到 10^5 的范围了。

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;

const int INF = 1000000000 + 5;
int getGCD(int x, int y) { return (y == 0) ? x : getGCD(y, x % y); }

int main()
{
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);

    int GCD, LCM;
    scanf("%d%d", &GCD, &LCM);

    LCM /= GCD;
    int ans = INF;
    for (int i = 1; i*i <= LCM; ++i)
        if (LCM % i == 0)
        {
            int j = LCM / i;
            if (getGCD(i, j) == 1) ans = min(ans, abs(i * GCD - j * GCD));
        //这里我采用的是 “在更新ans过程中就乘上GCD”的方式，换成输出再乘未免不可
        }
    printf("%d", ans);
    return 0;
}

T2 幻灯片

这题同样也要从暴力开始思考。显然，将每一个幻灯片的信息原样存储下来，再对所有格子枚举一次，就能得到答案。但是，这样做的时间复杂度高达 (10^9)^2 ！怎么进行优化呢？

通过 n \leq 100 可以知道，所有幻灯片的所有坐标（x 和 y）最多只有 100 * 4=400 种，但它们可能空隙很大 —— 每个幻灯片占据的位置看似很大，但实际上大部分都是无效的。此时，我们就能使用一种名为 “离散化” 的技巧 —— 将所有坐标存进一个数组，排序并去重。这样，我们让所有坐标等于它们离散化后的编号，就能在保持它们相对位置的前提下，大大缩小空间了。

不过，关于填充颜色，如果我们离散化后，对每一个幻灯片都填充一次颜色，显然效率会大大下降。此时，我们就能使用二维前缀和 —— 这是一个较难的内容，希望各位看代码自行体会。就这样，这个程序完成了基本内容。

但还存在一个问题 —— 题目要求我们统计 “矩阵”， 但给我们输入的是 “点” 。这样，当出现 “两个矩阵有重叠边” 的情况时，直接用上面的做法会将这个 “重叠边” 的颜色累加，但实际上 “重叠边” 根本没有颜色！怎么解决这个问题呢？比较普适的做法是，将每一个幻灯片 “放大一点点” 的样子和 “缩小一点点” 的样子一起离散化，并以 “缩小一点点” 的样子进行操作。这样，即使有重叠边，也不会被重复累加颜色了。

#include<cstdio>
#include<algorithm>
#define rr register
using namespace std;

const int MAXN = 100 + 5;
const int MAXC = 10000 + 5;
const int MAXP = MAXN << 3;

struct range
{
    double x1, y1, x2, y2; //(x1,y1)是左下角，(x2,y2)是右上角
    int c;
}
a[MAXN];

int len, sum[MAXP][MAXP], cnt[MAXC];
double ind[MAXP];

int main()
{
    freopen("b.in", "r", stdin);
    freopen("b.out", "w", stdout);

    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%lf%lf%lf%lf%d", &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2, &a[i].c);
        ind[++len] = a[i].x1 - 0.5; //“扩大一点”的区间
        ind[++len] = a[i].y1 - 0.5;
        ind[++len] = a[i].x2 + 0.5;
        ind[++len] = a[i].y2 + 0.5;
        ind[++len] = (a[i].x1 += 0.5); //“缩小一点”的区间，拿它来操作
        ind[++len] = (a[i].y1 += 0.5);
        ind[++len] = (a[i].x2 -= 0.5);
        ind[++len] = (a[i].y2 -= 0.5);
    }

    sort(ind + 1, ind + len + 1);
    len = unique(ind + 1, ind + len + 1) - (ind + 1);
    for (int i = 1; i <= n; ++i)
    {
        a[i].x1 = lower_bound(ind + 1, ind + len + 1, a[i].x1) - (ind + 1);
        a[i].y1 = lower_bound(ind + 1, ind + len + 1, a[i].y1) - (ind + 1);
        a[i].x2 = lower_bound(ind + 1, ind + len + 1, a[i].x2) - (ind + 1);
        a[i].y2 = lower_bound(ind + 1, ind + len + 1, a[i].y2) - (ind + 1);
        sum[ (int)a[i].x1 ][ (int)a[i].y1 ] += a[i].c;
        sum[ (int)a[i].x1 ][ (int)a[i].y2 + 1 ] -= a[i].c;
        sum[ (int)a[i].x2 + 1 ][ (int)a[i].y1 ] -= a[i].c;
        sum[ (int)a[i].x2 + 1 ][ (int)a[i].y2 + 1 ] += a[i].c;
    }

    int ans = 0;
    for (rr int i = 1; i <= len; ++i)
        for (rr int j = 1; j <= len; ++j)
        {
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
            if (sum[i][j] && !cnt[sum[i][j]]) { ans++; cnt[sum[i][j]]++; }
        }
    printf("%d\n", ans);
    return 0;
}

T3 导弹

首先，我们可以分析题目，提炼出题目的模型 —— 给定一个无向图，并将所有属于 B 国的点和部分 A 国的点连接，使其中选定的边的最大权值最小。这里边的 “权值” 是什么？自然就是两个点间的最短距离。设定数组 F[i,j] 代表从 i 点到 j 点的最短距离，通过分析题目数据范围可以得出，我们可以使用好写、并且时间能承受的 Floyd 。

在使用 Floyd 求出最短路以后，我们就要解决 “选定的边的最大权值最小” 这个问题。看到 “最大值最小” ，你想到了什么？二分查找。二分查找就是常见解决 “双最值” 问题的算法，通常用二分先确定一个答案，再检验这个答案是否合法。在本题中，我们以用时为 0 到 max(F[i,j]) 作为区间，在其中进行二分查找。每一次二分查找，我们求出 mid ，并且用所有用时 \leq mid 的、两国之间的边构成一个图，检验这个图是否让每个 A 国城市连接且只连接一个 B 国城市。这样，就完成了答案的搜索。

我们每次构成的图叫做 “二分图”。检验每次构成的二分图是否合法，我们需要使用 “匈牙利算法” 。匈牙利算法虽然对于初学者不是特别友好，但如果认真寻找资料，反复对比，相信各位一定可以理解，在此不多做阐述。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXK = 100 + 5;
int n, m, a[MAXK], b[MAXK], f[MAXK][MAXK];

const int MAXE = 10000 + 5; //邻接表存图
int head[MAXK], to[MAXE], last[MAXE], tot;
void addEdge(int u, int v)
{
    to[++tot] = v;
    last[tot] = head[u];
    head[u] = tot;
}

int now, vis[MAXK], belong[MAXK];
//now是当前匹配的点，虽然匹配过程中我们会递归，但终究是为了让now匹配
//vis是“访问时间”数组，用now来标记访问时间，如果重复标记同一个now就代表匹配失败
bool check(int u)
{
    if (vis[u] == now) return 0;
    vis[u] = now;

    for (int i = head[u]; i; i = last[i])
    {
        int v = to[i];
        if (!belong[v] || check(belong[v]))
        {
            belong[v] = u;
            return 1;
        }
    }
    return 0;
}
bool hungary()
{
    bool OK = true;
    for (now = 1; now <= m; ++now)
        if (!check(b[now])) { OK = false; break; }
    return OK;
}

int main()
{
    freopen("c.in", "r", stdin);
    freopen("c.out", "w", stdout);

    int k;
    scanf("%d", &k);
    for (int i = 1; i <= k; ++i)
        for (int j = 1; j <= k; ++j)
            scanf("%d", &f[i][j]);

    for (int p = 1; p <= k; ++p)
        for (int i = 1; i <= k; ++i)
            for (int j = 1; j <= k; ++j)
                f[i][j] = min(f[i][j], f[i][p] + f[p][j]);

    scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    scanf("%d", &m); for (int i = 1; i <= m; ++i) scanf("%d", &b[i]);

    int L = 0, R = 0;
    for (int i = 1; i <= k; ++i)
        for (int j = 1; j <= k; ++j)
            R = max(R, f[i][j]);
    while (L < R)
    {
        int mid = (L + R) >> 1;

        tot = 0;
        memset(head, 0, sizeof(head));
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                if (f[b[i]][a[j]] <= mid) addEdge(b[i], a[j]);

        memset(vis, 0, sizeof(vis));
        memset(belong, 0, sizeof(belong));
        if (hungary()) R = mid; else L = mid + 1; //二分的写法很重要哦
    }
    printf("%d\n", L);
    return 0;
}

T4 医院

由题意可以知道，不满意度肯定为 0（毕竟没有限定建医院的数量）。而且，这题还是 Special Judge ，所以输出方案也不必担心，只要能输出合理的方案就行了。那么，有什么简单的方法，能够保证一个方案的不满意度一定为 0 呢？答案是 “不能放的点就不放，可以放的点全都放” 。

首先，因为题目说这是一张有向图，所以显然，入度为 0 的点必须要放医院（我们称之为 “第一层” ）。之后，根据题目要求，与这些点相邻的点就不能放了（我们称之为 “第二层” ）。接下来，因为题目中 “/” 是整除，所以依照公式，理论上来讲，与 “第二层” 相邻的点也不用放。但是！本题是 Special Judge ，不用考虑数量的多少，那么为什么要记录它现在与 “第一层” 的点是隔一条边，还是隔两条边呢？所以，与 “第二层” 相邻的点仍然要放。

通过上述的分析，我们发现 —— 这就是一个贪心嘛！事实上，由于本题是 Special Judge ，所以这个贪心策略是完全正确的。依照这种贪心策略，虽然实现起来有些复杂，但总归是能得到正确的结果的。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 100 + 5;
int n;

int g[MAXN][MAXN], into[MAXN];

bool cantUse[MAXN], vis[MAXN];
void dfs(int i)
{
    if (!cantUse[i])
    {
        vis[i] = 1;
        for (int j = 1; j <= n; ++j)
            if (g[i][j]) cantUse[j] = 1;
        for (int j = 1; j <= n; ++j)
            if (g[i][j]) { vis[j] = 1; dfs(j); }
    }
    else
    {
        for (int j = 1; j <= n; ++j)
            if (g[i][j] && !vis[j]) { vis[j] = 1; dfs(j); }
    }
}

int main()
{
    freopen("d.in", "r", stdin);
    freopen("d.out", "w", stdout);

    printf("0\n");

    int m;
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        g[x][y] = 1;
        into[y] = 1; //我们只关心入度是否为0，所以直接标1可以避免“重边”造成的错误
    }

    int u;
    scanf("%d", &u);

    for (int i = 1; i <= n; ++i)
        if (!into[i])
        {
            cantUse[i] = 0; vis[i] = 1;
            for (int j = 1; j <= n; ++j)
                if (g[i][j]) cantUse[j] = 1;
        }

    bool flag = 1;
    for (int i = 1; i <= n; ++i)
        if (!into[i]) {
            flag = 0;
            dfs(i);
        }
    if (flag) //如果都是环，不存在入度为0的点，所有的点都要跑一遍
        for (int i = 1; i <= n; ++i)
            dfs(i);

    int numHosp = 0;
    for (int i = 1; i <= n; ++i)
        if (!cantUse[i]) numHosp++;
    printf("%d\n", numHosp);
    for (int i = 1; i <= n; ++i)
        if (!cantUse[i]) printf("%d%c", i, (i==n) ? '\n' : ' ');
    return 0;
}