ACM-ICPC 2017 现场赛(西安) 题解

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代码

点击

#include<bits/stdc++.h>
typedef 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<<i)))continue;
            if(!bas[i]){
                bas[i]=x;
                return;
            }
            x^=bas[i];
        }
    }
}empty,t[N];
int L[N],R[N];
linebase merge(linebase a,linebase b){
    int i;
    for(i=P;i>=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]<l)return empty;
    return merge(query(p<<1,l,r),query(p<<1|1,l,r));
}
int main(){
    int i,T;
    scanf("%d",&T);
    empty.clear();
    while(T--){
        int n,q,k;
        memset(L,0,sizeof(L));
        memset(R,0,sizeof(R));
        scanf("%d%d%d",&n,&q,&k);
        k=~k;
        for(i=1;i<=n;i++){
            scanf("%d",&a[i]);
            a[i]&=k;
        }
        k=~k;
        build(1,1,n);
        while(q--){
            int l,r,ans=k;
            scanf("%d%d",&l,&r);
            linebase cur=query(1,l,r);
            for(i=P;i>=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代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 200010
int 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<n;i++)scanf("%d",&a[i]);
        for(i=0;i<n;i++)scanf("%d",&b[i]),b[i]=k-b[i];
        sort(a,a+n);sort(b,b+n);
        int r=0,l=0;
        while(l<n&&r<n){
            if(a[l]>=b[r])ans++,l++,r++;
            else l++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

C - Naomi with Array

题目描述
解题思路
AC代码
点击
1
2

D - Islands

题目描述
解题思路
AC代码
点击
1
2

E - Naomi with Graph

题目描述
解题思路
AC代码
点击
1
2

F - God of Gamblers

题目描述
有一个赌博游戏，你有$n$个$RMB$，对方有$m$个$RMB$，从$1$个$RMB$开始赌起，每次每个人胜利的概率均为$50%$，如果某个人在赌注为$i$的时候输了，这$i$个$RMB$都归对方，两方都会拿出$2i$的$RMB$继续下一轮赌博。当某个人没有$RMB$时，对方获胜。问你获胜的概率是多少。

解题思路
不会做，但感觉是个很公平的游戏，输出$\frac {n}{n+m}$即可。

AC代码
点击
1
2
3
4
5
6
7
8
#include<bits/stdc++.h>
typedef 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代码

点击

#include<bits/stdc++.h>
typedef 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<L[p])return emp;
    return query(p<<1,l,r,x)+query(p<<1|1,l,r,x);
}
int main(){
    int i,T,n,q;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&q);
        for(i=1;i<=n;i++)scanf("%d",&a[i]);
        for(i=0;i<20;i++)build(1,1,n,i);
        while(q--){
            ll ans=0;
            int l,r;
            scanf("%d%d",&l,&r);
            for(i=0;i<20;i++)
                (ans+=(1LL<<i)*query(1,l,r,i).sub[1]%mod)%=mod;
            printf("%lld\n",ans);
        }
    }
    return 0;
}

H - Arrangement for Contests

题目描述

给定每个难度的题的个数，问最多能出多少套题。难度连续的$k$个题可以出成套题。

解题思路

贪心，每次找到区间最小值删除并更新答案，用线段树维护即可。

AC代码

点击

#include<bits/stdc++.h>
typedef 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]<l||L[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代码
点击
1
2

J - LOL

题目描述

一共$100$个英雄，我方五人，敌方五人，每人可以选择一个英雄、禁掉一个英雄，这$20$个英雄互不相同。已知敌方什么英雄都能选，而我方英雄只能从给定输入里的$1$中挑选。问有多少种方案。

解题思路

枚举我方前四个人的选法，第五个人的选法可以由此确定下来，设总方案数为$p$。我方英雄选好后，敌方可以有顺序选$5$个英雄，我方和敌方可无顺序选$5$个英雄禁掉。故答案为$p\times A_{95}^5\times C_{90}^5\times C_{85}^5$。

AC代码

点击

#include<bits/stdc++.h>
typedef 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代码
点击
1
2

L

题目描述
解题思路
AC代码
点击
1
2

M

题目描述
解题思路
AC代码
点击
1
2