牛客小白月赛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;
}