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