笔试强训：Day6
一、小红的口罩（贪心+优先级队列）
登录—专业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;
}