桜羽 エマ
138 字
1 分钟
题解:AT_abc236_f [ABC236F] Spices
贪心好题。题意不再赘述。
思路
将 数组升序排序,并依次判断每个数 。若 可被已被取的数字异或得出,则不取 ,否则比取。
正确性证明
若 可被已取的数异或得出,那么显然不用取。若不可被异或得出,则之后定存在取的 使得组合出 必要取 ,故取 定不劣。
代码
#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/ 最后更新于 2024-10-09,距今已过 455 天
部分内容可能已过时
Walter_Fang