题解：CF1992D Test of Love
__int127
·
·
题解
题解：CF1992D Test of Love
题目传送门
题目大意
本题有 t 组测试样例。
有一条长 n 米的河流 s 表示为 n 个 1m 的河段，第 i 个河段表示为 s_i，s_i\in\{L,C,W\}，分别为 “原木”、“鳄鱼”和“水”河段。你最开始在 s_0，希望到达 s_{n+1}。
移动规则如下：
问是否能到达 s_{n+1}，能输出 YES，否则输出 NO。
数据范围
## 思路
可以使用 $vis$ 数组记录每个河段的登陆情况（$1$ 为可以登陆，$0$ 为不可登陆），其中 $vis_0=1$。对于 $vis_i$，如果有 $vis_j=1(j<i)$，则可以到达 $s_i$。因为题目要求水中只能移动 $1m$，且对“下水”次数有要求，所以当 $j=i-1$ 时要特判。另外，如果 $s_{i-1}$（偏移量）是 `C`，直接将 $vis_i$ 赋值成 $0$ 就行了。（鳄鱼河段不可登陆！）
接下来判断是否能到达 $s_{n+1}$ 就比较简单了，如果 $vis_{n+1}=1$ 则可以到达。
不能到达有两种情况：
1. 存在一最小的 $i$，使得 $vis_{\max{0,i-m}}\sim vis_{i-1}$ 均 $\ne1$。
1. “下水”次数 $>k$。
循环代码（以下使用了快读快写）：
```cpp
int vis[N] = {}, wt = 0, flag = 0;
vis[0] = 1;
for (int i = 1; i <= n + 1; ++i){
if (s[i - 1] == 'C'){
continue;
}
int ans = -1;
for (int j = i - 1; j >= max(i - m, 0ll); --j){
if (vis[j] != 0 && (s[j - 1] != 'W' || j == i - 1)){
ans = j;
}
}
if (ans == -1 || wt > k){
if (wt > k){
flag = 1;
}
write_string("NO");
break;
}
if (ans == i - 1 && s[ans - 1] == 'W'){
++wt;
vis[i] = 1;
} else {
vis[i] = 1;
}
}
if (wt > k && !flag){
write_string("NO");
continue;
}
if (vis[n + 1] == 1){
write_string("YES");
}
```
## 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl putchar('\n')
inline int read(){
char ch, c;int res;
while (ch = getchar(), !isdigit(ch))c = ch;
res = ch - 48;
while (ch = getchar(), isdigit(ch))res = (res << 3) + (res << 1) + ch - 48;
if (c == '-')res = (res ^ -1) + 1;
return res;
}
inline string read_string(char p = ' '){
string str = "";
char ch = getchar();
while (ch == ' ' || ch == '\n' || ch == '\r')ch = getchar();
if (p == ' ')
while (ch != ' ' && ch != '\n' && ch != '\r')str += ch, ch = getchar();
else
while (ch != p)str += ch, ch = getchar();
return str;
}
inline void write_string(string str, int p = 0, int len = 0, char ch = '\n'){
len = str.size();
for (int i = p; i < len; i++)putchar(str[i]);
if (ch != '!')putchar(ch);
return;
}
const int N = 2e5 + 5;
int T = 1, n, m, k;
signed main(){
T = read();
while (T--){
n = read(), m = read(), k = read();
string s;
s = read_string();
int vis[N] = {}, wt = 0, flag = 0;
vis[0] = 1;
for (int i = 1; i <= n + 1; ++i){
if (s[i - 1] == 'C'){
continue;
}
int ans = -1;
for (int j = i - 1; j >= max(i - m, 0ll); --j){
if (vis[j] != 0 && (s[j - 1] != 'W' || j == i - 1)){
ans = j;
}
}
if (ans == -1 || wt > k){
if (wt > k){
flag = 1;
}
write_string("NO");
break;
}
if (ans == i - 1 && s[ans - 1] == 'W'){
++wt;
vis[i] = 1;
} else {
vis[i] = 1;
}
}
if (wt > k && !flag){
write_string("NO");
continue;
}
if (vis[n + 1] == 1){
write_string("YES");
}
}
return 0;
}
```