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;}