用bitset做的一些题
代表的意义
\(1.\)一个序列的全或加(\(01\)背包)
数组\(a\)中去任意数量的数累加起来的所有情况：
bitset<N> f;
for(auto x : a)
{
f |= f << x;
}
其中，\(f[idx] == 1\)表示存在起码一种组合加法，使得他们的和为\(idx\)。
\(2.\)分组背包
每次的单个状态转移都是从整个上一层状态转移而来
bitset<N> ans;
for(int i = 1;i<=n;i++)
{
bitset<N> temp;
for(auto x : a[i])
{
t |= ans << x;
}
ans = t;
}
Corns
解题思路：
就正常\(01\)背包思路，所有可转移到的状态即可。
当然，本题也可以做二进制拆分的分组背包。
代码:
分组背包:
#include<bits/stdc++.h>
using namespace std;
#define rg register
#define maxn 215300
#define ll long long
#define IT set<node>::iterator
#define int ll
#pragma GCC optimize(3)
#pragma -fcrossjumping
#pragma -fdefer-pop
#pragma -fmerge-constans
#pragma -fthread-jumps
#pragma -floop-optimize
#pragma -fif-conversion
#pragma -fif-conversion2
#pragma -fdelayed-branch
#pragma -fguess-branch-probability
#pragma -fcprop-registers
#pragma -fforce-mem
#pragma -foptimize-sibling-calls
#pragma -fstrength-reduce
#pragma -fgcse
#pragma -fcse-follow-jumps
#pragma -frerun-cse-after-loop
#pragma -fdelete-null-pointer-checks
#pragma -fextensive-optimizations
#pragma -fregmove
#pragma -fschedule-insns
#pragma -fsched-interblock
#pragma -fcaller-saves
#pragma -fpeephole2
#pragma -freorder-blocks
#pragma -fstrict-aliasing
#pragma -funit-at-a-time
#pragma -falign-functions
#pragma -fcrossjumping
#pragma -finline-functions
#pragma -fweb
#pragma -fgcse-after-reload
inline int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c<='9'&&c>='0')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline int max(int a,int b)
{
if(a>b) return a;
return b;
}
int n,m,nn;
bool vis[maxn];
int val[maxn],w[maxn],num[maxn],num1[maxn];
int f[maxn];
signed main()
{
// freopen("data.out","r",stdin);
nn=read(),m=read();
for(rg int i=1;i<=nn;++i)
{
w[i]=read();//物品体积、价值和数量
num1[w[i]]++;
}
for(rg int i=1;i<=nn;++i)
{
if(vis[w[i]]==0)
{
vis[w[i]]=1;
w[++n]=w[i];
val[n]=w[i];
num[n]=num1[w[i]];
}
}
for(rg int i=1;i<=n;++i)
{
if(num[i]*w[i]>=m)
{//这种情况可以理解成该种物品有无限个,用完全背包的做法即可
for(rg int j=w[i];j<=m;++j) f[j]=max(f[j],f[j-w[i]]+val[i]);
}
else
{ //这种情况下我们将num[i]进行二进制的拆分
/*
任何一个整数都可以分解成用2的次方表示的数
1,2,4,8,16...2^n
比如7=2^0+2^1+2^2
那么对于num[i],我们可以把其分解成一共log(num[i])个数,把每个数看作数量只有1的个体
由于[0,num[i]]之间的任意一个数都可以用这些二进制数来表示,所以我们可以处理所有的情况
同时时间复杂度从num[i]->log(num[i])
*/
int now=1;//从1开始
while(num[i]>now)
{
int cost=now*w[i],money=now*val[i];
for(rg int j=m;j>=cost;--j) f[j]=max(f[j],f[j-cost]+money);
num[i]-=now;
now<<=1;
}
if(num[i]!=0)//这里可能会有剩余
{
int cost=num[i]*w[i],money=num[i]*val[i];
for(rg int j=m;j>=cost;--j) f[j]=max(f[j],f[j-cost]+money);
num[i]=0;
}
}
}
cout<<f[m];
}
\(bitset\)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
void solve()
{
int n, w;
cin >> n >> w;
bitset<200005> f;
f[0] = 1;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
f |= f << x;
}
for (int i = w; i >= 0; i--)
{
if (f[i])
{
cout << i << endl;
return;
}
}
}
int main()
{
int t = 1;
while (t--)
{
solve();
}
return 0;
}
简单瞎搞题
解题思路：
分组背包，有\(n\)组，每组中只能选一个加到总值中，问最后我们得到的总值一共有多少种。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
const int N = 1e6 + 5;
void solve()
{
int n;
cin >> n;
bitset<N> ans;
ans[0] = 1;
for (int i = 1; i <= n; i++)
{
int l, r;
cin >> l >> r;
bitset<N> t;
for (int j = r; j >= l; j--)
{
t |= ans << j * j;
}
ans = t;
}
cout << ans.count() << endl;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int t = 1;
while (t--)
{
solve();
}
return 0;
}
E1 - PermuTree (easy version)
解题思路:
不难发现，对于每个结点\(u\)，我们能使其子树分为两类。一类是其中结点权值都小于\(u\),另一类则是都大于\(u\).
那么对于每个结点对答案的总贡献就很好计算了，设\(siz[l]\)为结点权值小于结点\(u\)的子节点的数量，\(siz[r]\)则反之。
那么结点\(u\)对答案的最大贡献就是\(max(siz[l] *siz[r])\).
我们用\(bitset\)枚举所有可能划分，取最大值即可。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
int n;
cin >> n;
vector<vector<int>> adj(n + 1);
for (int i = 2; i <= n; i++)
{
int p;
cin >> p;
adj[p].push_back(i);
adj[i].push_back(p);
}
vector<int> siz(n + 1);
ll ans = 0;
auto dfs = [&](auto self, int u, int fa) -> void
{
bitset<5010> f;
f[0] = 1;
for (auto v : adj[u])
{
if (v == fa)
{
continue;
}
self(self, v, u);
f |= f << siz[v];
siz[u] += siz[v];
}
ll res = 0;
for (int i = 0; i <= n / 2 + 1; i++)
{
if (f[i])
{
res = max(res, 1ll * i * (siz[u] - i));
}
}
siz[u]++;
ans += res;
};
dfs(dfs, 1, -1);
cout << ans << endl;
}
int main()
{
int t = 1;
while (t--)
{
solve();
}
return 0;
}
D - Earn or Unlock
解题思路:
如果我们确定了最后一个取值的牌，此时意味着后面没有开锁的牌了（有牌但没开锁），或者是说没有牌了（存在最后一次开锁开到后面，但没牌可开的说法）。
所以，我们可以枚举每张牌来作为最后一张牌，取最大值即可。
如果我们最后一张牌的位置是\(idx\),那么意味着前面我们花费\(ids - 1\)的价值来开锁开到这里。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
const int N = 2e5 + 5;
// 如果我们能够将第i张牌解锁，那么前面我们必定至少有(i-1)的胜点用来解锁
// 我们最后取胜点的位置，必定是取完后后面的牌就没了或者都是锁住的
// 所以，我们要知道哪些位置的牌可作为最后一张牌
// 换句话说，如果当前牌作为胜点取完后，后面还有牌可以得到胜点，那么继续取胜点得到的值一定更大
// 所以我们枚举能到达的最后的牌的位置 i, ans = max(ans,s[i] - (i - 1));
void solve()
{
int n;
cin >> n;
bitset<N> f;
// 首先，第一个点我们是肯定能够到达的
f[1] = 1;
vector<int> a(n + 1);
// 找到能作为最后一张牌的位置
// 直接左移的话，或运算会影响到之前的状态
// 由于对后续的牌的解锁是累加的，所以对后续的1直接一起移动即可
// 将1移到v[i]能够影响到的位置
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
f |= (f >> i) << (i + a[i]);
}
ll sum = 0;
ll ans = 0;
for (int i = 1; i <= N; i++)
{
if (i <= n)
{
sum += a[i];
}
if (f[i])
{
ans = max(ans, sum - i + 1);
}
}
cout << ans;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int t = 1;
while (t--)
{
solve();
}
return 0;
}