2019 BUAA Summer Training 1 题解

Solved	A	B	C	D	E	F	G	H	I	J
7/10	Ø	.	Ø	O	O	Ø	O	.	.	O

O for passing during the contest
Ø for passing after the contest
! for attempted but failed
· for having not attempted yet

题目来源：2018HDU多校第二场

比赛链接

A HDU 6309 - Absolute

题目描述
从原点出发，每次向$x$轴正向以等概率走$[l_i,r_i]$步（$-10^6\leq l_i\leq r_i\leq 10^6$），问最终离原点的距离期望。

解题思路
离原点距离可以分为$\sum x_i\geq 0,\sum x_i<0$两部分解决。

能到达的区间是$[\sum l_i,\sum r_i]$，显然如果这两个数同号则直接输出其平均值即可。

将每一次走法看做一个维度上的区间$x_i\in [0,r_i-l_i]$，设$a_i=r_i-l_i$，最终要求期望，可以先求概率，这个概率便是一个$n$维超体中经过一个$n-1$维超体的概率$P(n,x)$，其中$n-1$维超体方程为$x_1+x_2+…+x_n=x$。为方便求解，将问题全部转化为$n$维上的运算，即求一个$n-1$维超体上概率的前缀和$p(n,x)=\sum P(n,i)$。直观上理解这个前缀和，就是以原点为顶点的$n$维锥体。

好抽象，画个图理解。以二维为例：现在已知$0\leq x_1\leq a_1,0\leq x_2\leq a_2$，其中$x_1,x_2$为二维空间中的两个维度（平面直角坐标系中的$x,y$），显然这个区间代表的是一个矩形。那么$p(2,x)$代表的含义就是画一道$x_1+x_2=x$的直线，把这个矩形切下来的左下方的面积除以$a_1a_2$的大小。~~是不是很容易理解呀~~

这个面积显然可以用容斥求：我们假设$f(n,x)$为$n$维，$a_1=a_2=…=a_n=x$情况下的$p(n,x)$，对应二维也就是直角三角形面积比上正方形面积$\frac12$，三维就是三棱锥比上正方体体积$\frac16$，在$n$维情况下便是$\frac 1{n!}$，即$f(n,x)=\frac 1{n!}$。很容易在二维下面验证

$$s(2,x)=f(2,x)\cdot x^2-f(2,x-a_1)\cdot (x-a_1)^2-f(2,x-a_2)\cdot (x-a_2)^2+f(2,x-a_1-a_2)\cdot (x-a_1-a_2)^2$$

我们设$g(n,x)=f(n,x)\cdot x^n$，有

$$s(n,x)=g(n,x)-\sum_{i=1}^{n}g(n,x-a_i)+\sum_{i=1}^n\sum_{j=i+1}^{n}g(n,x-a_i-a_j)-…$$

于是，$p(n,x)=\frac{s(n,x)}{\prod a_i}$。

现在$p(n,x)$即为把原点移到$[-\sum l_i,0]$上后$[0,-\sum l_i]$上的概率前缀和（其实转化为了从$-\sum l_i$开始，每次走$[0,a_i]$长度后总共走的长度）。求一下这个$p$对应的期望：$E(n,x)=\int x\cdot p’(n,x)dx$，其中$p(n,x)$求导可以逐项进行，会转化成对$g(n,x)$求导。不妨将$p(n,x)$表示为$\sum g(n,x)=\sum\frac{x^n}{n!}$，则$E(n,x)=\int x\cdot \sum (\frac {x^n}{n!})’=\int \sum\frac{x^n}{(n-1)!}=\sum\frac{n\cdot x^{n+1}}{(n+1)!}$。转化成在原数轴上的期望，即为$xp(n,x)-E(n,x)=\sum\frac{x^{n+1}}{n!}-\frac{n\cdot x^{n+1}}{(n+1)!}=\sum \frac{x^{n+1}}{(n+1)!} $。

AC代码
点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 20
ll mod=998244353,inv[N];
int l[N],r[N],len[N],n;
ll qp(ll a,int p){
    ll ans=1;
    for(;p;p>>=1,a=a*a%mod)if(p&1)ans=ans*a%mod;
    return ans;
}
ll ie(int now,int sign,int sum){
    if(sum<=0)return 0;
    if(now>n)return qp(sum,n+1)*inv[n+1]%mod*(sign==-1?mod-1:1)%mod;
    return (ie(now+1,sign,sum)+ie(now+1,-sign,sum-len[now]))%mod;
}
int main(){
    int i;
    ll prod=1,ls=0,rs=0;
    inv[0]=1;
    for(i=1;i<N;i++)inv[i]=inv[i-1]*qp(i,mod-2)%mod;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d%d",&l[i],&r[i]);
        len[i]=r[i]-l[i];
        ls+=l[i];rs+=r[i];
        if(len[i])prod=prod*len[i]%mod;
    }
    if(ls>=0||rs<=0)printf("%lld",abs(ls+rs)*qp(2,mod-2)%mod);
    else printf("%lld",(((ie(1,1,-ls)+ie(1,1,rs))*qp(prod,mod-2)%mod)+mod)%mod);
    puts("");
    return 0;
}

B HDU 6310 - Counting Permutations

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

C HDU 6311 - Cover

题目描述

给一个非联通图，求用最少的笔数遍历所有边，每条边只能走一次。

解题思路

把度为奇数的点连上虚边，从度为奇数的点开始跑一下欧拉路，遇到虚边则断开即可。

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 100010
struct Edge{
    int e,n,del,sign,index;
}e[N<<4];
int hd[N],cnt;
int deg[N];
void add(int a,int b,int index,int sign){
    e[++cnt].e=b;e[cnt].n=hd[a];e[cnt].del=0;e[cnt].sign=sign;e[cnt].index=index;hd[a]=cnt;
    e[++cnt].e=a;e[cnt].n=hd[b];e[cnt].del=0;e[cnt].sign=sign;e[cnt].index=-index;hd[b]=cnt;
}
int vis[N],tot;
#define pb push_back
vector<int>ans[N];
void dfs(int p){
    vis[p]=1;
    int i;
    for(i=hd[p];i;i=e[i].n){
        int q=e[i].e;
        if(e[i].del)continue;
        e[i].del=e[i^1].del=1;
        dfs(q);
        if(e[i].sign)tot++;
        else ans[tot].pb(-e[i].index);
    }
}
int main(){
    int i,j,n,m,u,v;
    while(~scanf("%d%d",&n,&m)){
        memset(deg,0,sizeof(int)*(n+1));
        memset(vis,0,sizeof(int)*(n+1));
        memset(hd,0,sizeof(int)*(n+1));cnt=1;
        for(i=1;i<=m;i++){
            scanf("%d%d",&u,&v);
            deg[u]++;deg[v]++;
            add(u,v,i,0);
        }
        int last=0;
        for(i=1;i<=n;i++){
            if(deg[i]&1){
                if(last)add(last,i,0,1),last=0;
                else last=i;
            }
        }
        tot=0;
        for(i=1;i<=n;i++)if(!vis[i]&&(deg[i]&1))tot++,dfs(i);
        for(i=1;i<=n;i++)if(!vis[i])tot++,dfs(i);
        int res=tot;
        for(i=1;i<=tot;i++)if(ans[i].size()==0)res--;
        printf("%d\n",res);
        for(i=1;i<=tot;i++){
            int sz=ans[i].size();
            if(!sz)continue;
            printf("%d ",sz);
            for(j=0;j<sz;j++)printf("%d ",ans[i][j]);
            ans[i].clear();
            puts("");
        }
    }
    return 0;
}

D HDU 6312 - Game

题目描述
一个游戏，每人选一个数，这个数的约数之后不能再被选，问谁能赢。

解题思路
若先手不选$1$必输，则选$1$后必胜；否则必胜。故永远先手必胜。

AC代码
点击
1
2
3
4
5
6
7
8
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
    int n;
    while(~scanf("%d",&n))printf("Yes\n");
    return 0;
}

E HDU 6313 - Hack It

题目描述
构造一个$2000\times 2000$的$01$矩阵，要求不存在一个四个角都为$1$的子矩阵，且$1$的个数$\geq 85000$。

解题思路
考虑一个$25\times 25$的矩阵：

$10000\space 10000\space 10000\space 10000\space 10000$

$10000\space 01000\space 00100\space 00010\space 00001$

$10000\space 00100\space 00001\space 01000\space 00010$

$10000\space 00010\space 01000\space 00001\space 00100$

$10000\space 00001\space 00010\space 00100\space 01000$

$01000\space 01000\space 01000\space 01000\space 01000$

$01000\space 00100\space 00010\space 00001\space 10000$

$01000\space 00010\space 10000\space 00100\space 00001$

$01000\space 00001\space 00100\space 10000\space 00010$

$01000\space 10000\space 00001\space 00010\space 00100$

……

分成$5\times 5$个格子，每个格子里填一个数字，通过同行不同构、每隔五行整体平移的方法保证不存在四个顶点都是$1$的矩形存在。

AC代码
点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int a[2500][2500];
int main(){
    int i,j,k,x=47;
    for(i=0;i<x;i++)for(j=0;j<x;j++)for(k=0;k<x;k++)a[i*x+j][k*x+(i+k*j)%x]=1;
    printf("2000\n");
    for(i=0;i<2000;i++){
        for(j=0;j<2000;j++)printf("%d",a[i][j]);
        puts("");
    }
    return 0;
}

F HDU 6314 - Matrix

题目描述
给一个$n\times m$的网格图，每一个格子可以涂为黑色或白色，$n$行中要求至少有$a$行全涂为黑色，$m$列中要求至少有$b$列全涂为黑色，问有多少种本质不同的涂色方案。

解题思路
设$g(x)$为恰好涂$x$行黑色，$m$列至少涂$b$列黑色的方案数，答案显然为$\sum_{i=a}^{n}g(i)$。

$g(x)=f(n-x,b)\cdot C_n^x-\sum_{i=x+1}^{n}g(i)\cdot C_i^x$，其中$f(x,i)$表示在$x$行的时候，$m$列至少涂$i$列的方案数。这个式子的意义是，在涂了$x$行黑色后，剩下的$x-i$列中任意涂的方案数中包括了总共涂多于$x$列黑色的情况。假设多算了恰好涂$y$列的情况，那么有$C_y^x$种重复的方案（选择涂$x$列的时候选择$y$列中的$x$列）。

再考虑求$f(x,i)$。设$h(n,i)$表示有$n$行的时候，$m$列恰好涂$i$列的方案数，显然$f(n,i)=\sum_{j=i}^mh(n,j)$。而$h(n,i)=C_m^i\cdot (2^{i}-1)^{m-i}$，即选择$i$列全部填满，剩下$m-i$列不能全部填满的种类数。

全都预处理出来之后，时间复杂度是$O(Tnm)$的，但会卡常……

AC代码
点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#pragma GCC optimize(2)
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 3005
const ll mod=998244353;
ll f[N],g[N];
int c[N][N];
int main(){
    int i,j,n,m,a,b;
    for(i=0;i<N;i++)c[i][0]=1;
    for(i=1;i<N;i++)for(j=1;j<N;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    while(~scanf("%d%d%d%d",&n,&m,&a,&b)){
        ll ans=1,x=0;
        for(i=1;i<=n-a;i++){
            f[i]=0;
            x=(x*2+1)%mod;ll now=1;
            for(j=m;j>=b;j--){
                (f[i]+=c[m][j]*now)%=mod;
                now=now*x%mod;
            }
        }
        g[n]=1;
        for(i=n-1;i>=a;i--){
            g[i]=f[n-i]*c[n][i]%mod;
            for(j=i+1;j<=n;j++)(g[i]-=g[j]*c[j][i])%=mod;
            ans+=g[i];
        }
        printf("%lld\n",(ans%mod+mod)%mod);
    }
    return 0;
}

G HDU 6315 - Naive Operations

题目描述

有两个数组$a,b$，$a$初始都为$0$，$b$初始为一个$1-n$的排列。有$q$次区间询问，每次有两种操作：区间所有$a_i$加$1$；求出区间$\lfloor\frac {a_i}{b_i}\rfloor$的和。

解题思路

建一棵维护区间和的线段树，再维护一棵维护每个数$b_i-a_i$的线段树，表示再加几次就能够向第一棵线段树中加一了。

第二棵线段树需要维护一个区间最小值，每次更新的时候把所有区间最小值小于等于零的进行更新即可。最多更新$n\log n$次叶子节点，每次更新复杂度为$O(\log n)$，时间复杂度$O(n\log ^2n)$。

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 400010
struct SegTree{
    int lazy,data;
}tr[N],res[N];
int b[N],n,q;
void pushdown(int p){//res
    int t=res[p].lazy;
    if(!t)return;
    res[p<<1].lazy+=t;
    res[p<<1].data-=t;
    res[p<<1|1].lazy+=t;
    res[p<<1|1].data-=t;
    res[p].lazy=0;
}
void build(int p,int l,int r){//build res,tr
    tr[p].lazy=tr[p].data=res[p].lazy=res[p].data=0;
    if(l==r){
        res[p].data=b[l];
        return;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    res[p].data=min(res[p<<1].data,res[p<<1|1].data);
}
void add(int p,int l,int r,int L,int R){//add a_i
    pushdown(p);
    if(l<=L&&R<=r){
        res[p].lazy++;
        res[p].data--;
        return;
    }
    if(R<l||L>r)return;
    add(p<<1,l,r,L,(L+R)>>1);
    add(p<<1|1,l,r,((L+R)>>1)+1,R);
    res[p].data=min(res[p<<1].data,res[p<<1|1].data);
}
void modify(int p,int l,int L,int R,int x){//tr
    tr[p].data+=x;
    if(L>=R)return;
    int mid=(L+R)>>1;
    if(mid>=l)modify(p<<1,l,L,mid,x);
    else modify(p<<1|1,l,mid+1,R,x);
}
void update(int p,int l,int r,int L,int R){//res--
    pushdown(p);
    if(L==R){
        int x=-res[p].data/b[L]+1;
        modify(1,L,1,n,x);
        res[p].data+=x*b[L];
        return;
    }
    if(res[p].data>0)return;
    if(res[p<<1].data<=0)update(p<<1,l,r,L,(L+R)>>1);
    if(res[p<<1|1].data<=0)update(p<<1|1,l,r,((L+R)>>1)+1,R);
    res[p].data=min(res[p<<1].data,res[p<<1|1].data);
}
int query(int p,int l,int r,int L,int R){
    if(L>=l&&R<=r)return tr[p].data;
    if(r<L||l>R)return 0;
    return query(p<<1,l,r,L,(L+R)>>1)+query(p<<1|1,l,r,((L+R)>>1)+1,R);
}
void print(){
    int i;
    for(i=1;i<10;i++){
        printf("%d:%d %d ;%d %d\n",i,tr[i].lazy,tr[i].data,res[i].lazy,res[i].data);
    }
    puts("");
}
int main(){
    int i;
    while(~scanf("%d%d",&n,&q)){
        for(i=1;i<=n;i++)scanf("%d",&b[i]);
        build(1,1,n);
        while(q--){
            char a[10]={0};
            int l,r;
            //print();
            scanf("%s%d%d",a,&l,&r);
            if(a[0]=='a')add(1,l,r,1,n);
            else{
                update(1,l,r,1,n);
                printf("%d\n",query(1,l,r,1,n));
            }
        }
    }
    return 0;
}

H HDU 6316 - Odd Shops

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

I HDU 6317 - Segment

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

J HDU 6318 - Swaps and Inversions

题目描述

给一个序列，序列中一对逆序对需要花费$x$，移动相邻两个元素位置花费$y$，问最小花费。

解题思路

最优选择下，移动相邻两个元素必然能使一个且只能使一个逆序对消失（显然），故答案为逆序对数乘$min(x,y)$。

$WA$一发原因：归并排序的时候忘记把右边段可能剩下的部分加上…（$19$行）

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,x,y,a[100010],tmp[100010];
ll calc(int l,int r){
    int i,j,mid=(l+r)>>1;
    if(l>=r)return 0;
    ll res=calc(l,mid)+calc(mid+1,r);
    i=l,j=mid+1;
    int cnt=0;
    for(i=l;i<=mid;i++){
        while(j<=r&&a[i]>a[j]){
            tmp[cnt++]=a[j];
            j++;
        }
        res+=j-mid-1;
        tmp[cnt++]=a[i];
    }
    while(j<=r)tmp[cnt++]=a[j],j++;
    for(i=l;i<=r;i++)a[i]=tmp[i-l];
    return res;
}
int main(){
    int i;
    while(~scanf("%d%d%d",&n,&x,&y)){
        for(i=1;i<=n;i++)scanf("%d",&a[i]);
        ll num=calc(1,n);
        if(x>y)printf("%lld\n",num*y);
        else printf("%lld\n",num*x);
    }
    return 0;
}