GDKOI 2021 提高组第一试：图论与算法挑战

"GDKOI TG DAY1.pdf 是2021年广东省重点中学信息学冬令营(GDKOI2021)提高组第一试的比赛资料，包含了四道编程题目，分别为‘割’、‘忙碌的出题人’、‘回文’和‘东方永夜抄’。比赛语言为C++，使用的编译器版本为g++4.8.4，对于64位整数输入输出格式要求使用%lld。每道题目都有特定的输入输出文件名、时间限制和空间限制，且所有题目都有满分100分。第一题‘割’是一个图论问题，要求找到一个图的分割使得割的边数至少是边总数的1.5倍。第二题‘忙碌的出题人’、第三题‘回文’和第四题‘东方永夜抄’的具体细节未给出。" 本资源主要涉及的信息点有： 1. **比赛背景**：GDKOI2021是一个面向广东省重点中学的提高组信息学冬令营活动，第一试包含四道编程题目。 2. **编程语言与环境**：比赛使用C++语言，编译器为g++4.8.4。参赛者需注意64位整数的输入输出格式。 3. **比赛规则**：参赛者需按照题目要求的格式输入和输出，超时或不遵循格式都会影响得分。输入文件格式不需判断错误，文件名已给定。提交的源代码将作为评分依据。 4. **题目设置**：四道题目分别为： - **割**：这是一道图论问题，要求在无向图中找到两个集合S和T，使得它们的并集等于图的顶点集，且割的边数（连接S和T的边）至少为边总数的1.5倍。输入包括图的顶点数n和边数m，以及边的连接信息。输出是一个由0和1组成的字符串，表示每个顶点属于集合S(1)还是T(0)。题目保证有解，可以输出任意满足条件的解。 - **忙碌的出题人**、**回文**和**东方永夜抄**：这三道题目的具体细节未在摘要中提供，可能需要查阅完整的比赛文档获取详细信息。 5. **时间与空间限制**：每道题目的运行时间限制和内存限制都在512MB以内，具体时间限制因题目而异。 6. **评分标准**：每题满分为100分，评判标准基于源代码。 对于参与此类竞赛的学生，除了掌握基本的C++编程技巧，还需要熟悉图论（如最大流、最小割等概念）、算法设计和优化，以及如何在限制时间内高效地处理大量数据。此外，理解和遵循比赛规则也是取得好成绩的关键。