腾讯9.5第二批后端笔试牛客大佬全AC记录
来自小海胆胆
腾讯2022届第二次笔试
牛牛的数链们
难度：2星
知识点：链表，模拟
模拟一下即可
classSolution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param a ListNode类vector 指向这些数链的开头
* <a href="/profile/547241" data-card-uid="547241" class="" target="_blank" from-niu="default" data-card-index="3">@return ListNode类
*/
ListNode* solve(vector<ListNode*>& a) {
ListNode * head = newListNode(0);
ListNode * cur = head;
size_t non_empty_count = 0;
for(ListNode * x : a)
if(x != nullptr)
non_empty_count += 1;
while(non_empty_count > 0) {
for(ListNode * &x : a) {
if(x != nullptr) {
cur->next = x;
x = x->next;
cur = cur->next;
cur->next = nullptr;
if(x == nullptr)
non_empty_count -= 1;
}
}
}
cur = head->next;
delete head;
return cur;
}
};相似题目：
https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?from=2021qqexam
新精灵游戏
难度：2.5~3星
知识点：贪心，数论
田忌赛马的变种，首先需要知道[1,100000]中所有数的因子数量，可以用 O(nlogn) 或者 O(nlognn)或者O(n\sqrt(n))遍历每个数到sqrt(n)来求。
之后对于每个精灵，采用田忌赛马的贪心策略，在保证能赢的情况下， A 用因子数最少的精灵和 B 因子数更多的精灵进行对战，这样就能保证胜局数最大化。这个题目的数据，还能用vector删除的方法过
#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>
using namespace std;
int dp[100100];
int main(){
for(inti=1;i<=1e5;i++){
for(intj=i;j<=1e5;j+=i)dp[j]++;
}
intn,x;
while(cin >> n){
vector<int> tian(n),king(n);
for(inti = 0; i < n ; ++ i ) cin>>x,tian[i]=dp[x];
for(inti = 0; i < n ; ++ i ) cin>>x,king[i]=dp[x];
sort(tian.begin(),tian.end());
sort(king.begin(),king.end());
intleftTian = 0,leftKing = 0, rightTian = tian.size()-1, rightKing = king.size()-1, sum = 0;
while(leftTian <= rightTian){
if(tian[rightTian] > king[rightKing]){
rightTian--;rightKing--;
sum += 1;
}elseif(tian[leftTian] > king[leftKing]){
leftTian++;leftKing++;
sum += 1;
}else{
if(tian[leftTian] < king[rightKing]) sum-=0;
leftTian++;rightKing--;
}
}
cout<<sum<<endl;
}
}相似题目：
https://ac.nowcoder.com/acm/contest/940/H?from=2021qqexam
https://ac.nowcoder.com/acm/contest/919/A?from=2021qqexam
01串的价值
难度：3~4星
知识点：动态规划 ,找规律
#include <bits/stdc++.h>
using namespace std;
int main()
{
intn;
cin >> n;
string s;
cin >> s;
vector<vector<int>> cur(2, vector<int>(n + 1, -0x3f3f3f3f));
cur[0][0] = 0;
cur[1][0] = 0;
for(auto ch : s)
{
intx = ch - '0';
for(inti = n; i >= 1; i--)
cur[x][i] = max(cur[x][i], cur[x][i - 1] + i);
cur[1- x][0] = max(cur[1- x][0], *max_element(cur[x].begin(), cur[x].end()));
}
cout << max(*max_element(cur[0].begin(), cur[0].end()), *max_element(cur[1].begin(), cur[1].end()));
}数字划分
难度：4星
知识点：dfs，二分，分治
我们可以发现，对于一个数 x ，它可以被划分成 [x/2][x%2][x/2]三部分。这样对于 l 和 r 与len(x)/2的关系，我们就可以分类讨论了，根据不同的情况进行递归求解。
#include<bits/stdc++.h>
using namespace std;
#define ll longlong
typedef pair<int,int> P;
typedef pair<P,int> PP;
constintmaxn = 1e5+10;
constintmod = 1e9+7;
constll INF = 3e18;
ll n,l,r;
map<ll,ll> mp;
ll num(ll x)
{
if(x<=1) return 1;
if(mp.find(x)!=mp.end()) return mp[x];
return mp[x]=num(x/2)*2+1;
}
ll dfs(ll tl,ll tr,ll x)
{
if(x<=1) returnx;
ll mid = tl+num(x/2);
ll ans=0;
if(l<=mid&&mid<=r) ans+=x%2;
if(tl<=r&&l<=mid-1) ans+=dfs(tl,mid-1,x/2);
if(mid+1<=r&&l<=tr) ans+=dfs(mid+1,tr,x/2);
return ans;
}
int main()
{
ll up=1;
for(inti=1;i<=50;i++) up*=2;
scanf("%lld%lld%lld",&n,&l,&r);
assert(1<=n&&n<=up);
assert(0<=r-l&&r-l<=50000);
assert(r<=num(n));
printf("%lld\n",dfs(1,num(n),n));
return 0;
}当然差分一下更简单
#include<bits/stdc++.h>
using namespace std;
long long gao(long long x, long long base, long long i) {
if(base == 0) return0;
return i<=base/2-1?gao(x/2,base/2, i): x/2+x%2+gao(x/2,base/2, i-base/2);
}
int main() {
long long n, l, r; cin >> n >> l >> r;
long long base = 1ll<<int(log2l(n)+1);
cout << gao(n, base, r) - gao(n,base, l-1) << endl;
}有效序列的数量
难度：4.5星
知识点：数组，双指针，枚举，单调栈，线段树
这个题目出的非常好，一步一步进阶。首先想到的是3重循环暴力解法:
#include <iostream>
using namespace std;
int a[3001];
int main()
{
intn;
cin >> n;
for(inti = 0; i < n; i++)
{
cin >> a[i];
}
intans = 0;
for(inti = 0; i < n; i++)
{
for(intj = i + 1; j < n; j++)
{
if(j - i == 1)
{
ans++;
continue;
}
intflag = false;
for(intk = i + 1; k <= j - 1; k++)
{
if(a[k] < a[i] || a[k] < a[j])
{
flag = true;
break;
}
}
if(!flag)
{
ans++;
}
}
}
std::cout << ans;
return 0;
}然后就是进阶的双指针了，O(n^2)
当我们保持左端点 i 不动时，当右端点向右移动时，合法的右端点满足以下两个特性：
它更新了从 i+1 向右的最小值。
它左边没有小于 a[i] 的值。
所以我们可以将右端点 j向右移动，每次更新最小值时计数。然后当 a[j]<a[i] 时跳出。
这样的算法复杂度是 O(n^2)的，可以通过70%的用例。
#include <iostream>
using namespace std;
int a[100001];
int main()
{
intn;
cin >> n;
for(inti = 0; i < n; i++)
{
cin >> a[i];
}
intans = 0;
for(inti = 0; i < n; i++)
{
intmin_1_value = a[i];
intmin_2_value = 1e9 + 2;
for(intj = i + 1; j < n; j++)
{
if(j - i == 1)
{
min_2_value = a[j];
ans++;
continue;
}
if(a[j] <= min_2_value && min_2_value >= min_1_value)
{
min_2_value = a[j];
ans++;
}
}
}
std::cout << ans;
}不过我们还可以用线段树（复杂度 O(nlogn)）或者单调栈 （复杂度 O(n)）进一步加速，通过本题。
#include<bits/stdc++.h>
#define ll longlong
#define fors(i,a,b) for(inti = a; i < b; ++i)
#define pb push_back
#define all(a) a.begin(),a.end()
using namespace std;
constintmaxn = 1e5+5;
int a[maxn], n, pre[maxn];
int sol(){
intans = 0;
fors(i,1,n+1){
intp = i-1;
while(p&&a[p]>=a[i]) p=pre[p]; if(p) ans++; pre[i] = p;
}returnans;
}
intsame[maxn];
int main(){
scanf("%d", &n);
fors(i,1,n+1) scanf("%d", &a[i]);
ll ans = 0;
ans += sol();
reverse(a+1,a+1+n);
ans += sol();
fors(i,1,n+1){
intp = i-1;
while(p && a[p]>a[i]) p = pre[p];
if(p){
if(a[i] == a[p]) {
ans += same[p]; same[i] = same[p]+1;
}elsesame[i] = 1;
pre[i] = p;
}else{
pre[i] = 0; same[i] = 1;
}
}
cout<<ans<<endl;
return 0;
}这个题目的水平相当之高，数据设计的特别好
相似题目：
https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788?from=2021qqexam
以下是截图记录
