Forsaken喜欢玩自走棋

NC53424. Forsaken喜欢玩自走棋

描述

Forsaken最近迷上了玩一款自走棋，这个游戏最重要的属性就是羁绊属性，每种羁绊，都有一个增幅值，然而这个增幅值可能是负的，也就是 $debuff$ 。

这个游戏现在已经有 $n$ 种有属性变化羁绊，同时也有一些没有属性变化的羁绊，对于每种有属性变化羁绊，都有 $m$ 个限制，必须同时满足这 $m$ 个限制，你才能获得这个羁绊值。但是这个游戏特殊之处在于羁绊与羁绊之间的联系，如果羁绊 $a$ 里面的 $m_a$ 个限制含有另外一个羁绊 $b$ 的 $m_b$ 限制，那么羁绊 $b$ 就会继承羁绊 $a$ 的增幅值，也就是加上 $a$ 的增幅值。我们用二进制表示一个羁绊的 $m$ 个限制，假设 $b$ 的限制为 $0110$ ，羁绊 $a$ 的限制为 $1111$ ,那么 $b$ 就可以继承 $a$ 的增幅值。

Forsaken现在可以选一种羁绊，他想知道选哪种羁绊可以获得最大的增幅，并且他想知道最大的增幅值是多少。如果有多种羁绊的收益相同，输出限制在二进制表示下最小的那个。

输入描述

第一行一个表示羁绊的数量。
接下来行每行两个整数，代表在二进制下个限制代表的值，代表增幅值。

输出描述

两个整数,表示应该选哪个羁绊，表示最大的增幅值。

示例1

输入:

2
1 2
1 5

输出:

0 7

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 745ms, 内存消耗: 16024K, 提交时间: 2019-10-25 21:08:36

#include<bits/stdc++.h>
using namespace std;
long long t[1000005];
int s,v,y,n;
long long d[1000005],ans=-1e18;

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d %d",&s,&v);
		t[s]+=v;
	}
	for(int i=1;i<=1000000;i++){
		if(t[i]==0) continue; 
		for(int j=i;j;j=(j-1)&i){
			d[j]+=t[i];
		}
		d[0]+=t[i];
	}
	for(int i=0;i<=1000000;i++){
		if(ans<d[i]){
			ans=d[i];
			y=i;
		}
	}
	cout<<y<<" "<<ans<<endl;
	
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 187ms, 内存消耗: 10388K, 提交时间: 2019-10-30 18:15:16

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll a[1<<20+5];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		ll x,y;
		cin>>x>>y;
		a[x]+=y;
	}
	for(int j=0;j<20;j++)
	for(int i=0;i<1<<20;i++)
	{
		
			if(i>>j&1) a[i^(1<<j)]+=a[i];
	}
	ll ans=-1,idx=0;
	for(int i=0;i<1<<20;i++)
	{
		if(ans<a[i])
		{
			ans=a[i],idx=i;
		}
	}
	cout<<idx<<' '<<ans<<endl;
	return 0;
}