526互联

【CF1157C2】题解

发布时间 2023-07-05 11:12:53作者: Codehyx

CF1157C2

理解题意

首先，读题。题目传送门

题意：你一次可以取出序列的最左或最右边的数，然后要你求做了\(k\)次操作后的最长合法序列，输出你取出的数

看到题目第一行：

CF1157C1 与 CF1157C2 的不同在于 C1 中的所有 \(a_{i}\) 均是不同的，而在 C2 中是不一定的。

这一行预示了：这道题不能用 C1 那样的算法。

取走的数必须也是严格上升的。

所以 C1 的代码直接改。

C1 代码自己去看题解，这里是我自己的代码。

C1:

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 10;

int n,a[MAXN];

string ans;

int main(){

    cin >> n;

    for (int i = 1; i <= n; i++){

        cin >> a[i];
    }

    for (int l = 1, r = n, last = 0; l <= r && max(a[l],a[r]) > last;){ //l<=r知道吧，a[l]和a[r]其中一个要大于last知道吧。

        if (a[l] < a[r] && a[l] > last || a[r] <= last){
            /*第一个条件知道意思吧，第二个是指a[l]大于last或者a[r]小于等于last，因为a[r]小于等于就代表着a[l]一定可取。*/

            ans += 'L';//简便方法，重叠运算符。

            last = a[l++];//一定不要忘了重置last！
        }
        else {

            ans += 'R';

            last = a[r--];
        }
    }

    cout << ans.size() << '\n' << ans;

    return 0;
}

代码更改

我们看到第 32 行，也就是第2个 for 循环那里，底下有一个判断条件，我们可以看出，如果左右两个元素相等，那么就会出问题。

所以我们可以这样：如果发现相同元素，那么直接退出循环，再另作打算。

所以那一行就变成了：

for (int l = 1, r = n, last = 0; l <= r && a[l] != a[r] && max(a[l],a[r]) > last)

然后，我们发现有重复的之后，再在外面做操作。

可以另外再开两个字符串，名字随便。

这两个字符串的作用是存储接下来两个操作的答案。

而且一开始ans1和ans2都需要赋值为ans。

注意：后面的东西要用到 \(l,r,last\)，所以这仨玩意要开成全局变量。

好的言归正传，后面两个操作分为全部选左边和全部选右边，这两个循环很相似，但是不一样。

全选左边：

全选左边的话就需要一个循环，从 \(l\) 开始，另外还需要一个局部变量 \(c\)（开在循环里面）。\(i\) 得小于等于 \(r\)，还有 \(a_{i}\) 需要大于 \(c\)。

Code

for (int i = l, c = last; i <= r && a[i] > c;){

    ans1 += 'L';

    c = a[i++];
}

全选右边

右边也是一样，只不过 \(i\) 的值要初始化为 \(r\)，条件要变为 \(\ge l\)，还有就是循环里面的更改，这个简单吧。

Code

for (int i = r, c = last; i >= l && a[i] > c;){

    ans2 += 'R';

    c = a[i--];
}

最后要判断ans1和ans2的长度哪个大，把大的长度记录下来。

这是有人就会问了：

“题目明明是让我们求最长的合法序列，为什么这俩玩意判断哪个大呀？”

emmm……我也不知道。

最后输出长度和长度大的那个 ans。

Code

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 10;

int n,a[MAXN],l,r,last;

string ans,ans1,ans2;

int main(){

    cin >> n;

    for (int i = 1; i <= n; i++){

        cin >> a[i];
    }

    for (l = 1, r = n; l <= r && a[l] != a[r] && max(a[l], a[r]) > last;){

        if (a[l] < a[r] && a[l] > last || a[r] <= last){

            ans += 'L';

            last = a[l++];
        }
        else {

            ans += 'R';

            last = a[r--];
        }
    }

    ans1 = ans2 = ans;

    for (int i = l, c = last; i <= r && a[i] > c;){

        ans1 += 'L';

        c = a[i++];
    }

    for (int i = r, c = last; i >= l && a[i] > c;){

        ans2 += 'R';

        c = a[i--];
    }

    int len = max(ans1.size(),ans2.size());

    cout << len << '\n' << (ans1.size() > ans2.size() ? ans1 : ans2);

    return 0;
}