Wooden Sticks Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 19008 Accepted: 8012 Description
There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows: (a) The setup time for the first wooden stick is 1 minute. (b) Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l’ and weight w’ if l <= l’ and w <= w’. Otherwise, it will need 1 minute for setup. You are to find the minimum setup time to process a given pile of n wooden sticks. For example, if you have five sticks whose pairs of length and weight are ( 9 , 4 ) , ( 2 , 5 ) , ( 1 , 2 ) , ( 5 , 3 ) , and ( 4 , 1 ) , then the minimum setup time should be 2 minutes since there is a sequence of pairs ( 4 , 1 ) , ( 5 , 3 ) , ( 9 , 4 ) , ( 1 , 2 ) , ( 2 , 5 ) . Input
Description
Matt has N friends. They are playing a game together.
Each of Matt’s friends has a magic number. In the game, Matt selects some (could be zero) of his friends. If the xor (exclusive-or) sum of the selected friends’magic numbers is no less than M , Matt wins.
题意是说用 k 种颜色填充 nm 的方格，第 i 种颜色要用 c[i] 次，保证 c[i]（i 属于 1..k）的和为 nm，问是否有可行解，若有，输出任意一种。 第一感觉是 dfs，而且数据范围还那么小。但是鉴于我上次 dfs 写成汪的经历……嗯，不过群里有学长说似乎剪枝不太好想？ 我一开始分了四类：o 行 o 列、e 行 e 列、e 行 o 列、o 行 e 列（o 是 odd，e 是 even），然后将 c[i] 排序，先填大的 c[i]，感觉这样应该更容易找到解。交了一发，WA 掉了。发现当 k 较小的时候，也就是 c[i] 都相对较大的时候，先填大的 c[i] 的策略会出现错误。于是我换了下，按 c[i] 的大小从两边往中间填。然后我还发现其实 o 行 o 列和 e 行 e 列可以归为一类，同理，后两种也可以归为一类。又交，又 WA 2333333。然后想了好久，发现对于上面说的两类的处理顺序不同会得到不同的结果，只有一种是对的。于是加了个 judge 函数判断冲突，如果冲突就换个顺序。再交，A 了。