本文共 1254 字，大约阅读时间需要 4 分钟。

【题目】

【题解】

两步变换可以看成不小于两步变换：

1. 相同，那么可以把一个字母改成错误的再改成对的 2. 改变一个字母，可以把这个字母改成错误的再改成对的 3. 增加一个字母，可以增加一个错误的字母再改成对的 4. 减少一个字母，可以先把这个字母改变再删除这个字母 然后只需要暴力所有情况即可，复杂度O(n^3)。也可以dp，时间复杂度O(n^2)。

（莱文斯坦距离，又称Levenshtein距离，是编辑距离的一种。指两个字符串之间，由一个转成另一个所需的最少编辑操作次数。允许的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。）

【dfs】

#include
   
    using namespace std;string s,ch;int f=0;void dfs(int l,int r,int t){    if(t>2) return;    if(l==s.size()&&r==ch.size())    {        f=1; return;    }    if(s[l]!=ch[r]) t++;    if(l
    
     >s>>ch;    dfs(0,0,0);    if(f) puts("YES");    else puts("NO");    return 0;}
    
   

【dp】

#include 
   
    #define maxn 1005using namespace std;int dp[maxn][maxn];int main(){	string s,t; cin>>s>>t;	int l1=s.length();	int l2=t.length();	for(int i=0;i
   

【题目】

【题解】

首先，我们知道，在素数序列中任意一对素数都互质。任意一对素数a,b的乘积有1,a,b,a*b四个因子，但是题目要求任意一对因子个数要大于10，而任意两对素数对的乘积再乘积，所得的乘积会有16个因子，并且这个乘积值也满足互质的要求。最后一点，数据范围不能超过4*1e8，那么我们不能选择2*3，3*5，5*7这样的形式，所以我们选择第1个素数和第4000个数相乘，第2个数和第3999个数相乘，这样最大的数在4e8以内。

【代码】

#include 
   
    using namespace std;int F(int n){    for(int i=2;i*i<=n;i++)        if(n%i==0) return 0;    return 1;}int main(){    int n=0,a[4000];    for(int i=2;n<4000;i++)        if(F(i))        {            a[n++]=i;        }    for(int i=0;i<2000;++i)        cout<
    
     <
    
   

 

转载地址：http://gfben.baihongyu.com/