蓝桥杯02

发表于

激光炸弹

题目

题目

还卡我内存，一时代码还没过

学到了两个前缀和的运用技巧

关于初始化数组：可以将所有坐标+1，这样就回避了边界问题

前缀和问题可以节省一个数组，内存开销变小

边长r = x2 - x1 + 1, 如果题目给的是坐标, 那就是 x1 - 1 = x2 - r, 因为坐标x1是包括进矩形的,所以从x1 - 1开始,但这样也带来了一个问题, x1不能为0, 所以数组要从1开始计数

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
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 5010;
int s[N][N];
int n, r;

int main(){
    cin >> n >> r;
    r = min(r, 5001);
    for(int i = 0; i < n; i++){
        int x, y, w;
        cin >> x >> y >> w;
        s[++x][++y] += w;
    }
    for(int i = 1; i <= 5001; i++){
        for(int j = 1; j <= 5001; j++){
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    int res = 0;
    for(int i = r; i <= 5001; i++){
        for(int j = r; j <= 5001; j++){
            res = max(res, s[i][j] - s[i - r][j] - s[i][j - r] + s[i - r][j - r]);
        }
    }
    cout << res << endl;
    
    return 0;
}

K倍区间

题目

题目

这题的方法太妙了，首先前缀和就不说了，直接上公式， s[R] - s[L - 1] % k == 0 ==> s[R] % k == s[L - 1] % k ，所以只要有两个数s[R] 和 s[L - 1]的前缀和mod k的余数相同，那么就必然是一个K倍区间，所以每次出现一个之前出现过的mod k的余数的数，就要res += cnt[之前出现过的余数]， 而且还要出现次数加一

最后是一个边界问题，因为上面的都是两个端点所组成的区间（不包括左端点，所以是2~n的所有序列和子序列被包括了），有一种情况被排除了==>[0, n]，所以一开始就要包括cnt[0]=1, 这个区间的第一个值为零，所以是一个万能区间（因为值为0，对余数无影响），只要有[1, n]的数符合情况，那它也就非零了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
using namespace std;

const int N = 1e7 + 10;
int s[N], cnt[N];
int n, k;
int main(){
    cin >> n >>k;
    long long ans = 0;
    //cnt[0] = 1;
    for(int i = 1; i <= n ; i++){
        
        cin >> s[i];
        s[i] = (s[i - 1] + s[i]) % k;
        ans += cnt[s[i]];
        cnt[s[i]] ++;
    }
    cout << ans + cnt[0]<< endl; 
    
    return 0;
}

数的三次方根

题目

简单地二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
using namespace std;

int main(){
    double a;
    scanf("%lf", &a);
    double l = -10000, r = 10000; 
    while(r - l > 1e-8){
    	double mid = (r + l) / 2;
    	if(mid * mid * mid >= a) r = mid;
    	else l = mid;
    	printf("%lf\n", mid);
	}
	printf("%lf\n", l);
	return 0;
}