乐趣区

关于c++:解题-String-Transformation-1贪心

String Transformation 1(Codeforces 659 Div.2 C)

Codeforces 的 Div.2 真是越来越难了 QwQ

挂个链接先 – https://codeforces.com/contes/1384/problem/c

题面 – 一共若干组数据,每组数据蕴含 A,B 两个长度为 N 的由 a~t 组成的字符串,你能够抉择 A 串中任意几个雷同的字母减少它的 ACSLL 码,问起码多少次操作能够使其变为 B 串,无奈变成 B 串则输入 -1

Now,开始解题

必定先瞧下数据,10*100000 级别,那必定贪婪、DP(动静布局)、图论建模三选一

奢侈图论建模首当其冲的在工夫复杂度上挂掉了(官网题解是图论建模 + 贪婪 + 并查集(求连通块个数),我也写了相干文章)

再说 DP,无显著档次,可能会有后效性,也就在图论之后也挂掉了

那就只有贪婪了

先想到的是串转数后排序,再模拟题中的操作,这样就疏忽了地位,起初在笔者受同学的一种办法启发,想出了一种正确的贪婪并 AC 了这道题,上面将介绍这种贪婪办法

算法工夫复杂度 – O(Q*N)

核心思想 – 建表以体现状态的递进

首先,如何建表?建什么表?

笔者建的表是一个二维数组,体现的是同一下标的 A 与 B 的字母对应关系(实际上数量对后果没有影响,想想为什么)
a[i][j]寄存的就是有多少个 A 中的 (‘a’+i-1) 对应 B 中的 (a+j-1)
比方 a[1][2]= 3 示意有 3 个 A 中的 ’a’ 对应 B 中的 ’b’

举个残缺的栗子

开始贪婪的操作

按列扫描,对于每列,将这一整列移到与该该列第一个非零元素的下标雷同的列
还没懂的能够联合下相干程序

for(int k=j+1; k<=26; k++){if(a[k][j]>0){ // 如果该元素非零 
        if(f==0){ // 如果之前未有过非零元素 
            f=1; // 标记 
            temp=k-j; // 算出之后的元素要挪动的量 
        }
        else{ // 否则之前有过 
            a[k][j+temp]++; // 挪动  
}
            

贪婪这就完结了?!
没错,真的完结了 ……

这个贪婪看似漏洞百出,甚至笔者本人一开始都有所狐疑
这实际上无懈可击,没有任何谬误
在工夫复杂度上甚至优于官网给出的题解

最初照例奉上残缺程序 (C++) 和精心设计的注解

//CF #659 Div.2 C - String Transformation 1 
//https://codeforces.ml/contest/1384/problem/c
// 贪婪  

#include <bits/stdc++.h>
using namespace std;

int main(){ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    
    int T;
    cin >> T;
    int a[21][21];
    
    for(int i=1; i<=T; i++){
        int N, ans=0;
        cin >> N;
        for(int j=1; j<=26; j++)
            for(int k=1; k<=26; k++)
                a[k][j]=0;
        string A, B;
        cin >> A >> B;
        int f=0;
        for(int j=0; j<N; j++){if(A[j]>B[j]){ // 如果 A 内有元素大于 B 内所对应的 
                cout << -1 << endl; // 输入 -1 
                f=1; // 标记 
                break;
            }
            if(A[j]<B[j])
                a[B[j]-'a'+1][A[j]-'a'+1]++; // 否则填表 
        }
        if(f==1)
            continue;
        int temp;
        for(int j=1; j<=26; j++){
            f=0;
            for(int k=j+1; k<=26; k++){if(a[k][j]>0){ // 如果该元素非零 
                    if(f==0){ // 如果之前未有过非零元素 
                        f=1; // 标记 
                        temp=k-j; // 算出之后的元素要挪动的量 
                    }
                    else{ // 否则之前有过 
                        a[k][j+temp]++; // 挪动  
                    }
                }
            }
            if(f==1) // 如果执行过操作 
                ans++; // 操作总数 ++ 
        }
        cout << ans << endl;
    }
    
    return 0;
}

退出移动版