题解：P10297 [CCC 2024 S3] Swipe

· · 题解

-0x3f 扯淡

这道题真的很坑，细节超多，交了一面总算通过了。

0x01 第一部分思路

第一部分需要我们判断 YES 还是 NO。

先观察一下不能通关的一组样例：

4
1 2 4 3
1 4 2 3

这里不能通关的主要原因是 (2,4) 和 (4,2) 这边形成了类似于逆序对的结构。（瞎 BB 名词）

又观察发现 B 的的大部分元素都是重复的，考虑把 B 中一样的元素缩成一个元素再观察。

最后发现了一个答案为 YES 的充要条件：浓缩后的 B 为 A 的子序列。

0x02 第一部分的实现

int l = 1, r = 1, cnt = 0;
for (int i = 2; i <= n + 1; i ++)
{
    if (tb[i] == tb[i - 1]) r ++;
    else
    {
        b[++ cnt] = {tb[l], l, r};
            l = r + 1, r = l;
    }
}

实现对 B 的“浓缩”用上面的代码。

int i = 1;
for(int j = 1; j <= n; j ++)
{
    if(i <= cnt && b[i].x == a[j]) i ++; //这里使用双指针 
}

if(i == cnt + 1) cout << "YES\n";
else
{
    cout << "NO\n";
    return 0;
}

判断 YES 或者 NO 用上面的代码。

0x03 第二部分

有了上面的“浓缩”后的 B，第二部分就简单也不简单了。

可以发现，B 中的每一串数字都是有源点的，我们要做的，就是找到这个源点，向周围扩散，也就是说，每一个源点都会向右划一次，向左划一次。

找源点的方式非常简单，只要用“浓缩”的 B 和 A 一一对应就行了。

为了不超出 N 次操作，我们只要当源点在最左端时不往左扩展，当源点在最右端时不往右扩展。

有些时候会有前面的源点会覆盖后面的源点，所以要做一个排序（左右讨论）。

0x04 第二部分代码

int j = 1, cnt2 = 0;
for (int i = 1; i <= n; i ++)
{
    if (a[i] == b[j].x)
    {
        if (i < b[j].r)
        {
            ans[++ cnt2] = {1, i, b[j].r};
        }
        if (i > b[j].l)
        {
            ans[++ cnt2] = {-1, b[j].l, i};
        }
        j ++;
    }
    if (j > cnt) break;
}

cout << cnt2 << "\n";
sort(ans + 1, ans + 1 + cnt2, cmp);
for (int i = 1; i <= cnt2; i ++)
{
    if (ans[i].x == 1) 
    {
        cout << "R " << ans[i].l - 1 << " " << ans[i].r - 1 << "\n";
    }
    else
    {
        cout << "L " << ans[i].l - 1 << " " << ans[i].r - 1 << "\n";
    }
}

0x3F 一些hack

5
1 1 2 1 1
2 2 2 2 2
ans:
YES
2
L 0 2
R 2 4
7
1 2 3 4 5 6 7
1 1 1 1 1 5 5
ans:
YES
2
R 4 6
R 0 4