博客

关于我为什么会学这个东西：我vp一场

Dashboard – 2021 ICPC Gran Premio de Mexico 2da Fecha – Codeforces

开来6道题 毕竟是一个人感觉是挺不错的

现在补题中 这里的A题就有用到这个知识

1.sosdp就是一个和二进制子集价值有关的东西

他的只要用途就是用来0（n*2^n） 来枚举（1-2^n）的子集

SOS Dynamic Programming [Tutorial] – Codeforces

主要用途：

1.

Problem – F – Codeforces

关于这道题 其实我们要找到几点：

1.首先我们对于每个i要考虑ai|(aj&ak)肯定要先从高位往低位枚举

看看能不能搞出来(now|1<<f) 是aj&ak的子集

2.子集的传递性：假如now为aj&ak 的子集 now即为aj 的子集又是ak的子集

所以我们考虑每一个状态i看看其是否存在 两个及以上的父亲

也可以通过枚举该位数的子集来更新每一个状态

我们可以动态从后往前更新也可以通过处理每种状态的最后两位来处理

#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int maxn = 1e6 + 10;
pair<int, int>p[maxn * 2];
int a[maxn];
inline void update(int x, int id)
{
	if (id == 0||id==p[x].first||id==p[x].second)
		return;
	if (p[x].first == 0)
	{
		p[x].first = id;
		return;
	}
	else if (p[x].second == 0)
	{
		p[x].second = id;
		return;
	}
	else if (p[x].first < id)
	{
		p[x].second = p[x].first;
		p[x].first = id;
	}
	else if (p[x].second < id)
	{
		p[x].second = id;
		return;
	}
}
inline void init()
{
	for (register int i = 2e6; i >= 0; i--)
	{
		for (register int j = 21; j >= 0; j--)
		{
			if (i&(1 << j))//代表i存在一个子集 i^(1<<j)
			{
				update(i ^ (1 << j), p[i].first);
				update(i ^ (1 << j), p[i].second);
			}
		}
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for (register int i = 1; i <= n; i++)
	{
		cin >> a[i];
		update(a[i], i);
	}
	init();
	int ans = 0;
	for (register int i = 1; i <= n - 2; i++)
	{
		int now = 0;
		for (int j = 21; j >= 0; j--)
		{
			if (a[i] & (1 << j))
			{
				continue;
			}
			else if ((now | (1 << j)) <= 2e6&&p[now | (1 << j)].first > i&&p[now | (1 << j)].second > i)
			{
				now |= (1 << j);
			}
		}
		ans = max(ans, now | a[i]);
	}
	cout << ans;
}

2.

Problem – E – Codeforces

这道题要找 ai&aj

要是没学这个sos的话 我可能就在tire树上尝试dp了（虽然试过 不过没想出来）

这道题我们可以发现假如对于a来说 一个数要和其&=0 这个数一定是a的数值位全部取反的子集

这样就和子集挂钩起来了

我们利用b[x]来表示x的子集中最大的数

假如为0 代表没有这种数

假如有我们就输出

此时询问的是a[i]的取反

利用子集来维护的操作父亲的操作是sos的关键点

/*
1.对于一个a找一个b使其a^b=0
所以我对a->!a
b一定是!a的子集
我先将a数值中所有数都标记
在利用其将其父亲全部标记
*/
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int maxn = 1e6 + 10;
int a[maxn];
int b[(1ll<<22)+10];
void init()
{
    for(int i=0;i<=21;i++)
    {
       for(int j=0;j<(1ll<<22);j++)
       {
        if(j&(1ll<<i))
        {
            b[j]=max(b[j],b[j^(1ll<<i)]);          
        }
       }
    }
}
int c[maxn];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {    cin>>a[i];
        b[a[i]]=a[i];//标记
    }

    for(int i=1;i<=n;i++){
      for(int j=21;j>=0;j--)
      {
        if((a[i]>>j)&1)
       {  }
        else
            c[i]+=(1ll<<j);
      }
    }
    init();
    for(int i=1;i<=n;i++){
        if(b[(c[i])]==0)
        {
            cout<<-1<<' ';
        }
        else
            cout<<b[(c[i])]<<' ';
    }
}