9.5腾讯笔试（470/500）

最后一题的剩下百分30实在不会感觉要凉

第一题给你n个链表一个一个从头取拼成一个链表链表元素总个数<=100000

模拟

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param a ListNode类vector 指向这些数链的开头
     * @return ListNode类
     */
    
    ListNode* solve(vector<ListNode*>& a) {
        // write code here
        int end_cnt = 0;
        int n = a.size();
        ListNode* res=new ListNode(0);
        ListNode *temp=res;
        int empty_flag = 1;
        vector<int> flag(n,0);
        while (end_cnt<n){
            for (int i=0;i<n;i++){
                cout<<"i="<<i<<endl;
                if (flag[i]) continue;
                if (a[i]==nullptr){
                    end_cnt++;
                    flag[i]=1;
                    continue;
                }
                if (empty_flag){
                    res->val=a[i]->val;
                    empty_flag = 0;
                    a[i]=a[i]->next;
                    if (a[i]==nullptr){
                        end_cnt++;
                        flag[i]=1;
                    }
                }
                else{
                    ListNode * temp= new ListNode(a[i]->val);
                    res->next=temp;
                    res=res->next;
                    a[i]=a[i]->next;
                    if (a[i]==nullptr){
                        end_cnt++;
                        flag[i]=1;
                    }
                }
                
            }
        }
        if (empty_flag==1) return nullptr;
        return temp;
    }
};

第二题你跟对方都有n个数每次双方拿出一个数因子多的那方+1分对方出数的顺序固定问你最多能拿多少分 n<=100000，a[i],b[i]<=100000

贪心，每次对方出一个数我们出因子数比他大的最小的结果

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
#define fir first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define ull unsigned long long
#define cl(a, b) memset(a, b, sizeof(a))
#define quickio(a) ios::sync_with_stdio(a)
#define datatest() freopen("data.in", "r", stdin)
#define makeans() freopen("data.out", "w", stdout)
#define makedata() freopen("data.in", "w", stdout)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
using namespace std;
const int maxn = 1e5 + 10;
const int maxm = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxblock = sqrt(maxn) + 10;
const double eps = 1e-7;
const ll INF = 1e16;
int num[maxn];
void init() {
  for (int i = 1; i < maxn; i++) {
    num[i]++;
    for (int j = 2 * i; j < maxn; j += i) num[j]++;
  }
}
int n;
int a[maxn], b[maxn];
multiset<int> ms;
int main() {
  init();
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d", &b[i]);
  }
  for (int i = 1; i <= n; i++) {
    a[i] = num[a[i]];
    b[i] = num[b[i]];
  }
  ms.clear();
  for (int i = 1; i <= n; i++) ms.insert(a[i]);
  int res = 0;
  for (int i = 1; i <= n; i++) {
    auto it = ms.upper_bound(b[i]);
    if (it == ms.end()) {
      continue;
    }
    ms.erase(it);
    res++;
  }
  printf("%d\n", res);
  return 0;
}

第三题给定一个01串定义一个01串的权值为 $\sum_{}^{}{len*(len+1)/2}$ ，其中len是这个串的连续0/1段问子序列构成的01串最大权值字符串长度<=5000

dp 定义dp(i,j,k)表示用[1,i]的字符组成最后连续段长度为j且最后一个字母为k的最大权值根据这个位置用/不用转移即可

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
#define fir first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define ull unsigned long long
#define cl(a, b) memset(a, b, sizeof(a))
#define quickio(a) ios::sync_with_stdio(a)
#define datatest() freopen("data.in", "r", stdin)
#define makeans() freopen("data.out", "w", stdout)
#define makedata() freopen("data.in", "w", stdout)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
using namespace std;
const int maxn = 5000 + 10;
const int maxm = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxblock = sqrt(maxn) + 10;
const double eps = 1e-7;
const ll INF = 1e16;
int n;
char str[maxn];
//[1,i],last len is j, last char is k
int dp[maxn][maxn][2];
int main() {
  scanf("%d", &n);
  scanf("%s", str + 1);
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= n; j++) {
      for (int k = 0; k < 2; k++) dp[i][j][k] = -1;
    }
  }
  dp[0][0][0] = 0;
  dp[0][0][1] = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= i; j++) {
      for (int k = 0; k < 2; k++) {
        if (dp[i - 1][j][k] == -1) continue;
        // not choose
        dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k]);
        int bit = str[i] - '0';
        if (bit == k) {
          dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i - 1][j][k] + j + 1);
        } else {
          dp[i][1][bit] = max(dp[i][1][bit], dp[i - 1][j][k] + 1);
        }
      }
    }
  }
  int Max = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      for (int k = 0; k < 2; k++) {
        Max = max(Max, dp[i][j][k]);
      }
    }
  }
  printf("%d\n", Max);
  return 0;
}

第四题定义数组的一次分裂操作为：对于数组内大于1的数都用 n/2 n%2 n/2替换初始数组只有n 问最终数组中区间[l,r]有多少个1 n<=2^50

分治每次折半区间即可

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
#define fir first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define ull unsigned long long
#define cl(a, b) memset(a, b, sizeof(a))
#define quickio(a) ios::sync_with_stdio(a)
#define datatest() freopen("data.in", "r", stdin)
#define makeans() freopen("data.out", "w", stdout)
#define makedata() freopen("data.in", "w", stdout)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
using namespace std;
const int maxn = 1e6 + 10;
const int maxm = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxblock = sqrt(maxn) + 10;
const double eps = 1e-7;
const ll INF = 1e16;
ll n, l, r;
int solve(ll n, ll l, ll r) {
  ll Max = 0;
  for (int i = 0; i < 50; i++) {
    if (n & (1LL << i)) {
      Max = max(Max, 1LL << i);
    }
  }
  long long len = Max * 2 - 1;
  long long L = 1, R = len;
  if (L == l && R == r) return n;
  long long mid = (L + R) >> 1;
  int res = 0;
  if (r <= mid - 1) {
    if (l == 1 && r == mid - 1) {
      return n / 2;
    } else {
      return solve(n / 2, l, r);
    }
  } else if (r == mid) {
    if (n & 1) res++;
    if (l == r) return res;
    if (l == 1 && r - 1 == mid - 1) {
      return n / 2 + res;
    }
    return res + solve(n / 2, l, r - 1);
  } else {
    if (l >= mid + 1) {
      return solve(n / 2, l - mid, r - mid);
    } else if (l == mid) {
      if (n & 1) res++;
      return res + solve(n / 2, 1, r - mid);
    } else {
      if (n & 1) res++;
      return solve(n / 2, l, mid - 1) + res + solve(n / 2, 1, r - mid);
    }
  }
}
int main() {
  scanf("%lld %lld %lld", &n, &l, &r);
  printf("%d\n", solve(n, l, r));
  return 0;
}

第五题给定一个长度为n的数组a，求有多少个子数组满足子数组端点的值是这个子数组的最小跟次小值 n<=100000

只过了n<=3000的数据预处理出每个区间的最小值对于[l,r]，判断a[l],a[r]是不是比Min[l+1][r-1]小即可

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
#define fir first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define ull unsigned long long
#define cl(a, b) memset(a, b, sizeof(a))
#define quickio(a) ios::sync_with_stdio(a)
#define datatest() freopen("data.in", "r", stdin)
#define makeans() freopen("data.out", "w", stdout)
#define makedata() freopen("data.in", "w", stdout)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
using namespace std;
const int maxn = 3000 + 10;
const int maxm = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxblock = sqrt(maxn) + 10;
const double eps = 1e-7;
const ll INF = 1e16;
int n;
int a[maxn];
int Min[maxn][maxn];

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) Min[i][j] = 1e9 + 8;
  }
  for (int i = 1; i <= n; i++) Min[i][i] = a[i];
  for (int len = 2; len <= n; len++) {
    for (int l = 1; l + len - 1 <= n; l++) {
      int r = l + len - 1;
      Min[l][r] = min(Min[l][r - 1], a[r]);
    }
  }
  int res = 0;
  for (int len = 3; len <= n; len++) {
    for (int l = 1; l + len - 1 <= n; l++) {
      int r = l + len - 1;
      if (Min[l + 1][r - 1] >= a[l] && Min[l + 1][r - 1] >= a[r]) {
        // cout << l << " " << r << endl;
        res++;
      }
    }
  }
  printf("%d\n", res + max(n - 1, 0));
  return 0;
}

#腾讯##笔经#