c781: PD. 質數圖
標籤 :
通過比率 : 88% (7 人 / 8 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-10-27 00:46

內容

建構一個有2N個點的質數圖,其中編號為0到2N-1的整數,編號i和編號j的點有連邊若且維若4N-i-j是質數。我們稱這張圖為質數圖G_N。
現在,你必須求出G_N上最小字典序的最大匹配。

一張圖G邊集的子集E,滿足對所有e1,e2在邊集中且e1不等於e2均有e1和e2沒有公共點,則稱E為G上的一個匹配。
若G上的匹配E,滿足對所有G上的其他匹配E' 都有|E'|<=|E|,則我們稱E為圖G上的最大匹配。

我們將一條邊記為(a,b),代表這條邊兩端的編號是a,b且a<b。
若兩條邊x=(a,b),y=(c,d)滿足a<c或(a=c且b<d),則定義x<y。

定義一個邊集的排序S(E)=(e1,e2,...,ek)代表將E中所有邊由小到大排序。(
那們我們說E的字典序比另一個邊集F小若且維若S(E)的字典序比S(F)的字典序小

例如:當N=4時,{(0,3),(1,2),(4,5),(6,7)}的字典序比{(0,3),(1,2),(4,7),(5,6)}小。

輸入說明

輸入第一行有一個正整數$t\left( t\leq 5\right)$,表示一共有$t$筆測資。
接下來每行有一個正整數$N\left( 2\leq N\leq 2345678\right)$。

輸出說明

對每一筆測資,假設$X$為最大匹配的大小,你必須把$G_N$內的邊集輸出,一共輸出$X$行,每行都是兩個正整數$a$ $b$,表示$\left(a,b\right)$在$G_N$中,注意輸出時要將所有邊從小到大排序,且必須有$a<b$(即編號小的頂點在前)

由於有字典序的限制,因此答案是唯一的。

範例輸入
1
3
範例輸出
0 1
2 3
4 5
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (30%): 1.0s , <1K
不公開 測資點#2 (30%): 1.0s , <1K
不公開 測資點#3 (30%): 1.0s , <1K
提示 :

Subtasks:
N<=10 10%
N<=1000 30%
無限制 60%

 

 

感謝rsabcmoi贊助

標籤:
出處:
2018高雄市高師大附中資訊學科能力 [編輯:
ltf0501 (ltfsjl)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」