集训队作业解题报告spoj soilder parade

1、解题报SPOJSoldier还有 M 条限制，每条限制包含 P1,P2,Pk，表示AP1,AP2,APk 这些值互不相同。 奇数位置，34M 2 （或偶数）K条限制(X,Y)，X,Y 奇偶相同，表示 X,Y 这两个位置的数不相同。（就是诸如(X,Y),(Y,Z),(Z,X)的情况值（3,41,24开头就反过来，把所有能推算出来为什么呢？首先，前面定下来的值的边缘肯定是 1 或者 4，(如果是 2，3 那么还能够推算)，肯定是发生在(1,2),(1,1),(4,4),(4,3)之间的，就算交换前面的值，只能将 1 换成 2，将 3 换成 4，因此还是，所以肯定无解。这样每个位置顶多被枚举 2 次

2、，每条限制最多被检查 2 次，所以整个算法的时间复杂度就是 O(N+M)。SPOJProblemStarting from the new year onwards, some provinces are changing their set of protocolrules.AstheSeniorMilitarySecretaryofProtocol,itisyourtasktoapprove the new rules. To your surprise, some of the provinces have put forward protocol rules which are qui

3、te impossible to fulfill, even if the soldiers were to be specially on no account approve their laws.The line of input contains a single positive integer t=10 - the number of provinceswhichareproposingnewlaws.tsetsofrulesfollow,separatedbyempty Each set of rule begins with a line containing two non-

4、negative integers n p (n=100000, p=100000) - the number of soldiers arranged and the number of rules proposed in the province, respectively. Each of the next p lines contains a single rule: an integer bi (2=bi=n), followed by bi integers a1,a2,.,abi (1=ak=n).Sucharulemeansthatsoldiersstandingatpositionsa1,a2,.,abimust all be of different rank.For every set of rules presented at input, output a single line containing the word rejectedifnounitofsoldierscanbearrangedinaccordancewithprotocol,orthe word approvedin the opposite case.21215231 34