Chaos Slover 补档计划 - 拟阵

2015.11.12 16:11 Thu| 3 visits oi_2016| ChaosSlover补档计划| Text

拟阵

拟阵者,贪心算法之理论基础也……

拟阵是一个满足如下性质二元组 M=(S,L):

  1. S 是一个有限集,L 是一个以 S 的子集为元素的集合。
  2. 遗传性:若 A∈L,则 A 的子集也属于 L。
  3. 交换性:若 A∈L,B∈L,|A|<|B|,则存在一个 x∈B-A 使得 A∪{x} 也属于 L。

若 S 的一个子集属于 L,则称这个子集为独立集。

若 L 的元素 A 存在 A∪{x} 属于 L,则称 A 是可扩展的;否则称 A 是不可扩展的,也可称为极大独立集。

定义一个拟阵的秩等于拟阵中最大的极大独立集的大小。

于是可以得到定理:拟阵的极大独立集大小相等。

拟阵上的最优化问题我们可以用贪心解决,这是由拟阵的性质决定的。

对于 S 的每个元素 u 赋一个权值 w(u),S 的一个子集的权值等于这个子集内元素的权值和。

最优化问题指的就是求出一个权值和最大的极大独立集。

BZOJ3105 [cqoi2013]新Nim游戏

线性基有关内容。具体以后补档到代数的时候再玩吧 w

其实线性基就是一些数,它们之间不能够通过相互异或得到,然而它们在一起异或可以得到集合中所有的数。一个集合的线性基不一定只有一个,线性基中的元素不一定在集合中。

又到感性理解(口胡)的时间了,本人对以下内容不负责任。线性基中的元素长成一个倒三角形,第 i 位的线性基的最高位是 i。对于集合中的每一个元素,拿去和线性基们类似于高斯消元地消一下,一定可以被消成 0。这样我们就可以写代码了:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
struct linear_base
{
    long long base[64];
    bool insert(long long x)
    {
        for (int i = 63; i >= 0; --i)
            if ((x >> i) & 1)
            {
                if (base[i]) x ^= base[i];
                else { base[i] = x; return true; }
            }
        return false;
    }
};

对于这道题,首先知道这就是要取出一些数,使得包含剩下的数的集合不存在一个子集,使得子集中元素的异或和为 0。设 M=(S,L),其中 S 表示包含所有数的集合,L 表示其中元素线性无关的子集组成的集合。可以证明 M 满足拟阵的性质(遗传性显然,一堆线性无关的数中扔掉一些数,剩余的数仍然线性无关。交换性也很好证),然后就可以贪心了。

将所有元素从大到小排序,依次取出。如果这个数可以被加到线性基中,那么这个数就可以被保留下来啦,这样我们就能保证剩下的元素无论怎么异或,都不会得到 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
32
33
#include <bits/stdc++.h>
using namespace std;

struct linear_base
{
    long long base[32];
    bool insert(long long x)
    {
        for (int i = 30; i >= 0; --i)
            if ((x >> i) & 1)
            {
                if (base[i]) x ^= base[i];
                else { base[i] = x; return true; }
            }
        return false;
    }
} l;

int n, a[105];
long long ans;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = n; i; --i)
        if (!l.insert(a[i]))
            ans += a[i];
    cout << ans << endl;
    return 0;
}

BZOJ2460 [BeiJing2011]元素

我猜这道题和上一道题一模一样。

 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
32
33
34
#include <bits/stdc++.h>
using namespace std;

struct linear_base
{
    long long base[64];
    bool insert(long long x)
    {
        for (int i = 63; i >= 0; --i)
            if ((x >> i) & 1)
            {
                if (base[i]) x ^= base[i];
                else { base[i] = x; return true; }
            }
        return false;
    }
};

linear_base l;
int n, ans;
pair<int, long long> p[1005];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> p[i].second >> p[i].first;
    sort(p + 1, p + n + 1);
    for (int i = n; i; --i)
        if (l.insert(p[i].second))
            ans += p[i].first;
    cout << ans << endl;
    return 0;
}

BZOJ4004 [JLOI2015]装备购买

还是和上面的题一模一样,就是把异或变成了浮点数向量而已(怎么都一模一样啊魂淡!)。然后果然被卡精度了……

eps 开 10^5 AC,10^8 WA。

 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
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;

int n, m, ans1, ans2;
double a[505][505], *base[505];
pair<int, int> p[505];

bool check(double x[])
{
    for (int i = 1; i <= m; ++i)
        if (fabs(x[i]) > 1e-8)
        {
            if (base[i] != NULL)
            {
                double t = x[i] / base[i][i];
                for (int j = i; j <= m; ++j)
                    x[j] -= t * base[i][j];
            }
            else { base[i] = x; return true; }
        }
    return false;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%lf", &a[i][j]);
    for (int x, i = 1; i <= n; ++i)
        scanf("%d", &x), p[i] = make_pair(x, i);
    sort(p + 1, p + n + 1);
    for (int i = 1; i <= n; ++i)
        if (check(a[p[i].second]))
            ++ans1, ans2 += p[i].first;
    cout << ans1 << ' ' << ans2 << endl;
    return 0;
}