实际得分：100+0+0=100
T1
右上角是必败态，然后推下去
发现同行全是必胜态或全是必败态，不同行必胜必败交叉
列同行
所以n，m 只要有一个是偶数，先手必胜
#include<cstdio> using namespace std; int main()
{
freopen("star.in","r",stdin);
freopen("star.out","w",stdout);
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(!n) return ;
if(!(n&) || !(m&)) puts("Yuri");
else puts("Chito");
}
}
T2
k=1 暴力：
可持久化trie树 求 异或最大值
#include<cstdio>
#include<iostream>
#include<algorithm> #define N 50001 const int mod=1e9+; using namespace std; int bit[]; int a[N]; int root[N],ch[N*][],cnt[N*],tot; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void insert(int pre,int &now ,int dep,int x)
{
if(!now) now=++tot;
cnt[now]=cnt[pre]+;
if(dep<) return;
int p= (x&bit[dep])>;
ch[now][p^]=ch[pre][p^];
insert(ch[pre][p],ch[now][p],dep-,x);
} int query(int pre,int k,int dep,int x)
{
if(dep<) return ;
int p= (x&bit[dep])>;
if(cnt[ch[k][p^]]-cnt[ch[pre][p^]]) return bit[dep]+query(ch[pre][p^],ch[k][p^],dep-,x);
return query(ch[pre][p],ch[k][p],dep-,x);
} int main()
{
freopen("war.in","r",stdin);
freopen("war.out","w",stdout);
bit[]=;
for(int i=;i<=;++i) bit[i]=bit[i-]<<;
int n,k;
read(n); read(k);
for(int i=;i<=n;++i)
{
read(a[i]);
insert(root[i-],root[i],,a[i]);
}
int ans=;
for(int i=;i<=n;++i) ans=max(ans,query(root[],root[n],,a[i]));
cout<<ans%mod;
}
所有数不超过1023暴力：
预处理所有 i^j的结果，cnt[i]表示第i个数的个数
这样每一种 异或 值出现的次数=cnt[i]*cnt[j]
从大到小枚举，直至k个即可
#include<cstdio>
#include<iostream>
#include<algorithm> #define N 50001 const int mod=1e9+; using namespace std; int cnt[]; struct node
{
int i,j,y;
}e[*+]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} bool cmp(node p,node q)
{
return p.y>q.y;
} int main()
{
freopen("war.in","r",stdin);
freopen("war.out","w",stdout);
int n,x; long long k;
read(n); scanf("%I64d",&k);
for(int i=;i<=n;++i) read(x),cnt[x]++;
int tot=;
for(int i=;i<;++i)
for(int j=i+;j<;++j)
e[++tot].i=i,e[tot].j=j,e[tot].y=i^j;
sort(e+,e+tot+,cmp);
int ans=;
for(int i=;i<=tot;++i)
{
ans=(ans+min(k,1ll*cnt[e[i].i]*cnt[e[i].j])*e[i].y%mod)%mod;
k-=min(k,1ll*cnt[e[i].i]*cnt[e[i].j]);
if(!k) break;
}
cout<<ans;
}
满分做法：
二分出一个最大的t，t满>t的数至少有k个
然后查询所有异或值 >t 的数的和，最后在减去 属于前k大的数的和
二分检验与查询均在trie树上进行
查询>t的数的个数：
枚举n个数a[i]，累积 与每一个a[i] 异或后 >t 的个数
对于每一个a[i]，设现在是第j位
如果t的第j位是0，那么累加第j位与a[i] 不同 的数的个数，trie树上的当前位置转到 第j位与a[i] 的第j位相同的位置
因为所以在第j位就分出大小的数都以累加，继续找第j位分不出大小的数
如果t的第j位是1，什么都不累加，trie树上的当前位置 转到 第j位与a[i] 不同的 位置
因为如果这一位与t的第j位相同，异或得0，一定<t，如果不同，第j位 分不出大小，继续往后走
累积所有>t的数的和：
还是枚举n个数a[i]，累积 与每一个 a[i] 异或后>t 的数的和
累积方法思路与上面差不多
如果t的第j位是0，那么就累计 当前位置 所有的与a[i] 异或 为1的数的和，当前位置转到 与a[i]的第j位相同的位置
如果t的第j为是1，那么当前位置 转到与a[i]的第j位不同的位置
注意每一对合法的数会使用两次，所以累计个数 和 总和 时 注意 除以2
#include<cstdio>
#include<iostream> using namespace std; #define N 50001 const int mod=1e9+;
const int inv=5e8+; long long k; int n; int a[N],trie[N*][],all[N*][],tot=; int cnt[N*]; int bit[]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void insert(int x)
{
int now=,d;
for(int i=;i>=;--i)
{
d=(x&bit[i])>;
if(!trie[now][d]) trie[now][d]=++tot;
now=trie[now][d];
cnt[now]++;
for(int j=;j>=;--j)
if(x&bit[j]) all[now][j]++;
}
} int upper(int x,int t)
{
int pos=,d,sum=;
for(int i=;i>=;--i)
{
d=(x&bit[i])>;
if(!(t&bit[i])) sum+=cnt[trie[pos][d^]],pos=trie[pos][d];
else pos=trie[pos][d^];
// if(t==754974719 && x==962029906) cout<<i<<' '<<sum<<' '<<trie[pos][d^1]<<'\n';
}
return sum;
} int query(int x,int t)
{
int pos=,d,sum=;
for(int i=;i>=;--i)
{
d=(x&bit[i])>;
if(!(t&bit[i]))
{
for(int j=;j>=;--j)
if(x&bit[j]) sum=(sum+1LL*(cnt[trie[pos][d^]]-all[trie[pos][d^]][j])*bit[j]%mod)%mod;
else sum=(sum+1LL*all[trie[pos][d^]][j]*bit[j]%mod)%mod;
pos=trie[pos][d];
}
else pos=trie[pos][d^];
}
//cout<<sum<<'\n';
return sum; } long long check(int x)
{
long long sum=;
for(int i=;i<=n;i++)
{
sum+=upper(a[i],x);
//if(x==754974719) cout<<i<<' '<<sum<<'\n';
}
return sum/;
} int main()
{
freopen("war.in","r",stdin);
freopen("war.out","w",stdout);
read(n); scanf("%I64d",&k);
bit[]=;
for(int i=;i<=;++i) bit[i]=bit[i-]<<;
for(int i=;i<=n;++i)
{
read(a[i]);
insert(a[i]);
// cout<<i<<' '<<tot<<'\n';
}
int l=,r=,mid,tmp=-;
while(l<=r)
{
mid=l+r>>;
if(check(mid)>=k) l=mid+,tmp=mid;
else r=mid-;
// cout<<mid<<' '<<check(mid)<<'\n';
}
int ans=;
if(tmp!=-)
{
long long res=k-check(tmp);
for(int i=;i<=n;i++)
{
ans+=query(a[i],tmp),ans%=mod;
// cout<<ans<<'\n';
}
ans=1LL*ans*inv%mod;
ans=(ans+1LL*res*(tmp+)%mod)%mod;
}
else
{
for(int i=;i<=n;i++) ans+=query(a[i],),ans%=mod;
ans=1LL*ans*inv%mod;
}
cout<<ans;
//for(int i=1;i<=tot;i++) cout<<i<<' '<<cnt[i]<<'\n';
}
T3
因为k<=10 所以线段树维护区间前10大
合并的时候，用了类似于归并排序时用的 两个指针，扫一遍即可
#include<cstdio>
#include<cstring>
#include<iostream> using namespace std; #define N 100001 int f[N<<]; struct node
{
int mx[]; node() { memset(mx,,sizeof(mx));} node operator + (node p)
{
node t;
int a=,b=,c=;
while(c<=) t.mx[c++]=mx[a]>p.mx[b] ? mx[a++] : p.mx[b++];
return t;
}
}tr[N<<]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void build(int k,int l,int r)
{
if(l==r) { read(tr[k].mx[]); return; }
int mid=l+r>>;
build(k<<,l,mid);
build(k<<|,mid+,r);
tr[k]=tr[k<<]+tr[k<<|];
} void down(int k)
{
f[k<<]+=f[k];
f[k<<|]+=f[k];
for(int i=;i<=;++i)
{
if(tr[k<<].mx[i]) tr[k<<].mx[i]+=f[k];
if(tr[k<<|].mx[i]) tr[k<<|].mx[i]+=f[k];
}
f[k]=;
} node query(int k,int l,int r,int opl,int opr)
{
if(l>=opl && r<=opr) return tr[k];
if(f[k]) down(k);
int mid=l+r>>;
if(opr<=mid) return query(k<<,l,mid,opl,opr);
if(opl>mid) return query(k<<|,mid+,r,opl,opr);
return query(k<<,l,mid,opl,opr)+query(k<<|,mid+,r,opl,opr);
} void change(int k,int l,int r,int opl,int opr,int w)
{
if(l>=opl && r<=opr)
{
for(int i=;i<=;i++)
if(tr[k].mx[i]) tr[k].mx[i]+=w;
f[k]+=w;
return;
}
if(f[k]) down(k);
int mid=l+r>>;
if(opl<=mid) change(k<<,l,mid,opl,opr,w);
if(opr>mid) change(k<<|,mid+,r,opl,opr,w);
tr[k]=tr[k<<]+tr[k<<|];
} int main()
{
freopen("noname.in","r",stdin);
freopen("noname.out","w",stdout);
int n,m;
read(n); read(m);
build(,,n);
int op,l,r,w;
while(m--)
{
read(op); read(l); read(r); read(w);
if(!op)
{
if(r-l+<w) cout<<-<<'\n';
else cout<<query(,,n,l,r).mx[w]<<'\n';
}
else change(,,n,l,r,w);
}
}
错误：
将前10大全部放到一个结构体里，query时直接返回结构体
合并的时候 重载的 加号 运算符
所以 标记 不能放到 结构体里
下传标记的时候，只传前10大，但应先判断是否具有第i大