补题 [ABC303C] Dash

题面翻译

现在高桥在一个二维平面上。初始时他在 $(0,0)$ 处，生命值为 $H$。平面上有 $M$ 个可以恢复生命值的物品，其中第 $i$ 个物品的位置为 $(x_i,y_i)$。

高桥将要进行 $N$ 次移动，第 $i$ 次移动的方式如下：

  • 设高桥现在的位置是 $(x,y)$，那么他将会消耗 $1$ 点生命值，同时：
    • 如果 $S_i=\texttt R$，移动到 $(x+1,y)$；
    • 如果 $S_i=\texttt L$，移动到 $(x-1,y)$；
    • 如果 $S_i=\texttt U$，移动到 $(x,y+1)$；
    • 如果 $S_i=\texttt D$，移动到 $(x,y-1)$。
  • 如果高桥的生命值降为负数，他就会倒下无法行动；否则，如果当前位置有一个可以恢复生命值的物品，且当前生命值小于 $K$，那么生命值将会恢复到 $K$。

请判断高桥能否进行完所有的移动而不倒下。

数据范围与约定

$1\le N,M,H,K\le2\times10^5$，$|x_i|,|y_i|\le2\times10^5$。

保证 $S$ 是一个只由字符 R、L、U、D 构成的长度为 $N$ 的字符串。保证 $(x_i,y_i)$ 两两不同。保证所有输入的数均为整数。

输入格式

第一行输入四个数 $N,M,H,K$。第二行输入一个长度为 $N$ 的字符串 $S$。接下来 $M$ 行，第 $i$ 行输入两个数 $(x_i,y_i)$。

输出格式

如果高桥可以进行完所有 $N$ 次移动，输出 Yes，否则输出 No。

题目描述

二次元平面の点 $ (0,0) $ に高橋君がいます。初め、高橋君の体力は $ H $ です。また、二次元平面には $ M $ 個の体力を回復するアイテムがあり、$ i $ 個目のアイテムは点 $ (x_i,y_i) $ に置いてあります。

高橋君は、これから $ N $ 回の移動をします。$ i $ 回目の移動は以下の方法で行われます。

  1. 今高橋君がいる点を $ (x,y) $ とする。体力を $ 1 $ 消費し、$ S $ の $ i $ 番目の文字 $ S_i $ に応じて以下の点に移動する。
  • $ S_i $ が R のとき： $ (x+1,y) $
  • $ S_i $ が L のとき： $ (x-1,y) $
  • $ S_i $ が U のとき： $ (x,y+1) $
  • $ S_i $ が D のとき： $ (x,y-1) $
  1. 高橋君の体力が負になった場合、高橋君は倒れてしまい、移動をやめる。そうでない場合、移動した点にアイテムがあり、かつ高橋君の体力が $ K $ 未満ならば、移動した点に置かれたアイテムを消費し、高橋君の体力が $ K $ になる。

高橋君が一度も倒れることなく $ N $ 回の移動を行えるか判定してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ M $ $ H $ $ K $ $ S $ $ x_1 $ $ y_1 $ $ \vdots $ $ x_M $ $ y_M $

输出格式

高橋君が一度も倒れることなく $ N $ 回の移動を行える場合 Yes を、そうでない場合 No を出力せよ。

样例 #1

样例输入 #1

1
2
3
4
4 2 3 1
RUDL
-1 -1
1 0

样例输出 #1

1
Yes

样例 #2

样例输入 #2

1
2
3
4
5 2 1 5
LDRLD
0 0
-1 -1

样例输出 #2

1
No

提示

制約

  • $ 1\leq\ N,M,H,K\leq\ 2\times\ 10^5 $
  • $ S $ は R, L, U, D からなる長さ $ N $ の文字列
  • $ |x_i|,|y_i|\ \leq\ 2\times\ 10^5 $
  • $ (x_i,y_i) $ は互いに異なる
  • $ S $ 以外の入力は全て整数

Sample Explanation 1

初め高橋君の体力は $ 3 $ です。以下で移動を説明します。 - $ 1 $ 回目の移動： $ S_i $ が R なので点 $ (1,0) $ に移動する。高橋君の体力は $ 2 $ に減る。点 $ (1,0) $ にはアイテムが置いてあるが、高橋君の体力は $ K=1 $ 以上なのでアイテムは消費されない。 - $ 2 $ 回目の移動： $ S_i $ が U なので点 $ (1,1) $ に移動する。高橋君の体力は $ 1 $ に減る。 - $ 3 $ 回目の移動： $ S_i $ が D なので点 $ (1,0) $ に移動する。高橋君の体力は $ 0 $ に減る。点 $ (1,0) $ にはアイテムが置いてあり、体力は $ K=1 $ 未満なのでアイテムを消費し、体力が $ 1 $ になる。 - $ 4 $ 回目の移動： $ S_i $ が L なので点 $ (0,0) $ に移動する。高橋君の体力は $ 0 $ に減る。 以上より、高橋君は倒れずに $ 4 $ 回の移動を行えるので、Yes を出力してください。体力は $ 0 $ になってもいいことに注意してください。

Sample Explanation 2

初め高橋君の体力は $ 1 $ です。以下で移動を説明します。 - $ 1 $ 回目の移動： $ S_i $ が L なので点 $ (-1,0) $ に移動する。高橋君の体力は $ 0 $ に減る。 - $ 2 $ 回目の移動： $ S_i $ が D なので点 $ (-1,-1) $ に移動する。高橋君の体力は $ -1 $ に減る。体力が $ -1 $ になってしまったので、高橋君は倒れてしまい、移動をやめる。 以上より、高橋君は倒れてしまうので、No を出力してください。 高橋君がはじめいる点 $ (0,0) $ にはアイテムが置いてありますが、移動後にアイテムは消費されるので、$ 1 $ 回目の移動前にアイテムを消費しないことに注意してください。

题解

题目解析

这道题主要我卡在了开二维数组开超了.虽然代码写好了,但是无法运行…

看了看官方题解,发现官方给的方法是使用 std::set ,以前确实没用过这个解决这种问题,这倒是给了我一个解决数组问题的新方法.除此之外,我还学会了set.count() 与 set.find() 之间的区别.

除此之外,就是一个简单的小模拟了,相信大家都会做.

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <string>
#include <set>
#include <algorithm>
#define endl "\n"
using namespace std;

set<pair<int,int>> st;//以pair<x,y>代替[x][y].

int main(){
	int n,m,h,k;
	string s;
	cin >> n >> m >> h >> k;
	cin >> s;
	for(int i=1;i<=m;i++){
		int x,y;
		cin >> x >> y;
		st.insert({x,y});//set只能使用insert插入数据.
	}
	int x0 = 0,y0 = 0;
	for(int i=0;i<s.size();i++){
		int dx = 0,dy = 0;
		if(s[i] == 'R') dx = 1;
        if(s[i] == 'L') dx = -1;
        if(s[i] == 'U') dy = 1;
        if(s[i] == 'D') dy = -1;
        x0 += dx,y0 += dy;
        if(--h < 0){
        	cout << "No" << endl;
        	return 0;
        }
        if(h < k && st.count({x0,y0})){
        	st.erase({x0,y0});
        	h = k;
        }
	}
	cout << "Yes" << endl;
	return 0;
}

Remark

  • set.find():如果找到,返回对应位置的迭代器,如果没找到返回末尾的迭代器.
  • set.count():如果找到返回1,如果没找到返回0.