笔试强训：Day6

发布于：2025-05-30 ⋅ 阅读:(22) ⋅ 点赞:(0)

一、小红的口罩（贪心+优先级队列）

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

 

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int n,k;
int main(){
    //用一个小根堆  每次使用不舒适度最小的
    cin>>n>>k;
    int x;
    priority_queue<int,vector<int>,greater<int>> heap;
    for(int i=0;i<n;++i){
        cin>>x;
        heap.push(x);
    }
    //开始循环
    int sum=0,ret=0;
    while(sum<=k){
        int t=heap.top();
        heap.pop();
        sum+=t;
        heap.push(t*2);
        ++ret;
    }
    cout<<ret-1<<endl;
}

二、*春游（分类讨论+数学）

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

#include<iostream>
#include<cmath>
using namespace std;
typedef long long LL;
LL t,n,a,b;
LL func(){
    if(n<=2) return min(a,b);//做便宜的船
    if(a>=b) return (LL)ceil(n/3.0)*b;
    LL ret=0;
    if(a*3<b*2){//说明双人船便宜 尽量选择双人船
        ret+=n/2*a;
        if(n%2==1) ret+=min(a,b-a);//多1个人 看看是要直接租双人 还是退掉一个双人租三人
    }
    else{//说明要尽可能租三人船  b*2<=a*3 有可能b更便宜
        ret+=n/3*b;
        //此时可能剩1个人或者2个人
        n%=3;
        if(n==1) ret+=min(a,2*a-b);
        if(n==2) ret+=a;
    }
    return ret;
}
int main(){
    cin>>t;
    while(t--){
        cin>>n>>a>>b;
        cout<<func()<<endl;
    }
}

三、数位染色（01背包）

数位染色_牛客题霸_牛客网

#include <iostream>
using namespace std;
const int N=20,M=10*9;//记录所有数位
bool dp[M];//前i个数选 和恰好为target
int arr[N];//标记各个数位
long long x;
int n=0;//统计有多少位
int sum=0;//统计总和
bool func(){
    if(sum%2==1) return false;
    sum/=2;
    dp[0]=true;
    for(int i=0;i<n;++i)
      for(int j=sum;j>=arr[i];--j)
        dp[j]=dp[j]||dp[j-arr[i]];
    return dp[sum]; 
}
int main() {
    cin>>x;
    while(x){
       arr[n++]=x%10;
       sum+=x%10;
       x/=10;
    }
    if(func()) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

 四、素数回文（数学+模拟）

素数回文_牛客题霸_牛客网

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

string s;
bool isprim(long long x){
    if(x==2) return true;
    if(x<2||x%2==0) return false;
    int n=sqrt(x);
    for(int i=3;i<=n;i+=2)
       if(x%i==0) return false;
    return true; 
}
int main() {
   cin>>s;
   s.reserve(s.size()*2);
   for(int i=s.size()-2;i>=0;--i) s+=s[i];
   if(isprim(stoll(s))) cout<<"prime"<<endl;
   else cout<<"noprime"<<endl;
}

五、活动安排（左区间端点排序+贪心）

活动安排_牛客题霸_牛客网

#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N=2e5+1;
int n;
PII arr[N];
int main() {
   cin>>n;
   for(int i=0;i<n;++i) cin>>arr[i].first>>arr[i].second;
   sort(arr,arr+n);
   int ret=0,right=arr[0].second;
   for(int i=1;i<n;++i) 
   //如果有重叠 保留右侧最小的
      if(arr[i].first<right) right=min(right,arr[i].second);
      else{//如果没有重叠 就更新一下 然后++ret
         ++ret;
         right=arr[i].second;
      }
    cout<<ret+1<<endl;
}

六、**合唱团（多维状态dp）

合唱团_牛客题霸_牛客网

#include <iostream>
using namespace std;
typedef long long LL;
const int N=55,M=15;
const LL INF=0x3f3f3f3f3f3f3f3f;
int n,k,d;
LL arr[N],f[N][M],g[N][M]; //N和n有关系 M和k有关系
//该题的动归需要限制i位置必须选  因为有限制条件d
//f[i][j]表示从前i个挑选j个 且i位置必须选 的最大乘积
//g[i][j]表示从前i个挑选j个 且i位置必须选 的最小乘积
int main() {
    cin>>n;
    for(int i=1;i<=n;++i) cin>>arr[i];
    cin>>k>>d;
    for(int i=1;i<=n;++i){//填写每一行
       f[i][1]=g[i][1]=arr[i];
       for(int j=2;j<=min(k,i);++j){
          f[i][j]=-INF;
          g[i][j]=INF;
          for(int prev=max(i-d,j-1);prev<=i-1;++prev){
            f[i][j]=max(max(f[prev][j-1]*arr[i],g[prev][j-1]*arr[i]),f[i][j]);
            g[i][j]=min(min(f[prev][j-1]*arr[i],g[prev][j-1]*arr[i]),g[i][j]);
          }
       }
    }
    LL ret=-INF;
    for(int i=k;i<=n;++i) ret=max(ret,f[i][k]);
    cout<<ret<<endl;
}

七、*青蛙跳台阶问题（规律）

跳台阶扩展问题_牛客题霸_牛客网

#include <iostream>
using namespace std;

int main() {
    int n;
    cin>>n;
    cout<<(1<<(n-1))<<endl;
}

 八、包含不超过两种字符的最长子串（滑动窗口）

包含不超过两种字符的最长子串_牛客题霸_牛客网

#include <iostream>
#include <string>
using namespace std;
string s;
int main() {
    cin>>s;
    int n=s.size();
    int kinds=0;//记录种类
    int hash[26]={0};
    int ret=2;
    for(int left=0,right=0;right<n;++right){
        if(hash[s[right]-'a']++==0) ++kinds;
        while(kinds>2) 
           if(--hash[s[left++]-'a']==0) --kinds;
        ret=max(ret,right-left+1);
    }
    cout<<ret<<endl;
}

九、字符串的排列（排序+dfs）

字符串的排列_牛客题霸_牛客网

class Solution {
  public:
    vector<string> ret;
    string path;
    bool check[10] = {0};
    void dfs(string s) {
        if (path.size() == s.size()) {
            ret.emplace_back(path);
            return;
        }
        for (int i = 0; i < s.size(); ++i) {
            if(check[i]||i>0&&s[i-1]==s[i]&&!check[i-1])  continue;//但是前面的数没选
            path.push_back(s[i]);
            check[i] = true;
            dfs(s);
            path.pop_back();
            check[i] = false;

        }
    }
    vector<string> Permutation(string str) {
        if (str.empty()) return {};
        //要去重 所以排序一下
        sort(str.begin(), str.end());//保证相同的放在一起
        dfs(str);
        return ret;
    }
};

 十、[NOIP2008]ISBN号码（模拟）

[NOIP2008]ISBN号码_牛客题霸_牛客网

#include <iostream>
#include <string>
#include <cctype>
using namespace std;
string s;
int main() {
    cin>>s;
    int n=s.size();
    int sum=0;
    int count=1;//乘数
    for(int i=0;i<n-2;++i)
       if(isdigit(s[i])) sum+=(s[i]-'0')*count++;
    sum%=11;
    if(sum==s[n-1]-'0'||sum==10&&s[n-1]=='X')cout<<"Right"<<endl;
    else{
        s[n-1]=sum==10?'X':sum+'0';
        cout<<s<<endl;
    }
}

十一、kotori和迷宫（单源最短路bfs）

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

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=32;
int n,m;
int x1,y1;//起点位置
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
char arr[N][N];//迷宫
int dis[N][N];//不仅标记是否搜索过,也标记最短距离
queue<pair<int,int>> q;//用来BFS
//单源最短路问题
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j){
            cin>>arr[i][j];
            if(arr[i][j]=='k') x1=i,y1=j;
        }
    memset(dis,-1,sizeof dis);//表示没搜索过
    //开始进行最短路问题
    q.emplace(x1,y1);
    dis[x1][y1]=0;
    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>=1&&x<=n&&y>=1&&y<=m&&dis[x][y]==-1&&arr[x][y]!='*'){
                dis[x][y]=dis[a][b]+1;
                if(arr[x][y]!='e') q.emplace(x,y);
            }
        }
    }
    //搜索结束  我们就开始遍历dis找最近出口步数 和可到达的出口
    int count=0,ret=0x3f3f3f3f;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(arr[i][j]=='e'&&dis[i][j]!=-1){
                ++count;
                ret=min(ret,dis[i][j]);
            }
    if(count==0) cout<<-1<<endl;
    else cout<<count<<" "<<ret<<endl;
}

十二、矩阵最长递增路径（dfs+记忆化）

矩阵最长递增路径_牛客题霸_牛客网

    int m,n;
    int memo[1010][1010]={0};
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    int dfs(vector<vector<int>>& matrix,int i,int j){
       if(memo[i][j]) return memo[i][j];
       int len=1;
       for(int k=0;k<4;++k){
        int x=dx[k]+i,y=dy[k]+j;
        if(x>=0&&x<m&&y>=0&&y<n&&matrix[x][y]>matrix[i][j]) 
           len=max(len,1+dfs(matrix,x,y));
       }
       return memo[i][j]=len;
    }
    int solve(vector<vector<int>>& matrix) {
       m=matrix.size(),n=matrix[0].size();
       int ret=1;
       for(int i=0;i<m;++i)
         for(int j=0;j<n;++j)
            ret=max(ret,dfs(matrix,i,j));
        return ret;
    }
};

十三、奇数位丢弃（找规律）

奇数位丢弃_牛客题霸_牛客网

#include <iostream>
using namespace std;

int main() {
   int n;
   while(cin>>n){
     int ret=1;
     while(ret-1<=n) ret*=2;
     cout<<ret/2-1<<endl;
   }
}

十四、*求和（dfs）

求和__牛客网

该题没有顺序问题，所以可以用选or不选做 

#include <iostream>
using namespace std;
bool vis[11];//标记数组
int n,m;
int sum;//统计已选数字的总和
void dfs(int pos){
    if(sum==m){
       for(int i=1;i<=n;++i)
         if(vis[i]) cout<<i<<" ";
       cout<<endl;
       return;
    }
    if(sum>m||pos>n) return;//没有意义了
    //选
    sum+=pos;
    vis[pos]=true;
    dfs(pos+1);
    sum-=pos;
    vis[pos]=false;
    dfs(pos+1);//不选
}   
int main() {
   cin>>n>>m;
   dfs(1);//dfs枚举位置
}

 以选几个作为决策

#include <iostream>
using namespace std;
bool vis[11];//标记数组
int n,m;
int sum;//统计已选数字的总和
void dfs(int pos){
    if(sum==m){
       for(int i=1;i<=n;++i)
         if(vis[i]) cout<<i<<" ";
       cout<<endl;
       return;
    }
    if(sum>m) return;//没有意义了
    for(int i=pos;i<=n;++i){
        sum+=i;
        vis[i]=true;
        dfs(i+1);
        vis[i]=false;
        sum-=i;
    }
}   
int main() {
   cin>>n>>m;
   dfs(1);//dfs枚举位置
}

十五、计算字符串的编辑距离（双数组dp问题）

计算字符串的编辑距离_牛客题霸_牛客网

#include <iostream>
#include <string>
using namespace std;
const int N=1010;
int dp[N][N];
string a,b;
int main() {
   //dp[i][j]表示以0-i的A串 变成0-j的B串所需要的最小操作次数
   cin>>a>>b;
   int m=a.size(),n=b.size();
   a=' '+a,b=' '+b;//为了同步下标
   dp[0][0]=0;//都是空串
   for(int i=1;i<=m;++i) dp[i][0]=i;
   for(int j=1;j<=n;++j) dp[0][j]=j;
   for(int i=1;i<=m;++i)
     for(int j=1;j<=n;++j)
       if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1];
       else dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
    cout<<dp[m][n]<<endl;
}

十六、提取不重复的整数（模拟）

提取不重复的整数_牛客题霸_牛客网

#include <iostream>
using namespace std;
string s;
int main() {
    bool hash[10]={0};
    cin>>s;
    for(int i=s.size()-1;i>=0;--i){
        int x=s[i]-'0';
        if(!hash[x]){
            cout<<x;
            hash[x]=true;
        }
    }
}

十七、**【模板】哈夫曼编码

【模板】哈夫曼编码_牛客题霸_牛客网

#include <iostream>
#include <queue>
using namespace std;
typedef long long LL;
int n;
int main() {
    cin>>n;
    priority_queue<LL,vector<LL>,greater<LL>> heap;
    LL x;
    while(n--){
        cin>>x;
        heap.push(x);
    }
    LL ret=0;
    while(heap.size()>1){
        LL t1=heap.top();
        heap.pop();
        LL t2=heap.top();
        heap.pop();
        ret+=t1+t2;
        heap.push(t1+t2);
    }
    cout<<ret<<endl;
}

十八、**abb（多状态dp）

abb_牛客题霸_牛客网

#include <iostream>
using namespace std;
const int N=1e5+10;
typedef long long LL;
char s[N];
LL f[26],g[26];
//f[]表示以i位置为结尾时有多少个_x
//g[]表示以i位置为结尾时有多少个x
int n;
int main() {
    cin>>n>>s;
    LL ret=0;
    for(int i=0;i<n;++i){
        int x=s[i]-'a';
        ret+=f[x];
        f[x]+=i-g[x];
        g[x]+=1;
    }
    cout<<ret<<endl;
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布