138 字
1 分钟

题解:AT_abc236_f [ABC236F] Spices

2024-10-09
浏览量 加载中...

贪心好题。题意不再赘述。

思路#

cc 数组升序排序,并依次判断每个数 xx。若 xx 可被已被取的数字异或得出,则不取 xx,否则比取。

正确性证明#

xx 可被已取的数异或得出,那么显然不用取。若不可被异或得出,则之后定存在取的 yy 使得组合出 xx 必要取 yy,故取 xx 定不劣。

代码#

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=(1<<16)+10;
ll t,n,i,j,ans,a[N],p[N],f[N];
int main(){
cin>>t;n=(1<<t)-1;f[0]=1;
for(i=1;i<=n;i++)cin>>a[i],p[i]=i;
stable_sort(p+1,p+1+n,[](int x,int y){return a[x]<a[y];});
for(i=1;i<=n;i++)
if(!f[p[i]]){
ans+=a[p[i]];
for(j=0;j<=n;j++)f[j^p[i]]|=f[j];
}
cout<<ans;
}

支持与分享

如果这篇文章对你有帮助,欢迎分享给更多人或赞助支持!

赞助
题解:AT_abc236_f [ABC236F] Spices
https://blog.walterfang.site/posts/solution-at_abc236_f/
作者
Walter_Fang
发布于
2024-10-09
许可协议
CC BY-NC-SA 4.0
最后更新于 2024-10-09,距今已过 455 天

部分内容可能已过时

评论区

目录