构造算法题目积累

Posted on | In

cf1304D

题目给出n-1个‘<’‘>’约束，第i个位置的<意味着结果串中a[i]<a[i+1]，要求用1~n个数构造出两个串，分别拥有最小和最大的LIS。

思路：我们将升序1~n中连续>的区间执行reverse操作，执行完毕后的结果就是拥有最大LIS的满足约束的结果串。

证明：这种方法利用了全部的上升区间，及下降区间的一侧边界。我们知道对于连续下降区间，最多只能有一个元素被选入LIS，因此整体利用率达到最大。

最短的类似，首先降序n~1，然后不满足约束的reverse。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for(int i=0;i<n;i++)
    ans[i]=i+1;
l=0,r=0;
for(int i=0;i<n-1;i++){
    if(cst[i]=='>'){
        r=i+1;
    }else{
        if(l<r)
            reverse(ans+l,ans+r+1);
        l=i+1;
    }
}
if(l<r)
    reverse(ans+l,ans+r+1);
for(int i=0;i<n;i++){
    printf("%d%c",ans[i],(i==n-1?'\n':' '));
}

cf1350D

https://codeforces.com/contest/1350/problem/D

给一个序列，可以将其中任意一段全部改成该段中位数的大小，中位数如果是偶数长度则取n/2位置。问最后能否把序列所有值都改为k。

首先可以发现，如果我们手上有两个连续的k，那么必能实现（一步一步转化）；如果一个k都没有则必不可能实现。如果只有一些不连续的k呢？这个情况稍微复杂一点，我们发现，如果一个k和一个比它大的数相邻，那么可以转化为两个连续k。这里我们为了方便把a的值分为0、1、2，代表小于、等于和大于k。如果有两个相同的值相邻或者只间隔一个数，那么有办法把任意长的序列都转化为该值。那么我们就要求，必定存在一组11、12、22是相邻的或间隔一，如果是前两者那么可以直接从那里构造出等于k的序列，如果是后者则可以构造2序列直到临近k，然后执行12转化；如果说12的间隔都大于1，那么序列最后不可能转化为0以外的数，失败。

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
#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+4;
int a[maxn],t,n,k;

int main(){
    cin>>t;
    while(t--){
        cin>>n>>k;
        int f=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if(a[i]>k) a[i]=2;
            else if(a[i]==k) f=1,a[i]=1;
            else a[i]=0;
        }
        if(f&&n>1){
            f=0;
            for(int i=1;i<=n-1;i++){
                if((a[i]&&a[i+1])||(i<=n-2&&a[i]&&a[i+2])){
                    f=1;
                    break;
                }
            }
        }
        cout<<(f?"yes":"no")<<endl;
    }
}

cf1365F

对字符串定义这样一种操作：交换前缀和后缀。然后问字符串a经过若干次操作能不能变成b。2e5

最初看的时候理解成前后缀做轴对称，心想那不是简单，结果发现是交换……字符串的方向不变。

可以这样去理解交换操作：两个字符串分别向着彼此的方向移动，直到占据对方的位置。这样来看交换操作又变得对称了起来。然后就很容易发现一个性质：位于对称位置的字符，不管怎么交换，它们依然是一对。这样我们就得出一个结论，要想变换得到b字符串，首先要字符间的成对的关系是一致的。

接下来我们证明如果成对关系一致必然可以转换。我们可以从中间字符开始向两边一一变化，面临的任务就是要把一对靠边近的点转移到靠边远的一对位置上，我们发现最多三次就可以，并且不会用到更靠内的字符。也就是能在不影响之前成果的基础上转移成功。

所以只需要字符的成对关系一致就可以了，存一下pair，排序完比较一下，再特判一下奇数的中间元素相同。