笔试强训：Day8

一、**kotori和抽卡（概率论的数学期望）

登录—专业IT笔试面试备考平台_牛客网

#include<iostream>
#include<cmath>
using namespace std;
//3次出两张  c32*p^2*(1-p)^1 
int n,m;
int main(){
    cin>>n>>m;
    double ret=1.0;
    for(int i=n;i>n-m;--i) ret*=i;
    for(int i=m;i>=2;--i) ret/=i;
    printf("%.4f",ret*pow(0.8,m)*pow(0.2,n-m));
}

二、**ruby和薯条（排序+二分/（滑动窗口+前缀和））

登录—专业IT笔试面试备考平台_牛客网

解法1：

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
int n,l,r;
const int N=2e5+10;
int arr[N];
//排序+二分
int main(){
    cin>>n>>l>>r;
    for(int i=0;i<n;++i) cin>>arr[i];
    sort(arr,arr+n);
    LL ret=0;
    for(int i=1;i<n;++i){//从第二个数开始枚举 1 2 3 5 6   
        int left=0,right=i-1;
        int L,R;//记录左端点和右端点
        while(left<right){
            int mid=left+(right-left)/2;
            if(arr[mid]<arr[i]-r) left=mid+1;
            else right=mid;
        }
       //这种情况就是可能找到的数字也是不满足的
        if(arr[left]>=arr[i]-r) L=left;
        else L=left+1;
        left=0,right=i-1;//找右端点
        while(left<right){
            int mid=left+(right-left+1)/2;
            if(arr[mid]<=arr[i]-l) left=mid;
            else right=mid-1;
        }
         //这种情况就是可能找到的数字也是不满足的
        if(arr[left]<=arr[i]-l) R=left;
        else R=left-1;
        if(R>=L) ret+=R-L+1;
    }
    cout<<ret<<endl;
}

解法2： 

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
int n,l,r;
const int N=2e5+10;
int arr[N];
LL find(int x){
    LL ret=0;
    for(int left=0,right=0;right<n;++right){
        while(arr[right]-arr[left]>x) ++left;
        ret+=right-left;
    }
    return ret;
}
int main(){
    cin>>n>>l>>r;
    for(int i=0;i<n;++i) cin>>arr[i];
    sort(arr,arr+n);
    cout<<find(r)-find(l-1)<<endl;
}

三、**循环汉诺塔（递推）

循环汉诺塔_牛客题霸_牛客网

#include <iostream>
using namespace std;
int n;
const int MOD=1e9+7;
int main() {
  cin>>n;
  int x=1,y=2;//x=2y+1  y=2y+x+2
  for(int i=2;i<=n;++i){
     int xx=x,yy=y;
     x=(2*yy+1)%MOD;
     y=((2*yy)%MOD+xx+2)%MOD;
  }
  cout<<x<<" "<<y<<endl;
}

四、最小差值（排序）

登录—专业IT笔试面试备考平台_牛客网

class Solution {
public:
    typedef long long LL;
    int minDifference(vector<int>& a) {
        sort(a.begin(),a.end());
        int n=a.size();
        LL ret=1e16+10;
        for(int i=1;i<n;++i)
            ret=min(ret,(LL)a[i]-a[i-1]);
        return ret;
    }
};

五、kotori和素因子（枚举+dfs）

登录—专业IT笔试面试备考平台_牛客网

//这个数 所有因子里面 且必须是素数
#include<iostream>
#include<cmath>
using namespace std;
const int N=15,M=1010,INF=0x3f3f3f3f;
int n,arr[N];
bool vis[M];//是否被使用过
int path;//路径上所有因子的和
int ret=INF;//最终结果
bool isprime(int x){//是否是素数
    if(x==2) return true;
    if(x%2==0) return false;
    int n=sqrt(x);
    for(int i=3;i<=n;++i)
        if(x%i==0) return false;
    return true;
}
void dfs(int pos){
    if(pos==n){
        ret=min(ret,path);
        return;
    }
    //开始找这个数的所有因子
    for(int i=2;i<=arr[pos];++i)
        if(!vis[i]&&arr[pos]%i==0&&isprime(i)){
            path+=i;
            vis[i]=true;
            dfs(pos+1);
            vis[i]=false;
            path-=i;
        }
}
int main(){
    cin>>n;
    for(int i=0;i<n;++i) cin>>arr[i];
    dfs(0);
    if(ret==INF) cout<<-1<<endl;
    else cout<<ret<<endl;
}

六、dd爱科学1.0（贪心+二分）

登录—专业IT笔试面试备考平台_牛客网

#include<iostream>
#include<vector>
using namespace std;
string s;
int n;
//最长非下降子序列
int main(){
    cin>>n>>s;
    vector<char> v;
    for(int i=0;i<n;++i){
        char ch=s[i];
        if(v.size()==0||ch>=v.back()) v.emplace_back(ch);
        else{
            //开始二分
            int left=0,right=v.size()-1;
            while(left<right){
                int mid=left+(right-left)/2;
                if(v[mid]<=ch) left=mid+1;
                else right=mid;
            }
            v[left]=ch;
        }
    }
    cout<<n-v.size()<<endl;
}

七、kanan和高音（双指针）

登录—专业IT笔试面试备考平台_牛客网

#include<iostream>
using namespace std;
int n;
const int N=2e5+10;
int arr[N];
int main(){
    cin>>n;
    //双指针 
    for(int i=0;i<n;++i) cin>>arr[i];
    int ret=1;
    for(int i=0;i<n;){
        int j=i;
        while(j+1<n&&arr[j+1]-arr[j]<=8) ++j;
        ret=max(ret,j-i+1);
        i=j+1;
    }
    cout<<ret<<endl;
}

八、**拜访（单源最短路bfs）

拜访_牛客题霸_牛客网

#include <cstring>
class Solution {
public:
    int dx[4]={1,-1,0,0};
    int dy[4]={0,0,1,-1};
    int dis[11][11];//标记最短路和是否便利过的数组
    int cnt[11][11]={0};//标记走到这一格需要有多少方案
    int x1,y1,x2,y2;
    int countPath(vector<vector<int> >& CityMap, int n, int m) {
       //单源最短路方案数问题  首先要先找到起点和终点
        for(int i=0;i<n;++i)
            for(int j=0;j<m;++j)
                if(CityMap[i][j]==1) x1=i,y1=j;
                else if(CityMap[i][j]==2) x2=i,y2=j;
        memset(dis,-1,sizeof dis);//-1 表示还没搜索过
        queue<pair<int,int>> q;
        q.emplace(x1,y1);
        dis[x1][y1]=0;
        cnt[x1][y1]=1;//走到这一格有一个方法
        while(!q.empty()){
            auto[a,b]=q.front();
            q.pop();
            for(int k=0;k<4;++k){
                int x=dx[k]+a,y=dy[k]+b;
                //第一次到达这个位置
                if(x>=0&&x<n&&y>=0&&y<m&&CityMap[x][y]!=-1)
                    if(dis[x][y]==-1){
                        dis[x][y]=dis[a][b]+1;
                        cnt[x][y]+=cnt[a][b];
                        q.emplace(x,y);
                    }
                    //不是第一次到达这个位置,是最短路的话就更新到cnt数组里面
                    else if(dis[a][b]+1==dis[x][y]) cnt[x][y]+=cnt[a][b];
            }
        }
        return cnt[x2][y2];
    }
};

九、**买卖股票的最好时机4（多状态dp）

买卖股票的最好时机(四)_牛客题霸_牛客网

#include <iostream>
using namespace std;
const int N=1010,M=110,INF=0x3f3f3f3f;
int n,k,arr[N],f[N][M],g[N][M];
//f[i][j]表示第i天结束后 此时完成了j笔交易 手上有股票
//f[i][j]=max(f[i-1][j],g[i-1][j]-arr[i])
//g[i][j]表示第i天结束后 此时完成了j笔交易 手上没有股票
//g[i][j]=f[i-1][j-1]+arr[i],g[i-1][j])
int main() {
   cin>>n>>k;
   k=min(n/2,k);
   for(int i=0;i<n;++i) cin>>arr[i];
   f[0][0]=-arr[0];//初始化
   for(int j=1;j<=k;++j) f[0][j]=g[0][j]=-INF;
   for(int i=1;i<n;++i)
      for(int j=0;j<=k;++j){
        f[i][j]=max(f[i-1][j],g[i-1][j]-arr[i]);
        g[i][j]=g[i-1][j];
        if(j>=1)g[i][j]=max(f[i-1][j-1]+arr[i],g[i][j]);
      }
    int ret=0;
    for(int j=0;j<=k;++j) ret=max(g[n-1][j],ret);
    cout<<ret<<endl;
}

 十、AOE还是单体？（贪心）

登录—专业IT笔试面试备考平台_牛客网

#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e5+10;
int arr[N];
int n,x;
int main(){
    cin>>n>>x;
    for(int i=1;i<=n;++i) cin>>arr[i];
    sort(arr+1,arr+1+n);
    long long ret=0;
    int index=max(n-x,0);
    ret+=arr[index]*x;
    for(int i=index+1;i<=n;++i) ret+=arr[i]-arr[index];
    cout<<ret<<endl;
}

十一、**kotori和n皇后（哈希标记数组）

登录—专业IT笔试面试备考平台_牛客网

     关键就在于如何用哈希表存攻击范围，如果我们知道棋盘多大的话，其实是可以直接用bool数组标记的，但是这题是无限大的棋盘  所以只能用哈希

#include<iostream>
#include<unordered_set>
using namespace std;
//使用哈希表标记行列
unordered_set<int> col;//存x
unordered_set<int> row;//存y
unordered_set<int> dig1;//主对角线y-x
unordered_set<int> dig2;//副对角线y+x
const int N=1e5+10;
int k,t;//皇后个数和询问次数
int x,y;//坐标
int main(){
    cin>>k;
    int ret=N;//表示从第i次放置之后  后面都会相互攻击
    for(int i=1;i<=k;++i){
        cin>>x>>y;
        if(ret!=N) continue;
        if(row.count(y)||col.count(x)||dig1.count(y-x)||dig2.count(y+x))
            ret=i;
        else{
            row.insert(y);
            col.insert(x);
            dig1.insert(y-x);
            dig2.insert(y+x);
        }
    }
    cin>>t;
    int i;//第i次询问
    while(t--){
        cin>>i;
        if(i>=ret) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}

十二、**取金币（区间dp）

 取金币_牛客题霸_牛客网

class Solution {
public:
    int arr[110]={0};
    int dp[110][110]={0};
    int getCoins(vector<int>& coins) {
        //dp[i][j] i-j区间的最大积分
        int n=coins.size();
        arr[0]=arr[n+1]=1;
        for(int i=1;i<=n;++i) arr[i]=coins[i-1];
        for(int i=n;i>=1;--i)
            for(int j=i;j<=n;++j)
                for(int k=i;k<=j;++k)
                    dp[i][j]=max(dp[i][j],dp[i][k-1]+dp[k+1][j]+arr[k]*arr[i-1]*arr[j+1]);
        return dp[1][n];
    }
};

十三、矩阵转置（规律）

矩阵转置_牛客题霸_牛客网

#include <iostream>
using namespace std;
const int N=15;
int arr[N][N];
int n,m;
int main() {
    cin>>n>>m;
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j) cin>>arr[i][j];
    for(int j=0;j<m;++j){
        for(int i=0;i<n;++i)
           cout<<arr[i][j]<<" ";
        cout<<endl;
    }
}

十四、**四个选项（枚举+dfs）

登录—专业IT笔试面试备考平台_牛客网

#include<iostream>
#include<vector>
using namespace std;
int m,x,y;
bool same[13][13];//标记两题的选项是否相同
int ret=0;
int cnt[5];//记录每个选项的次数
vector<int> path;//记录过程中已经选过了哪些选项  1-12号位置分别代表1-12题 1-4分别代表具体选项
bool issame(int pos,int cur){//pos代表之前的位置 而cur表示当前选项
    for(int i=1;i<pos;++i)
        if(same[pos][i]&&path[i]!=cur) return false;
    return true;
}
void dfs(int pos){
    if(pos>12){
        ++ret;
        return;
    }
    //此时开始尝试填选项
    for(int i=1;i<=4;++i)
        if(cnt[i]&&issame(pos,i)){//有使用次数 并且要求相同的都相同了 那就可以
            path.emplace_back(i);
            --cnt[i];
            dfs(pos+1);
            path.pop_back();
            ++cnt[i];
        }
}
int main(){
    for(int i=1;i<=4;++i) cin>>cnt[i];
    cin>>m;
    while(m--){
        cin>>x>>y;
        same[x][y]=same[y][x]=true;//表示两个选项必须相同
    }
    path.emplace_back(0);//占位置
    dfs(1);
    cout<<ret<<endl;
}

十五、**接雨水（动归预处理/双指针/单调栈/正难则反）

42. 接雨水 - 力扣（LeetCode）

      一根柱子接到的雨水取决于左边最高柱子和右边最高柱子其中较矮的那根的高度再减掉当前柱子自己的高度。

 解法1：动归预处理

class Solution {
public:
//我怎么知道我这个柱子能接多少水呢？？取决于我左边最高的柱子和右边最高柱子的较小值 减掉的高度
//要把自己也算上 
    int trap(vector<int>& height) {
        int n=height.size();
        vector<int> left(n),right(n);
        left[0]=height[0],right[n-1]=height[n-1];
        for(int i=1;i<n;++i) left[i]=max(height[i],left[i-1]);
        for(int i=n-2;i>=0;--i) right[i]=max(height[i],right[i+1]);
        int ret=0;//统计雨水的数量
        for(int i=1;i<n-1;++i)
           ret+=min(left[i],right[i])-height[i];
        return ret;
    }
};

解法2：双指针

class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size();
        if(n<3) return 0;
        int ret=0;
        int left=0,right=n-1;
        int leftmax=height[0],rightmax=height[n-1];
        while(left<right)
            if(height[left]<height[right]){
                ret+=leftmax-height[left];
                leftmax=max(leftmax,height[++left]);
            }
            else{
                ret+=rightmax-height[right];
                rightmax=max(rightmax,height[--right]);
            }
        return ret;
    }
};

解法3：单调栈

class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size();
        stack<int> st;
        int ret=0;
        for(int i=0;i<n;++i){
            while(!st.empty()&&height[i]>=height[st.top()]){
                int top=st.top();
                st.pop();
                if(st.empty()) break;//因为还要找左边的柱子
                int left=st.top();
                int curwidth=i-left-1;
                int curheight=min(height[left],height[i])-height[top];
                ret+=curheight*curwidth;
            }
            st.push(i);
        }
        return ret;
    }
};

解法4：正难则反（总面积-柱子）

class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size();
        if(n<3) return 0;
        int zhuzi=accumulate(height.begin(),height.end(),0);//柱子的全部面积
        //正难则反
        int left=0,right=n-1;
        int prevh=0;//前置高度
        int sum=0;
        while(left<right){
            while(left<right&&height[left]<=prevh) ++left;
            while(left<right&&height[right]<=prevh) --right;
            sum+=(min(height[left],height[right])-prevh)*(right-left+1);
            prevh=min(height[left],height[right]);
        }
        return sum-zhuzi;
    }
};

十六、疯狂的自我检索者（贪心）

登录—专业IT笔试面试备考平台_牛客网

#include<iostream>
using namespace std;
int n,m;
int a;
int main(){
    cin>>n>>m;
    int sum=0;
    for(int i=0;i<n-m;++i){
        cin>>a;
        sum+=a;
    }
    printf("%.5lf %.5lf",(sum+m)*1.0/n,(sum+5*m)*1.0/n);
}

十七、**栈和排序（贪心+栈）

栈和排序_牛客题霸_牛客网

class Solution {
public:
    vector<int> solve(vector<int>& a) {
       //尽量让最大的数字出栈
       vector<int> ret;
       int n=a.size();
       ret.reserve(n);
       bool hash[50001]={0};
       stack<int> st;
       int aim=n;//一定要先让这个数字进去
       for(auto&e:a){
         st.push(e);
         hash[e]=true;
         while(hash[aim]) --aim;
         while(!st.empty()&&st.top()>=aim){//同时出
            ret.push_back(st.top());
            st.pop();
         }
       }
       return ret;
    }
};

十八、**加减（枚举+前缀和+数学+滑动窗口+贪心+排序）

登录—专业IT笔试面试备考平台_牛客网

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
typedef long long LL;
LL n,k,arr[N],sum[N];  // sum是前缀和数组
LL cal(int left,int right){
    //这个函数统计把该区间都变成相同的最小代价
    int mid=(left+right)>>1;
    return (mid-left-right+mid)*arr[mid]-(sum[mid-1]-sum[left-1])+(sum[right]-sum[mid]);
}

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;++i) cin>>arr[i];
    //排序+前缀和数组的预处理
    sort(arr+1,arr+1+n);
    for(int i=1;i<=n;++i) sum[i]=sum[i-1]+arr[i];
    int ret=1;
    for(int left=1,right=1;right<=n;++right){
        while(cal(left,right)>k) ++left;
        ret=max(ret,right-left+1);
    }
    cout<<ret<<endl;
}