数据结构水题大赛官方题解#2 XXX的脑白金

数据结构水题大赛 T2

XXX的脑白金

题面

洛谷链接

题解

本题就是要求查询一个区间最大值除以区间gcd的商. 有(20')的暴力得分, 可以用线段树得(60'), 正解是st表(是不是感觉有点面熟? 没错, t1也是这样)

20'暴力

这个不用说了, 直接几层循环套娃就能过

60'线段树

构造两棵线段树, 分别维护区间gcd, 区间最大值, 每次查询两个值, 输出 (区间最大值 / 区间gcd)

单次查询时间复杂度 (O(logn))

100'st表

因为一个数重复计算不会影响区间gcd, 所以区间gcd可以用st表维护, (O(1))查询

区间最值可以用st表维护, 所以也可以(O(1))查询

AC代码

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;
int m, n, st[15][10005][2], ans = 0, two[10005], A, B;
bool flg;
char ch;
string s;
inline int IN() {
  char ich = getchar();
  int intmp = 0, insign = 1;
  while (((ich < '0') || (ich > '9')) && ((ich != '-'))) {
    ich = getchar();
  }
  if (ich == '-') {
    insign = -1;
    ich = getchar();
  }
  while ((ich <= '9') && (ich >= '0')) {
    intmp *= 10;
    intmp += ich - '0';
    ich = getchar();
  }
  return intmp * insign;
}
inline int G (const int x, const int y) {
	if (y) {
		return G (y, x%y);
	}
	else{
		return x;
	}
}
inline void ask () {
	A = IN();
	B = IN();
	int tmp(two[B - A + 1]), tmp2(1 << tmp);
	printf("%d
", max(st[tmp][A][1], st[tmp][B - tmp2 + 1][1]) / G(st[tmp][A][0], st[tmp][B - tmp2 + 1][0]));
}
int main() {
    n = IN();
    for (register int i(1); i <= n; ++i) {
    	st[0][i][2] = st[0][i][1] = st[0][i][0] = IN();
    }
    int cnt(0);
    for (register int i(1); i <= n; ++i) {
    	if(1 << (cnt + 1) <= i) {
    		two[i] = ++cnt;
		}
		else {
			two[i] = cnt;
		}
	}
    for (register int i(1), ii(0); i <= n; i <<= 1, ++ii) {
    	int j(0);
		while((++j) + (i << 1) <= n + 1) {
			st[ii + 1][j][0] = G(st[ii][j][0], st[ii][j + i][0]);
			st[ii + 1][j][1] = max(st[ii][j][1], st[ii][j + i][1]);
		}
	}
	m = IN();
	for(register int i(1); i <= m; ++i) {
		ask();
	}
	return 0;
}