2019牛客暑期多校训练营第七场题解

Solved	A	B	C	D	E	F	G	H	I	J	K
8/11	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

题目描述

给一个 $01$ 串，求最少的分割使得每一段字符串都是把这段字符串循环一圈之中字典序最小的。

解题思路

暴力 $O(Tn^3)$ 居然可过......

AC代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
char a[250];
int cnt0[250],cnt1[250],top;
int judge(int l,int r){
    char b[250]={0},c[250]={0};
    int i,j;
    for(i=l;i<=r;i++)b[i-l]=a[i];
    for(i=1;i<=r-l;i++){
        for(j=0;j<=r-l;j++){
            c[j]=b[(j+i)%(r-l+1)];
        }
        c[j]=0;
        if(strcmp(b,c)>0)return 0;
    }
    return 1;
}
int main(){
    int i,j,T;
    scanf("%d",&T);
    while(T--){
        scanf("%s",a+1);
        int l=strlen(a+1),last=1;
        while(1){
            for(i=l;i;i--){
                if(judge(last,i)){
                    for(j=last;j<=i;j++)printf("%c",a[j]);
                    printf(" ");
                    last=i+1;
                    break;
                }
            }
            if(last>l)break;
        }
        puts("");
    }
    return 0;
}

B

题目描述

给一个多项式，判断能否拆成两个多项式相乘。

解题思路

$n\geq 3$ 时，多项式必有实根或共轭复根。若有共轭复根 $a+bi,a-bi$ ，则必然有因式 $(x-a)^2-b^2$ ；若有实根 $a$ ，则必然有因式 $(x-a)$ 。于是不能拆的情况只有两种：一次多项式； $\Delta<0$ 的二次多项式。

AC代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll a[25];
int main(){
    int i,t,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(i=1;i<=n+1;i++)scanf("%lld",&a[i]);
        if(n<2||(n==2&&a[2]*a[2]-4*a[1]*a[3]<0))printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

C

题目描述

有 $n$ 种树，每种树有一个高度 $H_i$ ，个数 $P_i$ ，砍掉一棵的代价 $C_i$ 。最终状态要求为，最高的树的个数之和严格大于总树数的一半，求最小代价。

解题思路

从高到低枚举高度，每次查询需要删掉的个数 $num$ 以及前 $num$ 个的代价和，查询后删除。

也就是需要一种数据结构，支持单点修改区间求和，显然可以用树状数组。根据代价升序排列，建两个树状数组，一个维护个数，一个维护总代价。

AC代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 100010
#define pb push_back
struct Tree{
    int h,c,p;
    bool operator<(const Tree&t)const{return c<t.c;}
}a[N];
ll b1[N<<2],b2[N<<2];
int n;
void ins(ll a[],int p,ll x){while(p<=n)a[p]+=x,p+=p&(-p);}
ll query(ll a[],int p){ll ans=0;while(p)ans+=a[p],p-=p&(-p);return ans;}
map<int,vector<int>>h;
int main(){
    int i;
    while(~scanf("%d",&n)){
        ll tot=0,ans=1e18,nowc=0;
        h.clear();
        for(i=1;i<=n;i++)scanf("%d%d%d",&a[i].h,&a[i].c,&a[i].p),tot+=a[i].p;
        sort(a+1,a+n+1);
        for(i=1;i<=n;i++)ins(b1,i,a[i].p),ins(b2,i,1LL*a[i].p*a[i].c),h[a[i].h].pb(i);
        for(auto it=h.rbegin();it!=h.rend();it++){
            ll sump=0,sumc=nowc;
            for(auto j:(*it).second){
                sump+=a[j].p;
                sumc+=1LL*a[j].p*a[j].c;
                ins(b1,j,-a[j].p);ins(b2,j,-1LL*a[j].p*a[j].c);
            }
            int l=1,r=n,res=n,mid;
            while(l<=r){
                mid=(l+r)>>1;
                if(query(b1,mid)>tot-2*sump)r=mid-1,res=mid;
                else l=mid+1;
            }
            ll x=max(tot-(sump*2-1)-query(b1,res-1),0LL);
            ans=min(ans,nowc+query(b2,res-1)+a[res].c*x);
            nowc=sumc;
            tot-=sump;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

D

题目描述

求出有没有一个可以被质数 $p$ 整除的 $n$ 位整数。

解题思路

后面加零就行了。

AC代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
    int i,cnt=0,n,p;
    scanf("%d%d",&n,&p);int t=p;
    while(t)cnt++,t/=10;
    if(cnt>n)printf("T_T");
    else{
        printf("%d",p);
        for(i=cnt;i<n;i++)printf("0");
    }
    return 0;
}

E

题目描述

$n$ 次操作，每次向数列中加入 $[L_i,R_i]$ 中所有数各一个，要求每次操作后输出中位数。

解题思路

中位数显然可以用线段树查询求出，或者二分查找大小求出，需要离散化一下，每个节点代表 $[L,R+1)$ 区间，所以离散化的时候也应当离散化 $L$ 和 $R+1$ 。线段树维护一下区间和就好了。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
unordered_map<int,int> id;

int n;
const int maxn=4e5+23;
int f[maxn<<1];
ll x1,x2,a,b,c,m;
ll x[maxn<<1];
int l[maxn],r[maxn];
ll st[maxn<<3];
int add[maxn<<3];
int v[maxn<<3];
int inde[maxn<<3];

void build(int o,int l,int r)
{
    if(l==r) v[o]=f[l]-f[l-1],inde[l]=o;
    else{
        int m=(r+l)>>1;
        build(o<<1,l,m);
        build(o<<1|1,m+1,r);
        v[o]=v[o<<1]+v[o<<1|1];
    }
}

void pushup(int o)
{
    st[o]=st[o<<1]+st[o<<1|1];
}

void pushdown(int o)
{
    if(add[o]){
        add[o<<1]+=add[o];
        add[o<<1|1]+=add[o];
        st[o<<1]+=(1LL*add[o]*v[o<<1]);
        st[o<<1|1]+=(1LL*add[o]*v[o<<1|1]);
        add[o]=0;
    }
}

void update1(int o,int l,int r,int ql,int qr,int addv)
{
    if(ql<l&&qr>=r){
        add[o]+=addv;
        st[o]+=(1LL*addv*v[o]);
        return ;
    }
    if(ql>=r||qr<l)return;
    pushdown(o);
    int m=(l+r)>>1;
    update1(o<<1,l,m,ql,qr,addv);
    update1(o<<1|1,m+1,r,ql,qr,addv);
    pushup(o);
}

ll query(int o,int l,int r,int ql,int qr)
{
    if(ql<=l&&qr>=r) return st[o];
    if(ql>r||qr<l)return 0;
    pushdown(o);
    int m=(l+r)>>1;
    ll ans=0;
    ans+=query(o<<1,l,m,ql,qr)+query(o<<1|1,m+1,r,ql,qr);
    return ans;
}
int y[maxn<<1];
int main()
{
    int i;
    cin >> n;
    cin >> x1 >> x2 >> a >> b >> c >> m;
    x[1]=x1,x[2]=x2;
    for(i=3;i<=n;i++){
        x[i]=(a*x[i-1]+b*x[i-2]+c)%m;
    }
    cin >> x1 >> x2 >> a >> b >> c >> m;
    x[1+n]=x1,x[2+n]=x2;
    for(i=3;i<=n;i++)x[n+i]=(a*x[n+i-1]+b*x[n+i-2]+c)%m;
    int cnt=1;
    for(i=1;i<=n;i++){
        l[i]=min(x[i],x[n+i])+1;
        r[i]=max(x[i],x[n+i])+1;
        y[cnt++]=l[i];
        y[cnt++]=r[i]+1;
    }
    sort(1+y,1+y+2*n);
    cnt=unique(y+1,y+1+2*n)-y-1;
    for(i=1;i<=cnt;++i){
        id[y[i]]=i;
        f[i]=y[i];
    }
    ll num=0;
    build(1,1,cnt);
    for(i=1;i<=n;i++){
        num+=r[i]-l[i]+1;
        int bb=id[l[i]],bbb=id[r[i]+1];
        update1(1,1,cnt,bb,bbb,1);
        int L=1,R=cnt,mid;
        ll ans=0,M=(num+1)/2;
        while(L<R){
            mid=(L+R)>>1;
            ans=query(1,1,cnt,1,mid);
            if(ans>=M) R=mid;
            else L=mid+1;
        }
        ans=query(1,1,cnt,1,L);
        ll temp=ans-M;
        ll m=st[inde[L]]/v[inde[L]];
        ll ret=f[L]-temp/m-1;
        printf("%d\n",ret);
    }
}

然后又发现了一种神奇的树状数组做法：

考虑一个 $x$ ，只要能够快速判断出 $x$ 左边有多少个数就能快速判断中位数的位置了。

$x$ 左边的数有两种情况：

是一个完整的区间

是一个跨越 $x$ 的区间

于是我们可以对跨越 $x$ 的区间进行计数 $cnt$ ，也就是区间 $[L,R]$ 内部 $cnt$ 都加一；完整的区间可以通过区间内 $cnt2+=-L$ ，右端点 $cnt2+=R-L$ 进行表示。

于是通过记录这两个值，可以看出，某一点 $x$ 的前面（包括本身）数的总数便是它的 $cnt2-cnt1\times (x+1)$ ，其中 $cnt2$ 一部分贡献来自于 $x$ 前面的完整区间，另一部分和 $cnt1$ 的 $x$ 倍共同组成跨越 $x$ 区间的左半边，再加上 $x$ 本身的 $cnt1$ 。

这是一个区间修改单点查询的问题，通过对左右端点的修改用树状数组即可维护。最后二分答案即可。

AC代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 400010
int n,x[N],y[N],l[N],r[N];
ll a1,a2,b1,b2,c1,c2,m1,m2;
int z[N<<1],cnt;
ll B1[N<<2],B2[N<<2];
void ins(ll a[],int p,int x){
    int i;
    for(i=p;i<=cnt;i+=i&(-i))a[i]+=x;
}
ll query(ll a[],int p){
    int i;ll ans=0;
    for(i=p;i;i-=i&(-i))ans+=a[i];
    return ans;
}
int main(){
    int i;ll t=0;
    scanf("%d%d%d%lld%lld%lld%lld%d%d%lld%lld%lld%lld",&n,&x[1],&x[2],&a1,&b1,&c1,&m1,&y[1],&y[2],&a2,&b2,&c2,&m2);
    for(i=1;i<=n;i++){
        if(i>2)x[i]=(a1*x[i-1]+b1*x[i-2]+c1)%m1;
        if(i>2)y[i]=(a2*y[i-1]+b2*y[i-2]+c2)%m2;
        l[i]=min(x[i],y[i])+1;
        r[i]=max(x[i],y[i])+1;
        z[++cnt]=l[i];z[++cnt]=r[i]+1;
    }
    sort(z+1,z+cnt+1);
    cnt=unique(z+1,z+cnt+1)-z-1;
    for(i=1;i<=n;i++){
        t+=r[i]-l[i]+1;
        int L=lower_bound(z+1,z+cnt+1,l[i])-z,R=lower_bound(z+1,z+cnt+1,r[i]+1)-z;
        ins(B1,L,-l[i]);ins(B1,R,r[i]+1);
        ins(B2,L,1);ins(B2,R,-1);
        L=1,R=1e9;
        while(L<R){
            int mid=(L+R)>>1,pos=upper_bound(z+1,z+cnt+1,mid)-z-1;
            ll tmp=query(B1,pos);
            tmp+=query(B2,pos)*(mid+1);
            if(tmp<(t+1)/2)L=mid+1;
            else R=mid;
        }
        printf("%d\n",L);
    }
    return 0;
}

F

题目描述

解题思路

AC代码

G

题目描述

解题思路

AC代码

H

题目描述

给 $1e9$ 以内的 $a,b,c$ ，求满足 $1\leq x\leq a,1\leq y\leq b$ ，且 $(x\& y)>c$ 或 $(x\oplus y)<c$ 的 $(x,y)$ 个数。

解题思路

找出 $(x\& y)\leq c$ 且 $(x\oplus y)\geq c$ 的 $x,y$ 对数，用总数减去即可。

从高位到低位枚举 $a,b$ 的每一二进制位，通过记录这两个条件是否已经满足（后面任选）、是否已经满足 $x\leq a,y\leq b$ 、是否全是 $0$ （ $1\leq x,y$ ）几种状态进行数位 $dp$ 。

AC代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int staa[40],stab[40],stac[40],top,a,b,c;
ll A,B,C,f[40][2][2][2][2][2][2];
ll dfs(int st,int ad,int xo,int lima,int limb,int la,int lb){
    if(st<0)return !la&&!lb;
    ll &ans=f[st][ad][xo][lima][limb][la][lb];
    if(~ans)return ans;
    ans=0;
    int i,j,mxa=lima?staa[st]:1,mxb=limb?stab[st]:1;
    for(i=0;i<=mxa;i++)
        for(j=0;j<=mxb;j++)
            if(ad&&(i&j)&&!stac[st]||xo&&!(i^j)&&stac[st]);
            else ans+=dfs(st-1,ad&((i&j)==stac[st]),xo&((i^j)==stac[st]),lima&(i==mxa),limb&(j==mxb),la&!i,lb&!j);
    return ans;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        memset(f,-1,sizeof(f));
        memset(staa,0,sizeof(staa));
        memset(stab,0,sizeof(stab));
        memset(stac,0,sizeof(stac));
        scanf("%d%d%d",&a,&b,&c);A=a;B=b;C=c;
        while(a)staa[top++]=a&1,a>>=1;top=0;
        while(b)stab[top++]=b&1,b>>=1;top=0;
        while(c)stac[top++]=c&1,c>>=1;top=0;
        printf("%lld\n",A*B-dfs(31,1,1,1,1,1,1));
    }
    return 0;
}

I

题目描述

给定两个数 $n,m$ ，可以取任意大小的 $k\times k$ 的正方形填数，填数的要求是：

任意 $k$ 个行列都不同的点，点上数的总和相等

点上数的总和不超过 $n$

任意点上的数字不少于 $m$

问有多少种方法。

解题思路

对于每一个 $k$ ，显然可以先把 $m$ 的限制去掉，限制 $n$ 改为 $n-mk$ 。

任意 $k$ 个不同行列的点，其数的和都相等，代表这个矩阵 $M$ 可以由第 $i$ 行全为 $1$ ，其他全为 $0$ 的矩阵 $A_i$ 和第 $i$ 列全为 $1$ ，其他全为 $0$ 的矩阵 $B_i$ 线性表示，即 $M=\sum_{i=1}^k(a_iA_i+b_iB_i)$ 。假设总和为 $x$ ，限制条件为 $0\leq x\leq n-mk$ ，则有 $\sum_{i=1}^k(a_i+b_i)=x,a_i\geq 0,b_i\geq 0$ 。把 $x$ 看做 $x$ 个 $1$ ，插总共 $2k-1$ 块板（ $a_1,a_2...a_k,b_1..b_k$ 共 $2k$ 个数，每个板子分开两个数），方案数为 $C_{x+2k-1}^{2k-1}$ 。

然后发现如果只用这个公式，多算了一些情况：如果 $a_i$ 全 $\geq 1$ ，那么把 $a_i$ 全都减一， $b_i$ 全都加一，会被重复统计。重复统计的个数即为 $\sum_{i=1}^k(a_i+b_i)=x,a_i\geq 1,b_i\geq 0$ ， $C_{x+k-1}^{2k-1}$ 。

枚举 $k,x$ ，得出答案。

AC代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 4020
ll mod=998244353;
ll inv[N],fac[N];
ll 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;
}
ll c(int n,int m){return n>=m?fac[n]*inv[m]%mod*inv[n-m]%mod:0;}
int main(){
    int i,k,t,n,m;
    fac[0]=inv[0]=1;
    for(i=1;i<N;i++)fac[i]=fac[i-1]*i%mod,inv[i]=qp(fac[i],mod-2);
    scanf("%d",&t);
    while(t--){
        ll ans=0;
        scanf("%d%d",&n,&m);
        for(k=1;k*m<=n;k++){
            for(i=0;i<=n-m*k;i++){
                ans+=c(i+2*k-1,2*k-1);
                ans+=mod-c(i+k-1,2*k-1);
                ans%=mod;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

J

题目描述

计算两个数倒过来的和，忽略掉首位 $0$ 。

解题思路

签到题。

AC代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
char a[50],b[50],c[50];
int main(){
    int i,T;
    scanf("%d",&T);
    while(T--){
        ll A=0,B=0;
        scanf("%s%s",a,b);
        for(i=strlen(a)-1;i>=0;i--)A=A*10+a[i]-'0';
        for(i=strlen(b)-1;i>=0;i--)B=B*10+b[i]-'0';
        memset(c,0,sizeof(c));
        ll C=A+B;
        while(C&&C%10==0)C/=10;
        sprintf(c,"%lld",C);
        for(i=strlen(c)-1;i>=0;i--)printf("%c",c[i]);
        puts("");
    }
    return 0;
}

K

题目描述

解题思路

AC代码

2019牛客暑期多校训练营第七场 题解

A

题目描述

解题思路

AC代码

B

题目描述

解题思路

AC代码

C

题目描述

解题思路

AC代码

D

题目描述

解题思路

AC代码

E

题目描述

解题思路

AC代码

AC代码

F

题目描述

解题思路

AC代码

G

题目描述

解题思路

AC代码

H

题目描述

解题思路

AC代码

I

题目描述

解题思路

AC代码

J

题目描述

解题思路

AC代码

K

题目描述

解题思路

AC代码

2019牛客暑期多校训练营第七场题解