bnds 8.28

csp 模拟赛。

A.

暴力枚举就行。

B.

中序遍历，然后就变为了给定一个序列 \(p\)，求最少修改几次能让 \(p\) 变的单调递增，并且满足 \(p_i - p_j \ge i - j (i > j)\)，变换一下就是 \(p_i - i \ge p_j - j\)，所以中序遍历完了之后 \(p_i\) 减去 \(i\)，后答案即为 \(ans - lis\)。

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

const int N = 1e6 + 7;
int a[N];
int p[N];
int cnt;
int ch[N][2];
void dfs(int u) {
    if(ch[u][0]) dfs(ch[u][0]);
    p[++ cnt] = a[u] - cnt;
    if(ch[u][1]) dfs(ch[u][1]);
}
struct node {
    int val, id;
}e[N];
int b[N];
signed main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++) {
        cin >> a[i];
    }
    for(int i = 2; i <= n; i ++) {
        int x, y;
        cin >> x >> y;
        ch[x][y] = i;
    }
    dfs(1); 
    int len = 0;
    for(int i = 1; i <= n; i ++) {
    	if(p[i] >= b[len]) {
    		b[++ len] = p[i];
		}
		else {
			int j = lower_bound(b + 1, b + len + 1, p[i]) - b;
			b[j] = p[i];
		}
	}
	cout << n - len << endl;
}

C.

二分长度 \(l\)，st 表维护区间 gcd 和区间最小值，时间复杂度 \(O(nlogn)\)

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

const int N = 5e5 + 500;
int a[N];
int fgcd[N][32], rmin[N][32];
int gcd(int x, int y)
{
	while(y)
	{
		x%=y;
		swap(x,y);
	}
	return x;
}
int getgcd(int l, int r) {
    int k = log2(r - l + 1);
    return gcd(fgcd[l][k], fgcd[r - (1 << k) + 1][k]);
}
int n;
int getmin(int l, int r) {
    int k = log2(r - l + 1);
    return min(rmin[l][k], rmin[r - (1 << k) + 1][k]);
}
int check(int l) {
    for(int i = 1; i <= n - l; i ++) {
        if(getgcd(i, i + l) % getmin(i, i + l) == 0	) {
            return 1;
        }
    }
    return 0;
}
int main() {
    memset(rmin, 0x3f, sizeof rmin);
    
    cin >> n;
    for(int i = 1; i <= n; i ++) {
        cin >> a[i];
        fgcd[i][0] = rmin[i][0] = a[i];
    }
    for(int j = 1; j < 23; j ++) {
        for(int i = 1; i <= n - (1 << (j - 1)); i ++) {
            fgcd[i][j] = gcd(fgcd[i][j - 1], fgcd[i + (1 << (j - 1))][j - 1]);
        }
    }
//    
    for(int j = 1; j < 23; j ++) {
        for(int i = 1; i <= n - (1 << (j - 1)); i ++) {
            rmin[i][j] = min(rmin[i][j - 1], rmin[i + (1 << (j - 1))][j - 1]);
        }
    }
    int l = 0, r = n;
    int ans;
    while(l <= r) {
        int mid = l + r >> 1;
        if(check(mid)) {
            l = mid + 1;
            ans = mid;
        }
        else {
            r = mid - 1;
        }
    }
    vector<int> v;
    int cnt = 0;
    for(int i = 1; i <= n - ans; i ++) {
        if(getgcd(i, i + ans) % getmin(i, i + ans) == 0	) {
            cnt ++;
            v.push_back(i);
        }
    }
    cout << cnt << " " << ans << endl;
    for(int i = 0; i < cnt; i ++) cout << v[i] << " ";
}