Pair of Numbers CodeForces - 359D（st表，二分）

89 阅读 0 评论 59 点赞

我是靠谱客的博主欢呼超短裙，这篇文章主要介绍Pair of Numbers CodeForces - 359D（st表，二分），现在分享给大家，希望可以做个参考。

Simon has an array a1, a2, …, an, consisting of n positive integers. Today Simon asked you to find a pair of integers l, r (1 ≤ l ≤ r ≤ n), such that the following conditions hold:

there is integer j (l ≤ j ≤ r), such that all integers al, al + 1, …, ar are divisible by aj;
value r - l takes the maximum value among all pairs for which condition 1 is true;
Help Simon, find the required pair of numbers (l, r). If there are multiple required pairs find all of them.

Input
The first line contains integer n (1 ≤ n ≤ 3·105).

The second line contains n space-separated integers a1, a2, …, an (1 ≤ ai ≤ 106).

Output
Print two integers in the first line — the number of required pairs and the maximum value of r - l. On the following line print all l values from optimal pairs in increasing order.

Examples
Input
5
4 6 9 3 6
Output
1 3
2
Input
5
1 3 5 7 9
Output
1 4
1
Input
5
2 3 5 7 11
Output
5 0
1 2 3 4 5
Note
In the first sample the pair of numbers is right, as numbers 6, 9, 3 are divisible by 3.

In the second sample all numbers are divisible by number 1.

In the third sample all numbers are prime, so conditions 1 and 2 are true only for pairs of numbers (1, 1), (2, 2), (3, 3), (4, 4), (5, 5).

题意： 找出一段l~r，使得存在l ≤ i ≤ r，使得a[i]为这段数的最大公约数。输出最长的。
思路： 又一次体会到了st表的神奇（上一次是cf234a https://blog.csdn.net/tomjobs/article/details/102728843)

本题中，如果存在这样的i使得a[i]为这段的最大公约数，很明显a[i]得是这段的最小值。那么，我们只需要打出每一段的gcd和min，每次比较就可以看这段是否符合要求了。问题就变成了怎样确定段的长度。很明显，长度是具有单调性的（如果长的满足，那么短的也满足），所以直接二分长度就好了。

复制代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

typedef long long ll;

const int maxn = 3e5 + 7;
vector<int>res,tmp;
int mi[maxn][22],gc[maxn][22],a[maxn],ans_len;
int n,m;

int gcd(int x,int y) {
    return y == 0 ? x : gcd(y,x % y);
}

void init() {
    for(int j = 1;j <= 20;j++) {
        for(int i = 1;i + (1 << j) - 1 <= n;i++) {
            mi[i][j] = min(mi[i][j - 1],mi[i + (1 << (j - 1))][j - 1]);
            gc[i][j] = gcd(gc[i][j - 1],gc[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int query_mi(int l,int r) {
    int k = (int)log2(r - l + 1);
    return min(mi[l][k],mi[r - (1 << k) + 1][k]);
}

int query_gc(int l,int r) {
    int k = (int)log2(r - l + 1);
    return gcd(gc[l][k],gc[r - (1 << k) + 1][k]);
}

bool check(int len) {
    tmp.clear();
    for(int i = 1;i + len <= n;i++) {
        if(query_mi(i,i + len) == query_gc(i,i + len)) {
            tmp.push_back(i);
        }
    }
    if(tmp.size()) {
        return true;
    }
    return false;
}

int main() {
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        scanf("%d",&a[i]);
        gc[i][0] = mi[i][0] = a[i];
    }
    init();
    int l = 0,r = n - 1;
    int ans = 0;
    
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(check(mid)) {
            ans = mid;
            res = tmp;
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }
    
    
    printf("%d %dn",res.size(),ans);
    for(int i = 0;i < res.size();i++) {
        printf("%d ",res[i]);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

typedef long long ll;

const int maxn = 3e5 + 7;
vector<int>res,tmp;
int mi[maxn][22],gc[maxn][22],a[maxn],ans_len;
int n,m;

int gcd(int x,int y) {
    return y == 0 ? x : gcd(y,x % y);
}

void init() {
    for(int j = 1;j <= 20;j++) {
        for(int i = 1;i + (1 << j) - 1 <= n;i++) {
            mi[i][j] = min(mi[i][j - 1],mi[i + (1 << (j - 1))][j - 1]);
            gc[i][j] = gcd(gc[i][j - 1],gc[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int query_mi(int l,int r) {
    int k = (int)log2(r - l + 1);
    return min(mi[l][k],mi[r - (1 << k) + 1][k]);
}

int query_gc(int l,int r) {
    int k = (int)log2(r - l + 1);
    return gcd(gc[l][k],gc[r - (1 << k) + 1][k]);
}

bool check(int len) {
    tmp.clear();
    for(int i = 1;i + len <= n;i++) {
        if(query_mi(i,i + len) == query_gc(i,i + len)) {
            tmp.push_back(i);
        }
    }
    if(tmp.size()) {
        return true;
    }
    return false;
}

int main() {
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        scanf("%d",&a[i]);
        gc[i][0] = mi[i][0] = a[i];
    }
    init();
    int l = 0,r = n - 1;
    int ans = 0;
    
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(check(mid)) {
            ans = mid;
            res = tmp;
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }
    
    
    printf("%d %dn",res.size(),ans);
    for(int i = 0;i < res.size();i++) {
        printf("%d ",res[i]);
    }
    return 0;
}

貌似有更简便的方法，记录每个数左右扩展的大小。可以证明复杂度均为O(n)级别。

复制代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

typedef long long ll;

const int maxn = 3e5 + 7;
int L[maxn],R[maxn],a[maxn];
vector<int>ans;

int main() {
    int n;scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        scanf("%d",&a[i]);
        L[i] = R[i] = i;
    }
    
    for(int i = 1;i <= n;i++) {
        int now = i - 1;
        while(now >= 1 && a[now] % a[i] == 0) {
            L[i] = L[now];
            now = L[now] - 1;
        }
    }
    for(int i = n;i >= 1;i--) {
        int now = i + 1;
        while(now <= n && a[now] % a[i] == 0) {
            R[i] = R[now];
            now = R[now] + 1;
        }
    }
    
    int mx = 0;
    for(int i = 1;i <= n;i++) {
        mx = max(mx,R[i] - L[i]);
    }
    
    for(int i = 1;i <= n;i++) {
        if(R[i] - L[i] == mx) {
            if(ans.empty()) {
                ans.push_back(L[i]);
            }
            else {
                if(L[i] != ans.back()) {
                    ans.push_back(L[i]);
                }
            }
        }
    }
    
    printf("%d %dn",ans.size(),mx);
    for(int i = 0;i < ans.size();i++) {
        printf("%d ",ans[i]);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

typedef long long ll;

const int maxn = 3e5 + 7;
int L[maxn],R[maxn],a[maxn];
vector<int>ans;

int main() {
    int n;scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        scanf("%d",&a[i]);
        L[i] = R[i] = i;
    }
    
    for(int i = 1;i <= n;i++) {
        int now = i - 1;
        while(now >= 1 && a[now] % a[i] == 0) {
            L[i] = L[now];
            now = L[now] - 1;
        }
    }
    for(int i = n;i >= 1;i--) {
        int now = i + 1;
        while(now <= n && a[now] % a[i] == 0) {
            R[i] = R[now];
            now = R[now] + 1;
        }
    }
    
    int mx = 0;
    for(int i = 1;i <= n;i++) {
        mx = max(mx,R[i] - L[i]);
    }
    
    for(int i = 1;i <= n;i++) {
        if(R[i] - L[i] == mx) {
            if(ans.empty()) {
                ans.push_back(L[i]);
            }
            else {
                if(L[i] != ans.back()) {
                    ans.push_back(L[i]);
                }
            }
        }
    }
    
    printf("%d %dn",ans.size(),mx);
    for(int i = 0;i < ans.size();i++) {
        printf("%d ",ans[i]);
    }
    return 0;
}

这个则是跳到右端点后面，因为右端点和i之间的数再怎么扩展也不会比原来的长。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

typedef long long ll;

const int maxn = 3e5 + 7;
int L[maxn],R[maxn],a[maxn];
vector<int>ans;

int main() {
    int n;scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        scanf("%d",&a[i]);
    }
    
    int mx = 0;
    for(int i = 1;i <= n;) {
        int l = i,r = i;
        while(l >= 1 && a[l] % a[i] == 0)l--;l++;
        while(r <= n && a[r] % a[i] == 0)r++;r--;
        if(r - l > mx) {
            ans.clear();ans.push_back(l);
            mx = r - l;
        }
        else if(r - l == mx) {
            ans.push_back(l);
        }
        i = r + 1;
    }
    printf("%d %dn",ans.size(),mx);
    for(int i = 0;i < ans.size();i++) {
        printf("%d ",ans[i]);
    }
    return 0;
}