HBC237466[HNOI2015]开店,树分治,分治Travel Round the Grid题解

不断提升技能，才能在职场中立于不败之地！全网最全C++题库，助您成为编程领域的佼佼者。

Little G lives in the Grid Country. The Grid Country can be regarded asnmn*mnmpoints, the top left is(1,1)(1,1)(1,1)and the bottom right is(n,m)(n,m)(n,m), and Little G lives in(a,b)(a,b)(a,b). One day, Little G wants to travel round the country forkkkdays. Every day, Little G can move up, down, left or right one step. More formally,(a,b)>(a,b) -> (a,b)>if Little G move up,(a,b)>(a,b) -> (a,b)>if Little G move down,(a,b)>(a,b) -> (a,b)>if Little G move left,(a,b)>(a,b) -> (a,b)>if Little G move right. Afterkkk-days travel, Little G must return home, the point(a,b)(a,b)(a,b). Also, Little G don't want to visit any point twice and Little G can't move out of the country. Please design a travel route for Little G. The travel route is a string of lengthkkk, consists of only ‘U’,‘D’,‘L’,‘R’, which means move up, down, left or right on this day.

Little G lives in the Grid Country. The Grid Country can be regarded as n∗mn*mn∗m points, the top left is (1,1)(1,1)(1,1) and the bottom right is (n,m)(n,m)(n,m), and Little G lives in (a,b)(a,b)(a,b). One day, Little G wants to travel round the country for kkk days. Every day, Little G can move up, down, left or right one step. More formally, (a,b)−>(a−1,b)(a,b) -> (a-1,b)(a,b)−>(a−1,b) if Little G move up, (a,b)−>(a+1,b)(a,b) -> (a+1,b)(a,b)−>(a+1,b) if Little G move down, (a,b)−>(a,b−1)(a,b) -> (a,b-1)(a,b)−>(a,b−1) if Little G move left, (a,b)−>(a,b+1)(a,b) -> (a,b+1)(a,b)−>(a,b+1) if Little G move right. After kkk-days travel, Little G must return home, the point (a,b)(a,b)(a,b) (but Little G doesn't want to return home before the end of the kkk-days travel). Also, Little G don't want to visit any point twice and Little G can't move out of the country. Please design a travel route for Little G. The travel route is a string of length kkk, consists of only ‘U’,‘D’,‘L’,‘R’, which means move up, down, left or right on this day.

标签： HBC237466[HNOI2015]开店 树分治 分治Travel Round the Grid题解