折半枚举+Hash（HDU1496升级版）

给定一个四元二次方程：

Ax1^2+Bx2^2+Cx3^2+Dx4^2=0

试求−1000≤x1,x2,x3,x4≤1000非零整数解的个数。

−10000≤A,B,C,D≤10000

输出解的个数。

解法：

首先这道题直接用网上HDU1496的板子过不去，原因是1e10的数组开不了那么大的。所以这里只能换思路。新思路如下（很典型的折半枚举，也就是meet-in-middle）：

把X1,X2的答案存下来（存在一个2000*2000的数组里面），然后排序

二分查找这个数组里面有多个数x了

AX_1^2+BX_2^2=-(CX_3^2+DX_4^2)

左边式子的答案我们已经存下来了，接下来算右边的

右边答案算出来过后，我们直接在左边数组里面二分有多少个一样的数值，答案加上这个数值就ok了

当然这里用数组会稍显笨拙，可以用map，卡时间可以过。

注意s[a*i*i + b*j*j]++会爆int，因此需要将a改为long long

代码如下：

#include<cstdio>

#include<map>

#include<algorithm>

using namespace std;

typedef long long ll;

map<ll, ll>s;

int main() {

    ll a, b, c, d;

    while (scanf("%lld %lld %lld %lld", &a, &b, &c, &d) != EOF) {

        if (a * b > 0 && b * c > 0 && c * d > 0) {

            printf("0\n");

            return 0;

        }

        for (ll i = 1; i <= 1000; i++) {

            for (ll j = 1; j <= 1000; j++) {

                //if (i == 0 || j == 0)continue;

                s[a*i*i + b*j*j]++;

            }

        }

        ll sum = 0;

        for (ll i = 1; i <= 1000; i++) {

            for (ll j = 1; j <= 1000; j++) {

                //if (i == 0 || j == 0)continue;

                ll t = c*i*i + d*j*j;

                sum += s[0 - t];

            }

        }

        printf("%lld\n", 16*sum);

    }

    return 0;

}

上面说了卡常数不是很严的做法，如果卡常数很严的话，比如x的范围变到4000，map就会T掉，这里直接采用hash的方法

关键词：数字hash

例题：Uva1152：4 Values whose Sum is 0

//hash数字编码

#include<cstdio>

#include<vector>

#include<algorithm>

#include<cstring>

#include<map>

using namespace std;

typedef long long ll;

map<ll, ll>s;

int a[4005], b[4005], c[4005], d[4005];

int n, T, cnt;

//w[i]表示第i个结点存储的数（也就是a+b），st[i]表示第i个结点有多少种表示方法

const int hashsize = 1000003;

int hd[hashsize], nxt[16000005], w[16000005], st[16000005];

void in(int x) {

    int h = (x % hashsize + hashsize) % hashsize, u = hd[h];

    while (u) {

        if (w[u] == x) {

            st[u]++;

            return;

        }

        u = nxt[u];

    }

    nxt[++cnt] = hd[h];

    hd[h] = cnt;

    w[cnt] = x;

    st[cnt] = 1;

}

int srch(int x) {

    int h = (x % hashsize + hashsize) % hashsize;//查询的数是负数，所以要这么算；

    int u = hd[h];

    while (u) {

        if (w[u] == x) return st[u];

        u = nxt[u];

    }

    return 0;

}

int main() {

    scanf("%d", &T);

    while (T--) {

        cnt = 0; memset(hd, 0, sizeof(hd));

        scanf("%d", &n);

        int A, B, C, D;

        for (int i = 0; i < n; i++) {

            scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);

        }

        for (ll i = 0; i < n; i++) {

            for (ll j = 0; j < n; j++) {

                in(a[i] + b[j]);

            }

        }

        ll sum = 0;

        for (int i = 0; i < n; i++) {

            for (int j = 0; j < n; j++){

                sum += srch(-c[i] - d[j]);

            }

        }

        printf("%lld\n", sum);

        if (T) printf("\n");

    }

    return 0;

}

巴特西

折半枚举+Hash（HDU1496升级版）

最新文章

热门文章