Solved
A
B
C
D
E
F
G
H
I
J
K
6/11
O
O
.
.
.
O
O
O
.
O
.
O for passing during the contest
Ø for passing after the contest
! for attempted but failed
· for having not attempted yet
比赛链接
A - XOR
题目描述给一个序列$a_i$和一个正整数$k$，$Q$次询问，每次询问一个区间$l,r$，求该区间中任取元素集合的异或和$v$与$k$取或（$v|k$）的最大值。
解题思路先不考虑$k$，考虑求区间异或和最大值，显然用线段树合并线性基即可求解。
考虑$k$的每一位，如果为$1$，则这一位在最终结果必然为$1$，故线性基中可以不考虑这一位，把所有的数这一位都置为$0$。其他位对线性基没有影响，照常取最大值即可。
我们发现这是一个对$k$取反变成$k’$，再把每个数与$k’$取与的操作。
线段树+线性基合并即可。复杂度$O(Pn+QP^3)$，$P=27$。
AC代码点击
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#includetypedef long long ll;using namespace std;#define N 40010#define P 28#define mid ((l+r)>>1)struct linebase{ int bas[2+P]; void clear(){memset(bas,0,sizeof(bas));} void insert(int x){ int i; for(i=P;i>=0;i--){ if(!(x&(1<=0;i--)if(a.bas[i])b.insert(a.bas[i]); return b;}int a[N];void build(int p,int l,int r){ L[p]=l;R[p]=r; t[p].clear(); if(l==r){ t[p].insert(a[l]); return; } build(p<<1,l,mid); build(p<<1|1,mid+1,r); t[p]=merge(t[p<<1],t[p<<1|1]);}linebase query(int p,int l,int r){ if(L[p]>=l&&R[p]<=r)return t[p]; if(!L[p]||L[p]>r||R[p]=0;i--)ans=max(ans,ans^cur.bas[i]); printf("%d\n",ans); } } return 0;}
B - Lovers
题目描述有两个数列$a_i,b_i$，$a_i+b_j\geq k$则$i,j$可匹配。每个$i$最多只能配对一个$j$，反之亦然，问最多能够匹配多少对。
解题思路问题转化成$a_i \geq c_j=(k-b_j)$，排序双指针模拟即可。
AC代码点击
1234567891011121314151617181920212223#includetypedef long long ll;using namespace std;#define N 200010int n,k,a[N],b[N];int main(){ int i,t; scanf("%d",&t); while(t--){ int ans=0; scanf("%d%d",&n,&k); for(i=0;i=b[r])ans++,l++,r++; else l++; } printf("%d\n",ans); } return 0;}
C - Naomi with Array
题目描述解题思路AC代码点击
12
D - Islands
题目描述解题思路AC代码点击
12
E - Naomi with Graph
题目描述解题思路AC代码点击
12
F - God of Gamblers
题目描述有一个赌博游戏，你有$n$个$RMB$，对方有$m$个$RMB$，从$1$个$RMB$开始赌起，每次每个人胜利的概率均为$50%$，如果某个人在赌注为$i$的时候输了，这$i$个$RMB$都归对方，两方都会拿出$2i$的$RMB$继续下一轮赌博。当某个人没有$RMB$时，对方获胜。问你获胜的概率是多少。
解题思路不会做，但感觉是个很公平的游戏，输出$\frac {n}{n+m}$即可。
AC代码点击
12345678#includetypedef long long ll;using namespace std;int main(){ int n,m; while(~scanf("%d%d",&n,&m))printf("%.5f\n",1.0*n/(n+m)); return 0;}
G - Sum of xor sum
题目描述给一个数列，每次询问一个区间$[l,r]$中的所有连续子区间异或和的和是多少。
解题思路考虑拆位。
对于每一位，相当于询问在$[l,r]$区间内有多少个不同的连续子区间，其总$1$的个数为奇数（或者说：异或和为$1$）。
考虑用线段树维护这个数据。要进行合并操作，还需要维护区间的异或和、前缀后缀各有多少个异或和为$0/1$的子区间。
AC代码点击
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#includetypedef long long ll;using namespace std;#define N 100010#define mid ((l+r)>>1)int mod=1000000007;struct Data{ ll sub[2],pre[2],suf[2],sum; friend Data operator+(const Data &a,const Data&b){ Data tmp; tmp.sum=a.sum^b.sum; tmp.sub[0]=a.sub[0]+b.sub[0]+a.suf[0]*b.pre[0]+a.suf[1]*b.pre[1]; tmp.sub[1]=a.sub[1]+b.sub[1]+a.suf[0]*b.pre[1]+a.suf[1]*b.pre[0]; tmp.pre[0]=a.pre[0]; tmp.pre[1]=a.pre[1]; if(!a.sum)tmp.pre[0]+=b.pre[0],tmp.pre[1]+=b.pre[1]; else tmp.pre[0]+=b.pre[1],tmp.pre[1]+=b.pre[0]; tmp.suf[0]=b.suf[0]; tmp.suf[1]=b.suf[1]; if(!b.sum)tmp.suf[0]+=a.suf[0],tmp.suf[1]+=a.suf[1]; else tmp.suf[0]+=a.suf[1],tmp.suf[1]+=a.suf[0]; for(int i=0;i<2;i++)tmp.sub[i]%=mod,tmp.pre[i]%=mod,tmp.suf[i]%=mod; return tmp; }}emp,tr[21][N<<2];int L[N],R[N],a[N];void build(int p,int l,int r,int x){ L[p]=l;R[p]=r; if(l==r){ int y=(a[l]>>x)&1; if(y)tr[x][p]=(Data){{0,1},{0,1},{0,1},1}; else tr[x][p]=(Data){{1,0},{1,0},{1,0},0}; return; } build(p<<1,l,mid,x); build(p<<1|1,mid+1,r,x); tr[x][p]=tr[x][p<<1]+tr[x][p<<1|1];}Data query(int p,int l,int r,int x){ if(l>=L[p]&&r<=R[p])return tr[x][p]; if(l>R[p]||r
H - Arrangement for Contests
题目描述给定每个难度的题的个数，问最多能出多少套题。难度连续的$k$个题可以出成套题。
解题思路贪心，每次找到区间最小值删除并更新答案，用线段树维护即可。
AC代码点击
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#includetypedef long long ll;using namespace std;#define N 400010#define mid ((l+r)>>1)int tr[N],L[N],R[N],mn[N],lazy[N],a[N];void pushdown(int x){ if(!lazy[x])return; int t=lazy[x]; if(L[x<<1])lazy[x<<1]+=t,mn[x<<1]-=t; if(L[x<<1|1])lazy[x<<1|1]+=t,mn[x<<1|1]-=t; lazy[x]=0;}void build(int l,int r,int p){ L[p]=l;R[p]=r; lazy[p]=mn[p]=0; if(l==r){ mn[p]=a[l]; return; } build(l,mid,p<<1); build(mid+1,r,p<<1|1); mn[p]=min(mn[p<<1],mn[p<<1|1]);}int query(int l,int r,int p){ if(l<=L[p]&&R[p]<=r)return mn[p]; if(R[p]r)return 1e9; pushdown(p); return min(query(l,r,p<<1),query(l,r,p<<1|1));}void modify(int l,int r,int p,int x){ pushdown(p); if(L[p]>=l&&R[p]<=r){ lazy[p]+=x; mn[p]-=x; return; } int m=(L[p]+R[p])>>1; if(m>=l)modify(l,r,p<<1,x); if(m+1<=r)modify(l,r,p<<1|1,x); mn[p]=min(mn[p<<1],mn[p<<1|1]);}int main(){ int i,t,n,k; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&k); for(i=1;i<=n;i++)scanf("%d",&a[i]); int l=1,r=k,ans=0; build(1,n,1); while(1){ int mn; while(r<=n&&(mn=query(l,r,1))<=0)l++,r++; if(r>n)break; ans+=mn; modify(l,r,1,mn); } printf("%d\n",ans); } return 0;}
I - Acedia
题目描述解题思路AC代码点击
12
J - LOL
题目描述一共$100$个英雄，我方五人，敌方五人，每人可以选择一个英雄、禁掉一个英雄，这$20$个英雄互不相同。已知敌方什么英雄都能选，而我方英雄只能从给定输入里的$1$中挑选。问有多少种方案。
解题思路枚举我方前四个人的选法，第五个人的选法可以由此确定下来，设总方案数为$p$。我方英雄选好后，敌方可以有顺序选$5$个英雄，我方和敌方可无顺序选$5$个英雄禁掉。故答案为$p\times A_{95}^5\times C_{90}^5\times C_{85}^5$。
AC代码点击
12345678910111213141516171819202122232425262728293031323334353637383940414243444546#includetypedef long long ll;using namespace std;char a[5][110];int vis[110];int mod=1000000007,ans;void dfs(int x,int s){ int i,tmp; if(x==4){ (ans+=s)%=mod; return; } for(i=0;i<100;i++)if(a[x][i]=='1'&&!vis[i]){ tmp=s; vis[i]=1; if(a[4][i]=='1')tmp--; dfs(x+1,tmp); vis[i]=0; }}int fac[110]={1},inv[110]={1};int c(int n,int m){ return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod;}int A(int n,int m){ return 1LL*fac[n]*inv[n-m]%mod;}int qp(ll x,int p){ ll ans=1; for(;p;p>>=1,x=x*x%mod)if(p&1)ans=ans*x%mod; return ans;}int main(){ int i,s=0; for(i=1;i<100;i++){ fac[i]=1LL*fac[i-1]*i%mod; inv[i]=qp(fac[i],mod-2); } while(~scanf("%s%s%s%s%s",a[0],a[1],a[2],a[3],a[4])){ s=0;ans=0; for(i=0;i<100;i++)if(a[4][i]=='1')s++; dfs(0,s); printf("%d\n",1LL*ans*A(95,5)%mod*c(90,5)%mod*c(85,5)%mod); } return 0;}
K LOVER II
题目描述解题思路AC代码点击
12
L
题目描述解题思路AC代码点击
12
M
题目描述解题思路AC代码点击
12