某渣A的某渣算法問題。有興趣的來做一下罷~

白银の式神

有一系列不重複的元素，a,b,c,d,e,...（也可以用整數1,2,3...表示）
每2個元素可以組成一個元素對(a,b),(a,d)
元素對不考慮順序，即(a,b)=(b,a)

需要給元素對設置標記，設置標記有3種指令格式
set a+b+c=red  即設置(a,b) (a,c) (b,c)=red
set a,b+c=red  即設置(a,b) (a,c) =red
set a,b=red  即設置(a,b) =red

現在用戶輸入一系列不重複的元素對
給出用最少的指令條數完整的且不重複的給用戶輸入的元素對設置標記的分組方法。

實例:
輸入
(a,b) (a,c) (a,e) (b,c) (b,e) (b,f) (c,e) (d,f)
輸出
set a+b+c+e
set f,b+d

Renee

表述上看起来貌似就很麻烦了~~

我大致想起来大约就是在指定正方形2维表上填色的游戏吧?~~由于坐标可以交换~~其实就只要考虑上三角就可以了~~填色方式有三角形(有转折的三个相连格子)、直线(两个相连格)、点(单个格子)~~

然后就是要求填色次数最少的方案罢？~~

Renee

跳格相加也可以么？

a+b+d？

原来也可以4连加。。

白银の式神

不一定要相連啊
(1,2) (1,4) (1,6)=set 1,2+4+6
(1,2) (1,4) (1,6) (2,4) (2,6) (4,6)=set 1+2+4+6
之所以偶用字母就素爲了防止誤解成連續的

Renee

唔~~你没有提及可以3个数以上连加嘛~~而且例子也是连一起的abc~~

我重新考虑下~~所谓连加无论几个元素都算一次操作嘛？~~

白银の式神

再解釋一下好了
前2條指令沒有個數限制，只要滿足條件
set a+b+c+d...指a,b,c,d...兩兩之間有元素對
即(a,b) (a,c),(a,d) (b,c) (b,d) (c,d)
如果增加一個e的話則要求e和前4個元素都要有元素對
set a,b+c+d...指元素對中a固定，另一個元素是b,c,d...
即(a,b) (a,c) (a,d)...
set a,b指單一元素對(a,b)

Renee

简单地说~~如果整个序列中存在有N个元素两两之间都有对应关系~~这N个元素就可以统一加起来算一次操作罢？~~