bzoj 2460:[BeiJing 2011]元素
2424 ワード
Description
古代、西洋大陸にあったMagic Landでは、魔法の鉱石で法杖を製錬する技術を身につけたと伝えられています.その時、人々は杖の法力が使用する鉱石にかかっていることを認識した.一般的に、鉱石が多ければ多いほど法力は強くなるが、物は必ず逆である.時には、人々はより強い法力を得るために多くの鉱石を使ったが、精製の過程で魔法鉱石がすべて消え、杖を精製できないことを発見し、この現象を「魔法相殺」と呼ぶ.特に、製錬中に同じ鉱石を1つ以上使用すると、必ず「魔法相殺」が発生する.その後、人々の認知レベルが高まるにつれて、この現象はよく説明された.大量の実験を経て、有名な法師Dmitriは発見しました:もし今発見したすべての鉱石に合理的な番号(番号が正の整数で、この鉱石の元素の番号と呼ばれています)を行うならば、1つの鉱石の組み合わせは“魔法の相殺”を生んで、しかも1つの非空の子のセットが存在する時だけ、それらの鉱石の元素の番号は位置によって異なってあるいはゼロになります.(異或とは何か分からない場合は、次のページの名詞の説明を参照してください.)例えば、2つの同じ鉱石を使用すると、この2つの鉱石の元素番号が同じであるため、異なるかゼロになるため、「魔法相殺」が発生します.そして魔力を測定する有効な方法があり、合成された杖の魔力は鉱石ごとの法力の和に等しいことが分かった.現在発見されているすべての鉱石の法力値を測定し,各鉱石の元素番号を実験により推定した.今、あなた以上の鉱石情報を与えて、当時鍛えられた法杖がどれだけの魔力を持っていたかを計算してください.
Input
第1行は、鉱石の種類数を表す正の整数Nを含む.次のN行、各行の2つの正の整数NumberiとMagiciは、この鉱石の元素番号と魔力値を表す.
Output
1行のみ、整数:最大の魔力値
Sample Input
3 1 10 2 20 3 30
Sample Output
50
HINT
「魔法相殺」という事実があるため、鉱石ごとに最大1枚使用される.すべての3種類の鉱石を使用すると、3つの元素の番号が異なるため、1 xor 2 xor 3=0になると、魔法の相殺が発生し、杖が得られない.最適なスキームは,20+30=50の法力を有する後の2つの鉱石を選択することであることが分かった.
すべてのデータについて:N≦1000,Numberi≦10^18,Magici≦10^4.
欲張りで、valueに従って大きくから小さく並べ替えてから線形基に挿入すれば答えが得られることを証明する(偽)私たちは先に並べ替えを行い、番号はa[1]からa[n]で、価値はv[1]からv[n]でまずa[1]が必ず答えの中でここで反証仮定で答えはa[k 1]、a[k 2],...,a[km]a[1]は中でa[1]がいくつかの線形表現であることを説明しないでa[1]=a[ki 1]^a[ki 2]^…^a[kix]では、右側のもう一つをa[1]で置き換えることで、すべての線形関係なくa[1]の価値が右側のいずれかよりも大きいようにすることができるので、a[1]は必ず答えの中でa[j]を考慮し、a[j]がa[1]からa[j-1]の数線形で表すことができれば、a[j]は決して好ましくなく、答えを加えない場合、すなわちa[j]線形基に挿入できないa[j]がa[1]からa[j-1]における数線形で表されない場合、すなわちa[j]が線形基に挿入できる場合、a[j]が答えでなければ、a[j]は必ずa[1]からa[j-1]とa[j+1]からa[n]の数線形で表され、a[j+1]からa[n]のうち少なくとも1つが存在する場合、この数をa[j]で置き換えることができる.すべての数の異種または0でないa[j]の価値をa[j+1]からa[n]のいずれかよりも大きくすることができるので、a[j]が線形基を挿入できれば、必ず答えの中にまとめられます.valueに従って大きい順に線形基を挿入し、挿入できるものをansに積算すればいいだけです.
古代、西洋大陸にあったMagic Landでは、魔法の鉱石で法杖を製錬する技術を身につけたと伝えられています.その時、人々は杖の法力が使用する鉱石にかかっていることを認識した.一般的に、鉱石が多ければ多いほど法力は強くなるが、物は必ず逆である.時には、人々はより強い法力を得るために多くの鉱石を使ったが、精製の過程で魔法鉱石がすべて消え、杖を精製できないことを発見し、この現象を「魔法相殺」と呼ぶ.特に、製錬中に同じ鉱石を1つ以上使用すると、必ず「魔法相殺」が発生する.その後、人々の認知レベルが高まるにつれて、この現象はよく説明された.大量の実験を経て、有名な法師Dmitriは発見しました:もし今発見したすべての鉱石に合理的な番号(番号が正の整数で、この鉱石の元素の番号と呼ばれています)を行うならば、1つの鉱石の組み合わせは“魔法の相殺”を生んで、しかも1つの非空の子のセットが存在する時だけ、それらの鉱石の元素の番号は位置によって異なってあるいはゼロになります.(異或とは何か分からない場合は、次のページの名詞の説明を参照してください.)例えば、2つの同じ鉱石を使用すると、この2つの鉱石の元素番号が同じであるため、異なるかゼロになるため、「魔法相殺」が発生します.そして魔力を測定する有効な方法があり、合成された杖の魔力は鉱石ごとの法力の和に等しいことが分かった.現在発見されているすべての鉱石の法力値を測定し,各鉱石の元素番号を実験により推定した.今、あなた以上の鉱石情報を与えて、当時鍛えられた法杖がどれだけの魔力を持っていたかを計算してください.
Input
第1行は、鉱石の種類数を表す正の整数Nを含む.次のN行、各行の2つの正の整数NumberiとMagiciは、この鉱石の元素番号と魔力値を表す.
Output
1行のみ、整数:最大の魔力値
Sample Input
3 1 10 2 20 3 30
Sample Output
50
HINT
「魔法相殺」という事実があるため、鉱石ごとに最大1枚使用される.すべての3種類の鉱石を使用すると、3つの元素の番号が異なるため、1 xor 2 xor 3=0になると、魔法の相殺が発生し、杖が得られない.最適なスキームは,20+30=50の法力を有する後の2つの鉱石を選択することであることが分かった.
すべてのデータについて:N≦1000,Numberi≦10^18,Magici≦10^4.
欲張りで、valueに従って大きくから小さく並べ替えてから線形基に挿入すれば答えが得られることを証明する(偽)私たちは先に並べ替えを行い、番号はa[1]からa[n]で、価値はv[1]からv[n]でまずa[1]が必ず答えの中でここで反証仮定で答えはa[k 1]、a[k 2],...,a[km]a[1]は中でa[1]がいくつかの線形表現であることを説明しないでa[1]=a[ki 1]^a[ki 2]^…^a[kix]では、右側のもう一つをa[1]で置き換えることで、すべての線形関係なくa[1]の価値が右側のいずれかよりも大きいようにすることができるので、a[1]は必ず答えの中でa[j]を考慮し、a[j]がa[1]からa[j-1]の数線形で表すことができれば、a[j]は決して好ましくなく、答えを加えない場合、すなわちa[j]線形基に挿入できないa[j]がa[1]からa[j-1]における数線形で表されない場合、すなわちa[j]が線形基に挿入できる場合、a[j]が答えでなければ、a[j]は必ずa[1]からa[j-1]とa[j+1]からa[n]の数線形で表され、a[j+1]からa[n]のうち少なくとも1つが存在する場合、この数をa[j]で置き換えることができる.すべての数の異種または0でないa[j]の価値をa[j+1]からa[n]のいずれかよりも大きくすることができるので、a[j]が線形基を挿入できれば、必ず答えの中にまとめられます.valueに従って大きい順に線形基を挿入し、挿入できるものをansに積算すればいいだけです.
#include
using namespace std;
struct magic
{
long long x;
int v;
bool operator y.v;
}
}a[1001];
int n,cnt;
long long p[64],d[64];
long long ans;
inline void guass()
{
memset(d,0,sizeof(d));
int i,j;
for(i=1;i<=n;i++)
{
for(j=63;j>=0;j--)
{
if((a[i].x>>j)&1)
{
if(d[j])
a[i].x^=d[j];
else
{
d[j]=a[i].x;
ans+=a[i].v;
break;
}
}
}
}
}
int main()
{
scanf("%d",&n);
int i;
for(i=1;i<=n;i++)
scanf("%lld%d",&a[i].x,&a[i].v);
sort(a+1,a+1+n);
guass();
printf("%lld
",ans);
return 0;
}