P3042 [USACO12JAN]牛跑Cow Run

    • 30通过
    • 129提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 贪心 连通块 队列 USACO 2012 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Farmer John and Bessie have devised a new exercise game for the cows. The cows are running on a circular track of length M (2 <= M <= 1,000,000,000) starting from the same position. The game proceeds in N (1 <= N <= 14) rounds using a deck of 8N cards each with a number X_i (0 <= X_i < M) written on it.

    Each round FJ moves the top 8 cards into a separate pile and selects either the top 4 or bottom 4 cards for Bessie to play with. Bessie then chooses either the top 2 cards or bottom 2 cards of the 4 cards FJ selected. After this FJ calls out the number on the top card, X_top, and the cows run a distance of R * X_top, where R is the total distance the cows have run so far. Bessie then calls out the number on the bottom card, X_bottom, and the cows run a distance of X_bottom.

    FJ is concerned that after the exercise the cows will be too tired to get back to the beginning of the track if they end up too far away. He believes if the cows end up more than a distance of K (0 <= K <= floor(M/2)) from their starting position they won't be able to get back home.

    It is guaranteed that if FJ plays correctly, he will always be able to ensure the cows can come home, irrespective of the moves made by Bessie! For each round, your task is to determine which half of the cards FJ should choose such that no matter what Bessie does from that point on, FJ can always get the cows home. Bessie will then make the move provided in the input and you can then continue onto the next round. Note that even though Bessie's moves are provided to you in the input, you are to specify moves for FJ that would have worked no matter what Bessie chooses (so it is effectively as if FJ does not really know what Bessie will do during her moves).

    FJ和贝茜为奶牛们设计了一个新的跑步游戏。跑道是环行的,长度为(2 <= M <= 1,000,000,000)的环行,奶牛们在相同的起跑位置。这个游戏一共要进行N (1 <= N <= 14)轮,通过一副8N张的纸牌来控制每一轮的跑步距离,每张纸牌都有一个数字X_i (0 <= X_i < M)。

    每一轮,FJ取出最上面的8张纸牌,然后再取出这8张的上面或者底下的4张。接着,贝茜从这4张牌中取出上面或者底下的2张,上面一张的数字为X_top,下面一张的数字是X_bottom,则牛先跑R*X_top的距离(R表示奶牛们已经跑过的距离),再跑X_bottom的距离。

    FJ担心奶牛们太累而回不到起点,游戏结束时,若奶牛们离开起点距离超过K (0 <= K <=floor(M/2)),则他们就回不了起点了。

    问题保证,当FJ选择正确的取牌策略,不论贝西如何取牌,奶牛们都能够回到起点。对于每一轮,你的任务是决定取哪4张纸牌。在输入数据中,贝西的每次选择都是已知的,但FJ的每次取牌时,贝西接着的选择应该被假定为是未知的,即不论贝西怎么选,FJ的选择都是能保证奶牛们能够回到起点。

    输入输出格式

    输入格式:

    * Line 1: Three space-separated integers N, M, K

    * Line 2: A string N characters. If the ith character is 'T' it means Bessie will select the top 2 cards in the ith round. Otherwise the ith character will be 'B' to indicate Bessie will select the bottom 2 cards in the ith round.

    * Lines 3..2+N: Each line contains eight integers representing the 8 cards to be used that round from top to bottom.

    输出格式:

    * Line 1: A string of N characters where the ith character is 'T' if FJ should choose the top 4 cards or 'B' if FJ should choose the bottom 4 cards in the ith round. If there are multiple ways to get the cows home, choose the lexicographically first (that is, the string that is alphabetically smallest).

    输入输出样例

    输入样例#1: 复制
    2 2 0 
    TT 
    1 0 0 0 0 0 0 1 
    0 1 1 1 0 0 1 0 
    
    输出样例#1: 复制
    TB 
    

    说明

    The cows must end up exactly where they started to be able to come home. Note that FJ is not aware of what choices Bessie is going to make beforehand. If FJ did know, he could have chosen the bottom half each time.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。