腾讯后台开发笔试9.20
第一题 ac90% 不知道为啥不是100%
t=int(input()) for i in range(t): n=int(input()) s=input() for j in range(len(s)): if s[j]=='8': break if n-j>=11: print("YES") else: print("NO")第二题 AC
n=int(input()) board=[] for i in range(n): board.append(list(map(int,input().split()))) board.sort(key=lambda x:x[1]) i=0 j=n-1 res=0 while i<j: p=board[i][0] q=board[j][0] res=max(res,board[i][1]+board[j][1]) if p-q==0: i+=1 j-=1 elif p<q: board[j][0]-=p i+=1 else: board[i][0]-=q j-=1 print(res)第三题 AC80% 0-1背包问题
#include<bits/stdc++.h> using namespace std; void help(int *num,int n){ int sum=0; bool flag=true; int l=n/2; if(n%2==1){ l++; flag=false; } for(int i=0;i<n;i++) sum+=num[i]; int target=sum/2; vector<vector<bool>> dp; for(int i=0;i<=n;i++){ vector<bool> tmp; for(int j=0;j<=target;j++){ tmp.push_back(false); } dp.push_back(tmp); } for(int i=0;i<=n;i++) dp[i][0]=true; for(int i=1;i<=target;i++) dp[0][i]=false; for(int i=0;i<=n;i++){ for(int j=min(l,i);j>0;j--){ for(int s=1;s<=target;s++){ if(s>=num[i-1] && dp[j-1][s-num[i-1]]) dp[j][s]=true; } } } if(flag){ for(int s=target;s>0;s--){ if(dp[l][s]){ int a=s,b=sum-s; if (a<b) cout<<a<<" "<<b<<endl; else cout<<b<<" "<<a<<endl; break; } } } else{ int res; for(int s=target;s>0;s--){ if(dp[l][s]){ res=sum-2*s; break; } } for(int s=target;s>0;s--){ if(dp[l-1][s]){ res=min(res,sum-2*s); break; } } int a=(sum-res)/2,b=(sum+res)/2; cout<<a<<" "<<b<<endl; } return; } int main(){ int T,n; int num[105]; scanf("%d",&T); for(int i=0;i<T;i++){ scanf("%d",&n); for (int j=0;j<n;j++) scanf("%d",&num[j]); help(num,n); } }第四题AC
#include<bits/stdc++.h> using namespace std; void help(int *num,int n,int k){ int pre=0; sort(num,num+n); int i=0,cnt=0; while(i<n && cnt<k){ if(num[i]>pre){ cout<<num[i]-pre<<endl; pre=num[i]; i++; cnt++; } else{ i+=1; } } for(int i=cnt;i<k;i++) cout<<0<<endl; } int main(){ int n,k; scanf("%d %d",&n,&k); int num[100005]; for(int i=0;i<n;i++) scanf("%d",&num[i]); help(num,n,k); }第五题 考异或数学知识 来不及推导了