- 题意可能有点出入，但是核心题意基本没啥问题。比赛是采用的ACM赛制取最高分，直接点保存或者调试然后查看保存记录就可以看到本次提交的结果了（保险起见还是每题做完之后点一下保存吧），可以本地调试。
- 睡过头了，十点半才开始登录做题，难崩，但是还好做完了。。。
- 祝大家早日拿到offer呀！！！
第一部分
第一题
- 题意：一个礼盒需要填充三个物品，只能用A和B物品来填充，同时每个礼盒A和B物品各至少有一个。现有A种物品x种，B种物品y种，问最多可以填充多少个礼盒？
- 思路：直接采用贪心的方法，取总物品/3，以及A和B物品的最小值即可。
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;cin>>t;
while(t--){
int x,y;cin>>x>>y;
int sum=x+y;
int ans=sum/3;
ans=min(ans,min(x,y));
cout<<ans<<endl;
}
return 0;
} 第二题
- 题意：给出一个长度为n(0<n<=1e5)的数组，数组的值只能为1，0，-1，在数组的某两个数之间划定一个分界线，使得这个分界线前面大于等于0的数和这个分界线后面小于等于0的数的总个数最小。
- 思路：现预处理出数组的大于等于0的数的总数和小于等于0的数的总数。然后直接遍历数组，然后记录下当前遍历过的大于等于0的个数，以及这个位置之后小于等于0的个数，取和的最小值即可。
#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int main(){
int n;cin>>n;
int sum1=0,sum2=0;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]>0) sum1++;
else if(a[i]<0) sum2++;
else sum1++,sum2++;
}
int now1=0,now2=0;
int ans=min(sum1,sum2);
for(int i=1;i<=n;i++){
if(a[i]>=0) now1++;
if(a[i]<=0) now2++;
ans=min(ans,now1+sum2-now2);
}
cout<<ans<<endl;
return 0;
} 第三题
- 题意：给出n(0<n<=1e5)个卡片，卡片有正面和反面，正面和反面分别有一个数代表这个卡片的种类，卡片的每个面的种类用一个数x（0<x<1e9) 来表示，卡片哪面朝上就表示这个卡片是哪种类型。初始时卡片都是正面朝上的。问最少翻动多少卡片使得至少有一半的卡片是同一种类型的。输入有两行，每行n个数字，第一行表示卡片的正面的种类，第二行表示卡片的反面的种类。
- 思路：我们发现卡片的种类最多也就是2e5种，所以我们可以记录下所有种类的卡片，同时记录每种卡片的初始正面朝上有多少，反面朝下有多少。最后遍历多有卡片的种类，维护一个需要翻转的最小值即可。
#include<bits/stdc++.h>
using namespace std;
int pos[100010],neg[100010];
map<int,int> mp1,mp2; // 分别表示正反面
vector<int> v;
map<int,bool> vis;
int main(){
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>pos[i];
mp1[pos[i]]++;
if(vis[pos[i]]==false){
v.push_back(pos[i]);
vis[pos[i]]=true;
}
}
for(int i=1;i<=n;i++){
cin>>neg[i];
if(pos[i]!=neg[i]){
mp2[neg[i]]++;
}
if(vis[neg[i]]==false){
v.push_back(neg[i]);
vis[neg[i]]=true;
}
}
int ans=1e9;
int tot=(n+1)/2; // 至少需要大于等于tot
for(auto x:v){
// 正面有多少个这个数值了
int sum=mp1[x];
if(sum>=tot){
ans=0;
break;
}else{
int need=tot-sum;
if(mp2[x]>=need){
ans=min(ans,need);
}
}
}
if(ans==1e9) ans=-1;
cout<<ans<<endl;
return 0;
} 第四题
- 题意：给出n(0<n<=1e5)个数，编号分别为从1到n，然后每个编号对应一个种类，种类数有k(0<k<=100)种。假设某一种类的编号一共有m个，我们需要将每个种类的编号更小的m/2(向上取整）放到数据集里面，其余的放到测试集里面，问最后两个集合的编号情况如何？
- 思路：直接对种类进行分组，然后使用sort函数排序，取出每个种类种最小的m/2个放到数据集，其余的放到测试集里面即可。
#include<bits/stdc++.h>
using namespace std;
vector<int> v[110];
vector<int> ans1,ans2;
int main(){
int n,k;cin>>n>>k;
for(int i=1;i<=n;i++){
int x;cin>>x;
v[x].push_back(i);
}
for(int i=1;i<=k;i++){
sort(v[i].begin(),v[i].end());
int m=v[i].size();
int x=(m+1)/2;
for(int j=0;j<m;j++){
if(j<x){
ans1.push_back(v[i][j]);
}else{
ans2.push_back(v[i][j]);
}
}
}
sort(ans1.begin(),ans1.end());
sort(ans2.begin(),ans2.end());
for(auto x:ans1){
cout<<x<<" ";
}
cout<<endl;
for(auto x:ans2){
cout<<x<<" ";
}
cout<<endl;
return 0;
}
第二部分
第一题
- 题意：初始字符串s为"Meituan",会经过若干次变换，每次变换按照s=s+r(s)+wow，来进行变换，r(s)表示s的反转之后的字符串，问第k(0<k<=1e18)个字符是什么？
- 思路：我们使用迭代的方法，找到第k个字符的迭代层数cnt，然后从cnt往前面不断反向迭代，也就是找第cnt次迭代的第k个字符相当于第cnt-1层的第几个字符。（注意，如果在某一层中位置k刚好是最后三个字符，那么可以直接得到最后的答案）如此循环，直到迭代到第一层。我们就可以求出最后的答案了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string s="MeiTuan";
void solve(){
ll k;cin>>k;
// 先计算迭代了多少层
ll cnt=0;
ll now=7,more=3; // now表示的是最后一个字符是第几个
while(now<k){
++cnt;
now=now*2+more;
}
//cout<<cnt<<" "<<pos<<endl;
// 一层一层往前面迭代
for(ll i=cnt;i;i--){
//cout<<i<<" "<<k<<endl;
ll y=now-k;
// 说明是最后三个字符，直接求出即可
if(y==0||y==2){
puts("w");
return;
}else if(y==1){
puts("o");
return;
}
ll pre=(now-more)/2;
// 说明是在当前这一层反转部分
if(k>pre){
k=pre+pre-k+1;
}
now=pre;
}
cout<<s[k-1]<<endl;
}
int main(){
int t;cin>>t;
while(t--){
solve();
}
return 0;
} - 最后打个小小小广告哈，大家有想投递字节跳动提前批和之后正式批的可以找我内推哈（内推码：JZZTBHN）
#题解##美团笔试题#
