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

1. 定义int a=19;float x=1.2,y=2.4;，表达式(int)(a * x) * y的值是 {{ select(1) }}

• 54.72
• 55.2
• 52.8
• 52

2. 计算机辅助制造缩写 {{ select(2) }}

• CAM
• CAD
• CAI
• CAT

3. 1000张1024×1536 32位真彩色图像，至少需要多少张300MB光盘存储 {{ select(3) }}

• 50
• 100
• 200
• 400

4. 中缀a*(b+c)*d后缀表达式 {{ select(4) }}

• abcd*+*
• abc+d
• abc+d
• abc*+d*

5. 空栈依次a,b,c,d,e入栈，不可能的出栈序列 {{ select(5) }}

• a,b,c,d,e
• a,b,d,c,e
• a,d,c,e,b
• a,e,d,b,e

6. 根为第0层，二叉第10层最多节点数 {{ select(6) }}

• 512
• 1024
• 2048
• 4096

7. 20人数学满分，10人物理满分，3人两科都满分，班级最少人数 {{ select(7) }}

• 20
• 24
• 27
• 30

8. 不稳定排序 {{ select(8) }}

• 堆排序
• 归并排序
• 插入排序
• 折半插入排序

9. n,m∈[0,255]，满足n+m=(n & m) ^ (n | m)的有序对数量 {{ select(9) }}

• 256
• 6561
• 6739
• 65536

10. n点m边图Floyd时间复杂度 {{ select(10) }}

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

11. 第一位计算机程序员 {{ select(11) }}

• 图灵
• 巴贝奇
• 香农
• 艾达·洛夫莱斯

12. 2021.9.1周三，2022.1周几 {{ select(12) }}

• 星期二
• 星期三
• 星期五
• 星期六

13. gcd(41184,65208)范围 {{ select(13) }}

• 1~1000
• 1001~2000
• 2001~3000
• 3001~4000

14. 1~10全排列，3在第二位、1相邻均为偶数的方案数 {{ select(14) }}

• 86400
• 100800
• 111600
• 120960

15. NOI C++源文件规定后缀 {{ select(15) }}

• cpp
• cjj
• c++
• c ++

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

阅读程序1 平面最远点最小最大距离

#include<bits/stdc++.h>
using namespace std;
struct Point{
    int x,y;
}s[1000];
int Dis(int a,int b,int x,int y){
    return (a-x)*(a-x)+(b-y)*(b-y);
}
int main(){
    int n;
    cin>>n;
    for (int i=0;i<n;i++){
        cin>>s[i].x>>s[i].y;
    }
    int ans=1e9;
    for (int i=0;i<n;i++){
        int t=-1e9;
        for (int j=0;j<n;j++){
            if(i==j){
                continue;
            }
            t=max(t,Dis(s[i].x,s[i].y,s[j].x,s[j].y));
        }
        ans=min(ans,t);
    }
    printf("%d\n",ans);
    return 0;
}

16. n>1，坐标0~1e3，t=0替换t=-1e9答案可能变 {{ select(16) }}

• √
• ×

17. 删除i==j跳过分支答案不变 {{ select(17) }}

• √
• ×

18. 1<n≤1e3输出非负整数 {{ select(18) }}

• √
• ×

19. j=0改为j=i+1答案不一定变 {{ select(19) }}

• √
• ×

20. n=1输出 {{ select(20) }}

• -1000000000
• 1000000000
• 0
• 1

21. n>1坐标0~1e3说法正确 {{ select(21) }}

• 所有x奇数答案偶数，则y全奇数
• 所有x奇数答案偶数，则y全偶数
• 所有x奇数答案奇数，则y不能全偶数
• 答案模4余3存在

阅读程序2 有序数组最小差值

#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
int n,a[1000];
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    int t=INF;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if (abs(a[j]-a[i])<t){
                t=abs(a[j]-a[i]);
            } else {
                break;
            }
        }
    }
    cout<<t<<endl;
    return 0;
}

22. a元素互不相同输出正数 {{ select(22) }}

• √
• ×

23. 删除sort输出不变 {{ select(23) }}

• √
• ×

24. 删除else break复杂度不变 {{ select(24) }}

• √
• ×

25. <改为<=复杂度不变 {{ select(25) }}

• √
• ×

26. n=10，递推a[i]=(a[i-1]*3+2)%49输出 {{ select(26) }}

• 0
• 1
• 2
• 4

27. 程序时间复杂度 {{ select(27) }}

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

阅读程序3 LR字符串区间递推

#include<bits/stdc++.h>
using namespace std;
int n,a[10005],q[10005],vis[10005];
int main(){
    int H=1,T=0;
    string s;
    cin>>s;
    n=s.length()+1;
    s=" "+s+" ";
    if(s[1]=='R'){
        q[++T]=1;
        vis[1]=1;
    }
    if(s[n-1]=='L'){
        q[++T]=n;
        vis[n]=1;
    }
    for (int i=2;i<n;i++){
        if(s[i-1]=='L'&&s[i]=='R') {
            q[++T]=i;
            vis[i]=1;
        }
    }
    while (H<=T){
        int k=q[H++];
        if(k>1 && s[k-1]=='L'){
            a[k-1]=max(a[k-1],a[k]+1);
            if(!vis[k-1]){
                q[++T]=k-1;
                vis[k-1]=1;
            }
        }
        if (k<n && s[k]=='R') {
            a[k+1]=max(a[k+1],a[k]+1);
            if(!vis[k+1]){
                q[++T]=k+1;
                vis[k+1]=1;
            }
        }
    }
    long long ans=0;
    for(int i=1;i<=n;i++){
        ans+=a[i];
    }
    printf("%lld",ans);
    return 0;
}

28. 答案严格小于$(|s|+1)^2$ {{ select(28) }}

• √
• ×

29. 循环结束T一定等于n {{ select(29) }}

• √
• ×

30. 去掉k>1判断输出可能改变 {{ select(30) }}

• √
• ×

31. 去掉vis允许重复入队复杂度不变 {{ select(31) }}

• √
• ×

32. s="RLRRRLLRLLR"输出 {{ select(32) }}

• 8
• 10
• 12
• 14

33. s由10段"LLRL"拼接输出 {{ select(33) }}

• 40
• 43
• 58
• 60

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

完善程序1 错位匹配线段树矩阵维护

#include<bits/stdc++.h>
#define LL long long
using namespace std;
namespace FastIO{
    template<typename Ty>void read (Ty &x){
        char c;int f=1;x=0;
        while (!isdigit(c)){
            if(c=='-') f=-1;
            c=getchar();
        }
        while (isdigit(c)){
            x=x*10+c-'0';
            c=getchar();
        }
        x*=f;
    }
    template<typename Ty,typename...Ar>void read (Ty &x,Ar &...y){read(x);read(y...);}
    template<typename Ty>void write (Ty x){
        if(x<0){ putchar('-');x=-x; }
        if(x<10) putchar(x+'0');
        else{ write(x/10); putchar(x%10); }
    }
    template<typename Ty>void writeln (const Ty &x){ write(x); putchar('\n'); }
}
using namespace FastIO;
const int N=3e4+10;
int n,q, ida[N], idb[N], ban[N],pa[N],pb[N];
LL inf=2e17,a[N],b[N];
struct Matrix{
    LL a[3][3];
    Matrix(){
        int i,j;
        for(i=0;i<3;i++)
            for(j=0;j<3;j++)
                ①;
    }
};
Matrix operator*(const Matrix &A,const Matrix &B){
    Matrix Ans;
    int i,j,k;
    for(i=0;i<3;i++)
        for(j=0;j<3;j++){
            Ans.a[i][j]=②;
            for(k=0;k<3;k++)
                Ans.a[i][j]=Ans.a[i][j]+A.a[i][k]*B.a[k][j];
        }
    return Ans;
}
Matrix T[N<<2];
Matrix Get(int x){
    Matrix Ans;
    Ans.a[1][0]=Ans.a[2][1]=0;
    if (ban[x]!=x){
        Ans.a[0][0]=a[x]*b[x];
    } else {
        Ans.a[0][0]=-inf;
    }
    if (x>1 && ban[x]!=x-1 && ban[x-1]!=x){
        Ans.a[0][1]=a[x]*b[x-1]+a[x-1]*b[x];
    } else {
        Ans.a[0][1]=-inf;
    }
    if(x>2){
        if (ban[x-2]!=x && ban[x-1]!=x-1 && ban[x]!=x)
            Ans.a[0][2]=max(Ans.a[0][2],a[x-2]*b[x]+a[x-1]*b[x-1]+a[x]*b[x-2]);
        ③;
    }
    return Ans;
}
void pushup (int x) {
    T[x]=④;
}
void Build(int x=1,int l=1,int r=n){
    if(l==r){
        T[x]=Get(l);
        return;
    }
    int mid=l+r>>1;
    Build(x<<1,l,mid);
    Build(x<<1|1,mid+1,r);
    pushup(x);
}
void Modify(int p,int x=1,int l=1,int r=n){
    if(l==r){
        T[x]=Get(l);
        return;
    }
    int mid=l+r>>1;
    if(p<=mid) Modify(p,x<<1,l,mid);
    else Modify(p,x<<1|1,mid+1,r);
    pushup(x);
}
void Work(int x){
    int i;
    for (i=max(1,pa[x]-2);i<=min (n,pa[x]+2);i++)
        Modify(i);
}
void Update (int x,int y){
    ⑤;
    Work(y);
}
int main(){
    int i,x,y;
    read(n,q);
    for(i=1;i<=n;i++) read(a[i]),ida[i]=i;
    for(i=1;i<=n;i++) read(b[i]),idb[i]=i;
    sort(ida+1, ida+n+1,[&](const int &x, const int &y){return a[x]<a[y];});
    sort(idb+1, idb+n+1,[&](const int &x, const int &y){return b[x]<b[y];});
    for(i=1;i<=n;i++){
        pa[ida[i]]=i;
        pb[idb[i]]=i;
    }
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    for(i=1;i<=n;i++){
        ban[pa[i]]=pb[i];
    }
    Build();
    while(q--){
        read(x,y);
        Update (x,y);
        writeln (T[1].a[0][0]);
    }
    return 0;
}

34. ① {{ select(34) }}

• a[i][j]=0
• a[i][j]=inf
• a[i][j]=-inf
• a[i][j]=1

35. ② {{ select(35) }}

• Ans.a[i][j]+A.a[i][k]*B.a[k][j]
• max(Ans.a[i][j], A.a[i][k]*B.a[k][j])
• Ans.a[i][j]*A.a[i][k]*B.a[k][j]
• 0

36. ③ {{ select(36) }}

• if(ban[x-2]!=x-1 && ban[x-1]!=x && ban[x]!=x-2) Ans.a[0][2]=max(Ans.a[0][2],a[x-2]*b[x-1]+a[x-1]*b[x]+a[x]*b[x-2])
• if(ban[x-2]!=x-2 && ban[x-1]==x && ban[x]!=x-1) Ans.a[0][2]=max(Ans.a[0][2],a[x-2]*b[x-2]+a[x-1]*b[x]+a[x]*b[x-1])
• if(ban[x-2]!=x && ban[x-1]!=x-2 && ban[x]!=x-1) Ans.a[0][2]=max(Ans.a[0][2],a[x-2]*b[x]+a[x-1]*b[x-2]+a[x]*b[x-1])
• if(ban[x-2]!=x-2 && ban[x-1]!=x && ban[x]!=x) Ans.a[0][2]=max(Ans.a[0][2],a[x-2]*b[x-2]+a[x-1]*b[x-1]+a[x]*b[x])

37. ④ {{ select(37) }}

• T[x<<1] * T[x<<1|1]
• T[x<<1|1] * T[x<<1]
• T[x<<1]+T[x<<1|1]
• max(T[x<<1], T[x<<1|1])

38. ⑤ {{ select(38) }}

• swap(ban[x], ban[y]);
• swap(pb[x],pb[y]);
• swap(ban[pa[x]], ban[pa[y]]);
• swap(ban[pb[x]], ban[pb[y]]);

完善程序2 树三角 子树线段树统计

#include<bits/stdc++.h>
#define N 100005
#define inf 1047483647
using namespace std;
const int p=1e9+7;
int n,tot,m,ans1,ans2,inv;
int fir[N],w[N<<1],nxt[N<<1],son[N<<1];
int rt[N],s[N*100],ss[N*100],sum[N*100],trl[N],trr[N];
int dis[N];
vector<int>g;
int power(int x){
    int y=p-2,z=1;
    while (y){
        if(y&1) z=1ll*z*x%p;
        x=1ll*x*x%p;
        y>>=1;
    }
    return z;
}
void add (int x,int y,int z){
    son[++tot]=y;
    nxt[tot]=fir[x];
    fir[x]=tot;
    w[tot]=z;
}
void PU(int x){
    s[x]=(s[trl[x]]+s[trr[x]])%p;
    ss[x]=(ss[trl[x]]+ss[trr[x]])%p;
}
void M(int &x,int y,int l,int r) {
    if(!x){
        ①;
        return;
    }
    sum[x]=(sum[x]+sum[y])%p;
    s[x]=(s[x]+s[y])%p;
    ss[x]=(ss[x]+ss[y])%p;
    if(l==r) return;
    int mid=l+r>>1;
    if(trl[y]) M(trl[x],trl[y],1,mid);
    if(trr[y]) M(trr[x],trr[y],mid+1,r);
}
int Q(int x,int l,int r,int ll,int rr){
    if(!x) return 0;
    if(l>=ll &&r<=rr) return s[x];
    int mid=l+r>>1,res=0;
    if(mid>=ll) res=Q(trl[x],l,mid,ll,rr);
    if(mid<rr) res+=Q(trr[x],mid+1,ll,rr);
    return res%p;
}
int Qs(int x,int l,int r,int ll,int rr){
    if(!x) return 0;
    if(l>=ll &&r<=rr) return sum[x];
    int mid=l+r>>1,res=0;
    if(mid>=ll) res=Qs(trl[x],l,mid,ll,rr);
    if(mid<rr) res+=Qs(trr[x],mid+1,ll,rr);
    return res%p;
}
int Qss(int x,int l,int r,int ll,int rr){
    if(!x) return 0;
    if(l>=ll &&r<=rr) return ss[x];
    int mid=l+r>>1,res=0;
    if(mid>=ll) res=Qss(trl[x],l,mid,ll,rr);
    if(mid<rr) res+=Qss(trr[x],mid+1,ll,rr);
    return res%p;
}
void U(int &x,int l,int r,int v){
    if(!x){
        ②;
    }
    sum[x]++;
    if(l==r){
        int vv=g[v-1];
        s[x]=(s[x]+vv)%p;
        ss[x]=(ss[x]+1ll*vv*vv)%p;
        return;
    }
    int mid=l+r>>1;
    if(mid>=v) U(trl[x],l,mid,v);
    else U(trr[x],mid+1,v);
    PU(x);
}
void dfs (int x,int fa){
    g.push_back(dis[x]);
    for(int i=fir[x];i;i=nxt[i]){
        if(son[i]^fa){
            dis[son[i]]=dis[x]+w[i];
            dfs(son[i],x);
        }
    }
}
void solve (int x,int y,int z){
    int X=3;
    int tmp1=Q(rt[z],1,m,1,dis[x]);
    int tmp2=Qs(rt[z],1,m,1,dis[x]);
    int tmp3=Qss(rt[z],1,m,1,dis[x]);
    int Z=2*tmp1-1;
    ans2=(ans2+1ll*tmp1*Z%p-1ll*tmp2)%p;
    if(ans2<0) ans2+=p;
    if(dis[x]<=m){
        tmp1=Q(rt[z],1,m,dis[x]+1,m);
        tmp2=Qs(rt[z],1,m,dis[x]+1,m);
        tmp3=Qss(rt[z],1,m,dis[x]+1,m);
        ③;
        if(ans1<0) ans1+=p;
    }
    for (int i=fir[x];i;i=nxt[i]){
        if (son[i]^y) solve (son[i],x,z);
    }
}
void dfs2 (int x,int fa){
    int Max=0;
    for(int i=fir[x];i;i=nxt[i]){
        if(son[i]!=fa){
            dfs2(son[i],x);
            s[x]+=s[son[i]];
            if(s[son[i]]>s[Max]) Max=son[i];
        }
    }
    if(!Max){
        U(rt[x],1,m,lower_bound(g.begin(),g.end(),dis[x])-g+1);
        return;
    }
    rt[x]=rt[Max];
    for(int i=fir[x];i;i=nxt[i]){
        if (son[i]!=fa && son[i]!=Max){
            int to=son[i];
            solve (to,x,x);
            M(rt[x],rt[to],1,m);
        }
    }
    U(rt[x],1,m,lower_bound(g.begin(),g.end(),dis[x])-g+1);
}
int main(){
    cin>>n;
    inv=power(2);
    for(int i=1;i<n;i++){
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z); add(y,x,z);
    }
    dfs(1,0);
    sort(g.begin(),g.end());
    g.erase(unique(g.begin(),g.end()),g.end());
    m=g.size();
    dfs2(1,0);
    if (!ans2){
        puts("0");
    } else{
        cout<<1ll*ans1*power(ans2)%p<<endl;
    }
    return 0;
}

39. ① {{ select(39) }}

• x=++tot
• y=++tot
• x=y
• y=x

40. ② {{ select(40) }}

• x=++tot
• y=++tot
• x=y
• y=x

41. ③ {{ select(41) }}

• ans1=(ans1+1llinv(2lltmp1-1llZ)%p*(2llX+1ll-Z)%p+2lltmp3%p-1lltmp1Z%p+1ll*(X+1-Z)(2lltmp1-1lltmp2Z%p)%p)%p
• ans1=(ans1+1ll*(X+1-Z)(2lltmp2-1llZ)%p+inv(2lltmp1-1llZ)%p+2ll*tmp3%p)%p
• ans1=(ans+2llX+1-Z)inv+(2tmp1-tmp2Z)%p
• ans1=ans1+tmp3

42. ④（题干标注5） {{ select(42) }}

• ans2=(ans2+1ll*(2ll*X-tmp1)*Z%p)%p
• ans2=(ans2+1ll*(2ll*X-Z)*tmp2%p)%p
• ans2=(ans2+1ll*(2ll*X-Z)*tmp1%p)%p
• ans2=(ans2+1ll*(2ll*X-tmp1)*tmp2%p)%p