复盘美团笔试

第一题：给一个区间[l, r]，计算区间中整数的因子数是奇数的个数并输出，比如12的因子数有：1，2，3，4，6，12，因此12不符合条件。

这题只要意识到因子数都是成对出现的即可，只有当有2个因子数相等时才会出现奇数情况，比如：1=1*1， 4=2*2， 9=3*3，81=9*9

我是对左右区间开平方取整，然后相减即可，注意想清楚并处理闭区间的特殊情况

第二题：给定一个超级斐波拉契数列，前k个值为1，第n项是前n-1到n-k之和，输入k和q，q代表查询次数，接下来有q次输入，每次输入x，x代表查询第x项，输出答案，答案可能很大，因此要求输出对（10^9+7）取模

这题考的时候想复杂了，半天没写出来，后来理清楚思路之后感觉也还好，但感觉还是挺多坑的，滑动窗口应该是最优时间复杂度吧。

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
// 参数：滑动数组、窗口大小、淘汰指针、结果、目标项序号、当前序号
int search(vector<long long>& path, int& k, int& re, long long& result, int& x, int& index)
{
// [re]需要用之前的result更新，而result又需要用[re]更新，因此必须用一个临时变量操作
int reval = path[re];         //临时变量保留滑出的值，用于更新result
path[re] = result;            //更新滑动窗口
++re;                         //更新滑动指针，并检测环
if(re==k)
re = 0;
++index;                              //更新index
result = (result*2 - reval) % MOD;    //更新第index项的值
if (result < 0) result += MOD;        // 保证非负
if(index==x)
return result;
return search(path, k, re, result, x, index);
}

int main()
{
int k;
int q;
cin >> k >> q;
while(q--)
{
int x;
cin >> x;
vector<long long> path(k, 1);
int re = 0;
long long result = k;
index = k+1;
if(x<=k)
cout << 1;
else if(x==k+1)
cout << k;
else
cout << search(path, k, re, result, x, index); //从第k+1项开始才滑动
if(q!=0)
cout << endl;
}
return 0;
}