【2019】0802 的 C 组模拟赛总结 + 题解

Cefola_Kiroxs · 2019-08-02 11:40:57 · 个人记录

比赛状况

比赛地址

排名 / 分数：75 / 51.1

各题分数：11.1 / 40 / 0 / 0

我，今日，爆惨 ，打钱

今天这次比赛，我的状态真的是差 “飞” 了 —— 做题策略上的重大失误都不值得一提了，因为今天状态已经差到一个 80分（其实跟正解区别不大了） 的程序 没 交 上 去 …… 别的题也是很惨，水题 T1 和 T3 大脑宕机，同样很水的 T2 本来写了个 80 分的程序，结果又补上了个 40 分的 “优化” ……

而且，今天题目也很水 —— 两个暴力，两个接近模板的题目，理解起来十分容易。但是，连这么水的题目都能这么惨，我已经不知道接下来的比赛会有多惨了 ……

不过不能沮丧啊，虽然收获可能会很少，但还是要努力做呢。

听课总结

思路类

• 其实我觉得今天这些题已经简单到没法总结了 …… 来说一下 学会利用题目中隐含的性质 吧。

  举例 ：T3 中，根据题目性质可以知道 “泵一定是放在图中的最低点” ，又根据样例可以知道 “图会被分成很多块，每块都有一个答案” ，所以将两者结合可以得出 “每次找到最低点并去掉最低点包含的块” 这个做法。

  （听起来很简单吧？但我考场上确实没想到呢 …… ）

习惯类

• 要提高代码实现能力 。T1 就是一个纯靠写代码的题，但是我即便想出了思路，也没有付诸于实际的能力，因此有 100 分就这么丢掉了 ……

• 对于基本凉透的比赛一定要对拍 。T2 我交的 “优化” 说不定是能对拍拍出来错误的，虽然我还没尝试，但这种本来能稳妥拿到的分居然丢了，令我不禁给自己敲响一个警钟 —— 在这种基本没什么希望能想出题的时候，抽时间来保住自己的分数是很有必要的。

• 学会适当转换思路 。不用说，我 T1 和 T3 就是这样透心凉的 ……

• 对于图论题中常见坑点要引起重视 。下面给出了一个表。

重边、自环；

被分成不连通的若干块； （T4 不能直接用边数判断是否不连通的原因）

某种结构的退化；

负权、负环、负数结果；

解题报告

T1 disease (细菌)

题目地址

题意概括 。有 n 个列表，每个列表会有若干个元素，一共有 d 种元素。现在要从这些列表中选出若干个列表，使得选出的列表中元素 的种类 不超过 k 种，问你能选出的最多列表数。

分析 。显然，水会一直流动，流到最低点才会停止，因此所有的水都会汇聚到最低点，在最低点设置泵就可以了。但是，根据样例可以看出，一个地区可能会有很多个 “块”，“块” 的外围是 “一睹围墙” ，高度很高（至少比围墙外那一圈地区要高），使得里面的水没法流出去，因此泵就可能会设置多个。

所以，只要解决 “怎么找到最低点” 和 “怎么找到多个块” 这两个问题，题目就基本解决了。实际上，看到题目那么小的数据范围，我们很容易想到一个又好写、又能 “一箭双雕” 的方法 —— 每次找一个未标记的最低点，并从最低点 “倒流” 到其它点（也就是找能流到这个最低点的所有点），将沿路的点全部由标记。这样重复多次，当矩阵全部被标记完成时，我们的任务就完成了。

如果将数据范围加大，可能需要更加优秀的算法，但我目前暂时没有什么头绪。如果对于本题有更优秀的思路，欢迎在评论中发表见解。

代码 。

#include <queue>
#include <cstdio>
#include <cstring>
#define rr register

struct point {
    int x, y;
    point() {}
    point(int x_, int y_) : x(x_), y(y_) {}
};

const int MAXN = 50 + 5;
int n, m, t, a[MAXN][MAXN];

const int dx[4] = {1, 0,  0, -1};
const int dy[4] = {0, 1, -1,  0};
bool f[MAXN][MAXN];

void BFS(point st)
{
    std::queue <point> q;

    q.push(st);
    t += (f[st.x][st.y] = true);

    int pre = -1;
    while (!q.empty())
    {
        point u = q.front();
        q.pop();

        for (int i = 0; i < 4; ++i)
        {
            point v(u.x + dx[i], u.y + dy[i]);

            if (v.x < 1 || v.x > n || v.y < 1 || v.y > m) continue; //是否合法
            if (a[v.x][v.y] < a[u.x][u.y]) continue; //是否能倒流
            if (i + pre == 3) continue; //是否在回退
            if (f[v.x][v.y]) continue; //是否已访问

            q.push(v);
            t += (f[v.x][v.y] = true);
        }
    }
}

int main()
{
    int arr;
    scanf("%d", &arr);

    for (int cnt = 0; cnt < arr; ++cnt)
    {
        scanf("%d%d", &n, &m);
        memset(a, 0, sizeof(a));

        for (rr int i = 1; i <= n; ++i)
        {
            char c = getchar();
            for (; c < 'a' || c > 'z'; c = getchar());
            for (rr int j = 1; j <= m; ++j)
            {
                a[i][j] = c - 'a';
                c = getchar();
            }
        }

        memset(f, 0, sizeof(f));

        int ans = 0;
        for (t = 0; t < n * m; ++ans)
        {
            int minv = 0x7f7f7f7f;
            point minc(0, 0);
            for (rr int i = 1; i <= n; ++i)
                for (rr int j = 1; j <= m; ++j)
                    if (!f[i][j] && minv > a[i][j]) {
                        minv = a[i][j];
                        minc = point(i, j);
                    }
            BFS(minc);
        }
        printf("%d\n", ans);
    }
    return 0;
}

T4 cowtract (网络)

题目地址

题意概括 。有一个 n 条边、m 条边的无向图，每条边有一个权值。现要从中选取若干条边建图，并且要求图 必须连通 ，而且 不能有环 ，求权值和最大的方案。