CF1148F Foo Fighters

牛逼贪心题

假设都是将总和正的变成负的，所以如果总和是负的，val取相反数

对于二进制操作，我们一位一位考虑，想让其二进制下1的个数最好变成奇数，只能选一个数保留哪些1，所以我们保留一个1就能乘上-1，改变了奇偶性。贪心满足无后效性，最优子结构，局部最优解为全局最优解，我们尝试将一个数二进制下最高位的位数的作为不同种类的划分依据，想让总和变负的，我们尽量让每个种类的和为负的，假设我们考虑到第\(i\)位，这一位作为哪些数的最高位，我把他们加起来，如果小于0了，我要是更改还可能为正数，不优，不更改。如果大于0，考虑把这一位上数是1的都取反了，显然当前就小于0了。现在来看一下为什么没有后效性：对于每一个种类，我从低到高考虑，假设有位数\(i\)>位数\(j\)，我\(i\)取什么值对\(j\)没有影响，因为我最高位为\(i\)的数不可能第\(j\)位是1

如果从大到小去一位一位考虑的话，想满足没有后效性，就去按照最低位的1分类，一样的

#include<bits/stdc++.h>
#define vd void 
#define int long long 
#define MAXN 300005
int gi(){
	char c;int x=0,f=0;
	while(!isdigit(c=getchar()))f|=(c=='-');
	while(isdigit(c))x=(x*10)+(c^48),c=getchar();
	return f?-x:x;
}
int n,val[MAXN],mask[MAXN],l1[MAXN];
int help(int x){for(int i=61;i>=0;i--)if((x>>i)&1)return i;return -1;}
signed main(){
	n=gi();int s=0,ans=0;
	for(int i=1;i<=n;i++)val[i]=gi(),mask[i]=gi(),s+=val[i],l1[i]=help(mask[i]);
	if(s<0)for(int i=1;i<=n;i++)val[i]=-val[i];
	for(int i=0;i<62;i++){
		int res=0;
		for(int j=1;j<=n;j++)if(l1[j]==i)res+=val[j];
		if(res>0){
			ans|=(1ll<<i);
			for(int j=1;j<=n;j++)if((mask[j]>>i)&1)val[j]=-val[j];
		}
	}
	printf("%lld\n",ans);
	return 0;
}

感觉比较神奇这道题，按位考虑是二进制常用的操作，想让贪心满足无后效性不妨钦定某个划分原则/依据