【笔试训练】day22

1.添加字符

求最少不相等的位数，可以先求最多相等的位数。

在添加字符之前，A和B最多相等的位数是多少？由于A后面可以添加字符，也就使得A字符可以在B的任意一个位置开始比较。遍历一遍这个比较的起点，从这个起点开始跟A比较，看有多少相等的。用一个变量维护这个添加字符前最多相等的数量。

添加字符后呢？由于是可以添加任何字符，我们默认添加多少，就有多少个相等，即两个字符的长度差。

代码：

#include <iostream>
#include<vector>
#include<string>
using namespace std;

int main(){
   string a;
   string b;
   cin>>a>>b;
   int n1=a.size();
   int n2=b.size();
 
    int ans=0;
   for(int i=1;i+n1-1<=n2;i++){
    int pos=i;
    int cnt=0;
    for(int j=1;j<=n1;j++,pos++){
        if(a[j-1]==b[pos-1]){
           cnt++;
        }
    }
    ans=max(ans,cnt);
   }
   cout<<n2-(n2-n1+ans)<<endl;
    return 0;
}

2.数组变换

排个序，遍历一遍数组，看当前元素的前一个元素是否能通过不断乘2来等于它。如果不能就直接NO

代码：

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef long long LL;

bool isfun(LL x,LL y){
    if(x==y)return true;
    int p=2;
    while(x<y){
        x=x*p;
    }
    if(x==y)return true;
    return false;
}
int main() {
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }

    sort(a.begin(),a.end());
    int f=0;
    for(int i=1;i<n;i++){
       if(!isfun(a[i-1],a[i])){
           f=1;
           break;
       }
    }
    if(f)cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
    return 0;
}

3.装箱问题

最小剩余空间，即v-最大利用空间。

01背包，只不过最大价值变成了最大利用空间。换一下值而已。

代码：

#include <iostream>
#include<vector>
using namespace std;
int main() {
    int v;
    int n;
    cin>>v>>n;
    vector<int> a(n+1);
    vector<vector<int>> f(n+1,vector<int>(v+1));
    for(int i=1;i<=n;i++)cin>>a[i];

    for(int i=1;i<=n;i++){
        for(int j=0;j<=v;j++){
             if(j>=a[i])f[i][j]=max(f[i-1][j-a[i]]+a[i],f[i-1][j]);
             else f[i][j]=f[i-1][j];
        }
    }
    cout<<v-f[n][v];
    return 0;
}