【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;
}