0928携程笔试题解
游游的字符交换
思路:按题意模拟即可。枚举交换每一对,判断完了再换回来。
参考代码:
#include<bits/stdc++.h> using namespace std; int main(){ int _; cin>>_; while(_--){ string s,y; cin>>s>>y; int n=s.length(),i,j,jud=0; for(i=0;i<n;i++){ for(j=i+1;j<n;j++){ swap(s[i],s[j]); if(s==y)jud=1; swap(s[i],s[j]); } } cout<<(jud?"Yes\n":"No\n"); } }
233星人
思路:如果不是233的倍数,显然无解。否则可以看成是233乘以一个十进制数,计算数位之和即可。
参考代码:
#include<bits/stdc++.h> using namespace std; int main(){ int _; cin>>_; while(_--){ long long x;cin>>x; if(x%233!=0){cout<<-1<<'\n';continue;} x/=233; int cnt=0; while(x)cnt+=x%10,x/=10; cout<<cnt<<'\n'; } }
数组平均
思路:先将数组排序,选择的元素一定是最小的一些元素和最大的一些元素。枚举选择的区间即可,可以用前缀和或者一边遍历一边维护选择的数之和。
#include <bits/stdc++.h> using namespace std; int a[202020]; long long op[202020],ed[202020]; int main() { int n,i,j,k; cin>>n>>k; for(i=1;i<=n;i++)cin>>a[i]; sort(a+1,a+n+1); long long s1=0,s2=0; for(i=1;i<=n;i++)op[i]=s1+=a[i]; for(i=n;i>=1;i--)ed[i]=s2+=a[i]; double mi=1e18; for(i=0;i<=k;i++){ int l=i+1,r=l+(n-k)-1; double avg=1.0*(op[i]+ed[r+1])/k; mi=min(mi,max(1.0*a[r],avg)-min(1.0*a[l],avg)); } printf("%.7f",mi); }
游游的k-好数组
思路:首先将数组变成k-好数组,即每个都相等的数都变成这些数的最大值,消耗一定的操作次数。
然后是两种方案:将小于的某个变得更大,或者将大于的某个变得更大。后者比前者需要多变一个数,分别统计可能拿到的最大值即可。
#include<bits/stdc++.h> using namespace std; int a[202020],ma[202020]; int main(){ int _; cin>>_; while(_--){ int n,k,x,i,mm=0,mm2=0; cin>>n>>k>>x; long long sum=0; for(i=0;i<k;i++)ma[i]=0; for(i=0;i<n;i++){ cin>>a[i]; ma[i%k]=max(ma[i%k],a[i]); if(i%k<n%k)mm=max(mm,a[i]); else mm2=max(mm2,a[i]); } long long s=0; for(i=0;i<n;i++){ s+=ma[i%k]-a[i]; } if(s>x){cout<<-1<<'\n';continue;} x-=s; cout<<max(mm+x/(n/k+1),mm2+x/(n/k))<<'\n'; } }#携程笔试##笔试#