【GDKOI】2021提高Day1

2021 年广东省重点中学信息学冬令营 (GDKOI 2021)

提高组 第一试

2021 年 1 月 29 日

注意事项

1. 严格按照题目所要求的格式进行输入、输出，否则严重影响得分。
2. 题目测试数据有严格的时间限制，超时不得分。
3. 输入文件格式不用判错；输入输出文件名均已给定，不用键盘输入。
4. 提交文件夹及保存方式请参考《考生注意事项》。评测以源程序为准。
5. 评测环境为 NOI 系列活动标准竞赛环境，编译器版本为 g++ 4.8.4。
6. 对于 C++ 选手，64 位整数输入输出格式为 %lld。

7. 本次竞赛的最终解释权归 GDOI 评委会所有。

   试题名称 割 忙碌的出题人 回文 东方永夜抄

   提交文件名 cut.cpp busy.cpp palindrome.cpp night.cpp

   输入文件名 cut.in busy.in palindrome.in night.in

   输出文件名 cut.out busy.out palindrome.out night.out

   时间限制 1s 1s 3.5s 1s

   空间限制 512MB 512MB 512MB 512MB

   编译选项 -O2

   满分 100 100 100 100

   第 1 页 共 6 页

   GDKOI 2021 TG Day1

第一题 割

提交文件: cut.cpp

输入文件: cut.in

输出文件: cut.out

时间空间限制： 1s, 512MB

有一个无向图 G = (V, E)，将 V 分成两个集合 S, T 使得 S ∩ T = ∅ 且 S ∪ T = V ，定义割为：

Cut(S, T) = {e = (x, y) ∈ E|x ∈ S, y ∈ T} 求 S, T 使得 |Cut(S, T)| ≥ 12 |E|。如有多种解，任意输出一种即可。

输入格式

第一行两个整数 n, m，表示 G 的点数以及边数。

接下来 m 行，每行两个数 x, y，表示一条边。

输出格式

输出一行，共 n 个数字 0 或 1，1 表示第 i 个点在集合 S 中，否则在集合 T 中。

保证一定有解，输出任意一组解即可。

样例数据

cut.in cut.out

4 6

1 2

1 3

1 4

2 3

2 4

3 4

0 0 1 1

数据范围

保证没有自环，注意重边需要重复计算。

对于 30% 的数据，n ≤ 20。

对于另外 20% 的数据，G 是二分图。

对于 100% 的数据，n ≤ 105

, m ≤ 2 × 105。第 2 页 共 6 页

GDKOI 2021 TG Day1

第二题 忙碌的出题人

提交文件: busy.cpp

输入文件: busy.in

输出文件: busy.out

时间空间限制： 1s, 512MB

出题人很忙，他不是在赶 ddl，就是在赶 ddl 的路上。

然而出题人很贪玩，他喜欢忙里抽空，在夜之城伸张正义。

某一天他来到了夜之城的一个神秘的街区。这个街区可以看做由网格中若干个边长为 1 的正方形 (block)

组成。

这个街区的形状很有特点，街区下端的边界是一条长为 n 的公路，被在网格图上能被分成 n 段。第 i 段

上方有 ai 个 blocks。如下图所示。

图 1: 街区

出题人在街区中解决大大小小的犯罪团伙的时候，想到了这样一个无厘头的问题：

假如出题人在夜之城找到了某种区域性武器。他可以把武器布置在下端的公路上。这种武器的攻击范围

是一个矩形，矩形的下边界必须与公路贴合。上边界必须与街区的某一个上边界贴合。他想知道，如果把所

有可能的攻击范围按面积从小到大排序，第 L 大到第 R 大的面积是多少。

出题人很善良，不想让选手看很长的题面，于是给出了一个简洁的题面：

给出长为 n 的序列 a1, a2, · · · , an，记

f(l, r) = (r l + 1) · min

l≤i≤r ai

若将所有的 f(l, r)(1 ≤ l ≤ r ≤ n) 从小到大排序，求排名为 L 到 R 的所有的 f 值。

输入格式

第一行一个正整数 n，表示序列 a 的长度。

第二行 n 个整数，表示 a1, · · · , an。

第三行两个整数 L, R，表示询问的排名区间。

输出格式

一行，共 R L + 1 个整数，第 i 个数表示排名在 L + i 1 的 f 值。

第 3 页 共 6 页

GDKOI 2021 TG Day1

样例数据

busy.in busy.out

8

1 5 10 4 7 8 1 2

4 10

2 2 2 3 3 3 4

数据范围

对于 20% 的数据，n ≤ 500；

对于 40% 的数据，n ≤ 10000；

另外存在 20% 的数据，保证 L = R；

对于 100%，n ≤ 3 × 105

, ai ≤ 109, 1 ≤ L ≤ R ≤ n(n+1)

2

, R L + 1 ≤ 3 × 105。 第 4 页 共 6 页

GDKOI 2021 TG Day1

第三题 回文

提交文件: palindrome.cpp

输入文件: palindrome.in

输出文件: palindrome.out

时间空间限制： 3.5s, 512MB

定义回文串为满足如下性质的字符串 t = t1t2 · · ·tn： ti = tn i+1 1 ≤ i ≤ n

给定一个字符串 s，以及 q 个询问。

每次询问给定两个整数 li

, ri，你能回答 s[li

, ri] 的最长回文子串的长度是多少吗？

输入格式

第一行一个字符串 s。

第二行一个整数 q，表示询问个数。

接下来 q 行，每行两个整数 li

, ri，表示询问 s[li

, ri] 的最长回文子串的长度。

输出格式

对于每个询问，输出一个整数表示 s[li

, ri] 的最长回文子串的长度。

样例数据

palindrome.in palindrome.out

aaacbdccccadaadabbdbadcbcbbadcadb

6

5 22

1 18

15 33

1 33

8 12

15 27

663633

数据范围

对于 10% 的数据, 保证 n ≤ 300, q ≤ 300。

对于 30% 的数据, 保证 n ≤ 5000, q ≤ 5000。

对于 70% 的数据, 保证 n ≤ 5 × 104

, q ≤ 5 × 104。

对于 100% 的数据, 保证 n ≤ 5 × 105

, q ≤ 5 × 105。 第 5 页 共 6 页

GDKOI 2021 TG Day1

第四题 东方永夜抄

提交文件: night.cpp

输入文件: night.in

输出文件: night.out

时间空间限制： 1s, 512MB

您在玩东方永夜抄。

历经重重磨难，您终于来到了辉夜姬面前，回答出了五个难题。

“想要通关，你还需要解决这第六道题哦”，等待您的却是这样的回答：

“我有一棵有根二叉树，但我已经遗忘了它本来的样子。

“我只知道它有 n 个叶子，每个叶子的美观度为 1，每个非叶节点均有两个儿子。

“我还记得 k 个信息，对于每个非叶节点，如果其左儿子的叶子节点个数为 si，则其美观度为 vi。

“如果 k 条信息均不满足，那么其美观度为 A。

“二叉树的美观度为所有节点美观度的乘积，现在请你告诉我所有可能的二叉树的美观度之和。”

是时候面对这最终的挑战了。

答案可能很大，您只需要回答答案对 109 + 7 取模之后的结果。

输入格式

第一行三个整数，表示 n, k, A。

接下来 k 行，每行两个整数，表示 si 和 vi。

输出格式

输出一行，一个整数，表示答案对 109 + 7 取模 之后的结果。

样例数据

night.in night.out

5 1 1

2 2

25

6 2 1

2 3

4 5

268

数据范围

本题采用子任务捆绑评测。

对于所有数据，满足 1 ≤ n ≤ 106, 0 ≤ k ≤ 10, 1 ≤ si < n, 0 ≤ vi

, A < 109 + 7，同时保证 ∀i = j, si = sj。

Subtask 1(20 pts)：n ≤ 103

Subtask 2(10 pts)：k = 0

Subtask 3(40 pts)：n ≤ 5 × 104

Subtask 4(30 pts)：无特殊限制

代码

T1

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct jgt
{
	int x,y,nxt;
} e[200010];
int head[100010],ans[100010];
int main()
{
	freopen("cut.in","r",stdin);
	freopen("cut.out","w",stdout);
	int n,m,sum0,sum1,i,j;
	scanf("%d%d",&n,&m);
	memset(ans,0,sizeof(ans));
	for(i=1; i<=m; i++)
		scanf("%d%d",&e[i].x,&e[i].y),e[i].nxt=head[e[i].x],head[e[i].x]=i;
	for(i=2; i<=n; ans[i]=(sum0>sum1),i++)
		for(sum0=sum1=0,j=head[i]; j; j=e[j].nxt)
			sum0+=(ans[e[j].y]==0),sum1+=(ans[e[j].y]==1);
	for(i=1; i<=n; i++)
		printf("%d ",ans[i]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}