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

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

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

摘要

/ABCDEFGHIJK
场上
zyj
wrf
lmj

题目

A.African Sort

zyj (赛后) +1

题意

给定一个排列 $p$ ,每次选一个环进行 $random$ $shuffle$ 后丢回对应的位置,费用为环长。
问将排列变成 ${1,2,...,n}$ 的期望费用。

题解

令$d p_{i}$为消除环长为$i$的期望费用,那么
$$d p_{i}=i+\sum_{j=1}^{i} C_{i}^{j} \cdot \frac{(j-1) !(i-j) !}{i !} \cdot d p_{j}$$
其中$i$为此次操作的费用,一次操作之后可能将一个大环分为若干小环,$C_{i}^{j}$为选出$j$个成环,$(j-1) !$为新环的排列数,$(i-j) !$为其他数的排列数。
由于$C_{i}^{j}=\frac{i !}{j !(i-j) !}$,因此原式等于
$$d p_{i}=i+\sum_{j=1}^{i} \frac{1}{j} \cdot d p_{j}$$
化简之后得
$$d p_{i}=(i+\sum_{j=1}^{i-1} \frac{1}{j} \cdot d p_{j})\frac{i}{i-1}$$
如此优雅的转移式还不会写?

代码

#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=998244353;
ll qpow(ll x,int n){
    ll res=1;
    while(n){
        if(n&1) res=(res*x)%mod;
        x=(x*x)%mod;n>>=1;
    } return res;
}
ll dp[maxn],tmp[maxn],a[maxn],vis[maxn];
ll inv(ll x){return qpow(x,mod-2);}
int main(){
    rep(i,2,maxn-1){
        dp[i]=1ll*i*inv(i-1)%mod*(tmp[i-1]+i)%mod;
        tmp[i]=(tmp[i-1]+dp[i]*inv(i)%mod)%mod;
    }
    int n,m;scanf("%d%d",&n,&m);
    while(m--){ll ans=0;
        rep(i,1,n) scanf("%lld",&a[i]),vis[i]=0;
        rep(i,1,n) if(!vis[i]){
            int now=i,cnt=0;
            while(!vis[now]) vis[now]=++cnt,now=a[now];
            ans=(ans+dp[cnt])%mod;
        }
        printf("%lld\n",ans);
    }
}

B.Binary Vector

wrf(0:59:59)+0

题意

给定 $n$,求随机取 $n$ 个长为 $n$ 的 $01$ 串,这些串之间线性无关的概率,对 $10^9+7$ 取模。
题目要求对给定的 $n$,输出上述答案的异或前缀和。

题解

做法

对所有的 $n$,递推预处理 $\prod_1^n 1-2^{-i}$,再求前缀和即可。
如果目前已经取得了 $i$ 个线性无关串,那么它们之间可能的 $2^i$ 种组合都是不可取的。此时可以取的就只剩 $2^n-2^i$ 个串。
所以所求概率为:

$$ {\prod_{0}^{n-1} 2^n-2^i \over (2^n)^n}=\prod_{0}^{n-1} {2^n-2^i \over 2^n}=\prod_{0}^{n-1} 1-2^{i-n}=\prod_{1}^{n} 1-2^{-i} $$

时间复杂度

$O(n)$

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=1000000007LL;

const int N=20000020;

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;
}

const ll inv2=500000004LL;
ll tab[N];

int main(void)
{
    tab[0]=1;   
    ll in2n=1;
    for(int i=1;i<N;i++) 
    {
        in2n=in2n*inv2%mod;
        tab[i]=tab[i-1]*(mod+1-in2n)%mod;
    }
    for(int i=2;i<N;i++)
    {
        tab[i]^=tab[i-1];
    }
    for(int _=read();_>0;_--)
    {
        printf("%lld\n",tab[read()]);
    }
    
    return 0;
}

C.Combination of Physics and Maths

zyj+lmj (01:30:54) +3

题意

给定一个矩阵,定义子矩阵的压力为子矩阵的元素和除以矩阵最后一行的元素和,问最大压力

题解

显然确定了底边之后底边上面的行都要全选,然后问题就转为如何选取列,有一个显然的发现就是:选单独列的收益大于等于选多列,因此只要选一列收益最大的即可。

代码

#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,m,v[222][222];
struct node{
    int fz,fm;
}dp[220][220];
int pre[222][222];
void solve(){
    scanf("%d%d",&n,&m);
    rep(i,1,n) rep(j,1,m) scanf("%d",&v[i][j]),pre[j][i]=0;
    rep(j,1,m) rep(i,1,n) pre[j][i]=v[i][j]+pre[j][i-1];
    node ans={0,0};
    rep(i,1,n){
        rep(j,1,m){
            if(1ll*ans.fz*v[i][j]<=1ll*ans.fm*pre[j][i]){
                ans.fz=pre[j][i];
                ans.fm=v[i][j];
            }
        }
    }printf("%.10lf\n",1.0*ans.fz/ans.fm);
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}

D.Data structure

zyj (赛后)

题意

题解

代码

#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=4e5+5;
const int S=8;
int n,m,rt,sz[maxn],fa[maxn];
vector<int> g[maxn];
struct ASK{int l,r,id;};
vector<ASK> q[maxn];
inline ll read(){
    ll x=0;int flag=0;char c=getchar();
    while(!isdigit(c)){if(c=='-') flag=1;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return flag?-x:x;
}
void dfs(int u,int f){
    fa[u]=f;sz[u]=1;
    for(auto v:g[u]) if(v!=f){
        dfs(v,u);sz[u]+=sz[v];
    }sort(g[u].begin(),g[u].end(),[](int x,int y){return sz[x]>sz[y];});
}
struct BLOCK{
    static const int S=300;//块大小
    static const int K=maxn/S+5;//块数量
    int big[K],small[maxn],bel[maxn],L[K],R[K];
    BLOCK(){
        for(int i=1;i<maxn;i++)bel[i]=(i-1)/S+1;
        for(int i=1;i<K;i++)L[i]=1+(i-1)*S,R[i]=i*S;
    }
    void insert(int x){
        for(int i=1;i<=bel[x];i++)big[i]++;
        for(int i=L[bel[x]];i<=x;i++)small[i]++;
    }
    int query(int l,int r){
        return big[bel[l]+1]+small[l]-big[bel[r+1]+1]-small[r+1];
    }
}block;
struct MODUI{
    int res,cnt[maxn];
    void clear(int tot){res=0;for(int i=1;i<=tot;i++)cnt[i]=0;}
    void insert(int x){res+=cnt[x]++;}
    void erase(int x){res-=--cnt[x];}
    inline int query(){return res;}
}md;
int now1,now2,cnt1[maxn],cnt2[maxn],dfn[maxn],rk[maxn],tot;
ll ans[maxn];
pair<int,int>col[maxn];
void dfs2(int x,int top){
    rk[dfn[x]=++tot]=x;
    int st1=now1,st2=now2;
    for(auto v:q[x]) cnt1[now1++]=-block.query(v.l,v.r);
    if(top!=x) for(auto v:q[fa[x]]) cnt2[now2++]=-block.query(v.l,v.r);
    block.insert(x);
    for(int i=0;i<g[x].size();i++){
        int y=g[x][i];
        if(y==fa[x])continue;
        if(i<S)dfs2(y,top);
        else dfs2(y,y);
    }
    for(int i=0;i<q[x].size();i++){
        cnt1[st1+i]+=block.query(q[x][i].l,q[x][i].r);
        ans[q[x][i].id]+=1ll*cnt1[st1+i]*(cnt1[st1+i]-1)/2;
    }
    if(top!=x)for(int i=0,len=q[fa[x]].size();i<len;i++){
        cnt2[st2+i]+=block.query(q[fa[x]][i].l,q[fa[x]][i].r);
        ans[q[fa[x]][i].id]-=1ll*cnt2[st2+i]*(cnt2[st2+i]-1)/2;
    }
    now1=st1,now2=st2;
    if(g[x].size()<S) return;
    int all=0,id=0;
    for(int i=S;i<g[x].size();i++){
        int y=g[x][i];
        if(y==fa[x])continue;
        id++;
        for(int j=dfn[y];j<dfn[y]+sz[y];j++)col[++all]=make_pair(rk[j],id);
    }
    sort(col+1,col+all+1);
    for(auto &v:q[x]){
        v.l=lower_bound(col+1,col+all+1,make_pair(v.l,0))-col;
        v.r=upper_bound(col+1,col+all+1,make_pair(v.r,maxn))-col-1;
    }int S=sqrt(all)+1;
    sort(q[x].begin(),q[x].end(),[&](ASK &a,ASK &b){
        if(a.l/S!=b.l/S)return a.l/S<b.l/S;
        return a.r<b.r;
    });
    int L=1,R=0;
    md.clear(id);
    for(auto &v:q[x]){
        int l=v.l,r=v.r,id=v.id;
        if(l>r)continue;
        while(R<r)md.insert(col[++R].second);
        while(L>l)md.insert(col[--L].second);
        while(R>r)md.erase(col[R--].second);
        while(L<l)md.erase(col[L++].second);
        ans[id]-=md.query();
    }
}
int main(){
    n=read();m=read();rt=read();
    rep(i,2,n){
        int u=read(),v=read();
        g[u].pb(v);g[v].pb(u);
    }
    rep(i,1,m){
        int l=read(),r=read(),x=read();
        q[x].pb({l,r,i});
    }dfs(rt,0);dfs2(rt,rt);
    rep(i,1,m) printf("%lld\n",ans[i]);
}

E.Easy Construction

wrf(0:20:43)+0

题意

给出 n,k,要求构造一个长为n的排列,使得对于每一个合法的子串长度i,都能找到一个子串使得其和模nk

题解

做法

首先如果所有数的总和模n不为k则无解。
此时可以发现,当n为偶数时,k=n/2;当n为奇数时,k=0
我们可以将所有数分为和为n的若干对,每对在所构造的排列中位置相邻。

证明

如果要求的子串长与原串奇偶相同,那么总可以拿去若干队;反之,总可以拿去n后再拿去若干对。

时间复杂度

$O(n)$

代码

#include <bits/stdc++.h>

using namespace std;

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;
}

int main(void)
{
    int n=read(),k=read();
    if(n%2==0 && k!=n/2) 
    {
        printf("-1");
        return 0;
    }
    if(n%2==1 && k!=0)
    {
        printf("-1");
        return 0;
    }
    if(n%2==0)
    {
        printf("%d %d",n,n/2);
        for(int i=1;i<n-i;i++)
        {
            printf(" %d %d",i,n-i);
        }
    }
    else
    {
        printf("%d",n);
        for(int i=1;i<n-i;i++)
        {
            printf(" %d %d",i,n-i);
        }
    }
    
    return 0;
}

F.Fibonacci Partition

题意

题解

代码


G.Grid Coloring

lmj 01:44:18 +1

题意

给一个$n*n$的网格,用k种颜色去涂边框,要求每种颜色数量一样,没有任意的颜色形成环,没有任意一行或者一列为同一种颜色,输出任意一种方案

题解

$n*n$的网格有$n*(n+1)*2$个边框,显然如果不模k等于0,那么不能满足,如果n=1或者k=1也显然不满足。然后考虑将竖着的也看成一行,共有2*n+1行,遍历所有行,从1-k进行填充。
证明:
首先该做法可以保证每种颜色数量一样。对于每一行,显然相邻的边颜色不同,满足任意一行有两种颜色以上。对于每个网格,竖着的2个边框会被顺序遍历,所以也不相同,满足没有任意颜色成环。对于列同色,可以发现对于同一列,每$n+n+1$遇到一次,那么如果要同色,那么$n+n+1$模k要为0,由于$gcd(n*(n+1),n+n+1)==1$,得到$gcd(n*(n+1)*2,n+n+1)==1$,由于$n*(n+1)*2$模k等于0,所以$gcd(k,n+n+1)==0$,所以不可能列同色

代码

#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 s1[205][205],s2[205][205];
void work()
{
    int n,k;
    scanf("%d%d",&n,&k);
    if(2*n*(n+1)%k!=0||k==1||n==1){
        printf("-1\n");return;
    }
    int cnt=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            s1[i][j]=cnt;
            cnt=cnt%k+1;
        }
        for(int j=1;j<=n+1;j++){
            s2[j][i]=cnt;
            cnt=cnt%k+1;
        }
    }
    for(int i=1;i<=n;i++){
        s1[n+1][i]=cnt;
        cnt=cnt%k+1;
    }
    for(int i=1;i<=n+1;i++){
        for(int j=1;j<=n;j++){
            printf("%d ",s1[i][j]);
        }
        printf("\n");
    }
    for(int i=1;i<=n+1;i++){
        for(int j=1;j<=n;j++){
            printf("%d ",s2[i][j]);
        }
        printf("\n");
    }
}
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();
    }
}

H.Harmony Pairs

wrf(赛后)

题意

[1,n]范围内,a的数字和大于ba<b的数对个数。
n不超过 100 位。

题解

做法

数位 dp。
考虑dp[t][d][p][q]代表当前从高到低枚举到第t位,目前b-a==dp,q分别表示目前是否有a==bb==n
显然当n[t]=='\0'时达到终止状态。此时判断是否有d>0,如果是则存在合法答案,返回1,否则返回0
在其他情况下,枚举下一位。注意按照pq特判情况。
按照上述转移记忆化搜索即可。

时间复杂度

$O(n^4)$(此处令位数为 $n$)

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=1000000007LL;

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;
}

char n[120];
int dp[120][2000][2][2];
int m;

int solve(int t,int delta,bool mxa,bool mxb)
{
    if(n[t]=='\0') return dp[t][delta][mxa][mxb]=(delta>1000?1:0);
    else if(dp[t][delta][mxa][mxb]!=-1) return dp[t][delta][mxa][mxb];
    else
    {
        dp[t][delta][mxa][mxb]=0;
        for(int i=0;i<=(mxb?n[t]-'0':9);i++)
        {
            for(int j=0;j<=(mxa?i:9);j++)
            {
                int ans=solve(t+1,delta+j-i,mxa && j==i,mxb && i==n[t]-'0');
                dp[t][delta][mxa][mxb]+=ans;
                if(dp[t][delta][mxa][mxb]>mod) dp[t][delta][mxa][mxb]-=mod;
            }
        }
    }
    return dp[t][delta][mxa][mxb];
}

int main(void)
{
    memset(dp,-1,sizeof(dp));

    scanf("%s",n);

    printf("%d",solve(0,1000,1,1));

    return 0;
}

I.Interesting Stiriling

题意

题解

代码


J.Josephus Transform

lmj 4:25:22 +0

题意

对一个长度为n的序列,做m轮操作,每次操作为以k为顺序得到约瑟夫环出队顺序,做x次,求m轮操作后的结果

题解

做一次约瑟夫环出队顺序,可以理解为做了一次置换,那么如果知道置换方式可以O(n)得到一轮操作的结果(置换群,不了解的话先去看看置换群),那么如何得到置换方式,考虑快速得到一次的约瑟夫环出队顺序,考虑采用权值线段树,每次求下一个要删的点在序列内为第k大,通过权值线段树快速求得并删除,即可得到一次置换后的结果,稍微变换即可得到置换方式,就可以O(n)得到一轮操作的结果,做m次即可。
复杂度$O(n*m*logn)$

代码

#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;
int a[N];
int b[N];
int c[N];
int d[N];
int vis[N];
int s[N<<2];
void build(int l,int r,int rt)
{
    if(l==r){
        s[rt]=1;
        return;
    }
    int m=(l+r)>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    s[rt]=s[rt<<1]+s[rt<<1|1];
}
void update(int l,int r,int rt,int x)
{
    if(l==r){
        s[rt]=0;
        return;
    }
    int m=(l+r)>>1;
    if(x<=m)update(l,m,rt<<1,x);
    else update(m+1,r,rt<<1|1,x);
    s[rt]=s[rt<<1]+s[rt<<1|1];
}
int query(int l,int r,int rt,int k)
{
    //printf("%d %d %d\n",l,r,k);
    s[rt]--;
    if(l==r){
        return l;
    }
    int m=(l+r)>>1;
    if(s[rt<<1]>=k)return query(l,m,rt<<1,k);
    else return query(m+1,r,rt<<1|1,k-s[rt<<1]);
}
int sum(int l,int r,int rt,int L,int R)
{
    if(L>R)return 0;
    if(L<=l&&R>=r){
        return s[rt];
    }
    int m=(l+r)>>1;
    if(R<=m)return sum(l,m,rt<<1,L,R);
    if(L>m)return sum(m+1,r,rt<<1|1,L,R);
    return sum(l,m,rt<<1,L,R)+sum(m+1,r,rt<<1|1,L,R);
}
void work()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        a[i]=i;
    }
    for(int i=1;i<=m;i++){
        int k,ss;
        scanf("%d%d",&k,&ss);
        build(0,n-1,1);
        int p=n;
        int now=-1;
        for(int j=0;j<n;j++){
            int tmp=sum(0,n-1,1,now+1,n-1);
            //printf("%d\n",tmp);
            int mm=k%p;
            //printf("%d %d %d %d\n",tmp,mm,(p-tmp+mm-1+p)%p+1,((mm-tmp-1)%p+p)%p+1);
            if(mm<=tmp)now=query(0,n-1,1,(p-tmp+mm-1+p)%p+1);
            else now=query(0,n-1,1,((mm-tmp-1)%p+p)%p+1);
            p--;
            b[j+1]=now+1;
        }
        for(int j=1;j<=n;j++){
            //printf("%d ",b[j]);
            vis[j]=0;
            c[b[j]]=j;
        }
        //printf("\n");
        for(int j=1;j<=n;j++){
            if(!vis[j]){
                vector<int>v;
                int x=j;
                while(!vis[x]){
                    v.push_back(x);
                    vis[x]=1;
                    x=c[x];
                }
                for(int k=0;k<v.size();k++){
                    d[v[(k+ss)%v.size()]]=a[v[k]];
                }
            }
        }
        for(int j=1;j<=n;j++){
            a[j]=d[j];
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
}
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();
    }
}

K.K-Bag

wrf(2:31:11)+7

题意

给出一个长为n的串,请问这个串是否被包含在某个由任意个长为k的排列拼接而成的串中。

题解

做法

首先通过双指针预处理每一个长为k的段落是否正好为一个排列(如果某个位置之后不足k位,那么检测它是否可能属于一个长为k的排列)。如果是,从它的开头位置向结尾位置连一条指针。
枚举前k位作为起始位置,然后按照所存储的指针不断向后跳跃。如果存在一个起始位置能够跳到结尾,那么答案为是。

证明

首先在起始位置之前的部分,可以被视作某个排列的一部分;
起始位置之后跳跃的部分,要么正好是一个排列,要么是排列的一部分且在结尾。
那么我们总能补全头尾而得到所求的串。

时间复杂度

$O(k \cdot \frac{n}{k} \log n)=O(n \log n)$

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=500020;

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;
}

bitset<N> b;
unordered_map<int,int> s;
int main(void)
{
    for(int _=read();_>0;_--)
    {
        int n=read(),k=read();
        bool f1=true,f2=false;
        vector<int> v(n);
        
        b.reset();
        s.clear();
        for(int i=0;i<n;i++) 
        {
            v[i]=read();
            if(v[i]<1 || v[i]>k) f1=false;
            if(i<k) s[v[i]]++;
        }
        int l=0,r=k-1;

        for(l=0;l<n;l++)
        {
            if(s.size()==min(k,n-l)) b[l]=true;
            if(r<n-1)
            {
                r++;
                s[v[r]]++;
            }
            s[v[l]]--;
            if(s[v[l]]==0) s.erase(v[l]);
        }
        s.clear();
        for(int i=0;i<min(n,k);i++)
        {
            int pos;
            for(pos=i;pos<n;pos+=k)
            {
                if(!b[pos]) break;
            }
            if(pos>=n) 
            {
                f2=true;
                break;
            }
            s[v[i]]++;
            if(s.size()!=i+1) break;
        }

        printf((f1 && f2)?"YES\n":"NO\n");
    }
    
    return 0;
}

Responses