牛客小白月赛101（栈、差分、调和级数、滑动窗口）

牛客小白月赛101（栈、差分、调和级数、滑动窗口）

---

A. tb的区间问题

维护连续 （n-k）个元素的sum，取max即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int maxn = 1e5 + 5;ll a[maxn];int main(){int n, k;cin >> n >> k;	for(int i = 1; i <= n; i++) cin >> a[i];ll sum = 0;for(int i = 1; i <= n-k; i++) sum += a[i];ll res = sum;for(int i = 1; i <= k; i++){sum -= a[i];sum += a[n-(k-i)];res = max(res, sum);}cout << res << endl;return 0;
}

B. tb的字符串问题（栈）

考虑需要不断弹出已经遍历部分子串的尾部，使用栈维护即可。

#include<bits/stdc++.h>
using namespace std;int main(){int n;cin >> n;string s;cin >> s;stack<char> st;for(auto c : s){if(c == 'c'){if(!st.empty() && st.top() == 'f') st.pop();else st.push(c);}else if(c == 'b'){if(!st.empty() && st.top() == 't') st.pop();else st.push(c);}else st.push(c);}cout << st.size() << endl;return 0;
}

C. tb的路径问题（思维）

打表：

1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
1  2  1  2  1  2  1  2  1  2  1  2  1  2  1
1  1  3  1  1  3  1  1  3  1  1  3  1  1  3
1  2  1  4  1  2  1  4  1  2  1  4  1  2  1
1  1  1  1  5  1  1  1  1  5  1  1  1  1  5
1  2  3  2  1  6  1  2  3  2  1  6  1  2  3
1  1  1  1  1  1  7  1  1  1  1  1  1  7  1
1  2  1  4  1  2  1  8  1  2  1  4  1  2  1
1  1  3  1  1  3  1  1  9  1  1  3  1  1  3
1  2  1  2  5  2  1  2  1  10 1  2  1  2  5
1  1  1  1  1  1  1  1  1  1  11 1  1  1  1
1  2  3  4  1  6  1  4  3  2  1  12 1  2  3
1  1  1  1  1  1  1  1  1  1  1  1  13 1  1
1  2  1  2  1  2  7  2  1  2  1  2  1  14 1
1  1  3  1  5  3  1  1  3  5  1  3  1  1  15

可以发现，当 n 比较大时一定存在如下路径，

• n % 2 = 0时：起点 -> 1 —> 2 —> 2(传送) —> 1 - > n
• n % 2 = 1时：起点 -> 1 —> 2 —> 2(传送，上一个偶数行的2) —> 1 or 3 —> 1 —> 1 —> n

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int maxn = 1e5 + 5;int gcd(int x, int y){if(y) return gcd(y, x%y);return x;
}void func(){ // 打表用int n = 15;for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){printf("%-3d", gcd(i, j));}printf("\n");}
}int main(){int n;cin >> n;if(n == 1) cout << 0 << endl;else if(n == 2) cout << 2 << endl;else if(n == 3) cout << 4 << endl;else if(n % 2 == 0) cout << 4 << endl;else cout << 6 << endl;return 0;
}

D. tb的平方问题（差分）

n 比较小，枚举每个区间（l，r），如果区间元素sum为完全平方数，则 l 到 r 之间每个位置多一个完全平方数，用差分维护即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int maxn = 1e5 + 5;ll a[maxn], v[maxn];map<int, int> POS;int main(){for(int i = 1; i <= 1e4; i++) POS[i*i] = i;int n, q;cin >> n >> q;for(int i = 1; i <= n; i++) cin >> a[i];for(int i = 1; i <= n; i++){int sum = 0;for(int j = i; j <= n; j++){sum += a[j];if(POS[sum] != 0){v[i]++;v[j+1]--;}}}for(int i = 1; i <= n; i++) v[i] += v[i-1];while(q--){int x;cin >> x;cout << v[x] << endl;}return 0;
}

E. tb的数数问题（调和级数）

根据题意，好的数字不会超过 $max(a_i),i\in (1,n)$。

直接枚举每个数的约数的个数，再判断与数组a能提供的约数的个数是否一致即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int maxn = 2e6 + 5;int a[maxn], v[maxn], f[maxn];int main(){int n;scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);sort(a+1, a+1+n);for(int i = 1; i <= n; i++){ 	// 判断 a 中元素能提供的约数个数if(a[i] != a[i-1]){int num = a[i];while(num <= 1e6){v[num]++;num += a[i];}}}int res = 0;for(int i = 1; i <= 1e6; i++){	// 判断 i 需要的约数个数，调和级数，时间复杂度O(n*log(n))int num = i;while(num <= 1e6){v[num]--;num += i;}if(v[i] == 0) res++;	// 为零则一致}printf("%d", res);return 0;
}

F. tb的排列问题（滑动窗口）

从左到右枚举 $i，i\in [1,n]$，维护 $[i,i+w+1]$ 这个区间中，-1的个数和已知位置的元素。

对于每一次枚举，称 $[i,i+w+1]$ 为当前窗口。
令当前方案数用res表示，有以下几种情况：

• b[i] 位置未知：

  • 当前窗口有-1：则可以用当前窗口中任意一个-1变换为 b[i]，让 a[i] 与之交换。res = res * 当前-1的个数。

    注意，如果此时的 a[i] != -1 的话，交换后，可以理解为 a[i] 被放到了下一个窗口中。
    

  • 当前窗口没有-1 ：res = 0。

• b[i] 位置已知:

  • b[i] 在当前窗口中，直接交换，res不变
  • b[i] 不在当前窗口中，不能交换得到，且不能使用-1，res = 0

#include<bits/stdc++.h>
#define ll long long
using namespace std;const ll mod = 998244353;
const int maxn = 2e6 + 5;int a[maxn], b[maxn];
int v[maxn], pos[maxn];int main(){int ncase;cin >> ncase;while(ncase--){int n, w;cin >> n >> w;for(int i = 1; i <= n; i++) cin >> a[i];for(int i = 1; i <= n; i++) cin >> b[i];for(int i = 1; i <= n; i++) if(a[i] != -1) pos[a[i]] = i; 	// 所有已知的数的位置 int count = 0;for(int i = 1; i <= w; i++){ 	// 先维护 1 到 w if(a[i] == -1) count++;else v[a[i]] = 1;}ll res = 1;for(int i = 1; i <= n; i++){if(i+w <= n){if(a[i+w] == -1) count++; else v[a[i+w]] = 1;} if(pos[b[i]]){	// b[i]位置已知 if(v[b[i]] == 0) res = 0;	// b[i] 不在【i，i+w+1】之间，不能交换得来else v[b[i]] = 0; 			// b[i] 在【i，i+w+1】之间，交换到该位置 }else{			// b[i]位置未知 if(count){  // 还有-1，则可以用当前位置的数，与任意的一个-1交换，方案数 * count res = res * count % mod;count--;}else{	// -1不够用，res = 0 res = 0;} }}cout << res << endl;for(int i = 1; i <= n; i++) if(a[i] != -1) v[a[i]] = pos[a[i]] = 0;}return 0;
}