Rank 66/3225. Solved 9/11.

这次的标题是 Arcaea 主线2 的时代了!

A. 宇宙的终结

题意

给定两个正整数 \(l, r\),找出 \([l, r]\) 中的一个数,满足其为三个不同素数的乘积。

思路

范围很小,直接打出 \(6\) 个素数然后暴力算一下就行。

时间复杂度:\(O(6^3)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    vector<int> pri = {2, 3, 5, 7, 11, 13};
    int l, r;
    cin >> l >> r;
    for(int i=0;i<6;i++) {
        for(int j=i+1;j<6;j++) {
            for(int k=j+1;k<6;k++) {
                int now = pri[i] * pri[j] * pri[k];
                if(now >= l && now <= r) {
                    cout << now << '\n';
                    return;
                }
            }
        }
    }
    cout << -1 << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

压根没看到 \(42\)

B. 爱恨的纠葛

题意

给定两个长度相等的数组 \(a, b\),在可以任意打乱 \(a\) 的条件下,使 \(\min\{|a_i - b_i|\}\) 最小,并输出方案。

思路

首先,这题不是让绝对值的和最小,不然直接按照 \(b\) 排个序就行了。

我们直接将 \(a\) 排序,然后对于每个 \(b\),通过二分的方式在 \(a\) 中找出最相近的元素,由此找出差值绝对值最小的 \(a_i\),以及 \(b_j\) 所在的位置 \(j\)

此时,我们直接交换 \(a_i, a_j\),即可得到正确的构造方案。

时间复杂度:\(O(n \log n)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++) cin >> b[i];
    sort(all(a));
    int ans = inf, val = -1, ind = -1;
    for(int i=1;i<=n;i++) {
        auto it = lower_bound(all(a), b[i]);
        if(it != a.end()) {
            if(abs(b[i] - *it) < ans) {
                val = *it;
                ind = i;
                ans = abs(b[i] - *it);
            }
        }
        if(it != a.begin()) {
            --it;
            if(abs(b[i] - *it) < ans) {
                val = *it;
                ind = i;
                ans = abs(b[i] - *it);
            }
        }
    }
    for(int i=1;i<=n;i++) {
        if(a[i] == val) {
            swap(a[i], a[ind]);
            break;
        }
    }
    for(int i=1;i<=n;i++) cout << a[i] << ' ';
    cout << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

一开始被骗了!

C. 心绪的解剖

题意

给定 \(q\) 次询问,每次询问给定一个正整数 \(n\),判断其是否能分解为三个斐波那契数之和,并输出方案。

思路

数据范围在 \(10 ^ 9\) 范围内,我们不妨直接递推,打表出 \(10^9\) 内的斐波那契数。

有趣的是,只有 \(45\) 个在范围内。

那就很简单了,我们以 \(O(n ^ 3)\) 的复杂度,预处理所有组合,以及组合对应的三个数之和,然后直接用于询问的查询即可。

一种简单的方式是用 \(map\) 存储,以和作为键,组合方案作为值,然后询问的时候判断是否存在这个键即可。

时间复杂度:\(O(45^3+q \log(45^3))\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

int fb[N], cnt;
map<int, array<int, 3>> ok;

void init() {
    fb[0] = 0, fb[1] = 1, cnt = 2;
    for(int i=2;;i++) {
        fb[i] = fb[i - 1] + fb[i - 2];
        if(fb[i] >= 1e9) break;
        cnt ++;
    }
    for(int i=0;i<cnt;i++) {
        for(int j=0;j<cnt;j++) {
            for(int k=0;k<cnt;k++) {
                ok.insert({fb[i] + fb[j] + fb[k], {fb[i], fb[j], fb[k]}});
            }
        }
    }
}

void solve() {
    int q;
    cin >> q;
    while(q --) {
        int n;
        cin >> n;
        if(ok.count(n)) {
            auto [i, j, k] = ok[n];
            cout << i << ' ' << j << ' ' << k << '\n';
        }else cout << -1 << '\n';
    }
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    init();
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

就很暴力,很诈骗

D. 友谊的套路

题意

对于 \(A, B\) 间的比赛,每一局 \(A\) 获胜的概率是 \(p\),输出在比 \(5\) 局的条件下,出现 \(3\)\(2\) 负的概率。

思路

对于 \(A\) 来说,要么 \(3\)\(2\) 负,要么 \(2\)\(3\) 负,把概率加起来就行。

时间复杂度:\(O(1)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    double p;
    cin >> p;
    double ans1 = p * p * (1 - p) * (1 - p) * (1 - p),
           ans2 = (1 - p) * (1 - p) * p * p * p;
    cout << fixed << setprecision(7) << ans1 + ans2 << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

签到

E. 未来的预言

题意

定义 \(\mathtt{BO}x\) 为两个队之间的比赛规则,当某一队获胜局数超过 \(x\) 的一半时,该队获胜。

保证 \(x\) 为奇数的条件下,给定一段时间内两队的获胜情况,判断哪队获胜,并输出能判断时,进行了几局。

思路

直接按题意模拟即可。

时间复杂度:\(O(n)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    char tmp;
    int x;
    cin >> tmp >> tmp >> x;
    string s;
    cin >> s;
    int cnt1 = 0, cnt2 = 0;
    for(char e : s) {
        if(e == 'R') cnt1 ++;
        else cnt2 ++;
        if(cnt1 == (x + 1) / 2) {
            cout << "kou!" << '\n';
            cout << cnt1 + cnt2 << '\n';
            return;
        }
        if(cnt2 == (x + 1) / 2) {
            cout << "yukari!" << '\n';
            cout << cnt1 + cnt2 << '\n';
            return;
        }
    }
    cout << "to be continued." << '\n';
    cout << cnt1 + cnt2 << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

又是这俩打架(

F. 命运的抉择

题意

给定一个数组 \(a\),将其划分为两个非空数组 \(b, c\),满足对于 \(b\) 中的任意元素 \(x\)\(c\) 中的任意元素 \(y\),都有 \(gcd(x, y) = 1\)

输出一个方案。

思路

这是一个暴力但是没有超时的做法。

我们可以先将一个元素放入 \(b\),然后枚举这个元素的所有质因子,将包含该质因子的所有元素都放入 \(b\),同时记录多出来的质因子,重复上述操作直到没有质因子多出来即可。

速度取决于实现,这里采取枚举质因子的倍数的方式,而不是直接分解因子再判是否包含,能快很多。

而分解质因子的时候,预处理了一个数组 \(st\)\(st[x]\)\(x\) 的最小质因子,这样我们直接用 \(while\) 循环就可以快速得到所有因子,速度优于 \(\log\) 的米勒罗宾,而后者会 \(tle\)

时间复杂度:\(O(能过)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()

constexpr int N = 1e6 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

bool not_pri[N];
int pr[N], cnt;

//线性筛求积性函数
static void sieve_mul_func(const int n, bool not_pri[], int pr[], int &cnt, const auto &&new_pri, const auto &&stop, const auto &&on) {
    for (int i = 2; i <= n; i ++) {
        if (!not_pri[i]) pr[cnt++] = i, new_pri(i);
        for (int j = 0; j < cnt && i * pr[j] <= n; j ++) {
            not_pri[i * pr[j]] = true;
            if (i % pr[j] == 0) {
                stop(i, pr[j]);
                break;
            }
            on(i, pr[j]);
        }
    }
}
//线性筛: pr[] 所有素数
static void get_prime(const int n, bool not_pri[], int pr[], int &cnt) {
    sieve_mul_func(n, not_pri, pr, cnt, [&](const int i) {}, [&](const int i, const int pr_) {}, [&](const int i, const int pr_) {});
}

int st[N];

void init() {
    get_prime(1e6, not_pri, pr, cnt);
    for(int i_=0;i_<cnt;i_++) {
        int i = pr[i_];
        for(int j=i;j<=1e6;j+=i) {
            if(st[j] != 0) continue;
            st[j] = i;
        }
    }
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<int> l;
    map<int, int> cnt;
    set<int> fac, ok;
    for(int i=1;i<=n;i++) {
        cin >> a[i];
        cnt[a[i]] ++;
    }
    int tp = (*cnt.begin()).fs;
    l.pb(tp);
    cnt[tp] --;
    if(cnt[tp] == 0) cnt.extract(tp);
    while(tp > 1) {
        int x = st[tp];
        fac.ep(x);
        ok.ep(x);
        while(tp % x == 0) tp /= x;
    }
    while(!fac.empty() && !cnt.empty()) {
        int i = *fac.begin(), mx = (*cnt.rbegin()).fs;
        fac.extract(i);
        for(int j=i;j<=mx;j+=i) {
            if(!cnt.count(j)) continue;
            for(int p=1;p<=cnt[j];p++) l.pb(j);
            cnt.extract(j);
            tp = j;
            while(tp > 1) {
                int x = st[tp];
                if(!ok.count(x)) fac.ep(x);
                ok.ep(x);
                while(tp % x == 0) tp /= x;
            }
        }
    }
    vector<int> r;
    for(auto [x, y] : cnt) {
        while(y --) r.pb(x);
    }
    if(l.empty() || r.empty()) {
        cout << -1 << ' ' << -1 << '\n';
        return;
    }
    cout << l.size() << ' ' << r.size() << '\n';
    for(auto &e : l) cout << e << ' ';
    cout << '\n';
    for(auto &e : r) cout << e << ' ';
    cout << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

写麻了,还是并查集简单

G. 人生的起落

题意

定义若三元组 \(<x, y, z>\) 满足 \(x = z > y\),那么这个三元组称为 "v-三元组"。

给定三个整数 \(n, S, k\),构造一个长为 \(n\) 且和为 \(S\) 的数组,满足其中恰好有 \(k\) 个长为 \(3\) 的连续子序列为 "v-三元组"。

思路

首先,我们不可以 \(212121212 \ldots\) 这样构造,因为可能会出现格子恰好放下 \(k + 1\)\(2\) 的情况,这个时候多出来的数就没地方搁了。

我们考虑 \(x\_x\_x\_x\_xy11111\ldots\) 的构造方式,其中 \(x\) 为将空格和 \(y\) 都填上 \(1\) 后能取到的最大值。

然后我们从左往右,把剩下的数放到空格中,每当空格值为 \(x - 1\) 时,切换到下一个空格,空格全填满时,将多余的数放到 \(y\) 中,如果不存在 \(y\) 这个空位,那么就是无解。

当然,格子不够放 \(x\) 也是无解的。

时间复杂度:\(O(n)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n, sum, k;
    cin >> n >> sum >> k;
    k ++;
    if(2 * k - 1 > n) {
        cout << -1 << '\n';
        return;
    }
    vector<int> ans(n + 1, 1);
    int each = (sum - (n - k)) / k;
    sum -= each * k + (n - k);
    for(int i=1;i<=k;i++) {
        ans[i * 2 - 1] = each;
    }
    for(int i=1;i<k;i++) {
        int add = min(each - ans[i * 2] - 1, sum);
        if(add <= 0) {
            if(ans[i * 2] >= each) {
                cout << -1 << '\n';
                return;
            }
        }else {
            ans[i * 2] += add;
            sum -= add;
        }
    }
    if(sum > 0) {
        if(k * 2 > n) {
            cout << -1 << '\n';
            return;
        }
        ans[k * 2] += sum;
    }
    for(int i=1;i<=n;i++) cout << ans[i] << ' ';
    cout << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

还好我没往 \(21212\) 上想(

H. 纷乱的红线

待补充

I. 时空的交织

题意

对于一个 \(n \times m\) 的矩阵,给定一个长度为 \(n\) 的数组 \(a\),以及一个长度为 \(m\) 的数组 \(b\),矩阵中 \((i, j)\) 所在的元素值为 \(a_i \times b_j\)

在矩阵中,找出一个子矩阵,使子矩阵中所有元素的和最大。

思路

如果我们选择的子矩阵的右下对角线的端点为 \((l_1, r_1), (l_2, r_2)\),那么元素的和为 \(\sum_{i=l_1}^{l_2} \sum_{j=r_1}^{r_2} (a_i \times b_j)\)

因为两个求和符号之间毫无关系,从而我们可以将其写为 \((\sum_{i=l_1}^{l_2} a_i) \times (\sum_{j=r_1}^{r_2} b_j)\)

这就很简单了,我们要求的就是 \(a, b\) 中连续子序列的最大和的乘积,这是一个再经典不过的 \(dp\)

当然,需要注意的是,因为存在负数,所以相乘可能会变成最小值,从而我们考虑再找出连续子序列的最小和,然后组合一下,对 \(4\) 种情况取最大值即可。

时间复杂度:\(O(n + m)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

int maxSubArray(vector<int>& nums) {
    int len = nums.size();
    if (len == 0) return 0;
    int sum = nums[1];
    int ans = nums[1];
    for (int i = 2;i < len;i++){
        sum = max(nums[i], sum + nums[i]);
        ans = max(ans,sum);
    }
    return ans;
}

int minSubArray(vector<int>& nums) {
    int len = nums.size();
    if (len == 0) return 0;
    int sum = nums[1];
    int ans = nums[1];
    for (int i = 2;i < len;i++){
        sum = min(nums[i], sum + nums[i]);
        ans = min(ans,sum);
    }
    return ans;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1), b(m + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=m;i++) cin >> b[i];
    int ans = maxSubArray(a) * maxSubArray(b);
    ans = max(ans, minSubArray(a) * minSubArray(b));
    ans = max(ans, minSubArray(a) * maxSubArray(b));
    ans = max(ans, maxSubArray(a) * minSubArray(b));
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

常数什么的无所谓啦(

J. 绝妙的平衡

题意

给定一棵根为 \(1\) 的有根树,每个节点具有点权 \(1\)\(2\)

有部分结点被标记,被标记结点需要满足 所有子树的点权和 加上 该结点本身的点权 为 \(3\) 的倍数。

输出一种构造方案,无解输出 \(-1\)

思路

我们考虑先给所有结点都赋上点权 \(1\),然后将某些结点改成 \(2\)

我们从底往上 \(\mathtt{dfs}\),如果我们当前枚举到结点 \(x\),那么我们可以得到当前的和为 \(sum\)

如果当前结点没被标记,我们就不用管了,否则我们需要满足 \(sum\)\(3\) 的倍数。

如果 \(sum \equiv 2 \pmod 3\),那么我们还缺一个 \(1\),此时我们直接将结点 \(x\) 的点权改为 \(2\) 即可。

如果 \(sum \equiv 1 \pmod 3\),那么在上面操作的基础上,我们还缺一个 \(1\)。这个时候,我们枚举 \(x\) 的所有子结点,如果存在一个没有被标记过的子结点,那么我们就将其点权改为 \(2\)。注意我们不能修改被标记的点,因为我们自底往上搜索的时候,保证了子树一定合法,修改之后就一定不合法了。

如上即可完成构造,为最优解。

时间复杂度:\(O(n)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<vector<int>> adj(n);
    for(int i=1;i<n;i++) {
        int x;
        cin >> x;
        x --;
        adj[x].pb(i);
    }
    bool valid = true;
    vector<int> ans(n, 1);
    auto dfs = [&](auto self, int x, int p) -> int {
        int sum = ans[x];
        for(auto y : adj[x]) {
            if(y == p) continue;
            sum += self(self, y, x);
        }
        if(s[x] == 'R') {
            int add = 0;
            if(sum % 3 != 0) {
                ans[x] = 2;
                add ++;
            }
            if(sum % 3 == 1) {
                bool ok = false;
                for(auto y : adj[x]) {
                    if(y == p) continue;
                    if(s[y] != 'R') {
                        ans[y] = 2;
                        add ++;
                        ok = true;
                        break;
                    }
                }
                if(!ok) {
                    valid = false;
                }
            }
            sum += add;
        }
        return sum;
    };
    dfs(dfs, 0, -1);
    if(valid) {
        for(auto e : ans) cout << e;
        cout << '\n';
    }else cout << -1 << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

构造大师

K. 错综的统一

待补充