POJ 2785

题目地址:http://poj.org/problem?id=2785

题目大意

给定各含有$n$个整数的四个数列$A, B, C, D$,要从每个数列中各取出一个数,使四个数和为0,求出有多少个这样的组合数。当一个数列中有多个相同的数字时应看成不同数字。

思路

若暴力搜索的话,复杂度达到$n^4$,所以可以考虑折半,将$A+B$的所有和组合存到一个数组中,这样有$n^2$种组合,排序后,然后再枚举$C, D$数列的和$c+d$,二分搜索$-(c+d)$的个数即可。

AC代码

/*************************************************************************
    > File Name: 2785.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-01-05 二 14:15:53 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;
const int MAXN = 4000 + 5;
ll A[MAXN], B[MAXN], C[MAXN], D[MAXN];
ll sum[MAXN * MAXN];
int N;

void solve() {
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j) sum[i*N + j] = A[i] + B[j];
    // for(int i=0; i<N*N; ++i) printf("%d: %lld\n", i, sum[i]);
    sort(sum, sum+N*N);
    ll res = 0;

    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j) {
            int s = C[i] + D[j];
            res += upper_bound(sum, sum+N*N, -s) - lower_bound(sum, sum+N*N, -s); // 累加相同数字个数。
        }
    cout << res << endl;
}

int main() {
#ifdef Oj
    freopen("2785.in", "r", stdin);
#endif
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> A[i] >> B[i] >> C[i] >> D[i];
    solve();
    return 0;
}

POJ 3977

题目地址:http://poj.org/problem?id=3977

题目大意

有$N(N\leq 35)$个绝对值小于$10^{15}$的数,求出其非空子集的最小和的绝对值和该子集个数(多解的话求出最小个数)。

思路

35个元素的话有$2^{35}$个子集,所以可以考虑折半枚举,折半后$2^{17}\approx 10^5$个子集,可以达到要求。

将前一半的和求出来,后一半就用二分搜索前一半的相反数,结果就是最接近0,也就是绝对值尽可能小。

不知为嘛用pair ps[MAXN]数组来求前一半和,排序,去掉相同和,老是Runtime error,非得用map来搞。

233,终于找到RE点了,在二分的时候粗心把m写成了1<<m不挂才怪。。

哈哈,来对比时间差。。

这是用map过的:

15055238    Netcan    3977    Accepted    7724K    15266MS    G++    1925B    2016-01-05 18:55:53

这是不用map

15055384    Netcan    3977    Accepted    17132K    1907MS    G++    1910B    2016-01-05 19:51:49

瞬间从15s飙到2s。。

不过这里有个需要注意的地方,就是pair模板的大小比较问题。

先来看看pair的重载操作符<吧:

template<class _T1, class _T2>
    inline _GLIBCXX_CONSTEXPR bool
    operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
    { return __x.first < __y.first
        || (!(__y.first < __x.first) && __x.second < __y.second); }

可以看出,若比较两个pair模板,若first大则大,一样大就看谁second大了。

AC代码

不使用Map

/*************************************************************************
    > File Name: 3977.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-01-05 二 16:21:31 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <limits>

using namespace std;
typedef long long ll;
typedef pair<ll, int> P;
const int MAXN = 40;
const int INF = numeric_limits<int>::max();
int N;
ll data[MAXN];
P ps[1<<(MAXN>>1)];

ll Abs(ll x) {
    return x > 0 ? x : -x;
}

void solve() {
    // 枚举前半部分
    P ans(Abs(data[0]), 1);
    int n1 = N >> 1;
    for(int i=0; i<1<<n1; ++i) {
        ll sum = 0;
        int cnt = 0;
        for(int j=0; j<n1; ++j)
            if(i >> j & 1) {
                sum += data[j];
                ++cnt;
            }
        ps[i] = P(sum, cnt);
        if(cnt > 0) ans = min(ans, P(Abs(sum), cnt));
    }
    sort(ps, ps+(1<<n1));

    // 去掉多余元素
    int m = 1;
    for(int i=1; i<1<<n1; ++i)
        if(ps[m-1].first < ps[i].first) ps[m++] = ps[i];

    for(int i=0; i<1<<(N-n1); ++i) { // 剩下部分
        ll sum = 0;
        int cnt = 0;
        for(int j=0; j<(N-n1); ++j) {
            if(i>>j & 1) {
                sum+= data[n1+j];
                ++cnt;
            }
        }
        // printf("sum: %lld\n", sum);
        if(cnt > 0) ans = min(ans, P(Abs(sum), cnt));

        P *f = lower_bound(ps, ps+m, P(-sum, -1));
        if(f < ps+m)
        if(f->second + cnt > 0) ans = min(ans, P(Abs(f->first+sum), f->second+cnt));

        if(f > ps) {
            --f;
            if(f->second + cnt > 0) ans = min(ans, P(Abs(f->first+sum), f->second+cnt));
        }
    }
    printf("%lld %d\n", ans.first, ans.second);
}

int main() {
#ifdef Oj
    freopen("3977.in", "r", stdin);
    // freopen("3977.out", "w", stdout);
#endif
    while(scanf("%d", &N) == 1 && N) {
        for (int i = 0; i < N; ++i) scanf("%lld", data+i);
        solve();
    }
    return 0;
}

使用Map

/*************************************************************************
    > File Name: 3977.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-01-05 二 16:21:31 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <limits>
#include <map>

using namespace std;
typedef long long ll;
typedef pair<ll, int> P;
const int MAXN = 40;
const int INF = numeric_limits<int>::max();
int N;
ll data[MAXN];
map<ll, int> ps;

ll Abs(ll x) {
    return x > 0 ? x : -x;
}

void solve() {
    // 枚举前半部分
    P ans(Abs(data[0]), 1);
    int n1 = N >> 1;
    for(int i=0; i<1<<n1; ++i) {
        ll sum = 0;
        int cnt = 0;
        for(int j=0; j<n1; ++j)
            if(i >> j & 1) {
                sum += data[j];
                ++cnt;
            }
        if(ps.find(sum) != ps.end())
            ps[sum] = min(ps[sum], cnt);
        else ps[sum] = cnt;
        if(cnt != 0) ans = min(ans, P(Abs(sum), cnt));
    }

    // for(int i=0; i<m; ++i)
        // printf("(%lld, %d)\n", ps[i].first, ps[i].second);


    // printf("n1:%d\n", n1);
    for(int i=0; i<1<<(N-n1); ++i) { // 剩下部分
        ll sum = 0;
        int cnt = 0;
        P res(0, 0);
        for(int j=0; j<(N-n1); ++j) {
            if(i>>j & 1) {
                sum+= data[n1+j];
                ++cnt;
            }
        }
        // printf("sum: %lld\n", sum);
        res = P(Abs(sum), cnt);
        if(ans > res && res.second != 0) ans = res;
        map<ll, int>::iterator f = ps.lower_bound(-sum);
        if(f!=ps.end()) {
            res = P(Abs(sum + f->first), f->second + cnt);
            if(ans > res && res.second != 0) ans = res;
        }
        if(f!=ps.begin()) {
            --f;
            res = P(Abs(sum + f->first), f->second + cnt);
            if(ans > res && res.second != 0) ans = res;
        }
    }
    cout << ans.first << ' ' << ans.second << endl;
}

int main() {
#ifdef Oj
    freopen("3977.in", "r", stdin);
    // freopen("3977.out", "w", stdout);
#endif
    while(cin >> N && N) {
        ps.clear();
        for (int i = 0; i < N; ++i) cin >> data[i];
        solve();
    }
    return 0;
}

POJ 2549

题目地址:http://poj.org/problem?id=2549

题目大意

给定一个集合$S(元素不超过1000)$,求出集合中互不相等的四个数$a, b, c, d$,使$a+b+c=d$,输出最大的$d$。若不存在,输出”no solution”。

思路

虽然明天就要考概率论了,鉴于后两章又臭又长,已弃疗。。

这题居然能用枚举求出来= =$O(N^3)$的时间复杂度。。

  1. 方法一:先将$S$排序,然后从大到小枚举$d$,再枚举$a, b, c$,符合就输出答案,不符合继续搜索。。
  2. 方法二:先将前半部分$a+b(N^2)$求出来,然后将$d-c(N^2)$求出来,然后枚举前半部分,二分搜索出后半部分。总复杂度$O(N^2 log N^2)$

AC代码

$O(N^3)$

/*************************************************************************
    > File Name: 2549.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-01-10 日 17:02:24 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;


int N;
int data[1024];

void solve() {
    sort(data, data+N);
    int n = unique(data, data+N) - data; // 去重
    for(int d=n-1; d>=0; --d) { // d从大到小枚举
        for(int i=0; i<n-3; ++i) { // 开始枚举
            int s = i + 1; // 从头开始枚举
            int t = n - 1; // 从尾开始枚举
            while(s < t) {
                int sum = data[i] + data[s] + data[t]; // s = a+b+c
                if(sum < data[d]) ++s;
                else if(sum > data[d]) --t;
                else {
                    if(i==d || s==d || t == d) break; // 后面的没必要枚举了。因为已经有等于d的值存在
                    else {
                        printf("%d\n", data[d]); // 最大的d
                        return;
                    }
                }
            }
        }
    }
    puts("no solution");
}

int main() {
#ifdef Oj
    freopen("2549.in", "r", stdin);
    // freopen("2549.out", "w", stdout);
#endif
    while(scanf("%d", &N) == 1 && N) {
        for (int i = 0; i < N; ++i) scanf("%d", &data[i]);
        solve();
    }
    return 0;
}

$O(N^2 log N^2)$

/*************************************************************************
    > File Name: 2549_2.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-01-10 日 20:11:06 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <limits>
#include <vector>
using namespace std;

int N;
int data[1024];

struct ds {
    int v, i, j; // 记录两个数i, j的和或者差。
    ds(int v, int i, int j):v(v), i(i), j(j) {}
    bool operator<(const ds &b) const{
        return v < b.v;
    }
};

// 计算前半部分a+b的和,以及后半部分d-c,最后求出a+b==d-c时最大的d

vector<ds> sum; // a+b
vector<ds> diff; // d-c

void solve() {
    sum.clear();
    diff.clear();
    for(int a=0; a<N; ++a)
        for(int b=a+1; b<N; ++b) sum.push_back(ds(data[a]+data[b], a, b));
    for(int c=0; c<N; ++c)
        for(int d=c+1; d<N; ++d) {
            diff.push_back(ds(data[d]-data[c], d, c));
            diff.push_back(ds(data[c]-data[d], c, d));
        }

    int ans = numeric_limits<int>::min(); // 因为最大值可能为负数

    sort(diff.begin(), diff.end());

    for(vector<ds>::iterator i=sum.begin(); i!=sum.end(); ++i) { // a+b
        vector<ds>::iterator lb = lower_bound(diff.begin(), diff.end(), ds(i->v, 0, 0)); // d-c
        vector<ds>::iterator rb = upper_bound(diff.begin(), diff.end(), ds(i->v, 0, 0)); // d-c
        for(;lb!=rb; ++lb) {// 因为可能有多组相同的d-c
            if(lb->i != i->i && lb->j != i->i && lb->i != i->j && lb->j != i->j) {
                ans = max(ans, data[lb->i]);
            }
        }
    }
    if(ans == numeric_limits<int>::min()) puts("no solution");
    else cout << ans << endl;
}

int main() {
#ifdef Oj
    freopen("2549.in", "r", stdin);
    // freopen("2549_2.out", "w", stdout);
#endif
    while(cin >> N && N) {
        for (int i = 0; i < N; ++i) cin >> data[i];
        solve();
    }
    return 0;
}