題目鏈接
題目描述
給定兩個由數字 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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/300506.html
標籤：其他