[Mujin17A] Robot Racing 题解

FFTotoro · 2022-10-12 21:05:41 · 题解

Part 1：前言

本题具有较高的思维难度，AtCoder Problems 评分 1900，个人认为应该评蓝。

Part 2：500 分做法

因为 N\le 8，N! 可以枚举全部的排列。对于每个排列，只要按照顺序判定机器人是否能够到达终点即可。

这里我们需要应用一个重要的性质：机器人 k 最初能够到达目标的充分必要条件是：对于各 i<k，x_i\ge 2i-1 成立。

证明：

• 条件 x_i\ge 2i-1 成立时，对于各 i<k，机器人 i 向坐标 2i-1 移动后，可使机器人 k 到达目标。
• 反之，如果条件不成立，存在 x_j<2j-1 的 j(<k)。假设机器人 k 跳过各 i<k 到达目标。机器人 k 跳过机器人 i 时，将机器人 i 的坐标设为 y_i。那么，0<y_1,y_2-y_1\ge 2,y_j-y_j-1\ge2,y_j<2j-1。很显然，这是矛盾的。

因此，要按照排列 p_1,\ldots,p_N 的顺序判定机器人能否到达目标，如下所示即可：

• 首先，检查机器人 p_1 的上述条件是否成立。
• 接下来，去除机器人 p_1，检查机器人 p_2 的上述条件是否成立。
• 以此类推。

Part 3：900 分（AC）做法

首先计算最初能到达目标的机器人的个数：很显然，我们需要从这些机器人中选择 1 个作为第一个到达目标的机器人。

我们可以使用一个栈，从左到右不断地放入机器人。在栈中放入机器人时，如果该机器人是栈中的第 k 个元素且坐标小于 2k-1，则将该机器人弹出并将答案乘以 k（因为我们必须去除这些 k 个机器人中的任意一个）。

将所有机器人放入栈后，进入栈中的机器人可以按照任意顺序到达目标；因此，将剩余机器人个数的阶乘乘以答案即可。

Part 4：代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int m=1e9+7;
main(){
  ios::sync_with_stdio(false);
  int n,c=0,s=1; cin>>n;
  for(int i=0;i<n;i++){
    int x; cin>>x;
    if(x<(c<<1|1))s=s*(c+1)%m;
    else c++;
  }
  while(c)s=s*c--%m;
  cout<<s<<endl;
  return 0;
}