专栏文章

题解:AT_arc081_c [ARC081E] Don't Be a Subsequence

AT_arc081_c题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minci9na
此快照首次捕获于
2025/12/02 00:10
3 个月前
此快照最后确认于
2025/12/02 00:10
3 个月前
查看原文
记录下一个出现的位置,由于 queue 内部严格字典序递增,所以可以直接把每个位置使用了就标记。至于怎么记录,没有优化的时候可以考虑直接用数组模拟队列,记录下标即可。

code

CPP
#pragma GCC optimize(3)
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using ai2 = array<int, 2>;
const int N = 2e5 + 10;
int n, pos[N][26], nxt[26];
bool vis[N];
string str;
struct Node {
	int u, lst;
} que[N << 8];
void dfs(int u) {
	if(!u) return ;
	dfs(que[u].lst);
	cout << str[que[u].u];
}
int main() {
	ios::sync_with_stdio(false);
	
	cin >> str;
	n = str.size();
	str = ' ' + str;
	for(int i = n; ~i; i --) {
		for(int j = 0; j < 26; j ++) pos[i][j] = nxt[j];
		if(i) nxt[str[i] - 'a'] = i;
	}
	int hh = 1, tt = 0;
	for(int i = 0; i < 26; i ++) {
		if(pos[0][i]) que[++ tt] = Node{pos[0][i], 0};
		else return cout << (char)(i + 'a') << '\n', 0;
	}
	while(hh <= tt) {
		auto [u, lst] = que[hh ++];
		vis[u] = true;
		for(int i = 0; i < 26; i ++) {
			if(pos[u][i]) {
				if(vis[pos[u][i]]) continue;
				vis[pos[u][i]] = true;
				que[++ tt] = Node{pos[u][i], hh - 1};
			} else {
				dfs(hh - 1);
				cout << (char)(i + 'a');
				return 0;
			}
		}
	}
	return 0;
}

评论

0 条评论,欢迎与作者交流。

正在加载评论...