题目链接:https://vjudge.net/problem/HDU-4027

主要题意:区间开方,区间求和

#include 
#include 
#include 
#include 
using namespace std;
const int N = 1e5 + 100;
int n, m;
int bl[N];
long long blo;
long long sum[N], s[N];
bool flag[N];
void solve(int x) {
	if(flag[x]) return;
	flag[x] = 1;
	sum[x] = 0;
	for(long long i = (x - 1) * blo + 1; i <= x * blo; i++) {
		s[i] = sqrt(s[i]);                    //数字处理[开方]
		sum[x] += s[i];
		if(s[i] > 1) flag[x] = 0;          //终止点[不等于1]
	}
}
void add(long long l,long long r) {
	for(long long i = l; i <= min(bl[l] * blo, r); i++) {//左端点所属的半块
		sum[bl[l]] -= s[i];
		s[i] = sqrt(s[i]);                  //数字处理[开方]
		sum[bl[l]] += s[i];
	}
	if(bl[l] != bl[r])                    //右端点所属的半块
		for(long long i = (bl[r] - 1) * blo + 1; i <= r; i++) {
			sum[bl[r]] -= s[i];
			s[i] = sqrt(s[i]);          //数字处理[开方]
			sum[bl[r]] += s[i];
		}
	for(long long i = bl[l] + 1; i <= bl[r] - 1; i++) solve(i);  //整块
}
long long query(long long l,long long r) {
	long long ans = 0;
	for(long long i = l; i <= min(bl[l] * blo, r); i++) ans += s[i];
	if(bl[l] != bl[r])
		for(long long i = (bl[r] - 1) * blo + 1; i <= r; i++) ans += s[i];
	for(long long i = bl[l] + 1; i <= bl[r] - 1; i++) ans += sum[i];
	return ans;
}
int main() {
	int cnt = 0;
	while(~scanf("%d", &n)) {
		printf("Case #%d:\n", ++cnt);
		memset(sum, 0, sizeof sum);
		memset(flag, 0, sizeof flag);
		blo = sqrt(n);
		for(long long i = 1; i <= n; i++) scanf("%d", &s[i]);
		for(long long i = 1; i <= n; i++) {
			bl[i] = (i - 1) / blo + 1;
			sum[bl[i]] += s[i];
		}
		scanf("%d", &m);
		for(long long i = 1; i <= m; i++) {
			int oper, l, r;
			scanf("%d %d %d", &oper, &l, &r);
			if(l > r) swap(l, r);
			if(oper == 1) printf("%d\n", query(l, r));
			else add(l, r);
		}
		printf("\n");
	}
	return 0;
}

修改方式

  1. 数字操作:一共3个点,表示对数字的操作,原题是sqrt()[开方]。
  2. 终止项:一个点,降低时间复杂度关键点,可以打表得到,意思是一个数字经过多次[常数级]操作后都会转化到的一个数。

例子

题目链接:https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/4524.html

数字操作代码:

long long getdf(long long x) {
	int len;
	int arr[19];
	for(len = 0; x != 0; len++) {
		arr[len] = x % 10;
		x /= 10;
	}
	long long sum = 0;
	for(int i = 0; i < len; i++) sum += arr[i];
	return 3 * sum + 1;
}

于是,数字操作处sqrt()改为getdf(),同时打表得到终止项为13。

PS:坑点是变量别忘了long long。

发表回复