526互联

AtCoder Beginner Contest 335

发布时间 2024-01-07 11:45:56作者: 加固文明幻景

基本情况

ABD秒了，C卡了一会，空间换时间然后爆内存，最后交了个100多行的逆天模拟终于+4过。

赛后发现其实是手写了双端队列。

C - Loong Tracking

C - Loong Tracking

思路很明显，空间换时间，把每个状态用数组全记录下来。

但是纯这样写数组会开的巨大，所以得让后面没用的状态出去。

用双端队列来实现就贼直接。

void solve()
{
	cin >> n >> Q;
	pair<int, int> move[200];
	move['R'] = make_pair(1, 0);move['L'] = make_pair(-1, 0);
 	move['U'] = make_pair(0, 1);move['D'] = make_pair(0, -1);
	deque<pair<int, int> > q;
	for (int i = 1; i <= n; i++) q.push_back({i, 0});
	int x = 1, y = 0;
	while(Q--)
	{
		int opt; cin >> opt;
		if (opt == 1)
		{
			char c; cin >> c;
			q.pop_back();
			x += move[c].first, y += move[c].second;
			q.push_front({x, y});
		}
		else
		{
			int x;
			cin >> x;
			cout << q[x - 1].first << ' ' << q[x - 1].second << '\n';
		}
	}
}