计算机笔试题题解
摘要
这里塔子哥收集了22,23年各公司学校计算机机试真题
http://101.43.147.120/p
我来记录非简单题
k优雅阈值
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int n,a[N],f[N],x,k;
int c[N];
map<int,int>p[N];
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>k;long long ans=0;for(int i=1;i<=n;i++){f[i]=f[i-1];cin>>x;c[x]++;p[x][c[x]]=i;if(c[x]>=k)f[i]=max(f[i],p[x][c[x]-k+1]);if(f[i])ans+=f[i];}cout<<ans;
}
华为od-2022.11.5-插队
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int n;
typedef pair<int,int>PII;
priority_queue<PII,vector<PII>,greater<PII>>q;
int id[N];
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<=n;i++){char op;cin>>op;if(op=='p'){cout<<id[q.top().second]<<'\\n';q.pop();}else {int o,x;cin>>o>>x;id[i]=o;q.push({x,i});}}
}
分糖果
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int n,x;
int a[N];
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;int sum=0;int ans=0;int mi=1e9;for(int i=0;i<n;i++)cin>>a[i],sum^=a[i],ans+=a[i],mi=min(mi,a[i]);if(sum!=0){cout<<"NO";return 0;}cout<<ans-mi;}
P1004. 华为校招-2022.9.23-求和
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,f[N],sum;
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;f[0]=1;for(int i=1,x;i<=n;i++){cin>>x;sum+=x;for(int j=1e5;j>=0;j--){if(j>=x)f[j]+=f[j-x];}}if(sum&1){cout<<0;return 0;}cout<<f[sum/2];
}
P1078. 美团春招-2023.3.11-第二题-天文爱好者
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n;
typedef pair<int,int>PII;
int ma,ans;
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;vector<PII>v;for(int i=1,x;i<=n;i++){cin>>x;v.push_back({x,-1});}for(int i=1,x;i<=n;i++){cin>>x;v.push_back({x,1});}sort(v.begin(),v.end());int p=0;int pre=0;for(auto [x,c]:v){c=-c;// cout<<"x="<<x<<" c="<<c<<'\\n';// cout<<"p="<<p<<'\\n';if(c==-1&&p==ma){ans+=x-pre+1;p--;continue;}if(c==1&&p+1==ma){pre=x;p++;continue;}if(p+c>ma){ma=p+c;ans=0;pre=x;}pre=x;p+=c;}cout<<ma<<" "<<ans;
}
（58同城-校招-11.5）
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,p[27];
char s[N];
map<char,int>mp;
signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>s+1;n=strlen(s+1);int l=1;int ans=0;for(int i=1;i<=n;i++){if(mp.count(s[i]))l=max(l,mp[s[i]]+1);mp[s[i]]=i;ans=max(ans,i-l+1);}cout<<ans;
}
P1018. 蚂蚁校招-2022.10.27-由其他元素组成的元素
这是一道多项式题目
#include<bits/stdc++.h>
#define p 1004535809
using namespace std;
#define int long long
typedef long long ll;
const int N=1e5+10;
const int mod=1004535809;
// const int mod=998244353;
int fac[N],inv[N],n,m,k;
typedef vector<int>vi;
#define ksm qpow
int qpow(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a%mod;b/=2;a=a*a%mod;}return ans;
}
int getinv(int x){if(x==1)return x;return getinv(mod%x)*(mod-mod/x)%mod;
}
void init(){fac[0]=1;for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod;inv[N-1]=getinv(fac[N-1]);for(int i=N-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
}
vi rev;
void ntt(vi&a,int len,int op=1){rev.resize(len);for(int i=0;i<len;i++)rev[i]=(rev[i>>1]>>1)+(i&1)*(len>>1);for(int i=0;i<len;i++){if(i<rev[i])swap(a[i],a[rev[i]]);}for(int i=1;i<len;i*=2){int w=ksm(3,(mod-1)/i/2);for(int j=0;j<len;j+=(i<<1)){int wn=1;for(int k=0;k<i;k++,wn=wn*w%mod){int t=wn*a[i+j+k]%mod;a[i+j+k]=(a[j+k]-t+mod)%mod;a[j+k]=(a[j+k]+t)%mod;}}}if(op==-1){reverse(a.begin()+1,a.begin()+len);int inv=ksm(len,mod-2);for(int i=0;i<len;i++)a[i]=a[i]*inv%mod;}
}
int C(int n,int k){if(k>n)return 0;return fac[n]*inv[k]%mod*inv[n-k]%mod;
}
vi operator*(vi a,vi b){int re=a.size()+b.size()-1;int len=1;while(len<re)len*=2;a.resize(len),b.resize(len);ntt(a,len),ntt(b,len);for(int i=0;i<len;i++)a[i]=a[i]*b[i]%mod;// for(int i=0;i<len;i++)a[i]=(2-a[i]*b[i]%mod+mod)%mod*a[i]%mod;ntt(a,len,-1);a.resize(re);return a;
}
vi v[N];
vi dfs(int l,int r){if(l==r)return v[l];int mid=l+r>>1;return dfs(l,mid)*dfs(mid+1,r);
}
vi dfs2(int n){int D=ceil(log2(n));int len=1ll<<D;// cout<<"len="<<len<<'\\n';// exit(0);v[1][0]=qpow(v[0][0],mod-2);for(int s=2;s<=len;s*=2){v[2].resize(s);for(int i=0;i<s;i++)v[2][i]=v[0][i];v[1]=v[1]*v[2];// for(int i=s;i<v[1].size();i++)v[1][i]=0;for(int i=s;i<s*2;i++)v[1][i]=0;}return v[1];
}
inline void read(int &x){x = 0;char c = getchar();while(c<'0'||c>'9') c = getchar();while(c>='0'&&c<='9'){x = (x<<3)+(x<<1)+(c^48);c = getchar();}
}inline void mod_read(int &x){x = 0;char c = getchar();while(c<'0'||c>'9') c = getchar();while(c>='0'&&c<='9'){x = (((ll)x<<3)+(x<<1)+(c^48))%p;c = getchar();}
}
int F[N];
signed main(){// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,m,k;// init();// cin>>n>>m>>k;// for(int i=1;i<=m;i++){// int x;// cin>>x;// v[i].resize(x+1);// for(int j=1;j<=x;j++){// v[i][j]=C(x,j);// }// }// cout<<dfs(1,m)[k];cin>>n;v[1].resize(N);for(int i=1,x;i<=n;i++){cin>>x;F[i]=x;v[1][x]=1;}v[2]=v[1];auto ans=dfs(1,2);for(int i=1;i<=n;i++){int x=F[i];if(ans[x])cout<<"Yes"<<'\\n';else cout<<"No"<<'\\n';}}蚂蚁校招-2022.10.27-括号匹配
f[i][j]表示前i个左臂右多j的方案数
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int N=2020;
int n,f[N][N];
char s[N];signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>s+1;n=strlen(s+1);f[0][0]=1;for(int i=1;i<=n;i++){for(int j=0;j<=i;j++){if(s[i]=='('&&j>0)f[i][j]+=f[i-1][j-1];if(s[i]==')'&&j+1<=i-1)f[i][j]+=f[i-1][j+1];if(s[i]=='?'){if(j>0)f[i][j]+=f[i-1][j-1];f[i][j]+=f[i-1][j+1];}f[i][j]%=mod;}}cout<<f[n][0];
}
百度春招-2023.3.13-第二题-构造回文串
eeeeeeeeeeeeeeeeeeedddddddddddddddddddddddredredredred
x-=a*(a+1)
x-=b*(b+1)
x-=c*(c+1)
持续若干次就好了
#include<bits/stdc++.h>
using namespace std;
#define int long long
string s="red";
int p,x;signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>x;while(x){int b=1;while((b+1)*b/2<=x)b++;b--;for(int i=1;i<=b;i++)cout<<s[p];p=(p+1)%3;x-=(b+1)*b/2;}
}拼多多春招-2023.3.12-多多进行团建
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=1e6+10;
int n,m,S,T,h[N],e[M],ne[M],f[M],w[M];
int incf[N],pre[N],d[N],st[N],idx,q[N];
void add(int a,int b,int c,int d){e[idx]=b,f[idx]=c,w[idx]=d,ne[idx]=h[a],h[a]=idx++;e[idx]=a,f[idx]=0,w[idx]=-d,ne[idx]=h[b],h[b]=idx++;
}
bool spfa(){memset(d,0x3f,sizeof d);memset(incf,0,sizeof incf);int hh=0,tt=1;q[0]=S,d[S]=0,incf[S]=1e9;while(hh!=tt){int t=q[hh++];if(hh==N)hh=0;st[t]=0;for(int i=h[t];~i;i=ne[i]){int ver=e[i];if(f[i]&&d[ver]>d[t]+w[i]){d[ver]=d[t]+w[i];pre[ver]=i;incf[ver]=min(incf[t],f[i]);if(!st[ver]){st[ver]=1;q[tt++]=ver;if(tt==N)tt=0;}}}}return incf[T]>0;
}
void EK(int &flow,int &cost){flow=cost=0;while(spfa()){int t=incf[T];flow+=t;cost+=t*d[T];for(int i=T;i!=S;i=e[pre[i]^1]){f[pre[i]]-=t;f[pre[i]^1]+=t;}}
}
unordered_map<string,int>id;
string mp[N];
int vis[N];
void dfs1(int u){cout<<mp[u-n]<<'\\n';vis[u]=1;for(int i=h[u];~i;i=ne[i]){int j=e[i];if(!f[i]&&j>=1&&j<=n){dfs1(j+n);break;}}
}
void dfs2(int u){vis[u]=1;for(int i=h[u];~i;i=ne[i]){int j=e[i];if(!f[i]&&j>=1&&j<=n&&!vis[j+n]){dfs2(j+n);}}cout<<mp[u-n]<<'\\n';
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);memset(h,-1,sizeof h);cin>>n;S=0,T=N-1;for(int i=1;i<=n;i++)add(S,i,1,0);for(int i=1;i<=n;i++){string s;cin>>s;for(auto c:s){int j=c-'A'+n+1;add(i,j,1,0);}}for(int j=n+1;j<=n+3;j++){int x,y;cin>>x>>y;// int k=j+10;// add(j,k,x,y);// add(k,T,1e9)add(j,T,x,y);}int flow,cost;EK(flow,cost);if(flow!=n)cout<<"NO"<<'\\n'<<flow;else cout<<"YES"<<'\\n'<<cost;
}
P1023. 百度校招-2022.9.13-删除游戏
跳着拿就好
携程算法岗-2023.3.7-第三题:游游出游
#include<bits/stdc++.h>
using namespace std;
double v,x,y;
signed main(){cin>>v>>x>>y;double t=max(0.0,(sqrt(x*y)-v))/x;double ft=1e9;if(v<1)ft=y/v;ft=min(ft,t+y/(v+t*x));printf("%.5lf",ft);
}
导数做法不知道为什么错了
居然要用三分法
#include <bits/stdc++.h>
using namespace std;int v, x, y;
double res = 1e9;
double calc(double t1) {double t = y / (v+t1*x) + t1;res = min(res, t);return t;
}
int main()
{cin >> v >> x >> y;double L = 0, R = 1e9;for(int i = 0 ; i <= 5000 ; i ++){double lmid=L+(R-L)/3;double lres = calc(lmid);double rmid=R-(R-L)/3;double rres = calc(rmid);if (lres <= rres) {R = rmid;} else {L = lmid;}}printf("%.9lf\\n", res);
}
携程算法岗-2023.3.7-第四题:游游买商品
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2020+10;
int f[N][N],n,m;
int a[N],b[N];
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)cin>>b[i];int ans=0;for(int i=1;i<=n;i++){for(int j=m;j>=0;j--){f[i][j]=f[i-1][j];if(j>=a[i])f[i][j]=max(f[i][j],f[i-1][j-a[i]]+b[i]);int c=a[i-1]+a[i]/2;if(i>=2&&j>=c)f[i][j]=max(f[i][j],f[i-2][j-c]+b[i-1]+b[i]);ans=max(ans,f[i][j]);}}cout<<ans;
}
#P1017. 蚂蚁校招-2022.10.27-数位和为n的最大整数
#include<bits/stdc++.h>
using namespace std;
int n;
signed main(){cin>>n;if(n>45){cout<<-1;return 0;}int ans=-1;for(int i=1;i<(1<<9);i++){int sum=0;int t=0;for(int j=8;j>=0;j--){if(i>>j&1){sum+=j+1;t=t*10+j+1;}}if(sum==n){ans=max(ans,t);}}cout<<ans;
}
字节校招-2022.10.9-二叉树染色
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,c[N];
string s="RB";
vector<int>g[N];
void dfs(int u=1,int fa=0){int sz=0;for(auto j:g[u]){if(j==fa)continue;dfs(j,u);sz++;}c[u]=sz%2==0;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<n;i++){int a,b;cin>>a>>b;g[a].push_back(b);g[b].push_back(a);}dfs();for(int i=1;i<=n;i++)cout<<s[c[i]];
}
#P1084. 阿里春招-2023.3.15-第三题-k次操作最小化极差
这是目前做过的最难的一道题
用multiset维护一个集合，然后枚举l和r进行删数加数
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int n,k,a[N];
signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>k;if(n==1){cout<<0;return 0;}//l=0~k// aaaaaa xxxxx bbbbbint ans=2e9;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);if(k==0){cout<<a[n]-a[1];return 0;}multiset<int>S;for(int i=1;i<=n-k;i++)S.insert(a[i]);for(int i=n-k+1;i<=n;i++)S.insert(a[i]/2);auto L=S.begin();auto R=--S.end();ans=min(ans,*R-*L);for(int l=1,r=n-k+1;l<=k;l++,r++){auto prel=S.lower_bound(a[l]);S.erase(prel);S.insert(a[l]*2);auto prer=S.lower_bound(a[r]/2);S.erase(prer);S.insert(a[r]);auto L=S.begin();auto R=--S.end();ans=min(ans,*R-*L);}cout<<ans;
}
P1072. 百度校招-2023.3.7-第三题-魔法师
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int n,a[N];
int mp[2];
signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n;int A=0,B=0;mp[0]=1;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]>0)a[i]=0;else a[i]=1;a[i]^=a[i-1];A+=mp[a[i]];B+=mp[a[i]^1];mp[a[i]]++;}cout<<B<<" "<<A;
}
P1025. 华为校招-2022.11.9-攻城战
每门炮在时间限制上是独立的
f[i]表示准确使用i的体积的时候的最大贡献
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2020;
int n,m,T;
int f[1010];
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m>>T;memset(f,-0x3f,sizeof f);f[0]=0;//每门炮在时间的限制上是独立的for(int i=1;i<=n;i++){int a,b,c;cin>>a>>b>>c;for(int j=m;j>=0;j--){int mx=min(T/c,(m-j)/b);for(int k=1;k<=mx;k++){f[j+k*b]=max(f[j+k*b],f[j]+k*a);}}}int ans=0;for(int i=m;i>=0;i--)ans=max(ans,f[i]);cout<<ans;
}
P1053. 华东师范大学保研机试-2022-Minimum_Sum
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10,M=40*N;
int n,q,root[N];
int ls[M],rs[M],c[M],o,a[M];
void pushup(int u){c[u]=c[ls[u]]+c[rs[u]];a[u]=a[ls[u]]+a[rs[u]];
}
void ins(int &u,int p,int x,int l=1,int r=1e9){u=++o;a[u]=a[p],c[u]=c[p],ls[u]=ls[p],rs[u]=rs[p];if(l==r){c[u]++;a[u]+=x;return;}int mid=l+r>>1;if(x<=mid)ins(ls[u],ls[p],x,l,mid);else ins(rs[u],rs[p],x,mid+1,r);pushup(u);
}
int L=0,R=0;
int query(int u,int p,int k,int l=1,int r=1e9){if(l==r)return r;int mid=l+r>>1;int lc=c[ls[u]]-c[ls[p]];int Ls=a[ls[u]]-a[ls[p]];int Rs=a[rs[u]]-a[rs[p]];if(k<=lc){// R+=Rs;return query(ls[u],ls[p],k,l,mid);}else {// L+=Ls;return query(rs[u],rs[p],k-lc,mid+1,r);}
}int ql(int u,int p,int x,int l=1,int r=1e9){if(x>=r)return a[u]-a[p];if(l==r)return 0;int mid=l+r>>1;if(x<=mid)return ql(ls[u],ls[p],x,l,mid);return a[ls[u]]-a[ls[p]]+ql(rs[u],rs[p],x,mid+1,r);
}
int qr(int u,int p,int x,int l=1,int r=1e9){if(x<l)return a[u]-a[p];if(l==r)return 0;int mid=l+r>>1;if(x>mid)return qr(rs[u],rs[p],x,mid+1,r);return a[rs[u]]-a[rs[p]]+qr(ls[u],ls[p],x,l,mid);
}
int qk(int u,int p,int x,int l=1,int r=1e9){if(l==r)return c[u]-c[p];int mid=l+r>>1;int lc=c[ls[u]]-c[ls[p]];if(x<=mid)return qk(ls[u],ls[p],x,l,mid);return lc+qk(rs[u],rs[p],x,mid+1,r);
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=1,x;i<=n;i++){cin>>x;ins(root[i],root[i-1],x);}cin>>q;while(q--){int l,r;cin>>l>>r;int len=r-l+1;int k=(r-l+2)/2;//小于等于k的就是L=0,R=0;int x=query(root[r],root[l-1],k);//L是小于等于x的权值和L=ql(root[r],root[l-1],x);R=qr(root[r],root[l-1],x);int K=qk(root[r],root[l-1],x);// cout<<"k="<<k<<" x="<<x<<'\\n';// cout<<"K="<<K<<" L="<<L<<" R="<<R<<'\\n';int ans=K*x-L + R-(len-K)*x;cout<<ans<<'\\n';}
}
