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

1. 无符号二进制A=101010101，B=01010111，哪种运算结果最大 {{ select(1) }}

• A and B
• A or B
• A xor B
• ~A

2. 48和60最大公约数 {{ select(2) }}

• 1
• 6
• 12
• 24

3. $(2019)_{10}+(2020)_{10}$ 结果 {{ select(3) }}

• $(3049)_{10}$
• $(BF3)_{16}$
• $(101111110001)_2$
• $(5765)_8$

4. 元素值域极小时最优排序 {{ select(4) }}

• 快速排序
• 归并排序
• 桶排序
• 插入排序

5. 不需要操作系统处理的操作 {{ select(5) }}

• 内存管理分配
• 资源优先级调度
• 解析xls文件
• 网络与文件管理

6. 不属于OSI七层应用层协议 {{ select(6) }}

• TCP
• HTTP
• FTP
• SMTP

7. 不属于解释型语言 {{ select(7) }}

• Python
• Ruby
• Java
• JavaScript

8. 未使用贪心算法 {{ select(8) }}

• Dijkstra最短路
• Huffman编码
• DP合法括号计数
• Kruskal最小生成树

9. n,k同阶，数组找第k大最坏最优复杂度 {{ select(9) }}

• $O(n\log n)$
• $O(n)$
• $O(nk)$
• $O(n^2)$

10. 5个有标号球放入3个有标号盒子，每盒至少1个方案数 {{ select(10) }}

• 540
• 720
• 150
• 144

11. x=7,y=7,z=4，val=2+1<<x/2 & y+z结果 {{ select(11) }}

• 70
• 8
• 10
• 37

12. 5点完全图，至少删几条边无环 {{ select(12) }}

• 0
• 4
• 5
• 6

13. 双端队列初始1,2,3,4,5,6，不可能出队序列 {{ select(13) }}

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

14. NOI考场合规行为 {{ select(14) }}

• 自带键盘
• 偷看他人屏幕
• 吃泡面
• 电脑异常举手示意监考

15. 正确说法 {{ select(15) }}

• Dijkstra支持任意边权
• 数组插入O(1)
• BFS用栈
• 树上两点唯一简单路径

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

阅读程序1 组合枚举DFS

#include<bits/stdc++.h>
using namespace std;
int n,m,a[15];
void dfs(int i,int value){
    if(i==m+1){
        for(int j=1;j<=m;j++) printf("%d ",a[j]);
        printf("\n");
        return;
    }
    if(value>n) return;
    for(int j=value;j<=n;j++){
        a[i]=j;
        dfs(i+1,j+1);
        a[i]=0;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    dfs(1,1);
    return 0;
}

16. m=0程序运行错误 {{ select(16) }}

• √
• ×

17. 删除第11行if(value>n) return不影响输出 {{ select(17) }}

• √
• ×

18. n不变，m增大输出行数增加 {{ select(18) }}

• √
• ×

19. 程序存在无输出情况 {{ select(19) }}

• √
• ×

20. 1<n≤6，1≤m≤n，最大输出行数 {{ select(20) }}

• 6
• 15
• 20
• 24

21. 1<n<15，多少组(n,m)仅输出一行 {{ select(21) }}

• 1
• 13
• 26
• 28

阅读程序2 分组标记矩阵

#include<bits/stdc++.h>
using namespace std;
int n,m,a[105][105],people[105];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int k,main_people=0;
        scanf("%d",&k);
        for(int j=1;j<=k;j++) scanf("%d",&people[j]);
        for(int j=1;j<=k;j++) if(people[j]==1) main_people=1;
        if(main_people){
            for(int j=1;j<=k;j++) a[people[j]][i]=1;
        }else{
            for(int j=1;j<=k;j++){
                int can=0;
                for(int l=1;l<=k;l++) if(a[people[l]][j]) can=1;
                if(can){
                    for(int l=1;l<=k;l++) a[people[l]][j]=can;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        int ok=1;
        for(int j=1;j<=m;j++) if(a[1][j]!=a[i][j]) ok=0;
        if(ok) printf("%d",i);
    }
    return 0;
}

22. 输出数字个数一定小于n {{ select(22) }}

• √
• ×

23. 18行m改为i不改变结果 {{ select(23) }}

• √
• ×

24. 删除22、25行程序结果改变 {{ select(24) }}

• √
• ×

25. 输入样例输出 {{ select(25) }}

• 1
• 1238
• 1268
• 128

26. k=2,m=3,n=5，people[2]随机2~5，输出数字和期望 {{ select(26) }}

• 39/32
• 23/16
• 15/8
• 6/5

阅读程序3 树上分组背包树形DP

#include<bits/stdc++.h>
using namespace std;
const int N=10005,M=10005,P=1e9+7;
int n,k,siz[N],dp[N][M][2][2];
vector<int>G[N];
void calc(int u,int v,int i,int j){
    for(int u_flag=0;u_flag<=1;u_flag++)
        for(int u_covered=0;u_covered<=1;u_covered++)
            for(int v_flag=0;v_flag<=1;v_flag++)
                for(int v_covered=0;v_covered<=1;v_covered++){
                    if(!v_covered&&!u_flag) continue;
                    long long tmp=1ll*dp[v][j][v_flag][v_covered]*dp[u][i][u_flag][u_covered]%P;
                    g[u][i+j][u_flag|v_flag]=(g[u][i+j][u_flag|v_flag]+tmp)%P;
                }
}
void dfs(int u,int fa){
    siz[u]=1,dp[u][0][0][0]=1,dp[u][1][1][0]=1;
    for(auto v:G[u])if(v!=fa){
        dfs(v);
        for(int i=min(siz[u],k);i>=0;i--)
            for(int j=min(siz[v],k);j>=0;j--)
                calc(u,v,i,j);
        swap(g[u],dp[u]);
        for(int i=0;i<=min(siz[u],k);i++)
            for(int a=0;a<=1;a++)
                for(int b=0;b<=1;b++) g[u][i][a][b]=0;
        siz[u]+=siz[v];
    }
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=2;i<=n;i++){
        int x,y;scanf("%d%d",&x,&y);
        G[x].push_back(y),G[y].push_back(x);
    }
    dfs(1,0);
    printf("%d",(dp[1][k][0][1]+dp[1][k][1][1])%P);
    return 0;
}

27. 邻接表遍历整树最坏$O(n^2)$ {{ select(27) }}

• √
• ×

28. 删除if(v!=fa)不改变结果 {{ select(28) }}

• √
• ×

29. i,j循环上限替换为n不影响运行 {{ select(29) }}

• √
• ×

30. n=5链，k=3输出 {{ select(30) }}

• 0
• 1
• 2
• 3

31. $n=10^3,k=10^4$复杂度 {{ select(31) }}

• $O(nk)$
• $O(n^2)$
• $O(k^2)$
• $O(nk^2)$

32. $n=10^4,k=10^3$复杂度 {{ select(32) }}

• $O(nk)$
• $O(n^2)$
• $O(k^2)$
• $O(nk^2)$

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

完善程序1 区间众数随机+树状数组

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct qry{ int rk,l,r; };
int a[N],b[N],c[N],ans[N];
vector<qry>q[N];
vector<int>pos[N];
void update(int x,int cc){
    for(int i=x;i<=n;i+=i&-i) c[i]+=cc;
}
int query(int x,int ret=0){
    for(int i=x;i>=1;i-=i&-i) ret+=c[i];
    return ret;
}
int Rand(int l,int r){
    return 1ll*rand()*rand()%(r-l+1)+l;
}
int main()
{
    memset(ans,-1,sizeof(ans));
    srand(time(NULL));
    cin>>n>>m;
    for(i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
    sort(b+1,b+n+1);
    int len=①;
    for(i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+len+1,a[i])-b;
        ②;
    }
    for(i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        if(l==r){
            ans[i]=min(a[l],a[r]);
            continue;
        }
        for(j=1;j<=40;j++){
            int pos=Rand(l,r);
            q[a[pos]].push_back((qry){i,l,r});
        }
    }
    for(i=1;i<=len;i++){
        for(j=pos[i].size()-1;j>=0;j--)
            update(pos[i][j],1);
        for(j=q[i].size()-1;j>=0;j--)
            if(③) continue;
        int tmp=query(q[i][j].r)-query(q[i][j].l-1);
        if(④) ⑤;
        for(j=pos[i].size()-1;j>=0;j--)
            update(pos[i][j],-1);
    }
    for(i=1;i<=m;i++){
        if(~ans[i]) printf("%d\n",b[ans[i]]);
        else printf("-1\n");
    }
    return 0;
}

33. ① {{ select(33) }}

• unique(b+1,b+n+1)-b
• unique(b+1,b+n)-b-1
• unique(b+1,b+n+1)-b-1
• unique(b+1,b+n)-b

34. ② {{ select(34) }}

• pos[i].push_back(a[i])
• pos[a[i]].push_back(i)
• pos[b[a[i]]].push_back(i)
• pos[i].push_back(b[a[i]])

35. ③ {{ select(35) }}

• ans[q[i][rk]]
• !ans[q[i][j].rk]
• ans[q[i][j].rk]==-1
• ~ans[q[i][j].rk]

36. ④ {{ select(36) }}

• tmp >=(q[i][j].r-q[i][j].l+1)/2+1
• tmp >=(q[i][j].r-q[i][j].l)/2
• tmp >=(q[i][j].r-q[i][j])/2+1
• tmp >=(q[i][j].r-q[i][j]+1)/2

37. ⑤ {{ select(37) }}

• ans[q[i][j].rk]=a[i]
• ans[q[i][j].rk]=b[i]
• ans[q[i][j].rk]=i
• ans[q[i][j].rk]=b[a[i]]

完善程序2 状压Dijkstra多电脑加速

#include<bits/stdc++.h>
#define LL long long
using namespace std;
struct edge{ LL v,val; };
struct com{ LL pos,vel; };
const LL M=20,N=1e6+10;
LL dis[N],vis[N],mp[M][M];
double dp[1<<(M+1)][M],vel[1<<M+1];
double ans=1e12;
LL i,j,k,m,n,s,t,now;
com c[M];
vector<edge>a[N];
priority_queue<pair<LL,LL>,vector<pair<LL,LL>>,greater<pair<LL,LL>>>q;
bool cmp(com aa,com bb){ return aa.pos<bb.pos; }
void dij(LL x){
    memset(dis,1,sizeof(dis));
    memset(vis,0,sizeof(vis));
    q.push(make_pair(0,x));
    dis[x]=0;
    while(!q.empty()){
        LL u=q.top().second;
        if(vis[u]){ q.pop(); continue; }
        vis[u]=1;
        for(edge e:a[u]){
            if(dis[e.v]<=dis[u]+e.val) continue;
            dis[e.v]=dis[u]+e.val;
            ①;
        }
    }
}
int main(){
    ans=1e12,now=0;
    memset(vel,0,sizeof(vel));
    cin>>n>>m>>s>>k;
    for(i=1;i<=n;i++) a[i].clear();
    for(②){
        cin>>c[i].pos>>c[i].vel;
    }
    for(i=1;i<=m;i++){
        LL x,y,z;
        cin>>x>>y>>z;
        a[x].push_back((edge){y,z});
        a[y].push_back((edge){x,z});
    }
    c[1].pos=1,c[1].vel=s,c[k+2].pos=n,c[k+2].vel=0;
    sort(c+1,c+k+3,cmp);
    for(i=1;i<=k+2;i++){
        if(c[i].pos==c[i+1]) ③;
        else c[++now]=c[i];
    }
    k=now;
    for(i=1;i<=k;i++){
        dij(c[i].pos);
        for(j=1;j<=k;j++) mp[i][j]=dis[c[j].pos];
    }
    if(mp[1][k]>=1e11){
        printf("Impossible\n");
        return 0;
    }
    for(i=1;i<1<<k;){
        for(j=1;j<=k;){
            ④;
        }
    }
    dp[1][1]=0;
    for(i=1;i<1<<k;i++)
        for(j=1;j<=k;j++){
            if(((1<<(j-1))&i)==0) continue;
            for(LL l=1;l<=k;l++){
                if(l==j||((1<<(l-1))&i)) continue;
                ⑤;
            }
        }
    for(i=1;i<1<<k;i++) ans=min(ans,dp[i][k]);
    printf("%.2f\n",ans);
    return 0;
}

38. ① {{ select(38) }}

• q.push(make_pair(dis[e.v],-e.v))
• q.push(make_pair(-dis[e.v],e.v))
• q.push(make_pair(dis[e.v],e.v))
• q.push(make_pair(-dis[e.v],-e.v))

39. ② {{ select(39) }}

• i=2;i<=k+1;i++
• i=1;i<=k;i++
• i=3;i<=k+2;i++
• i=0;i<=k-1;i++

40. ③ {{ select(40) }}

• c[now+1].vel+=c[i].vel
• c[i].vel+=c[i+1].vel
• c[now+1].vel+=c[i+1].vel
• c[i+1].vel+=c[i]

41. ④ {{ select(41) }}

• if((1<<j)&i) vel[j]+=c[i].vel
• if((1<<(j-1))&i) vel[j]+=c[i].vel
• if((1<<j)&i) vel[i]+=c[j].vel
• if((1<<(j-1))&i) vel[i]+=c[j].vel

42. ⑤ {{ select(42) }}

• dp[i][l]=min(dp[i][l],dp[i-(1<<(j-1))][j]+mp[j][l]/vel[i-(1<<(j-1))])
• dp[i][j]=min(dp[i][j],dp[i-(1<<(j-1))][l]+mp[j][l]/vel[i-(1<<(j-1))])
• dp[i][l]=min(dp[i][l],dp[i-(1<<(l-1))][j]+mp[i][l]/vel[i-(1<<(l-1))])
• dp[i][j]=min(dp[i][j],dp[i-(1<<(l-1))][i]+mp[1][i]/vel[i-(1<<(j-1))])