QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#855098#9925. LR StringRepeaterRE 1ms3572kbC++201.4kb2025-01-12 14:32:272025-01-12 14:32:27

Judging History

你现在查看的是最新测评结果

  • [2025-01-12 14:32:27]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3572kb
  • [2025-01-12 14:32:27]
  • 提交

answer

#include <bits/stdc++.h>

void solve()
{
	std::string s; std::cin >> s;
	int n = s.size();

	std::vector nxt(100, std::vector<int>(n, -1));
	std::vector<std::vector<int>> pos(100);
	std::vector<int> lst(100, -1);
	for(int i = 0; i < n; i++)
	{
		if(lst[s[i]] != -1) nxt[s[i]][lst[s[i]]] = i;
		lst[s[i]] = i;
		pos[s[i]].emplace_back(i);
	}
	nxt['L'][pos['L'].back()] = n;
	nxt['R'][pos['R'].back()] = n;
	for(int i = 1; i < n; i++)
	{
		nxt['L'][i] = std::max(nxt['L'][i], nxt['L'][i - 1]);
		nxt['R'][i] = std::max(nxt['R'][i], nxt['R'][i - 1]);
	}

	int q; std::cin >> q;
	while(q--)
	{
		std::string t; std::cin >> t;
		int m = t.size();

		if(m == 1)
		{
			if(t == "R" && s.front() == 'R') std::cout << "YES\n";
			else if(t == "L" && s.back() == 'L')  std::cout << "YES\n";
			else std::cout << "NO\n";
			continue;
		}
		if(t.front() == 'R' && s.front() != 'R')
		{
			std::cout << "NO\n";
			continue;
		}

		int cur = pos[t[0]][0];
		bool ok = true;
		for(int i = 1; i < m && cur < n; i++)
		{
			int ncur = nxt[t[i]][cur];
			if(s[i - 1] == 'L' && s[i] == 'R' && ncur - cur > 1) ok = false;
			cur = ncur;
		}
		if(cur >= n) ok = false;

		if(ok) std::cout << "YES\n";
		else std::cout << "NO\n";
	}
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int t; std::cin >> t;
	while(t--) solve();

	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3572kb

input:

2
RRLLRRLL
4
LLLLL
LLR
LRLR
R
RLLLLLL
3
LLLLL
RL
RRL

output:

NO
YES
NO
YES
YES
YES
NO

result:

ok 7 lines

Test #2:

score: -100
Runtime Error

input:

100000
RRLLR
4
R
R
R
R
LRLLL
6
R
L
L
L
L
R
RLLRR
1
L
LRLLL
3
R
L
L
RLRRL
2
LRRRR
RRRL
LRLRR
2
L
R
RRLRL
4
RLRLR
RLLL
LR
RLL
RLRLL
8
R
R
R
L
L
L
R
L
RLLRR
7
R
LL
RL
R
L
L
L
LLRLR
2
L
R
RRRRL
1
RLLLR
RRLLL
2
L
L
RLLRL
1
RLLRL
LRLLL
5
RLRLL
RLLLR
RRRRL
LLRRR
RLLRR
LRLLL
3
RRLL
R
RL
LLRRL
3
L
R
LLLRR
RR...

output:


result: