流浪地球

题目描述

流浪地球计划在赤道上均匀部署了N个转向发动机, 按位置顺序编号为0~N-1.

1. 初始状态下所有的发动机都是未启动状态
2. 发动机启动的方式分为"手动启动"和"关联启动"两种方式
3. 如果在时刻1一个发动机被启动, 下一个时刻2与之相邻的两个发动机就会被"关联启动"
4. 如果准备启动某个发动机时, 它已经被启动了, 则什么都不用做
5. 发动机0与发动机N-1是相邻的

地球联合政府准备挑选某些发动机在某些时刻进行"手动启动", 当然最终所有的发动机都会被启动.

哪些发动机最晚被启动呢?

输入描述

• 第一行两个数字N和E, 中间有空格
  • N代表部署发动机的总个数, E代表计划手动启动的发动机总个数
  • 1 < N <= 1000, 1 <= E <= 1000, E <= N
• 接下来共E行, 每行都是两个数字T和P, 中间有空格
  • T代表发动机的手动启动时刻, P代表此发动机的位置编号
  • 0 <= T <= N, 0 <= P < N

输出描述

• 第一行一个数字N, 以回车结束
  • N代表最后被启动的发动机个数
• 第二行N个数字, 中间有空格, 以回车结束
  • 每个数字代表发动机的位置编号, 从小到大排序

示例1

输入:

8 2
0 2
0 6

输出:

2
0 4

示例2

输入:

8 2
0 0
1 7

输出:

1
4

题解

对于离散型的问题, 我们可以使用快照的方式, 下个快照里的状态是基于当前状态的变化.

Python

def main():
    # 读取输入
    parts = input().split()
    assert len(parts) == 2
    num_engines = int(parts[0])
    num_initial_startup = int(parts[1])

    # 引擎初始状态
    initials = []

    # 哪些引擎是被"手动启动"的
    for i in range(num_initial_startup):
        parts = input().split()
        assert len(parts) == 2
        tick = int(parts[0])
        position = int(parts[1])
        initials.append((tick, position))

    # 标记引擎是否点火
    engines = [False for i in range(num_engines)]

    engines_started = 0
    # 记录本轮中点火的引擎
    started_this_round = []

    # 模拟每个时间点
    for tick in range(num_engines):
        # 如果所有引擎都已点火, 就终止循环
        if engines_started == num_engines:
            break

        started_this_round.clear()
        # 当前时间点中的快照
        snapshot = engines[:]

        # "关联启动"模式, 启动相邻的引擎
        for index in range(num_engines):
            # 当前引擎已经被启动
            if engines[index]:
                #print("CHECK sibling:", index)
                previous_index = (num_engines + index - 1) % num_engines
                next_index = (index + 1) % num_engines
                if not snapshot[previous_index]:
                    snapshot[previous_index] = True
                    started_this_round.append(previous_index)
                    engines_started += 1
                    #print("  START previous:", previous_index)
                if not snapshot[next_index]:
                    snapshot[next_index] = True
                    started_this_round.append(next_index)
                    engines_started += 1
                    #print("  START next:", next_index)

        # 检查"手动启动"的引擎
        for (initial_tick, initial_position) in initials:
            if initial_tick == tick and not snapshot[initial_position]:
                snapshot[initial_position] = True
                engines_started += 1
                started_this_round.append(initial_position)
                #print("START initial:", initial_position)

        # 保存快照
        engines = snapshot

    # 打印结果
    print("%d" % len(started_this_round))
    print(" ".join(str(pos) for pos in started_this_round))


if __name__ == "__main__":
    main()

C++

#include <cassert>
#include <iostream>
#include <tuple>
#include <vector>

int main() {
  // 读取输入
  int num_engines = 0 ;
  int num_initial_startup = 0;
  std::cin >> num_engines >> num_initial_startup;
  assert(1 <= num_engines && num_engines <= 1000);
  assert(1 <= num_initial_startup && num_engines <= 1000);

  // 引擎初始状态, (tick, position)
  std::vector<std::tuple<int, int>> initials;

  // 哪些引擎是被"手动启动"的
  for (int i = 0; i < num_initial_startup; ++i) {
    int tick = 0;
    int pos = 0;
    std::cin >> tick >> pos;
    initials.emplace_back(tick, pos);
  }

  // 标记引擎是否点火
  std::vector<bool> engines(num_engines, false);

  int engines_started = 0;
  // 记录本轮中点火的引擎
  std::vector<int> started_this_round;

  // 模拟每个时间点
  // 如果所有引擎都已点火, 就终止循环
  for (int tick = 0; engines_started < num_engines; ++tick) {
    started_this_round.clear();

    // 当前时间点中的快照
    std::vector<bool> snapshot = engines;

    // "关联启动"模式, 启动相邻的引擎
    for (int index = 0; index < num_engines; ++index) {
      // 当前引擎已经被启动
      if (engines[index]) {
        //std::cout << "CHECK sibling: " << index << std::endl;
        const int previous_index = (num_engines + index - 1) % num_engines;
        const int next_index = (index + 1) % num_engines;
        if (!snapshot[previous_index]) {
          snapshot[previous_index] = true;
          started_this_round.push_back(previous_index);
          engines_started += 1;
          //std::cout << "  START previous: " << previous_index << std::endl;
        }
        if (!snapshot[next_index]) {
          snapshot[next_index] = true;
          started_this_round.push_back(next_index);
          engines_started += 1;
          //std::cout << "  START next: " << next_index << std::endl;
        }
      }
    }

    // 检查"手动启动"的引擎
    for (const auto initial: initials) {
      const int initial_tick = std::get<0>(initial);
      const int initial_position = std::get<1>(initial);
      if (initial_tick == tick && !snapshot[initial_position]) {
        snapshot[initial_position] = true;
        engines_started += 1;
        started_this_round.push_back(initial_position);
      }
    }

    // 保存快照
    engines = snapshot;
  }

  // 打印结果
  std::cout << started_this_round.size() << std::endl;
  for (int i = 0; i + 1 < started_this_round.size(); ++i) {
    std::cout << started_this_round[i] << " ";
  }
  if (!started_this_round.empty()) {
    std::cout << started_this_round[started_this_round.size() - 1] << std::endl;
  }

  return 0;
}

Rust

use std::io::{stdin, BufRead};

fn main() {
    // 读取输入
    let mut line = String::new();
    let ret = stdin().lock().read_line(&mut line);
    assert!(ret.is_ok());
    let mut parts = line.split_ascii_whitespace();
    let num_engines: usize = parts.next().unwrap().parse().unwrap();
    let num_initial_startup: usize = parts.next().unwrap().parse().unwrap();
    assert!((1..=1000).contains(&num_engines));
    assert!((1..=1000).contains(&num_initial_startup));

    // 引擎初始状态
    let mut initials = Vec::with_capacity(num_initial_startup);

    // 哪些引擎是被"手动启动"的
    for _i in 0..num_initial_startup {
        line.clear();
        let ret = stdin().lock().read_line(&mut line);
        assert!(ret.is_ok());
        let mut parts = line.split_ascii_whitespace();
        let tick: usize = parts.next().unwrap().parse().unwrap();
        let pos: usize = parts.next().unwrap().parse().unwrap();
        initials.push((tick, pos));
    }

    // 标记引擎是否点火
    let mut engines = vec![false; num_engines];

    let mut engines_started = 0;

    // 记录本轮中点火的引擎
    let mut started_this_round = Vec::<usize>::new();

    // 模拟每个时间点
    for tick in 0..num_engines {
        // 如果所有引擎都已点火, 就终止循环
        if engines_started == num_engines {
            break;
        }

        started_this_round.clear();

        // 当前时间点中的快照
        let mut snapshot = engines.clone();

        // "关联启动"模式, 启动相邻的引擎
        for (index, engine_started) in engines.iter().enumerate() {
            // 当前引擎已经被启动
            if *engine_started {
                println!("CHECK sibling: {index}");
                let previous_index = (num_engines + index - 1) % num_engines;
                let next_index = (index + 1) % num_engines;
                if !snapshot[previous_index] {
                    snapshot[previous_index] = true;
                    started_this_round.push(previous_index);
                    engines_started += 1;
                    println!("  START previous: {previous_index}");
                }
                if !snapshot[next_index] {
                    snapshot[next_index] = true;
                    started_this_round.push(next_index);
                    engines_started += 1;
                    println!("  START next: {next_index}");
                }
            }
        }

        // 检查"手动启动"的引擎
        for (initial_tick, initial_position) in &initials {
            if *initial_tick == tick && !snapshot[*initial_position] {
                snapshot[*initial_position] = true;
                engines_started += 1;
                started_this_round.push(*initial_position);
                println!("START initial: {initial_position}");
            }
        }

        // 保存快照
        engines.clone_from(&snapshot);
    }

    // 打印结果
    println!("{}", started_this_round.len());
    let s = started_this_round
        .into_iter()
        .map(|x| x.to_string())
        .collect::<Vec<_>>()
        .join(" ");
    println!("{s}");
}