Acwing二分和前缀和（二）

2024-02-18 08:28:38 浏览数 (2)

机器人跳跃问题

原题链接：https://www.acwing.com/activity/content/problem/content/1570/

二分查找更新条件只有两种：

  • R=mid;else L=mid 1：mid=(L R)/2
  • L=mid;else R =mid-1：mid=(L R 1)/2

这两种更新条件的结果是一样的。

代码语言：javascript复制
#include<iostream>
#include<cstdio>

using namespace std;
const int N = 1e5   10;
int n;
int h[N];

bool check(int e) {
    for (int i = 1; i <= n; i  ) {
        e = e * 2 - h[i];
        if (e >= 1e5)
            return true;
        if (e < 0)
            return false;
    }
    return true;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i  ) {
        scanf("%d", &h[i]);
    }
    int l = 0, r = 1e5;
    while (l < r) {
        int mid = (l   r) / 2;
        if (check(mid))
            r = mid;
        else
            l = mid   1;
    }
    printf("%d", l);
    return 0;
}

四平方和（拉格朗日定理）

原题链接：https://www.acwing.com/problem/content/1223/

  • 数据范围5*1e6：最多只能枚举2个数
  • 用空间换时间

三重循环时间太长：

image.pngimage.png
代码语言：javascript复制
#include<iostream>
#include<cstdio>
#include "cmath"

using namespace std;
const int N = 5 * 1e6   10;
int n;

int main() {
    scanf("%d", &n);
    for (int a = 0; a * a < n; a  ) {
        for (int b = a; a * a   b * b < n; b  ) {
            for (int c = b; a * a   b * b   c * c < n; c  ) {
                int t = n - a * a - b * b - c * c;
                int d = sqrt(t);
                if (d * d == t) {
                    printf("%d %d %d %d", a, b, c, d);
                    return 0;
                }
            }
        }
    }
    return 0;
}

结构体 二分查找，可以通过oj：

代码语言：javascript复制
#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;
const int N = 5 * 1e6   10;

struct Sum {
    int s, c, d;

    bool operator<(const Sum &t) const {
        if (s != t.s)return s < t.s;
        if (c != t.c)return c < t.c;
        return d < t.d;
    }
} sum[N];

int n, m;


int main() {
    scanf("%d", &n);
    for (int c = 0; c * c <= n; c  ) {
        for (int d = c; c * c   d * d <= n; d  ) {
            sum[m  ] = {c * c   d * d, c, d};
        }
    }
    sort(sum, sum   m);
    for (int a = 0; a * a <= n; a  ) {
        for (int b = a; a * a   b * b <= n; b  ) {
            int t = n - a * a - b * b;
            int l = 0, r = m - 1;
            while (l < r) {
                int mid = l   r >> 1;
                if (sum[mid].s >= t)r = mid;
                else l = mid   1;
            }
            if (sum[l].s == t) {
                printf("%d %d %d %d", a, b, sum[l].c, sum[l].d);
                return 0;
            }
        }
    }
    return 0;
}

哈希在这道题中慢于二分：

image.pngimage.png
代码语言：javascript复制
#include<iostream>
#include<cstdio>
#include<algorithm>
#include "unordered_map"

#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 5 * 1e6   10;
unordered_map<int, PII> s;
int n, m;

int main() {
    scanf("%d", &n);
    for (int c = 0; c * c <= n; c  ) {
        for (int d = c; c * c   d * d <= n; d  ) {
            int t = c * c   d * d;
            if (s.count(t) == 0)s[t] = {c, d};
        }
    }
    for (int a = 0; a * a <= n; a  ) {
        for (int b = a; a * a   b * b <= n; b  ) {
            int t = n - a * a - b * b;
            if (s.count(t)) {
                printf("%d %d %d %d", a, b, s[t].x, s[t].y);
                return 0;
            }
        }
    }
    return 0;
}

分巧克力

原题链接：https://www.acwing.com/problem/content/1229/

要求符合check的最大值。

代码语言：javascript复制
#include<iostream>
#include<cstdio>
#include<algorithm>
#include "unordered_map"

using namespace std;
typedef long long LL;
const int N = 1e5   0;
int n, m;
int h[N], w[N];

bool check(int mid) {
    LL res = 0;
    for (int i = 0; i < n;   i) {
        res  = (LL) h[i] / mid * (w[i] / mid);
        if (res >= m)return true;
    }
    return false;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i  ) {
        scanf("%d%d", &h[i], &w[i]);
    }
    int l = 1, r = 1e5;
    while (l < r) {
        int mid = l   r   1 >> 1;
        if (check(mid))l = mid;
        else r = mid - 1;
    }
    printf("%d", l);
    return 0;
}

激光炸弹

原题链接：https://www.acwing.com/problem/content/101/

一共分为三个部分：

  • 输入二维数组
  • 计算前缀和
  • 枚举所有区间

分别对应下面的三个for循环：

代码语言：javascript复制
#include<iostream>
#include<algorithm>

using namespace std;
const int N = 5010;
int sum[N][N];

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

输入部分，sum[x][y]需要通过 =而不是=。因为一个点可能有多个目标。 必须要调整r的范围，否则无法进入后面的循环。r = min(5001, r); 一直计算到了5001，是因为这个数字的平方复杂度比较小，可以接受。

K倍区间

原题链接：https://www.acwing.com/problem/content/1232/

如果通过枚举端点，累加求和的方式，复杂度为平方。也可以接受，但不是最优。 可以通过前缀和。 如果是K倍区间，那么两个前缀和做差之后模K余0。 这两个前缀和一定是模K同余的。 可以将同余的个数N存储起来。 那么同余的K倍区间的个数就是1 2 …N-1。 把所有余数的情况的加起来就是最终的答案。

代码语言：javascript复制
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;

const int N = 1e5   10;
int n, k;
LL s[N];
int cnt[N];

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i  ) {
        scanf("%d", s   i);
        s[i]  = s[i - 1];
    }
    LL res = 0;
    cnt[0]  ;
    for (int i = 1; i <= n; i  ) {
        res  = cnt[s[i] % k];
        cnt[s[i] % k]  ;
    }
    printf("%lld", res);
    return 0;
}

上面的代码把累加的过程放在for循环中，一个字 ，绝！

sum include int return scanf

0 人点赞