洛谷MYOI月报【7月刊】

duanfeitong · 2023-07-01 19:43:59 · 个人记录

文章作者：@Cyx20110930 @duanfeitong @__immccn123__ @2044_space_elevator

审核：@duanfeitong @SaintRelief @Dream_Creator

技术支持：@L1uTongwei

格式修改：@Dream_Creator

欢迎加入 MYOI出题组！也欢迎向@SaintRelief投递广告（详情见本报最下方）

您也可以在这里阅读本刊：

云剪切板：https://www.luogu.com.cn/paste/hlw6kyz5

七月，是一个充满了激情、热血与奋斗的月份。提起七月，你想起的可能是炎热天气、漫长白天、冰激凌、空调、风扇以及超多的暑假作业……但是，还有一些永远值得记忆的日子，发生在过去的七月。

2023年7月1日，是建党 102 周年。一百余年前，1921年的夏天，一条小船承载着人民的重托、民族的希望，像一盏明灯，冲破黑暗，照亮了中国革命的航向！

同时，2023年7月1日也是香港回归 26 周年。1997年7月1日起，中国在香港成立特别行政区，开始对香港岛、界限街以南的九龙半岛、新界等土地重新行使主权和治权，香港回归祖国怀抱。

1776年7月4日，美利坚合众国成立。

1840年7月6日，第一次鸦片战争开始。拉开了中国近代史的序幕，使中国开始沦为半殖民地半封建社会。

2023年7月7日，是卢沟桥事变（又称“七七事变”）86周年。1937年7月7日，日本开始全面侵华，抗日战争爆发。

2001年7月13日，北京申奥成功，获得了2008年第29届夏季奥林匹克运动会的举办权。

1822年7月20日，遗传学的奠基人、现代遗传学之父格雷戈尔·孟德尔出生于奥地利帝国。

1945年7月26日，《波兹坦公告》发表。

让我们永远地记下这些或神圣或悲哀或伟大的时刻吧！

提示，本文为作者原创，同步发布于codeforces：https://codeforces.com/blog/entry/114946

Overview

Graph is a kind of data struction. It's very useful, it can descripe the relationship of a lot things. In the life, we always see the graph, such as the traffic graph. For instance, this is a graph. There are 4 nodes in this graph. And there are two edges in this graph. It is a undirected graph.

Of course, we have directed graph too. This is directed graph about my genealogy.

This is a directed graph too.

Now, you know what a graph is, and then, I will introduction how to denote a graph.

Denote a graph

There are two representation methods to denote a graph. One is matrix, and the other one is adjacency table, adjacency table is a little complex. In this article, I only introduction matrix representation method.

Undirected graph

For instance, we denote the graph of picture 1, this the matrix of picture 1:

In matrix, if node a and node b are connected, A_{ab},A_{ba}=1, otherwise A_{ab},A_{ba}=0

In picture 1, there are 2 edges, they are:

• 1 \operatorname{and} 2
• 2 \operatorname{and} 3

So:

• A_{12},A_{21}=1
• A_{23},A_{32}=1

Directed graph

There are new rules for representing directed graphs in matrices:

• If a \to b, A_{ab}=1
• If b \to a, A_{ba}=1

For instance, we denote the graph of picture 3.

There are 4 edges in picture 3, they are:

• 1\to 2
• 2\to 3
• 3\to 4
• 2\to 4

So, the matrix of picture 3 like this:

Weighted graph

This is a weighted graph.

If node a and b are connected, and there weight is k, this is the representation method of weighted graphs.

• If a\to b, A_{ab} = k
• If b\to a, A_{ba} = k
• Otherwise, A_{ab},A_{ba}=\infty

The matrix of picture 4:

Denote by code

Undirected graph

Let's first define a two-dimensional array. For instance, this is the input of picture 3.

4
1 2
2 3
3 4
2 4

It means, there are 4 edges in this graph, 1 and 2 was connected, 2 and 3 was connected, 3 and 4 was connected, 2 and 4 was connected.

This is the code to record the graph:

#include <iostream>
using namespace std;

bool A[10][10];
int n;

int main()
{
    cin >> n;
    while (n--)
    {
        int node1, node2;
        cin >> node1 >> node2;
        A[node1][node2] = 1;
        A[node1][node2] = 1;
    }
    return 0;
}

Directed graph

This is the code of denote directed graph.

#include <iostream>
using namespace std;

bool A[10][10];
int n;

int main()
{
    cin >> n;
    while (n--)
    {
        int node1, node2;
        cin >> node1 >> node2;
        A[node1][node2] = 1;
    }
    return 0;
}

Weighted graph

This is the code of denote directed graph:

#include <iostream>
using namespace std;
#define oo 123456
int A[10][10];
int n;

int main()
{
    // init
    cin >> n;
    for (int i = 1; i <= 9; i++)
    {
        for (int j = 1; j <= 9; j++)
        {
            A[i][j] = oo;
        }
    }
    while (n--)
    {
        int node1, node2, weight;
        cin >> node1 >> node2 >> weight;
        A[node1][node2] = weight;
    }
    return 0;
}

Search algorithm

There are two kinds of search algorithms graphs: depth first search(dfs) and breadth first search(bfs), dfs is easier than bfs, but dfs is very slow.

In this article, we call the first node of graph "root", such as in picture 4, the "root" is node 1.

Depth first search

You maybe have learnt the backtracking algorithm, this is template code for backtracking:

void backtracking(...)
{
    if (Marginal Condition)
    {
        Save result
        return;
    }
    for (int i = startIndex; i <= n; i++)
    {
        Record vales
        backtracking(...);
        Delet vales
    }
}

Backtracking is a kind of depth first search., the dfs of graph is very like backtracking, this is the template code of dfs of graph:

bool vis[N]; // Tag
int n; // node number
void dfs(int node)
{
    if (node == n)
    {
        // output path
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if ((A[i][node] == 1 || A[node][i] == 1) && !vis[i])
        {
            vis[i] = 1;
            dfs(i);
            vis[i] = 0;
        }
    }
}

Breadth first search

In fact, breadth first search (bfs) equivalent to level traversal, such as, this is the bfs of picture 3, we set the root node is 1.

We need a queue. First, we put the root node in the queue:

queue:
1
path:

And then, we record node 1, and put all children of node 1 in the queue:

queue:
2
path:
1

Next, we record node 2, and put all children of node 1 in the queue:

queue:
3 4
path:
1 2

Finally, we record node 3 and node 4, put all children of them in the queue:

queue:
path:
1 2 4 3

Node 4 has no children, the children of node 3 has a child (node 4), but it has recorded.

So this is the temple code of bfs:

#include <queue> // We need the queue
int A[N][N];
bool vis[N]; // Has visited?
void bfs()
{
    queue<int> path;
    path.push(/*root node*/);
    vis[/*root node*/] = true;
    while (!path.empth())
    {
        int node = path.front();
        /*record node*/
        path.pop();
        for (int i = 1; i <= N; i++)
        {
            if ((A[node][i] || A[i][node]) && !vis[i])
            {
                path.push(i);
                vis[i] = true;
            }
        }
    }
}

Summarize

Of course, there are many special graphs, such as: binary trees, red-black trees, cyclic graphs and so on. This article introduces the basic knowledge of graphs.

If this article is helpful to you, please give it a positive review. Thank you!

这是洛谷英文原文，本文不严格按照原文句式翻译，可能会存在小部分修改的情况。

什么是图？

图是一种数据结构。它可以用来描述不同物体之间的关系。我们可以在任何地方看到图，比如一个城市的交通图。例如，这是一个图：

这幅无向图有 4 个结点，两条边。

既然有无向图，那肯定有有向图，这就是描述我家谱的有向图：

这又是一个有向图：

现在，你知道了什么是图，下面我将介绍如何在计算机里存储一个图。

存储一个图

算法竞赛中，有两种常用的存储图的方式：邻接矩阵法和邻接链表法。本文中，我只介绍如何使用邻接矩阵法。

无向图

例如，使用邻接矩阵法存储图一，我们将得到以下矩阵：

矩阵中，如果结点 a 与结点 b 之间存在一条边，则 A_{ab}=1 且 A_{ba}=1。

图一中有两条边，它们是：

• 结点 1 与 结点 2
• 结点 2 与 结点 3

因此：

• A_{12},A_{21}=1
• A_{23},A_{32}=1

有向图

有向图的描述就更简单了，如果 a 有一条边指向 b，则 A_{ab}=1。

现在我们尝试存储图三，图三有四条边，他们是：

• 1\to 2
• 2\to 3
• 3\to 4
• 2\to 4

所以，图三的矩阵是这样子的：

带权图

这是一个带权图：

如果结点 a 与结点 b 之间是相连的，且这条边的权值为 k，则 A_{ab}=k，否则 A_{ab}=\infty。

所以，我们就可以得到了图四的矩阵：

使用代码存储图

无向图

我们规定这是图三的输入：

4
1 2
2 3
3 4
2 4

它的意思是：图三有四条边，结点一与结点二相连，结点二与结点三相连，结点三与结点四相连，结点二与结点四相连。

这是存储图的代码：

#include <iostream>
using namespace std;

bool A[10][10];
int n;

int main()
{
    cin >> n;
    while (n--)
    {
        int node1, node2;
        cin >> node1 >> node2;
        A[node1][node2] = 1;
        A[node1][node2] = 1;
    }
    return 0;
}

有向图

有向图不过多赘述了，直接给出代码：

#include <iostream>
using namespace std;

bool A[10][10];
int n;

int main()
{
    cin >> n;
    while (n--)
    {
        int node1, node2;
        cin >> node1 >> node2;
        A[node1][node2] = 1;
    }
    return 0;
}

带权图

同样直接给出代码：

#include <iostream>
using namespace std;
#define oo 123456
int A[10][10];
int n;

int main()
{
    // init
    cin >> n;
    for (int i = 1; i <= 9; i++)
    {
        for (int j = 1; j <= 9; j++)
        {
            A[i][j] = oo;
        }
    }
    while (n--)
    {
        int node1, node2, weight;
        cin >> node1 >> node2 >> weight;
        A[node1][node2] = weight;
    }
    return 0;
}

搜索算法

图有两种搜索算法：深度优先搜索 (dfs)，广度优先搜索 (bfs)。

本文中，我们将第一个要访问的结点称为“根节点”，例如图四中，根节点为 1。

深度优先搜索

你可能学过回溯算法，这是回溯算法的模板：

void backtracking(...)
{
    if (达到边际条件)
    {
        存储结果
        return;
    }
    for (int i = startIndex; i <= n; i++)
    {
        记录值
        backtracking(...);
        撤销值
    }
}

回溯就是一种深度优先搜索，我们由回溯不难得出 dfs 的代码：

bool vis[N]; // 记录用
int n; // 结点个数
void dfs(int node)
{
    if (node == n)
    {
        // 输出路径
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if ((A[i][node] == 1 || A[node][i] == 1) && !vis[i])
        {
            vis[i] = 1; // 防止重复访问
            dfs(i);
            vis[i] = 0;
        }
    }
}

广度优先搜索

实际上，广度优先搜索就是层级遍历，比如，这是图三的 bfs（设根节点为 1）。

bfs 时需要一个队列。首先，我们将根节点放入队列：

队列:
1
结果:

接着，我们记录结点 1，把结点 1 所有的子节点放入队列：

队列:
2
结果:
1

然后，我们记录结点 2，把结点 2 所有的子节点放入队列:

队列:
3 4
结果:
1 2

最后，我们记录结点 3,4，把所有 3,4 的子节点放入队列

队列:
结果:
1 2 4 3

结点 4 没有子节点，结点三有个子节点，但已经被放入结果了

所以这就是 bfs 的代码：

#include <queue> // 头文件
int A[N][N];
bool vis[N]; // 记录
void bfs()
{
    queue<int> path;
    path.push(/*根节点*/);
    vis[/*根节点*/] = true;
    while (!path.empth())
    {
        int node = path.front();
        /*记录结点*/
        path.pop();
        for (int i = 1; i <= N; i++)
        {
            if ((A[node][i] || A[i][node]) && !vis[i])
            {
                path.push(i);
                vis[i] = true;
            }
        }
    }
}

总结

当然，还有很多特殊的图，例如二叉树、红黑树、有环图等等，这里只谈及冰山一角。

如果这篇文章对你有用，请你给作者一个赞，谢谢！

洛谷MYOI快报！

luogu 大战开辟第五战场！

起因

帖主RyexAwl因为某些原因（大概率是被chen_zhe挂到了知乎上）与chen_zhe展开了对线。

责任

当然，两方都有责任。

帖主由于自身原因，报了洛谷的网校课程却没进省队。

@chen_zhe作为大管理，的确不能随意把别人信息挂到第三方网站上。

这件事很值得我们考究。

事实到底是怎样的

帖主卡在瓶颈期了，辱骂洛谷。

见此页Balor说的话与此页he_____he说的话，都表明虽然@RyexAwl有些过分，但实在不应该侵权。

可根据此页chen_zhe亲自证实后，确有此事。

虽然这样，大部分谷民还是选择站在帖主一边。

@听取MLE声一片 
2023-06-09 14:02

简单说一下过程：

昨天晚上在兔群开打，开辟第一战场。

今天中午又在兔群打。

过了一会去 uoj 群打，开辟第二战场。

然后去 LA 群打，开辟第三战场。

接着去 HL1 群打，开辟第四战场。

最后来洛谷讨论区，开辟第五战场。

在第19页帖主的强硬回答更表明事态正在愈发严重。

结果

虽然RyexAwl最后没打赢，但仍有不少人发扬了他的精神，导致这件事发酵的结果正一步步走向不可预测的深渊。

0. 写在前面

本文的每一个章节有一个「推荐阅读」标记，根据读者对不同技术栈、工具的了解程度进行了区分。\small\colorbox{#128e5a}{\color{white}Tool name} 代表「不熟悉/没用过」，\small\colorbox{#3173B3}{\color{white}Tool name} 代表「有一些相关了解，但只会基础操作」，\small\colorbox{orange}{\color{white}Tool name} 代表「非常熟悉」。

示例：

编写 Github Action File

这代表推荐「对 GitHub 有基础了解或者没有了解的读者」阅读此章节。

还有一个标记，\small\colorbox{gray}{\color{white}Magic}，代表对应操作可能需要科学上网。

本文推荐对于 Web 技术有浅显理解的读者阅读，知道「网页」「静态页面/资源」「相对路径」的相关概念，并对各种环境下的命令行相对熟悉。

重要提示：如果你需要搭建 Hexo 博客，请先完整阅读一遍文章再开始。 这关系到你每个步骤的选择以及最终成果。

本文的大部分内容主要是针对「喜欢折腾的」（可能是）小白，并应当知晓「仅使用谷歌浏览器上不了谷歌」的事实。部分文段略显啰嗦，但是对于部分内容因为「不适合」新手接触会写得简略一些。

1. 简介

首先，你的计算机需要安装有：

• Git: https://git-scm.org
• Node.js (版本 12 及以上): https://nodejs.org

如果下载很慢或无法访问，请善用搜索引擎查找可以正常访问的安装程序下载链接，或者科学上网。

这两个程序都是在控制台使用的，因此可能没有图形界面。

此外，非常推荐安装 VSCode 用于博客编辑。

安装 Hexo