2020牛客暑期多校训练营(第五场)
in 牛客多校多校训练 with 0 comment

2020牛客暑期多校训练营(第五场)

in 牛客多校多校训练 with 0 comment

摘要

/ABCDEFGHIJK
场上
zyj
wrf
lmj

题目

A.Portal

lmj (赛后)

题意

n个点m条边,开始时在点1,要求做q次操作,每次将$a_i$位置的东西运到$b_i$,可以在当前点建一个传送门,传送门最多2个,破坏传送门可以在任意点,传送门的两个点的距离为0,求做完这q次操作最少的路径。

题解

考虑将题目简化,变成要从1按顺序经过这2*q个点,然后进行dp(当成q个的话,不仅dp时不能达到更优,而且还特别难写),dpi代表到了第i个点,当前传送门在j位置,然后是否经过传送门,先到新的传送门还是先到点,写出dp转移方程。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
ll a[305][305];
ll dp[605][305];
ll b[605];
void work()
{
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j)a[i][j]=0;
            else a[i][j]=1e15;
        }
    }
    for(int i=0;i<=2*q;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]=1e15;
        }
    }
    for(int i=1;i<=m;i++){
        int x,y;
        ll z;
        scanf("%d%d%lld",&x,&y,&z);
        a[x][y]=a[y][x]=min(a[x][y],z);
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                a[j][i]=a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
            }
        }
    }
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=n;j++){
    //         printf("--%d %d %lld\n",i,j,a[i][j]);
    //     }
    // }
    dp[0][1]=0;
    b[0]=1;
    for(int i=1;i<=q;i++){
        scanf("%d%d",&b[i*2-1],&b[i*2]);
    }
    for(int i=1;i<=2*q;i++){
        for(int j=1;j<=n;j++){
            for(int t=1;t<=n;t++){
                dp[i][j]=min(dp[i][j],dp[i-1][t]+
                    min(
                        min(a[b[i-1]][j],a[t][j])+min({a[t][b[i]],a[j][b[i]],a[b[i-1]][b[i]]}),
                        min(a[b[i-1]][b[i]],a[t][b[i]])+min({a[b[i-1]][j],a[b[i]][j],a[t][j]})
                    )
                );
                //printf("%d %d %d\n",i,j,dp[i][j]);
            }
        }
    }
    ll ans=1e18;
    for(int i=1;i<=n;i++){
        ans=min(ans,dp[2*q][i]);
    }
    printf("%lld\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

B.Graph

zyj+lmj (01:40:02) +0

题意

给一棵树,每条边有边权。可以任意加边和删边,但要满足任何时刻图连通,而且任何一个
环的边权异或和为0。求操作后最小权值和。

题解

可以发现任意两个点之间连边的权值都是固定的。由于图始终联通,所以两点间始终存在至少一条路径,如果存在多条,根据环的异或和为0,两点间的路径的异或和应该相等,且始终是固定的,所以可以给每个点一个权值,那么两点间的连边权值就应该是两端点权的异或。

于是可以转换为一道CF原题

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e6+100;
const int mod=(int)1e9+7;
const int inf=mod;
int n,s[maxn];
struct Edge{
    int v,w,nxt;
}g[maxn<<1];
int head[maxn],edge_tot;
void init(){rep(i,0,n) head[i]=0;edge_tot=1;}
void addedge(int u,int v,int w=1){g[edge_tot]={v,w,head[u]};head[u]=edge_tot++;}
ll cal(int d,int l1,int r1,int num1,int l2,int r2,int num2){
    if(d<0)return 0;
    int p1,p2,aa=num1+(1<<d),bb=num2+(1<<d);ll A=inf,B=inf;
    if(s[r1]<aa&&s[l2]>=bb)
        return cal(d-1,l1,r1,num1,l2,r2,num2+(1<<d))+(1<<d);
    if(s[l1]>=aa&&s[r2]<bb)
        return cal(d-1,l1,r1,num1+(1<<d),l2,r2,num2)+(1<<d);
    p1=lower_bound(s+l1,s+r1+1,aa)-s-1;
    p2=lower_bound(s+l2,s+r2+1,bb)-s-1;
    if(s[l1]<aa&&s[l2]<bb)A=cal(d-1,l1,p1,num1,l2,p2,num2);
    if(s[r1]>=aa&&s[r2]>=bb)
        B=cal(d-1,p1+1,r1,num1+(1<<d),p2+1,r2,num2+(1<<d));
    return min(A,B);
}
ll solve(int num,int d,int l,int r){
    if(d<0||l==r)return 0;
    if(s[r]<num+(1<<d))return solve(num,d-1,l,r);
    if(s[l]>=num+(1<<d))return solve(num+(1<<d),d-1,l,r);
    int mid=lower_bound(s+l,s+r+1,num+(1<<d))-s-1;
    ll A=solve(num,d-1,l,mid);
    ll B=solve(num+(1<<d),d-1,mid+1,r);
    ll C=cal(d,l,mid,num,mid+1,r,num);
    return A+B+C;
}
void dfs(int u,int fa){
    for(int i=head[u];i;i=g[i].nxt) if(g[i].v!=fa){
        s[g[i].v]=s[u]^g[i].w;
        dfs(g[i].v,u);
    }
}
int main(){
    scanf("%d",&n);init();
    rep(i,1,n-1){
        int u,v,w;scanf("%d%d%d",&u,&v,&w);u++;v++;
        addedge(u,v,w);addedge(v,u,w);
    } dfs(1,0);
    sort(s+1,s+n+1);
    printf("%lld\n",solve(0,30,1,n));
}

C.Easy

wrf (赛后) +1

题意

给定$n, m, k$,长度为$k$的两数组$A,B$满足$\sum_{i=1}^{K} a_{i}=N \text { 和 } \sum_{i=1}^{K} b_{i}=M$,求所有合法方案下$P=\prod_{i=1}^{K} \min \left(a_{i}, b_{i}\right)$中$P$的和。

题解

$\prod \min \left(a_{i}, b_{i}\right)$等于满足$c_{i} \leq \min \left(a_{i}, b_{i}\right)$的数组$C$的个数。
考虑枚举数组$C$的和为$i$,合法方案就是$i$个相同的球放入$k$个不同的箱子,对任一种合法方案下,先将$A$和$B$放成和$C$相同,那么$A$剩下$N-i$个球,$B$剩下$M-i$个球,这些球可以任意放在$k$个箱子里,因为不管剩下的这些怎么放都满足$c_{i} \leq \min \left(a_{i}, b_{i}\right)$,答案就是三个组合数相乘。

代码

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
const int inf=0x3f3f3f3f;
const ll mint=0x7fffffff;
const ll linf=1000000000000000000LL;
const ll mod=998244353LL;
const double eps=1e-3;
 
const int N=2000200;
 
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
 
 
 
ll inv[N];
ll pinv[N];
 
int main(void)
{
    //ios::sync_with_stdio(false);
     
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
     
    inv[0]=0;
    inv[1]=1;
    pinv[0]=1;
    for(int i=2;i<N;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1;i<N;i++) pinv[i]=pinv[i-1]*inv[i]%mod;
 
    for(int _=read();_>0;_--)
    {
        ll n=read(),m=read(),k=read();
        vector<ll> cik(max(n,m)*2+1,0);
 
        for(int i=0;i<k-1;i++) cik[i]=0;
        cik[k-1]=1;
        for(int i=k;i<=max(n,m)*2;i++) cik[i]=cik[i-1]*i%mod*inv[i-k+1]%mod;
 
        ll ans=0;
        for(int i=k;i<=min(m,n);i++)
        {
            ans=(ans+cik[i-1]*cik[n+k-i-1]%mod*cik[m+k-i-1]%mod)%mod;
        }
        printf("%lld\n",ans);
    }
     
    return 0;
}

D.Drop Voicing

lmj 1:26:17 +0

题意

给定一个序列,两种操作,第一种将倒数第二个数移到前面,第二种将第一个数放到最后,每种操作连续做只计1次,求最少需要多少次操作一使得使得最后序列为递增

题解

两种操作一起做,相当于将某一个位置的数放到另一个位置。那么只需要求出n种序列的最长上升子序列,用n减去即为答案。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int a[N];
int dp[1005];
void work()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=n+1;i<=2*n;i++){
        a[i]=a[i-n];
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        int l=i;
        int r=n+i-1;
        dp[l]=1;
        for(int j=l+1;j<=r;j++){
            dp[j]=1;
            for(int k=l;k<j;k++){
                if(a[j]>a[k]){
                    dp[j]=max(dp[j],dp[k]+1);
                }
            }
        }
        for(int j=l;j<=r;j++){
            ans=max(ans,dp[j]);
        }
    }
    printf("%d\n",n-ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

E.Bogo Sort

wrf 0:50:15+0

题意

给出长为 $n$ 的排列,求该排列的循环节对 $10^n$ 取模。

题解

做法

分别求循环节取 lcm 即可,注意高精度。

时间复杂度

首先定义基本运算为高精度数 $a$ 与低精度数的加、减、乘、除、取模操作,时间复杂度为 $O(\log a)$(即高精度数的位数)
考虑进行循环节 lcm 前缀和。每次 lcm 都可以分为:乘法、除法、gcd 的第一次取模、gcd 的后若干次取模四个部分。

假设共做了 $m$ 次 lcm,则总时间复杂度为 $O(m\log n+\sum \log a)$。
考虑

$$ \sum \log a=\log \prod a \leq \log ({nm \over m})^m=m \log n \leq n \log n $$

即得总时间复杂度为 $O(n\log n)$。

代码

n=int(input())
fpos=0

def gcd(x,y):
    if y>0:
        return gcd(y,x%y)
    else:
        return x
def lcm(x,y):
    return x*y//gcd(x,y)

p=[0]
p+=[int(n) for n in input().split(' ')]
did=[False]
ans=1
for i in range(n):
    did.append(False)
for i in range(n):
    if not did[i]:
        pos=p[i]
        j=1
        did[i]=1
        while pos!=i:
            did[pos]=True
            j+=1
            pos=p[pos]
        ans=lcm(ans,j)

cnt=[]
for i in range(n):
    if ans==0:
        break
    cnt.append(ans%10)
    ans//=10

cnt.reverse()
for i in cnt:
    print(i,end='')

F.DPS

zyj (00:17:58) +2

题意

模拟显示游戏中的伤害数据

题解

签到题,模拟即可

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n,d[maxn],mx;
int main(){
    scanf("%d",&n);
    rep(i,1,n) scanf("%d",&d[i]),mx=max(mx,d[i]);
    rep(i,1,n){
        ll s=(50ll*d[i]+mx-1)/mx;
        printf("+");
        rep(j,1,s) printf("-");
        printf("+\n");
        printf("|");
        rep(j,1,s-1) printf(" ");
        if(d[i]==mx) printf("*");
        else if(s) printf(" ");
        printf("|");
        printf("%d\n",d[i]);
        printf("+");
        rep(j,1,s) printf("-");
        printf("+\n");
    }
 
}

G.Greetings Souvenir

题意

题解

代码


H.Interval

zyj (赛后) +0

题意

定义$F(l, r)=A_{l} \& A_{l+1} \& \ldots \& A_{r}$
$S(l, r)={F(a, b)} \mid \min (l, r) \leq a \leq b \leq \max (l, r)$
给出$A$数组,有$Q$次询问,每次给出$l$和$r$,问$S(l,r)$的内有多少数。

题解

有一个显然的发现是:

对于一个确定的左端点或右端点,他确定的区间至多只有$log(n)$个不同的数

这个发现其实很显然,因为确定一个端点之后目前的$F(l,l)$就是$A[l]$,区间往左或右扩的时候就算每次只改一个二进制位,也只需要$log$次就可以改成0。
我们把所有不同区间的取值拿出来是$n log(n)$种,询问就变成了询问被$[l,r]$完全包含的区间权值和有多少种。
比较棘手的问题就是如何去重,我们发现若有$F(l_1,r_1)=F(l_2,r_2)$,那么区间$[l_1,r_2]$被重复算了一次,就在这个区间内减一即可。
对于强制在线且不带修的二维偏序问题,我们用主席树维护即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
#define lson tr[rt].l
#define rson tr[rt].r
#define mid ((l+r)>>1)
#define x first
#define y second
#define pii pair<int,int>
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
struct node{int l,r,sum;}tr[maxn<<5];
int tot;
void build(int &rt,int l,int r){
    rt=++tot;if(l==r) return;
    build(lson,l,mid);build(rson,mid+1,r);
}
void add(int &rt,int l,int r,int pre,int pos,int val){
    rt=++tot;tr[rt]=tr[pre];tr[rt].sum+=val;
    if(l==r) return;
    if(pos<=mid) add(lson,l,mid,tr[pre].l,pos,val);
    else add(rson,mid+1,r,tr[pre].r,pos,val);
}
int query(int rt,int l,int r,int pre,int ql,int qr){
    if(ql<=l&&r<=qr) return tr[rt].sum-tr[pre].sum;
    int ans=0;
    if(ql<=mid) ans+=query(lson,l,mid,tr[pre].l,ql,qr);
    if(mid<qr) ans+=query(rson,mid+1,r,tr[pre].r,ql,qr);
    return ans;
}
int a[maxn],root[maxn];
map<int,int> mp,tmp;
map<int,vector<pii> > po;
vector<int> vadd[maxn],vsub[maxn];
bool cmp(pii a,pii b){return a.x==b.x?(a.y>b.y):(a.x<b.x);}
int main(){
    int n;scanf("%d",&n);
    rep(i,1,n){
        scanf("%d",&a[i]);tmp.clear();
        for(auto u:mp) tmp[u.x&a[i]]=u.y;
        tmp[a[i]]=i;mp=tmp;
        for(auto u:mp) po[u.x].pb({u.y,i});
    }
    for(auto &u:po){
        auto &v=u.y;
        sort(v.begin(),v.end(),cmp);
        vector<pii> sta;
        for(auto p:v){
            if(!sta.size()) sta.pb(p);
            else{
                if(p.y<=sta.back().y) sta.pop_back();
                sta.pb(p);
            }
        }int sz=sta.size();
        rep(i,0,sz-1){
            vadd[sta[i].x].pb(sta[i].y);
            if(i) vsub[sta[i-1].x].pb(sta[i].y);
        }
    }build(root[0],1,n);
    rep(i,1,n){
        int pre=root[i-1];
        for(auto u:vadd[i]) add(root[i],1,n,pre,u,1),pre=root[i];
        for(auto u:vsub[i]) add(root[i],1,n,pre,u,-1),pre=root[i];
    }int q,las=0;scanf("%d",&q);
    while(q--){
        int l,r;scanf("%d%d",&l,&r);
        l=(l^las)%n+1;r=(r^las)%n+1;
        if(l>r) swap(l,r);
        printf("%d\n",las=query(root[n],1,n,root[l-1],1,r));
    }
}

I.Hard Math Problem

lmj 0:31:20 +3

题意

nm的矩阵填H,E,G,要求每个H旁边至少有一个E和G,f(n,m)代表H的最多数量,求n和m趋近于无穷时f(n,m)/(nm)的值

题解

每个E和G对应4个H,设E、G的数量为x,那么H的数量为4x,4x/(x+x+4x)=2/3

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
void work()
{
    printf("%.6f\n",2.0/3);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

J.Cone walker

题意

题解

代码


K.Git Merge

题意

题解

代码

Responses