CSUST OJ 7050

题目链接

题目描述

给定两个由数字 0 0 0到 9 9 9构成的序列 s , t s,t s,t，每次选定 s s s的一个连续区间并将其转成升序，在有限步（可以为 0 0 0）后是否能使得 s , t s,t s,t相同？

将一个连续区间变成升序后是不可逆的，那么每次就只选择两个相邻的数字变成升序以减少影响。

考虑去模拟这个过程，注意不要真的去移动实际值，那样的复杂度是不可接受的。

由于数字的种类有限，直接记录每个数字所在的位置，就可以判断当前位置上的所需要的数字是否可以移动到该位置上。

判断方式也很简单，两位置之间没有比它更小的数存在即可移动到所需位置。

所以每次只需要知道该位置（包含在内）之后的每个数字第一次出现的位置，就可以了，考虑使用栈去维护。

---

(赛中思路没理清，写了一堆没用的代码进去（赛后一度想Hack自己），好在基本方向对了)

#include <iostream>
#include <string>
#define str string
using namespace std;

const int N = 1e5 + 10;

str s, t;
int cnt[15], p[15][N];

int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> s >> t;
  int n = s.length();
  for (int i = n - 1; i >= 0; i--) {
    int d = s[i] & 15;
    p[d][++cnt[d]] = i;
  }
  bool ans = true;
  for (char x : t) {
    int d = x & 15;
    if (cnt[d] == 0) {ans = false; break;}
    bool tmp = false;
    for (int i = 0; i < d; i++)
      if (cnt[i] && p[i][cnt[i]] < p[d][cnt[d]]) {
        tmp = true; break;
      }
    if (tmp) {ans = false; break;}
    --cnt[d];
  }
  cout << (ans ? "True" : "False");
  return 0;
}