26美团笔试题第一、二批前两道题

鼠鼠有幸收到了第四批笔试，明天搞，今天做了下牛客上能找到的一二批，第一二题还可以，第三题一涉及到复杂点树图鼠鼠就不会了。。。

第一题都是思维题，千万不能暴力硬搞，想一下其中数字规律关系很快就能出来。

11.小美的因子数量

小美很喜欢因子数量为奇数的数。现在小芳给了小美一个区间[l,r][l,r]，请你帮小美算出区间内有多少个因子数量为奇数的数。

【名词解释】因子：对于正整数xx，如果存在正整数pp 使得xx 能被pp 整除，则称pp 是xx 的因子。例如，1212 的因子有1,2,3,4,6,121,2,3,4,6,12。

解释：数字的因数都是一对一的比如6的因子是1，6 |2，3|偶数只有完全平方数才是奇数个，所以只要看完全平方数个数就行，怎么看一个区间，先弄出来[1,r]-[1,l-1]的就行，sqrt处理一下就好，记得开long long

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie();
    long long l, r;
    if (cin >> l >> r) {
        long long cnt = sqrt(r);
        long long ans= sqrt(l - 1);
        cout << cnt-an<< "\n";
    }
    return 0;
}

11.无限循环

小美有一个长度为 nn 的数组 {a1,a2,…,an}{a1,a2,…,an}，她为了研究这个数组做出了个大胆的决定。现在，将与初始数组完全相同的数组连续拼接到其末尾，共拼接 109109 次。设拼接完成后的新数组记为 a′a′，则新数组的长度为 n×(109+1)n×(109+1)，并且对于任意的 n<i≦n×(109+1)n<i≦n×(109+1)，都有 ai′=ai−n′ai′=ai−n′。

请你计算新数组 a′a′ 的最长严格递增子序列的长度，并输出这个长度。

【名词解释】

子序列：从原序列中删除任意个（可以为零、可以为全部）元素后按原相对顺序得到的新序列。

严格递增子序列：子序列中相邻元素的值严格递增，即若子序列为 {b1,b2,…,bk}{b1,b2,…,bk}，则对所有 1≦i<k1≦i<k，都有 bi<bi+1bi<bi+1。

解释：10^9这么多重复串，看最长严格递增子序列，只要看这个子序列里的不重复元素个数就行。因为每次都能从每段拿一个元素出来。11322 取1 2 3 最长就是3

#include <iostream>
#include <vector>
#include <algorithm>
#include<set>
using namespace std;
void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    set<int>b;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];b.insert(a[i]);
    }
  cout<<b.size()<<'\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie();
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}

第二题涉及一些基础算法，但是很难想到，得仔细思考其中关系，贪心构造前缀和差分dp二分

12.超级斐波那契数列

定义超级斐波那契数列如下：给定整数 kk，该序列的前 kk 项均为 11；对于 n>kn>k，第 nn 项为前 kk 项之和，即现给定整数 kk 和查询次数 qq，每次查询一个正整数 xx，请输出该序列的第 xx 项对 109+7109+7 取模后的值。

解释：做一个前缀和运算最后再查询记得mod运算

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MOD = 1e9 + 7;
int main() {
    ios::sync_with_stdio(false);
    cin.tie();
    int k, q;
    if (!(cin >> k >> q)) return 0;
    vector<int> queries(q);
    int max_x = 0;
    for (int i = 0; i < q; ++i) {
        cin >> queries[i];
        if (queries[i] > max_x) {
            max_x = queries[i];
        }
    }
    vector<long long> S(max_x + 1, 0);
    long long current_sum = 0;
    for (int i = 1; i <= max_x; ++i) {
        if (i <= k) {
            S[i] = 1;
            current_sum = (current_sum + 1) % MOD;
        } else {
            S[i] = current_sum;
            current_sum = (current_sum + S[i] - S[i - k] + MOD) % MOD;
        }
    }
    for (int i = 0; i < q; ++i) {
        cout << S[queries[i]] << "\n";
    }
    return 0;
}

12.交换括号

我们称一个括号序列为“平衡的括号序列”，当且仅当满足以下归纳定义：

1) 空串是平衡的；

2) 若字符串 AA 是平衡的，则“(A)(A)”是平衡的；

3) 若字符串 AA 与 BB 均是平衡的，则“ABAB”是平衡的（表示连接）。

例如：括号序列 ()()()() 与 (())(()) 是平衡的；而 ))、)()(、 (( 不是。

给定一个偶数长度的括号序列 s（仅包含 '(' 与 ')'）。你可以进行若干次如下操作：

选择一个位置 i（1≤i<n）i（1≤i<n），交换相邻的两个字符 sisi 与 si+1si+1。

请你计算，最少需要进行多少次这样的相邻交换，才能使整个序列变为一个平衡的括号序列。

解释：贪心思想我们可以从左到右遍历这个括号序列，并维护一个变量 b，表示当前“左括号的数量减去右括号的数量”：

遇到 ( 时，b++，遇到 ) 时，b--

在任何一个合法的平衡括号序列中，b 在任何时刻都不能小于 0。如果在某个时刻 b < 0，说明我们遇到了一个“多余”的右括号 )，此时序列是不合法的。为了以最少的相邻交换次数修复这个问题，我们必须从右边最近的地方拿一个左括号 ( 移到当前位置。

为什么是最少交换次数？当 b< 0 时，意味着当前有 -b 个右括号处于“未匹配”状态等待左括号。当我们继续向右遍历，遇到第一个左括号 ( 时，这个左括号前面其实全部都是未匹配的右括号（因为如果中间有匹配好的括号对，它们内部的 b 为 0，不影响整体结构）。所以，这个左括号想要填补最早的那个空缺，它必须要越过的右括号数量，恰好就是当前的 -b！越过一个字符就需要 1 次交换，因此它贡献的交换次数就是 -b。

#include <iostream>
#include <string>
#include <vector>
using namespace std;
void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    long long p = 0;   
    long long b = 0; 
    for (char c : s) {
        if (c == '(') {
            if (b < 0) {
                p += -b;
            }
            b++; 
        } else {
            b--;
        }
    }
    cout << p << "\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie();
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}

#26届求职交流#

蜀黍面试记录文章被收录于专栏

记录面试的问题