腾讯笔试0901，代码实现+思路（c++)
第一题，水题
#include<iostream>
#include<algorithm>
#include<cstdio>
int n,m;
int cnt11,cnt12,cnt21,cnt22;
int num1[111111],num2[111111];
using namespace std;
int main()
{
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%d",&num1[i]);
if(num1[i]&1)
cnt11++;
else
cnt12++;
}
for(int i=0;i<m;i++)
{
scanf("%d",&num2[i]);
if(num2[i]&1)
cnt21++;
else
cnt22++;
}
int ans=min(cnt11,cnt22)+min(cnt12,cnt21);
printf("%d\n",ans);
}
第二题，简单的贪心策略
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n;
struct person
{
int a,b;
}num[111111];
bool cmp(person a,person b)
{
return a.b+b.a<a.a+b.b;
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d %d",&num[i].a,&num[i].b);
}
sort(num,num+n,cmp);
long long ans=0;
for(int i=0;i<n;i++)
{
ans+=(long long)i*num[i].a;
ans+=(long long)num[i].b*(n-1-i);
}
cout<<ans<<endl;
}
第三题，没有做出来，gg
第四题，一个简单的单调栈模板题
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stack>
using namespace std;
int n;
int w[111111];
int res[111111];
struct range
{
int l,r;
}temp[111111];
stack<int> sk;
long long sum[111111];
long long ans;
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&w[i]);
if(i==0)
sum[i]=w[i];
else
sum[i]=sum[i-1]+w[i];
temp[i].l=temp[i].r=i;
while(!sk.empty()&&w[sk.top()]>w[i])
{
temp[sk.top()].r=i-1;
temp[i].l=temp[sk.top()].l;
sk.pop();
}
sk.push(i);
}
int temp1;
if(!sk.empty())
temp1=sk.top();
while(!sk.empty())
{
temp[sk.top()].r=temp1;
sk.pop();
}
ans=0;
for(int i=0;i<n;i++)
{
ans=max(ans,(long long)w[i]*(sum[temp[i].r]-sum[temp[i].l-1]));
}
cout<<ans<<endl;
return 0;
}
第五题，简单的动态规划
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stack>
using namespace std;
int t,k;
int l,r;
int mod=1000000007;
long long dp[111111][2];
long long sum[111111];
int main()
{
scanf("%d %d",&t,&k);
dp[0][0]=1;
for(int i=0;i<k;i++)
{
dp[i+1][0]=dp[i][0];
dp[i+1][0]%=mod;
dp[i+k][1]+=dp[i][0];
dp[i+k][1]%=mod;
}
for(int i=k;i<=100000;i++)
{
dp[i+1][0]+=dp[i][0];
dp[i+k][1]+=dp[i][0];
dp[i+1][0]+=dp[i][1];
dp[i+k][1]+=dp[i][1];
dp[i+1][0]%=mod;
dp[i+k][1]%=mod;
}
sum[0]=0;
for(int i=1;i<=100000;i++)
{
sum[i]=sum[i-1]+dp[i][0]+dp[i][1];
sum[i]%=mod;
}
while(t--)
{
scanf("%d %d",&l,&r);
long long ans=sum[r]-sum[l-1];
if(ans<0)
ans+=mod;
printf("%lld\n",ans);
}
return 0;
}
先这样，晚些更新详细思路
投递百度等公司10个岗位