2019 BUAA Spring Training 15 题解

Solved	A	B	C	D	E	F	G	H	I	J	K	L
6/12	.	.	.	.	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 HDU 6426 - Alkane

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

B HDU 6427 - Beads

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

C HDU 6428 - Calculate

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

D HDU 6429 - Permutation

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

E HDU 6430 - TeaTree

题目描述

给一棵树，每个节点有一个权值，某点的答案为该点任意两棵子树上的任意两点的$gcd$的最大值。求这个答案。

解题思路

观察到权值最大在$100000$以内，故将每一个点上建立一个权值的集合，$dfs$的过程不断合并即可。$set$的常数太大，用$vector$存，二路归并的思想合并同时计算答案即可。

AC代码

点击

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+23;
const int N=1e5+2;
int n,m;
int v[maxn],ans[maxn],cnt[maxn],f[maxn];
int exi[maxn];
vector<int>fac[maxn],thi[maxn],g[maxn];
void uni(int a,int b){
    int i,j;
    vector<int>p;
    for(i=0,j=0;i<thi[a].size()&&j<thi[b].size();){
        int x1=thi[a][i],x2=thi[b][j];
        if(x1<x2)p.push_back(x1),i++;
        else if(x1>x2)p.push_back(x2),j++;
        else p.push_back(x1),i++,j++,ans[a]=max(ans[a],x1);
    }
    while(i<thi[a].size())p.push_back(thi[a][i]),i++;
    while(j<thi[b].size())p.push_back(thi[b][j]),j++;
    thi[a]=p;
}
void dfs(int x){
    int i;
    for(i=0;i<g[x].size();i++){
        int q=g[x][i];
        dfs(q);
        uni(x,q);
    }
}
int main(){
    int n,i,j;
    scanf("%d",&n);
    for(i=2;i<=n;i++){
        scanf("%d",&m);
        cnt[m]++;f[i]=m;
        g[f[i]].push_back(i);
    }
    for(i=1;i<=n;i++)scanf("%d",v+i);
    for(i=1;i<maxn;i++)for(j=i;j<maxn;j+=i)fac[j].push_back(i);
    for(i=1;i<=n;i++)thi[i]=fac[v[i]];
    memset(ans,-1,sizeof(ans));
    dfs(1);
    for(i=1;i<=n;i++)printf("%d\n",ans[i]);
}

F HDU 6431 - NewNippori

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

G HDU 6432 - Cyclic

题目描述
求长度为$n$的环排列$(0,1,…,n-1)$中，不包含$(a_i+1-a_{(i+1)%n})%n=0$（下面称这个为相邻递增）的个数。

解题思路
环排列一共有$(n-1)!$种。

至少有两个相邻递增的种类数为$C_n^1(n-2)!$，即$n$种两个相邻递增中选择一个，合并在一起后进行$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
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int mod=998244353;
ll fac[100010]={1,1},inv[100010]={1,1};
ll c(int n,int m){return fac[n]*inv[m]%mod*inv[n-m]%mod;}
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;
}
int main(){
    int i,j,t,n;
    for(i=2;i<100010;i++)fac[i]=fac[i-1]*i%mod,inv[i]=qp(fac[i],mod-2);
    scanf("%d",&t);
    for(i=0;i<t;i++){
        scanf("%d",&n);
        ll ans=0,now=-1;
        for(j=0;j<n;j++){
            now=now*-1;
            (ans+=now*c(n,j)*fac[n-1-j])%=mod;
        }
        (ans+=now*-1+mod)%=mod;
        printf("%lld\n",(ans%mod+mod)%mod);
    }
    return 0;
}

H HDU 6433 - Pow

题目描述

从$3^0,3^1,…,3^n-1$中任选子集加成一个新数，问有多少种可能，$n\leq 1000$。

解题思路

输出$2^n$即可，用$JAVA$可过。

AC代码

点击

import java.math.BigDecimal;
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner s=new Scanner(System.in);
        int t=s.nextInt();
        while(t>0){
            t--;
            int n=s.nextInt();
            BigDecimal res=new BigDecimal(2);
            System.out.println(res.pow(n));
        }
    }
}

I HDU 6434 - Count

题目描述
$n\leq 2e7$，$T\leq 1e5$组数据，求$\sum_{i=1}^n\sum_{j=1}^{i-1}[gcd(i+j,i-j)==1]$。

解题思路
$\sum_{i=1}^n\sum_{j=1}^{i-1}[gcd(i+j,i-j)==1]$

$=\sum_{i=1}^n\sum_{j=1}^{i-1}[gcd(i+j,2j)==1]$

$=\sum_{i=1}^n\sum_{j=1}^{i-1}[gcd(i+j,j)==1\space and\space (i+j) \ &1]$

$=\sum_{i=1}^n\sum_{j=1}^{i-1}[gcd(i,j)==1\space and\space (i+j)\ &1]$

分类讨论，$i$为偶数时，所有偶数$j$都有$gcd(i,j)!=1$，故贡献为$\phi(i)$；$i$为奇数时，假设$gcd(i,j)==1$，则$gcd(i,i-j)==1$，$i$与$i-j$奇偶性相反，故贡献为$\frac{\phi(i)}2$。

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 20000000
int prime[N],a[N+10]={1,1},cnt;
ll phi[N+10];
void sieve(){
    int i,j;
    for(i=2;i<N;i++){
        if(!a[i])prime[++cnt]=i,phi[i]=i-1;
        for(j=1;j<=cnt&&prime[j]*i<N;j++){
            a[prime[j]*i]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
    for(i=1;i<N;++i){
        if(i&1)phi[i]>>=1;
        phi[i]+=phi[i-1];
    }
}
int main(){
    int t,i,n;
    sieve();
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        printf("%lld\n",phi[n]);
    }
    return 0;
}

J HDU 6435 - CSGO

题目描述

武器$i$有两类属性，$S_i$和${a_{ij}}(1\leq j\leq k)$。有两种武器，要从每一种武器中各选出一个$A,B$配合使用，威力为$S_A+S_B+\sum_{i=1}^{k}|x_{Ai}-x_{Bi}|$，最大化威力。$k\leq 5$。

解题思路

直接去绝对值号，正负用$0/1$表示，观察到$k\leq 5$，直接状态压缩即可。

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 100010
#define K 7
ll s[N],x[N][K],s2[N],x2[N][K];
ll sit[1<<K];
int main(){
    int i,t,n,m,k,j,l;
    scanf("%d",&t);
    while(t--){
        ll ans=0;
        memset(sit,0,sizeof(sit));
        scanf("%d%d%d",&n,&m,&k);
        int S=1<<k;
        for(i=0;i<n;i++){
            scanf("%lld",&s[i]);
            for(j=0;j<k;j++)scanf("%lld",&x[i][j]);
            for(j=0;j<S;j++){
                ll now=s[i];
                for(l=0;l<k;l++){
                    if(j&(1<<l))now+=x[i][l];
                    else now-=x[i][l];
                }
                sit[j]=max(sit[j],now);
            }
        }
        for(i=0;i<m;i++){
            scanf("%lld",&s2[i]);
            for(j=0;j<k;j++)scanf("%lld",&x2[i][j]);
            for(j=0;j<S;j++){
                ll now=s2[i];
                for(l=0;l<k;l++){
                    if(j&(1<<l))now-=x2[i][l];
                    else now+=x2[i][l];
                }
                ans=max(ans,now+sit[j]);
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

K HDU 6436 - Pow2

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

L HDU 6437 - Videos

题目描述

电影有$AB$两种类型，现在给出$m$个电影的起止时间、观看获得的收益$w$，类型$op(0/1)$，有$k$个人，每个电影只能被一个人看，一个人在上一个电影结束时刻之前不能看别的电影，电影必须完整看完。如果一个人相邻两次看电影是相同类型的，那么他额外损失$W(W\leq w)$。求这些人能获得的最大收益。

解题思路

显然，人数越多越优。于是问题变成了以人数为流量、负收益为费用的最小费用最大流。

建图：

$S\rightarrow temp$，流量$k$，费用$0$
$temp\rightarrow i$，流量$1$，费用$0$
$i\rightarrow i+m$，流量$1$，费用$-w_i$
$i+m\rightarrow j$，流量$1$，费用$W$（$i.T\leq j.S$）
$i+m\rightarrow T$，流量$1$，费用$0$

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 10010
struct Edge{
    int e,l,c,n;
}e[N<<5];
int maxflow,mincost;
int hd[N],dis[N],flow[N],vis[N],cnt=1,s,t;
struct Pre{
    int pre,e;
}pre[N];
void add(int a,int b,int l,int c){
    e[++cnt].e=b;e[cnt].c=c;e[cnt].l=l;e[cnt].n=hd[a];hd[a]=cnt;
    e[++cnt].e=a;e[cnt].c=-c;e[cnt].l=0;e[cnt].n=hd[b];hd[b]=cnt;
}
queue<int>Q;
int spfa(){
    memset(dis,0x7f,sizeof(dis));
    memset(flow,0x7f,sizeof(flow));
    memset(vis,0,sizeof(vis));
    while(!Q.empty())Q.pop();
    int i,top,q;
    Q.push(s);vis[s]=1;dis[s]=0;pre[t].pre=0;
    while(!Q.empty()){
        top=Q.front();Q.pop();
        vis[top]=0;
        for(i=hd[top];i;i=e[i].n){
            q=e[i].e;
            if(e[i].l&&dis[q]>dis[top]+e[i].c){
                dis[q]=dis[top]+e[i].c;
                pre[q].pre=top;
                pre[q].e=i;
                flow[q]=min(flow[top],e[i].l);
                if(!vis[q]){
                    vis[q]=1;
                    Q.push(q);
                }
            }
        }
    }
    return pre[t].pre;
}
void ek(){
    int i;
    while(spfa()){
        maxflow+=flow[t];
        mincost+=flow[t]*dis[t];
        for(i=t;i!=s;i=pre[i].pre){
            e[pre[i].e].l-=flow[t];
            e[pre[i].e^1].l+=flow[t];
        }
    }
}
struct VIDEO{
    int S,T,W,op;
}v[N];
int main(){
    int i,j,n,m,T,k,w;
    scanf("%d",&T);
    while(T--){
        memset(hd,0,sizeof(hd));cnt=1;mincost=maxflow=0;
        scanf("%d%d%d%d",&n,&m,&k,&w);
        for(i=0;i<m;i++)scanf("%d%d%d%d",&v[i].S,&v[i].T,&v[i].W,&v[i].op);
        s=2*m;t=s+1;int tmp=t+1;
        add(s,tmp,k,0);
        for(i=0;i<m;i++)
            add(tmp,i,1,0),add(i,i+m,1,-v[i].W),add(i+m,t,1,0);
        for(i=0;i<m;i++){
            for(j=0;j<m;j++){
                if(i==j)continue;
                if(v[i].T<=v[j].S)add(i+m,j,1,v[i].op==v[j].op?w:0);
            }
        }
        ek();
        printf("%d\n",-mincost);
    }
    return 0;
}