【笔试训练】day22

简介: 【笔试训练】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;
}


相关文章
|
7月前
【笔试训练】day21
【笔试训练】day21
|
7月前
|
算法 Shell
【笔试训练】day12
【笔试训练】day12
|
7月前
【笔试训练】day16
【笔试训练】day16
|
7月前
【笔试训练】day23
【笔试训练】day23
|
7月前
|
人工智能
【笔试训练】day20
【笔试训练】day20
|
7月前
|
并行计算
【笔试训练】day14
【笔试训练】day14
|
7月前
|
人工智能 BI
【笔试训练】day24-day48合集(2)
【笔试训练】day24-day48合集(2)
|
7月前
|
人工智能
【笔试训练】day2
【笔试训练】day2
|
7月前
【笔试训练】day15
【笔试训练】day15

热门文章

最新文章