昨日作业讲解

1、最大抑或对

这里有视频喔：

最大异或对
本题考点是变形的Trie树
Trie树我们上节课讲过，这里大家想一想如何用Trie树。
好大家想好就继续看。
我们可以把每个节点定义两种状态，一种是这个节点存的是1，第二种存的是0.
我们可以通过2进制把数放进Trie树。
很弱吧？
插入操作与我们朴素的Trie树一样，思路就是：

没有路你就自己铺，不管有没有路都要走。

查找操作如图所示：

红色是一个不存在的数，绿色是一个存在的数的查找方式。
那我们如何去把思路套进代码里呢？
首先大家看下我们的插入函数。

void add(int x)
{
    int p = 0;
    for(int i = 30; i >= 0; i --)
    {
        int &s = son[p][x >> i & 1];
        if(!s) s = ++ idx;
        p = s;
    }
}

是不是让你想起了Trie树的标准模板？
好我们在看看如何算出我们的最大抑或值。
我们每次看看这里是0还是1，是1最好，走下去，不是1就只能将就着像0走了。
好我们看下代码：

int query(int x)
{
    int p = 0, ans = 0;
    for(int i = 30; i >= 0; i --)
    {
        int s = x >> i & 1;
        if(son[p][!s])//是1最好，继续走
        {
            ans += 1 << i;
            p = son[p][!s];
        }
        else p = son[p][s];//将就下
    }
    return ans;
}

我们看一下完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 100010, M = N * 30;
int n, a[N], son[M][2], res, idx;
void add(int x)
{
    int p = 0;
    for(int i = 30; i >= 0; i --)
    {
        int &s = son[p][x >> i & 1];
        if(!s) s = ++ idx;
        p = s;
    }
}
int query(int x)
{
    int p = 0, ans = 0;
    for(int i = 30; i >= 0; i --)
    {
        int s = x >> i & 1;
        if(son[p][!s])
        {
            ans += 1 << i;
            p = son[p][!s];
        }
        else p = son[p][s];
    }
    return ans;
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i], add(a[i]);
    for(int i = 0; i < n; i ++) res = max(res, query(a[i]));
    cout << res << endl;
    return 0;
}

好接下来是第二题：小猫爬山
本题有点难。。
好我们先考虑下如何进行DFS。

考虑完请继续看下图：

我们可以分为这几种情况去进行我们的dfs。
请看分别的代码：

首先是优化1：

if(k > ans) return;

如果已经比目前最优方案差那就不用继续搜了。

然后是情况1，可以在坐1量车：

for(int i = 0; i < k; i ++ )
{
    if(s[i] + c[u] <= m)
    {
        s[i] += c[u];
        dfs(u + 1, k);
        s[i] -= c[u];//还原（犯罪）现场。
    }
}

情况2我们要单开一辆车：

s[k] = c[u];
dfs(u + 1, k + 1);
s[k] = 0;//还原现场（回溯）

如果已经搜完了：

if(u == n)
{
    ans = k;
    return;
}

优化2：

sort(c, c + n);
reverse(c, c + n);

完整代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int n, m, s[N], c[N], ans = N;
void dfs(int u, int k)
{
    if(k > ans) return;
    if(u == n)
    {
        ans = k;
        return;
    }
    for(int i = 0; i < k; i ++ )
        if(s[i] + c[u] <= m)
        {
            s[i] += c[u];
            dfs(u + 1, k);
            s[i] -= c[u];
        }
    s[k] = c[u];
    dfs(u + 1, k + 1);
    s[k] = 0;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> c[i];
    sort(c, c + n);
    reverse(c, c + n);
    dfs(0, 0);
    cout << ans << endl;
    return 0;
}

好今天我们就到这里了。

未经允许，请勿转载！

这是我的全部分享~

bye~