牛客小白月赛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的数数问题（调和级数）
根据题意，好的数字不会超过 m a x ( a i ) , i ∈ ( 1 , n ) max(a_i), i\in(1,n) max(ai),i∈(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 ∈ [ 1 , n ] i，i \in [1,n] i，i∈[1,n]，维护 [ i , i + w + 1 ] [i, i+w+1] [i,i+w+1] 这个区间中，-1的个数和已知位置的元素。
对于每一次枚举，称
[
i
,
i
+
w
+
1
]
[i, i+w+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;
}
原文地址：https://blog.csdn.net/mldl_/article/details/142406989
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！