首页 > 代码库 > Maximum number, GCD condition (codechef March Challenge 2014)
Maximum number, GCD condition (codechef March Challenge 2014)
题目 ： http://acm.bnu.edu.cn/v3/problem_show.php?pid=40489
最近做到的一道蛮有意思的题目(codechef现在的题目确实很赞了)
题意 ：中文题面 (cc的一大好处就是有中文翻译，嘿嘿)
区间Max = max{a_i|gcd(a_i, g) > 1 && x <= i <= y}
做法 ： 一开始我是用分块做的，复杂的O(m * sqrt(n) * C) C 是所含不同素数的个数， C大概最大只有6或7吧
然后裸裸的T了，换了一个姿势：用线段树或者RMQ把查询从sqrt(n) -> log(n)， 这里最初的想法就是直接对于每个素数开一个线段树，但是这样预处理空间和时间都过不了
，但是考虑的其实n个数都分解一下只有C*n个数，那么的话我们可以用动态开线段树的方法，当然这个我不会- - ！，还有一种比较好的实现方式是对于每个素数都建立一段段的RMQ，额，， 具体就是比如 a[] : 2, 3, 4, 6 那么我建立一个RMQ为 ：2 4 6 3 6，前三个是2的倍数，后两个是3的倍数，，并通过一些其他辅助操作可以使得复杂度降为log(n)。
分块做法(TLE) :
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <vector> 5 6 using namespace std; 7 inline int gcd(int a, int b) {return !b ? a : gcd(b, a % b);} 8 const int MAXN = 100005; 9 int check[MAXN] = {0};10 const int M = 320;11 vector<int> prime[MAXN];12 int ptot = 0;13 int n, m;14 int blocks[1<<9][10005];15 int a[MAXN];16 void init(int N) {17 for (int i = 2; i <= N; i++) {18 if (!check[i]) {19 for (int j = 1; j * i <= N; j++) {20 prime[j * i].push_back(i);21 check[i * j] = 1;22 }23 check[i] = ++ ptot;24 }25 }26 }27 vector<int> G[MAXN];28 int query(int x, int y, int e) {29 return upper_bound(G[e].begin(), G[e].end(), y) - lower_bound(G[e].begin(), G[e].end(), x);30 }31 32 int main() {33 init(100000);34 scanf("%d%d", &n, &m);35 for (int i = 1; i <= n; i++) {36 scanf("%d", &a[i]);37 int e = i / M;38 for (int j = 0; j < prime[a[i]].size(); j++) {39 int v = prime[a[i]][j];40 blocks[e][check[v]] = max(blocks[e][check[v]], a[i]);41 }42 G[a[i]].push_back(i);43 }44 while (m --) {45 int g, x, y;46 scanf("%d%d%d", &g, &x, &y);47 int l = x / M, r = y / M, Max = -1;48 if (l == r) {49 for (int i = x; i <= y; i++) {50 if (gcd(g, a[i]) > 1) Max = max(Max, a[i]);51 }52 }else {53 for (int i = x; i < (l+1) * M; i++) {54 if (gcd(g, a[i]) > 1) Max = max(Max, a[i]);55 }56 for (int i = r * M; i <= y; i++) {57 if (gcd(g, a[i]) > 1) Max = max(Max, a[i]);58 }59 for (int i = 0; i < prime[g].size(); i++) {60 int v = prime[g][i];61 for (int j = l + 1; j <= r - 1; j++) {62 if (blocks[j][v] > 0)Max = max(Max, blocks[j][v]);63 }64 }65 }66 if (Max == -1) printf("-1 -1\n");67 else {68 printf("%d %d\n", Max, query(x, y, Max));69 }70 }71 return 0;72 }
RMQ做法:
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <vector> 5 6 using namespace std; 7 const int MAXN = 100005; 8 struct RMQ { 9 int a[MAXN * 7][20];10 int log2[MAXN * 7];11 void init(int A[], int N) {12 for (int i = 0; i < MAXN * 7; i++) log2[i] = (i == 0 ? -1 : log2[i >> 1] + 1);13 for (int i = 1; i <= N; i++) a[i][0] = A[i];14 for (int j = 1; (1 << j) <= N; j++) {15 for (int i = 1; i + (1<<j) - 1 <= N; i++) {16 a[i][j] = max(a[i][j-1], a[i + (1<<(j-1))][j - 1]);17 }18 }19 }20 int rmq(int L, int R) {21 if (R < L) return 0;22 int k = log2[R - L + 1];23 return max(a[L][k], a[R-(1<<k)+1][k]);24 }25 }AC;26 vector<int> prime[MAXN];27 int check[MAXN] = {0}, ptot = 0;28 void init(int N) {29 for (int i = 2; i <= N; i++) {30 if (!check[i]) {31 for (int j = 1; j * i <= N; j++) {32 prime[j * i].push_back(i);33 check[i * j] = 1;34 }35 check[i] = ++ ptot;36 }37 }38 }39 vector<int> G[MAXN];40 int query(int x, int y, int e) {41 return upper_bound(G[e].begin(), G[e].end(), y) - lower_bound(G[e].begin(), G[e].end(), x);42 }43 int n, m;44 int b[MAXN * 7];45 int a[MAXN];46 int pre[MAXN];47 vector<int> gao[MAXN];48 49 int main() {50 init(100000);51 scanf("%d%d", &n, &m);52 for (int i = 1; i <= n; i++) {53 scanf("%d", &a[i]);54 for (int j = 0; j < prime[a[i]].size(); j++) {55 int v = check[prime[a[i]][j]];56 gao[v].push_back(i);57 }58 G[a[i]].push_back(i);59 }60 int tot = 0;61 for (int i = 1; i <= ptot; i++) {62 if (gao[i].size() == 0) continue;63 pre[i] = tot;64 for (int j = 0; j < gao[i].size(); j++) {65 b[++ tot] = a[gao[i][j]];66 }67 }68 AC.init(b, tot);69 while (m--) {70 int g, x, y, Max = -1;71 scanf("%d%d%d", &g, &x, &y);72 for (int i = 0; i < prime[g].size(); i++) {73 int v = check[prime[g][i]];74 int r = upper_bound(gao[v].begin(), gao[v].end(), y) - gao[v].begin() + pre[v] + 1;75 int l = lower_bound(gao[v].begin(), gao[v].end(), x) - gao[v].begin() + pre[v] + 1;76 r --;77 if (r >= l)Max = max(Max, AC.rmq(l, r));78 }79 if (Max == -1) {80 printf("-1 -1\n");81 }else {82 printf("%d %d\n", Max, query(x, y, Max));83 }84 }85 return 0;86 }
Maximum number, GCD condition (codechef March Challenge 2014)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。