(CF1333D)Challenges in school No.41

发表于 分类于 ，

原题链接

思路:

有点类似于蚂蚁过桥的碰撞问题，首先将所有 L 的位置从小到大记为 \(pos_i\).

然后需要计算移动次数 \(k\) 的上界和下界 \(kmax\) 和 \(kmin\) 以确定是否有解.

已知最终状态的形式是 LLL…RRR, 可设 \(d_i = pos_i - i\), 即为 L 当前位置与目标位置的差.

则 \(kmax\) 很好求得，即 \(\sum\limits_{i=0}^{size\ d} d_i\), 因为最大值肯定是每次只移动一个.

最小值 \(kmin\) 即是每次移动所有可移动的 L, 需要通过模拟求出.

在原始串 \(s\) 中，只有 \(s_{i-1} = R\) 的 \(s_i=L\) 才能被移动.

对应到数组 \(d\) 中，对于某个值 \(x\), 只有第一个 \(d_i=x\) 的 L 才能被移动，因为所有 \(d_i=x\) 是排在一起的 (可以脑补一下). 代码中用了一个数组 \(num\) 来维护对于每个 \(x\) 的第一个 \(d_i=x\) 的 L 在 \(d\) 的位置.

若有解，即 \(kmin \le k \le kmax\), 则可通过下面的步骤生成解:

当 \(k \le kmax\) 时， 直接移动所有可以移动的 L, 直至 \(k=kmax\). 然后一次移动一个.

由于生成解的步骤与求 \(kmin\) 的步骤类似 (移动所有可移动的 L), 所以在求 \(kmin\) 时可以同时生成解.

时间复杂度 \(O(n^2)\)(实际应该快不少).

需要特别注意的是，这题输出量很大， 所以尽量用 printf 输出 (或者自己写个快写) 因为用的 cout 痛失 n 分 QAQ

代码:

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int Mn(3050);
int d[Mn],num[Mn];

vector<vector<int> > ans;    //答案

int main() {
    int n,k;
    scanf("%d %d",&n,&k);
    string sin;    //输入字符串
    cin >> sin;
    int lcnt(0);
    for(int i(0);i<sin.size();++i)
        if(sin[i]=='L') d[++lcnt] = i+1;    //记录L的位置
    int sum(0);    //sumd即kmax
    for(int i(1);i<=lcnt;++i)
    {
        d[i] -= i;    //计算d
        sum += d[i];
    }
    if(k>sum)
    {
        printf("-1");
        return 0;
    }
    num[0] = 1;
    for(int i(1),p(1);i<=d[lcnt];++i)    //计算num
    {
        num[i] = num[i-1];
        for(;p<=lcnt;++p)
            if(d[p]>=i) break;
        num[i] = p;
    }
    bool isans(false);    //是否有解
    for(int ki(k-1);ki>=0;--ki)
    {
        ans.push_back(vector<int>());
        for(int i(1);i<=d[lcnt];++i)
        {
            if(d[num[i]]==i && sum>ki)
            {
                ans[k-ki-1].push_back(d[num[i]]+num[i]-1);
                --d[num[i]];
                ++num[i];
                --sum;
            }
        }
        if(ki==sum)    //sum=k时变为每次动一个
        {
            isans = true;
            break;
        }
    }
    if(!isans)    //k<kmin
    {
        printf("-1");
        return 0;
    }
    for(int i(0);i<ans.size();++i)    //输出解
    {
        printf("%d",ans[i].size());
        for(int j(0);j<ans[i].size();++j)
            printf(" %d",ans[i][j]);
        printf("\n");
    }
    for(int i(1);i<=lcnt;++i)    //输出解2
    {
        if(d[i]!=0)
        {
            for(int j(d[i]);j;--j)
                printf("1 %d\n",i+j-1);
        }
    }
    return 0;
}