Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

一种解题思路

Posted by huicpc39 at 2007-09-07 00:34:45 on Problem 1058
其实,这个题可以不用(标程)搜索求解,解可以直接生成。思路如下:
首先,可以从前三天的列表得到后两天的相容(也即尚未同桌)关系。如下面是前三天的安排:
MFKP  BELO   CHIN   DGJA
MEIA  CGKO   BFJN   DHLP
MBCD  EFGH   IJKL   ANOP
则每个人的相容关系为:
A:BCFHKL
B:AGHIKP
.....
因为每两个人之间必须有一次同桌,所以A、B一定有一次同坐,而与A、B都相容的是H、K,所以第四天第一桌为:ABHK,而第五天第一桌为:ACFL(与A相容剩下的)。第五天第2,3,4桌用如下方法得到,依次取出第四天第一桌ABHK的一个字母,加上其相容关系剩下的。如第二个字母是B,与B相容剩下的是GIP,所以第二桌为BGIP。
同样可以得到第四天剩下桌的排列。
上述排桌位的过程中,如果某次一桌人数不等于4,结果为“不可能”。


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator