按价值从大到小考虑每个元素,维护一个线性基,如果向其中加入该元素的编号仍然构成线性基,则将其加入。
不会证明。当做线性基的一个性质吧。
#include#include #include #include #include #include using namespace std;#define ll long long#define N 1010ll read(){ ll x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,ans;ll base[63];struct data{ ll x;int v; bool operator <(const data&a) const { return v>a.v; }}a[N];int main(){#ifndef ONLINE_JUDGE freopen("bzoj2460.in","r",stdin); freopen("bzoj2460.out","w",stdout); const char LL[]="%I64d\n";#else const char LL[]="%lld\n";#endif n=read(); for (int i=1;i<=n;i++) a[i].x=read(),a[i].v=read(); sort(a+1,a+n+1); for (int i=1;i<=n;i++) for (int j=62;~j;j--) if (a[i].x&(1ll<