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