4.28 吉比特笔试 2题编程题

感觉填空有点难。

时间1个半小时，做变态的填空题，选择，还有编程。

感觉有点不够。

第一题

就是找出字符串s2,是否是s1的子序列，并返回最大的起始下标。

数据不大，所以暴力就行。

复杂度 O(n^2)

char s1[300],s2[300];
int n,m;
bool ck(int pos){
    int cnt=0;
    for(int i=pos;i<=n;i++){
        if(s1[i]==s2[cnt+1])cnt++;
        if(cnt==m)return 1;
    }
    return 0;
}
int main(){
    sc("%s%s",s1+1,s2+1);
    n=strlen(s1+1);
    m=strlen(s2+1);
    int ans=0;
    for(int i=1;i<=n;i++){
        if(ck(i))ans=i;
    }
    O(ans);
}

第二题

给你一个图，每个点最多走2次，走完所有点的最小花费。

TSP问题，因为每个点可能访问过，0，1，2次。

所以用三进制表示状态。然后就是状压dp了。

dp[S][k]=min(dp[S][k],dp[S-j][k]+dis[j][k]) j属于S集合。

复杂度 O(3^n * n^2)

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
int O(){putchar('\n');return 0;}template<typename T,typename... Ty>
int O(const T& a,const Ty&... b){cout<<a<<' ';return O(b...);}
void I(){}template<typename T,typename... Ty>void I(T& a,Ty&... b){cin>>a;I(b...);}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
const int INF=1e9+999;
int dp[60001][11];
int p_3[11];  // 三进制 
int state[60001][11]; // 表示状态  0 1 2
int dis[15][15];
int n,m;
void pre(){
    p_3[0]=1;
    for(int i=1;i<11;i++)p_3[i]=p_3[i-1]*3;
    for(int i=0;i<p_3[10];i++){
        int tem=i;
        for(int j=0;j<10;j++){
            state[i][j]=tem%3;
            tem/=3;
        }
    }
    for(int i=0;i<11;i++)
       for(int j=0;j<11;j++)
           dis[i][j]=INF;
    for(int i=0;i<p_3[10];i++){
        for(int j=0;j<10;j++){
            dp[i][j]=INF;
        }
    }
}
int main(){
    pre();
    I(n,m);
    while(m--){
        int a,b,c;
        I(a,b,c);
        dis[a-1][b-1]=dis[b-1][a-1]=min(c,dis[b-1][a-1]);  //可能有重边
    }
    for(int i=0;i<n;i++){
        dp[p_3[i]][i]=0;
    }
    int ans=INF;
    int S=p_3[n];
    for(int j=0;j<S;j++){
        bool flag=1;
        for(int i=0;i<n;i++){
            if(state[j][i]==0)flag=0;
            if(dp[j][i]!=INF){
                for(int k=0;k<n;k++){
                    if(dis[i][k]!=INF&&state[j][k]!=2){ // 保证集合j 所有点 经过次数小于2
                        dp[j+p_3[k]][k]=min(dp[j][i]+dis[i][k],dp[j+p_3[k]][k]);
                    }
                }
            }
            
        }
        if(flag){
            for(int i=0;i<n;i++){
                ans=min(ans,dp[j][i]);
            }
        }
    }
    if(ans>=INF)ans=-1;
    O(ans);
}

#吉比特笔试##腾讯##笔试题目#