F - Integer Division
挺有意思的一道题，
贪心的做法就是排序之后，逐个加入，如果不能被之前的表示则加入
题解证明的话大概是这样
考虑第i个数选不选
首先加入前面选的数，如果能够表示当前的数，则必然不选
否则前面的数不能表示当前的数，假如我们不选\(p_i\)
假设最后得到一个合法序列，则必然能够表示\(p_i\)
\[x_1 \oplus x_2 \oplus x_3 ...\oplus x_m=p_i
\]
\[p_i \oplus x_2 \oplus x_3 ...\oplus x_m=x_1
\]
且其中必定有一个数的位置大于i，不妨设为x1
那么根据上面的柿子，任意一个需要x1表示的数，都可以用上面的柿子替代，而\(p_i\)的代价要更小，所以应当直接选择。
#include<algorithm>
#include<cstdio>
#include<cstring>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++) //
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("YES")
#define B puts("NO")
using namespace std;
typedef double db;
typedef long long ll;
const int N=1e5+5;
struct node{
ll x,id;
};
node a[N];
ll n,ans;
bool vis[N];
ll c[N],r;
bool cmp(node a,node b){
return a.x<b.x;
}
int main()
{
// freopen("data.in","r",stdin);
scanf("%lld",&n);
n=(1<<n)-1;
fo(i,1,n) {
scanf("%lld",&a[i].x);
a[i].id=i;
}
sort(a+1,a+n+1,cmp);
r=1;
c[1]=0;
fo(i,1,n) {
int z=a[i].id,y;
if (vis[z]) continue;
ans+=a[i].x;
fo(j,1,r) {
y=c[j]^z;
vis[y]=1;
c[j+r]=y;
}
r*=2;
}
printf("%lld",ans);
return 0;
}