一、单项选择题（每题2分，共15题，30分）

1. 八位有符号二进制反码为11110010，对应真值 {{ select(1) }}

• $72_{(16)}$
• $-15_{(8)}$
• $-13_{(8)}$
• $-10_{(14)}$

2. 下列不属于图像格式 {{ select(2) }}

• JPG
• HEIC
• WEBP
• MOV

3. 12分钟视频，每秒12帧，960×540 32位真彩色，预留2G，最优压缩率 {{ select(3) }}

• 15%
• 8%
• 10%
• 12%

4. 入栈序列1,3,2,4,5，非法出栈序列 {{ select(4) }}

• 1, 2, 3,4, 5
• 3, 2, 4, 1,5
• 1, 3,5, 2,4
• 2, 3, 4, 5, 1

5. 二叉树先序ABDHCFCE，中序BHDAFCCE，层序遍历 {{ select(5) }}

• ABCDFEHG
• ABCDEFCH
• ADBCEFHG
• ADCFBEHG

6. 核心采用二分思想的数据结构 {{ select(6) }}

• 伸展树
• 动态树
• 线段树
• 分块

7. n点m边稀疏正权图单源最短路最优复杂度 {{ select(7) }}

• $O(n^3)$
• $O(m \log n)$
• $O(nm)$
• $O((n+m)\log m)$

8. 根深度0，高度h三叉树最多节点 {{ select(8) }}

• $h$
• $3^{h+1}-1$
• $3$
• $\frac{3^{h+1}+1}{2}$

9. DFS对应数据结构 {{ select(9) }}

• 栈
• 队列
• 堆
• 链表

10. 5个无标号无根树数量 {{ select(10) }}

• 2
• 3
• 4
• 5

11. $T(N)=5T(\frac{N}{4})+O(N)$ 复杂度 {{ select(11) }}

• $O(N^{\log_4 5})$
• $O(N \log_2 N)$
• $O(N^{\log_4 5}\log_2 N)$
• $O(N^{\log_4 5}\log_2\log_2 N)$

12. 6本不同书放3不同书架，书架内顺序区分，每架至少一本方案数 {{ select(12) }}

• 14400
• 7200
• 43200
• 5760

13. 递推$f_n=(2017 f_{n-1}+2018 f_{n-2})\bmod 2020,f_1=0,f_2=1$，求$f_{2021}$ {{ select(13) }}

• 1825
• 1107
• 1791
• 1239

14. 前缀表达式 *+3 1-8/4 2 结果 {{ select(14) }}

• 30
• 54
• 24
• 28

15. 5G在OS七层模型层级 {{ select(15) }}

• 数据链路层(L2)
• 传输层(L4)
• 会话层(L5)
• 应用层(L7)

二、阅读程序（判断1.5分，选择3/4分，总分40）

阅读程序1 排列计数取模

#include<bits/stdc++.h>
#define MAXN 5005
using namespace std;
const int MOD=1e9+7;
int pw(int x,int i){
    if(!i)return 1;
    int mid=pw(x,i>>1);
    return ((long long)mid*mid%MOD)*((i&1)?x:1)%MOD;
}
int A(int n,int m){
    int s=1;
    for(int i=1;i<=m;i++)
        s=(long long)s*(n-i+1)%MOD;
    return s;
}
int a[MAXN], cnt[MAXN], chk[MAXN];
int main(){
    int n;
    scanf("%d",&n);
    long long sum=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum=sum+a[i];
        chk[i]=a[i];
    }
    int aver=sum*1.0/n;
    if((long long)aver*n!=sum){
        printf("0\n");
        return 0;
    }
    sort(chk+1,chk+n+1);
    int tot=unique(chk+1,chk+n+1)-chk-1,upper=0,lower=0;
    for(int i=1;i<=n;i++){
        int pos=lower_bound(chk+1,chk+tot+1,a[i])-chk;
        cnt[pos]++;
        if(a[i]<aver) lower++;
        if(a[i]>aver) upper++;
    }
    int b=1;
    for(int i=1;i<=tot;i++){
        int c=1;
        for(int j=1;j<=cnt[i];j++)
            c=(long long)c*j%MOD;
        b=(long long)b*pw(c,MOD-2)%MOD;
    }
    long long ans=A(lower,lower)*A(upper,upper)%MOD*A(n,n-lower-upper)%MOD*b%MOD;
    if(lower==1) swap(lower,upper);
    if(upper==1) printf("%lld",(long long)A(n,n)*b%MOD);
    else if(lower) printf("%lld",2*1ll*ans%MOD);
    else printf("%lld",ans);
    return 0;
}

16. 47行删除swap，48行前加else输出不变 {{ select(16) }}

• √
• ×

17. 程序最坏时间$O(n^2)$ {{ select(17) }}

• √
• ×

18. 浮点数aver会产生精度误差 {{ select(18) }}

• √
• ×

19. MOD改为1000000000代码逻辑不变 {{ select(19) }}

• √
• ×

20. 输入4换行2 8 2 4输出 {{ select(20) }}

• 8
• 6
• 4
• 3

21. n=3，1~5随机$a_i$输出期望 {{ select(21) }}

• $\frac{185}{41}$
• $\frac{37}{25}$
• $\frac{41}{35}$
• $\frac{41}{13}$

阅读程序2 bitset高精度数列

#include<bits/stdc++.h>
#define rep(x,1,r) for(int x=(1);x<=(r);++x)
#define per(x,r,1) for(int x=(r);x>=(1);--x)
using namespace std;
const int maxn=1e4+5;
int k,tot;
struct number{
    bitset<200>a;int len;
    number(){a.reset();len=0;}
    inline void print (){
        per(i,len-1,0)printf("%d",(int)a[i]);puts("");
    }
    friend number operator+(number p,number q){
        number res;res.len =max(p.len,q);
        int c=0,t;
        rep(i,0,res.len-1){
            t=(int)p.a[i]+(int)q.a[i]+c;
            res.a[i]=t%2;c=t>>1;
        }
        if(c&&res<180) res.a[res.len++]=1;
        return res;
    }
}dp[maxn],p[200],d[maxn];
int g(){
    int res=0,f=1;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));
    do{res=res*10+ch-'0';ch=getchar();}while (isdigit(ch));
    return res*f;
}
int main(){
    p[0].a[0]=1;p[0].len=1;
    rep(i,1,180) rep(j,1,10) p[i]=p[i]+p[i-1];
    k=g();
    rep(i,0,114514){
        int n=tot;
        rep(i,0,n){
            number res=dp[i];
            res.len =1;res.a[1]=1;
            number dd=d[i];
            int fl=1;
            rep(t,0,res.len-1)
                if(dd.a[t]!=res.a[t]){fl=0;break;}
            if(fl){
                dp[++tot]=res;
                d[tot]=dd;
            }
            if(tot==k)break;
        }
        if(tot==k)break;
    }
    dp[k].print();
    return 0;
}

22. p[i]+=p[i]替换重载+可编译 {{ select(22) }}

• √
• ×

23. print去掉(int)强制转换编译错误 {{ select(23) }}

• √
• ×

24. g函数去掉负号判断输出不变 {{ select(24) }}

• √
• ×

25. 末尾d[0].print会输出0 {{ select(25) }}

• √
• ×

26. 程序时间复杂度最接近 {{ select(26) }}

• $O(kk)$
• $O(k^3)$
• $O(k \ln k)$
• $O(k^2)$

27. 输入17输出 {{ select(27) }}

• 11001
• 11000
• 11100
• 11010

阅读程序3 区间懒标记线段树

#include<bits/stdc++.h>
#define int long long
#define rep(x,1,r) for(int x=(1);x<=(r);++x)
#define per(x,r,1)for(intx=(r);x>=(1);--x)
using namespace std;
const int maxn=5e5+5;
int n,m,a[maxn],s[maxn];
struct DataStructure{
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1 |1,mid+1,r
    int ad[maxn<<2], lz[maxn<<2],mul[maxn<<2];
    int tl[maxn<<2],tr[maxn<<2],mx[maxn<<2],mn[maxn<<2], sum[maxn<<2];
    void build(int rt,int l,int r){
        ad[rt]=lz[rt]=0;mul[rt]=1;
        tl[rt]=l;tr[rt]=r;mx[rt]=0;mn[rt]=0;sum[rt]=0;
        if(l==r)return;
        build(lson);build(rson);
    }
    void add(int rt,int x,int y,int z){
        mul[rt]*=y;ad[rt]*=y;lz[rt]*=y;ad[rt]+=x;lz[rt]+=z;
        mx[rt]=mx[rt]*y+x+z*a[tr[rt]];
        mn[rt]=mn[rt]*y+x+z*a[tl[rt]];
        sum[rt]=sum[rt]*y+x*(tr[rt]-tl[rt]+1)+z*(s[tr[rt]]-s[tl[rt]-1]);
    }
    void pushdown(int rt){
        add(rt<<1,ad[rt],mul[rt],lz[rt]);
        add(rt<<1|1,ad[rt],mul[rt],lz[rt]);
        ad[rt]=lz[rt]=0;mul[rt]=1;
    }
    void pushup(int rt){
        sum[rt]=sum[rt<<1]+sum[rt<<1|1];
        mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
        mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
    }
    void modify(int rt,int l,int r){
        if(l==r){add(rt,limit,0,0);return;}
        pushdown(rt);
        if(mx[rt<<1]>limit) modify(lson);
        else modify(rson);
        pushup(rt);
    }
    int query(int rt,int l,int r,int x,int y){
        if(x<=l&&r<=y) return sum[rt];
        pushdown(rt);int res=0;
        if(x<=mid) res+=query(lson,x,y);
        if(mid+1<=y) res+=query(rson,x,y);
        return res;
    }
}T;
int g(){
    int res=0,f=1;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));
    do{res=res*10+ch-'0';ch=getchar();}while (isdigit(ch));
    return res*f;
}
signed main(){
    n=g();m=g();
    rep(i,1,n)a[i]=g();
    sort(a+1,a+n+1);
    rep(i,1,n)s[i]=s[i-1]+a[i];
    T.build(1,1,n);
    rep(turn,1,m){
        int d=g(),limit=g();
        T.add(1,0,1,d-1);
        int ss=T.query(1,1,n,1,n);
        if(T.mx[1]>limit) T.modify(1,1,n);
        printf("%lld\n",ss-T.query(1,1,n,1,n));
    }
    return 0;
}

28. 第58行sort不可删除 {{ select(28) }}

• √
• ×

29. modify判断mx改为mn逻辑不变 {{ select(29) }}

• √
• ×

30. #define mid (l+r)>>1语法合法 {{ select(30) }}

• √
• ×

31. add内语句交换顺序结果不变 {{ select(31) }}

• √
• ×

32. 输入4 4 1 2 4 3 1 12 2 3 0 4 4输出 {{ select(32) }}

• 4 6 13 2
• 6 6 18 0
• 3 4 10 1
• 5 9 20 4

33. 整体时间复杂度 {{ select(33) }}

• $O((n+m)\log m)$
• $O(n \log(n+m))$
• $O(m \log(n+m))$
• $O((n+m)\log n)$

三、完善程序（每题3分，共30分）

完善程序1 三类重量01背包优化

#include<bits/stdc++.h>
#define int long long
#define rep(x,1,r) for(int x=(1);x<=(r);++x)
#define per(x,r,1) for(int x=(r);x>=(1);--x)
const int maxn=3e5+5;
int n,m,ans;
pair<int, int>dp[maxn];
int v[4][maxn],p[4];
int g(){
    int res=0,f=1;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));
    do{res=res*10+ch-'0';ch=getchar();}while (isdigit(ch));
    return res*f;
}
signed main(){
    n=g();m=g();
    rep(i,1,n){
        int w=g(),c=g();
        v[w][++p[w]]=c;
    }
    rep(i,1,3) sort(v[i]+1,v[i]+p[i],greater<int>());
    rep(i,1,3) rep(j,1,p[i]) v[i][j]+=v[i][j-1];
    dp[1].first=1;
    rep(i,2,m){
        if(dp[i-1].first<p[1]){
            dp[i].first=dp[i-1].first+1;
            dp[i].second=dp[i-1].second;
        }else if(①){
            dp[i].first=dp[i-2].first;
            dp[i].second=dp[i-2].second;
        }
        if(②>v[1][dp[i].first]+v[2][dp[i].second]){
            dp[i].first=dp[i-1].first+1;
            dp[i].second=dp[i-1].second;
        }
    }
    rep(i,0,m/3){
        ans =max(ans,③);
    }
    printf("%lld\n",ans);
    return 0;
}

34. ① {{ select(34) }}

• dp[i-2].second<p[2]
• dp[i-2].second<p[1]
• dp[i-2].first<p[1]
• dp[i-2].first<p[2]

35. ② {{ select(35) }}

• v[1][dp[i-1].first+1]+v[2][dp[i-1].second]
• v[2][dp[i-1].first]+v[1][dp[i-1].second+1]
• v[1][dp[i-1].first]+v[2][dp[i-1].second+1]
• v[2][dp[i-1].first+1]+v[1][dp[i-1].second]

36. ③ {{ select(36) }}

• v[1][dp[m-i3].first ]+v[2][dp[m-i3].second ]
• v[1][dp[m-i].first ]+v[2][dp[m-i*2].second ]
• v[1][dp[m-i2].first ]+v[2][dp[m-i1].second ]
• v[1][dp[m-i2].first ]+v[2][dp[m-i2].second ]

完善程序2 红蓝花花环计数DP

#include<bits/stdc++.h>
#define rep (x,1,r)for(intx=(1);x<=(r);++x)
#define per(x,r,1) for(int x=(r);x>=(1);--x)
using namespace std;
const int maxn=505;
int n,k,a[maxn],b[maxn],dp[maxn][maxn];
int g(){
    int res=0,f=1;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while (!isdigit (ch));
    do{res=res*10+ch-'0';ch=getchar();}while (isdigit (ch));
    return res*f;
}
signed main(){
    n=g();k=g();
    long long sum=0,ans=0;
    rep(i,1,n)a[i]=g(),b[i]=g(),sum+=a[i]+b[i];
    dp[0][0]=1;
    rep(i,1,n){
        rep(j,0,k){
            dp[i][j]=dp[i-1][①];
            int lim=min(k-1,a[i]);
            rep(l,0,lim){
                if((j-l+k)%k==0){
                    dp[i][j]=dp[i-1][(j-l+k)%k];
                }
            }
        }
    }
    per(i,k-1,0){
        if(dp[n][i]){
            ans=max(ans,②);
        }
    }
    printf("%lld\n",ans);
    return 0;
}

37. ① {{ select(37) }}

• k
• k-1
• k-2
• k+1

38. ② {{ select(38) }}

• (sum-i)/k*2
• (sum-i-k)/k
• (sum-i)/k
• (sum-i+k)/k