Expand the Path

Created by LXC on Mon Jun 12 14:33:31 2023

https://codeforces.com/problemset/problem/1644/E

ranting: 1900

tag: brute force, combinatorics, data structures, implementation, math

problem

有一个 n * n 的网格，现在你在网格中(1,1)位置。
给你一个只包含D和R字符串，代表着移动的序列。D则向下移动，即(x,y)位置变为(x+1,y)；R则向右移动，即(x,y)位置变为(x,y+1)；

现在你可以执行任意次操作，每次操作让移动序列中某个单次移动变为连续两次移动，比如D变为DD。并且移动完后不会越界。

问在所有通过操作后的合法序列中，能够经过的点有哪些。

solution

在第一次转向之前如果走了k步，会有k*(n-1)格无法到达，显然当序列中只有一种字符那么就只有n格能到达。

其余的格子几乎都能到达。

设在第一次转向前如果到达的位置是(x1,y1)，最后结束的位置是(x2,y2)。

那么再以对角线(x1,y1)(x2,y2)的矩形中只有(x2-x1+y2-y1+1)个格子是能到达的

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    ll n;
    string s;
    cin >> n >> s;
    if (!count(s.begin(), s.end(), 'R') || !count(s.begin(), s.end(), 'D')) {
        cout << n << "\n";
        return;
    }
    int x1 = 1, y1 = 1, i = 0;
    while (i < s.size() && s[i] == s[0]) {
        if (s[i] == 'R') {
            y1++;
        } else {
            x1++;
        }
        i++;
    }
    int x2 = x1, y2 = y1, j = i;
    while (j < s.size()) {
        if (s[j] == 'R') {
            y2++;
        } else {
            x2++;
        }
        j++;
    }
    cout << (x1 + y1 - 2) + ((n - x1 + 1) * (n - y1 + 1) -
                             ((y2 - y1 + 1) * (x2 - x1 + 1) - (j - i + 1)))
         << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}