牛客小白月赛101
考点为：A题 滑动窗口、B题 栈、C题 找规律、D 差分、E 筛约数。C题可能会卡住，不过手搓几组，或者模拟几组规律就显而易见了
A：
思路：
无论去头还是去尾，最后所留下的数据长度一定为：n - k ，那么问题就变成：对于数组a，长度为n - k的子序列中，sum最大的子序列。即滑动窗口，由于是求和，那么前缀和也可解。
代码：
前缀和：
#include<bits/stdc++.h>
using namespace std;
const int N = 5 * 1e3 + 10;
int n, k;
int a[N], sum[N];
int main()
{
cin >> n >> k;
for(int i = 1; i <= n; i ++ )
{
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
}
int s = n - k, ans = -1;
for(int i = s; i <= n; i ++ )
ans = max(ans, sum[i] - sum[i - s]);
cout << ans << endl;
}滑动窗口：
数组模拟：
#include<bits/stdc++.h>
using namespace std;
const int N = 5 * 1e3 + 10;
int n, k;
int a[N];
int main()
{
cin >> n >> k;
for(int i = 0; i < n; i ++ ) cin >> a[i];
int s = n - k, ans = -1;
int cnt = 0;
for(int i = 0; i < n; i ++ )
{
cnt += a[i];
if(i >= s - 1)
{
ans = max(cnt, ans);
cnt -= a[i - s + 1];
}
}
if(n == k) ans = 0;
cout << ans << endl;
}队列：
#include<bits/stdc++.h>
using namespace std;
const int N = 5 * 1e3 + 10;
int n, k;
deque<int> dq;//滑动窗口一律使用双端队列
int a[N];
int main()
{
cin >> n >> k;
for(int i = 1; i <= n; i ++ ) cin >> a[i];
int sum = 0, ans = -1;
for(int i = 1; i <= n; i ++ )
{
dq.push_back(a[i]);
if(dq.size() == n - k)
{
for(auto &t : dq) sum += t;
dq.pop_front();
ans = max(ans, sum);
sum = 0;
}
}
if(n == k) ans = 0;
cout << ans << endl;
}B
思路：
括号问题，即匹配左右括号。这里tb 和fc 当作左右括号，判断是否能匹配即可。我们用栈来维护，因为栈顶元素即是刚放进去的元素，即top()函数。
代码：
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
string S;
cin >> S;
stack<char> a;
for(auto &ch : S)
{
//能消除则消除
if(!a.empty())
{
if(a.top() == 'f' && ch == 'c') {a.pop();continue;}
if(a.top() == 't' && ch == 'b') {a.pop();continue;}
}
//否则的话，将当前元素放入进来
a.emplace(ch);
}
cout << a.size() << endl;
}
int main()
{
solve();
return 0;
}C
思路：
找规律，既然有传送阵如此强烈的性质，那么优先考虑规律而非bfs。
先来观察(1, 1)附近的点的gcd：（1，2），（2，1），（2，2）->1、1、2。无论n的大小如何，我们都不可能直接传送到(n，n)（原因很简单，gcd(n，n） = n，无法直接传送），而（n，n）附近的点一定为1或2，又因为不可以借助gcd = 1的点进行传送，所以借助距离最近的传送阵gcd = 2时为最优。所以分为如下几种情况。
①当n为偶数时，距离（n，n）最近的传送点即为：(n - 2，n）、（n，n - 2），所以消耗的步数为：从（1，1）走向（2，2）所消耗的两步 + 从（n - 2，n）或者（n，n - 2）走向（n，n）所消耗的两步，一共是4步
②当n为奇数时，距离（n，n）最近的传送点gcd全为1，但是n - 1为偶数，那么对于（n - 1，
n - 1）从（1，1）走到偶数点只需要四步，所以先从（2，2）传送至距离（n，n）最近的可传送的点（n - 1，n - 1），再走两步即可抵达（n，n）点，则一共需要6步
③当n过小时，模拟可发现当n <= 3时，直接走所需的步数最少。1' n == 1，所需0步。2' n == 2所需两步。3' n == 3所需4步
代码：
#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
cin >> n;
if(n < 4)
{
if(n == 1) cout << 0;
if(n == 2) cout << 2;
if(n == 3) cout << 4;
}
else if(n % 2 == 1) cout << 6;
else cout << 4;
return 0;
}D
思路：
问题转换：求出所有包含x位置的子区间。转化之后就变成很简单的差分问题，用一个差分数组ans[ ]来维护，最后输出ans[x]即可。
回归到本题，只需要判断包含该点的子区间的和是否为平方数即可，对于本题数据n <= 1000，ai <= 100000，那么总区间最大长度为1e8，对于1~1e8之间的平方数为10000个。所以我们只需要用O(n ^ 2)的时间复杂度内维护差分数组，再用O(1) 的时间复杂度输出即可，总时间复杂度为O(n ^ 2 + q)
代码：
#include<bits/stdc++.h>
using namespace std;
int n, q;
int ans[1050], a[1050], sum[1050];
set<int> st;
int main()
{
cin >> n >> q;
//求出1e8以内的所有平方数，并将其插入到set中
for(int i = 1; i <= 10000; i ++ ) st.insert(i * i);
for(int i = 1; i <= n; i ++ )
{
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
}
for(int i = 0; i < n; i ++ )
for(int j = i + 1; j <= n; j ++ )
if(st.find(sum[j] - sum[i]) != st.end())//如果该区间的和是平方数
{
//维护差分数组。由于数组的索引从0开始，所以+1.
ans[i + 1] ++ ;
ans[j + 1] -- ;
}
for(int i = 1; i <= n; i ++ ) ans[i] += ans[i - 1];
while(q -- )
{
int x;
cin >> x;
//即包含x的区间，且区间和为平方数的所有区间的个数
cout << ans[x] << endl;
}
return 0;
}E
思路：
感觉是这次月赛最简单的一道题。在数组最大值的范围之内，不属于数组的数（x）单独记录下来，那么数组内的数只要是x的倍数，那么都不是一个好数
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n;
int st[N], a[N];
int main()
{
cin >> n;
int mans = -1;
for(int i = 0; i < n; i ++ )
{
cin >> a[i];
st[a[i]] = 1;//出现了，则记为1
mans = max(mans, a[i]);//找出数组内的最大值
}
sort(a, a + n);
//特判
if(a[0] != 1)
{
cout << 0;
return 0;
}
//已经特判1，则可以从2开始
for(int i = 2; i <= mans; i ++ )
//找出不属于数组的数，对于所有是其倍数的数全都不符合题意
if(!st[i])
for(int j = i; j <= mans; j += i)
st[j] = 0;
int ans = 0;
//遍历一遍即可
for(int i = 1; i <= mans; i ++ )
if(st[i])
ans ++ ;
cout << ans << endl;
return 0;
}