该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ⨉ ；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

#include<bits/stdc++.h>
using namespace std;
template <class T>
class MyHeap {
    vector <T> ve;
    vector <int> place;
    vector <bool> vis;
public:
    void push(T a){
        int now;
        if (ve.empty()) {
            ve.push_back(a);
            vis.push_back(0);
        }
        if (place.size()) {
            now = place[place.size() - 1];
            vis[now] = 0;
            ve[now] = a;
            place.pop_back();
        } else {
            ve.push_back(a);
            vis.push_back(0);
            now = ve.size() - 1;
        }
        while (now != 1) {
            if (ve[now / 2] > ve[now]) {
                swap(ve[now / 2] ,ve[now]);
                now /= 2;
            } else {
                break;
            }
        }
    }
    unsigned long long size() {
        return ve.size() - place.size() - 1;
    }
    bool empty() {
        return ve.size() - place.size() - 1 <= 0;
    }
    T top() {
        return ve[1];
    }
    void pop() {
        int now = 1;
        while (true) {
            if (now * 2 + 1 >= ve.size() || vis[now * 2 + 1]) {
                if (now * 2 >= ve.size() || vis[now * 2]) {
                    vis[now] = 1;
                    place.push_back(now);
                    break;
                } else {
                    swap(ve[now],ve[now * 2]);
                    now *= 2;
                }
            } else if(vis[now * 2]) {
                swap(ve[now * 2 + 1], ve[now]);
                now = now * 2 + 1;
            } else if(ve[now * 2] < ve[now * 2 + 1]) {
                swap(ve[now],ve[now * 2]);
                now *= 2;
            } else {
                swap(ve[now * 2 + 1], ve[now]);
                now = now * 2 + 1;
            }
        }
    }
};
int main(){
    MyHeap<long long>my;//69行
    long long n,a,sum = 0,b;
    cin >> n;
    //cout << my.size() << endl; 72行
    while (n--) {
        cin >> a;
        my.push(a);
    }
    while (my.size() >= 2) {//76行
        a = my.top();
        my.pop();
        b = my.top();
        my.pop();
        sum += a + b;
        my.push(a + b);
    }
    cout << sum << endl;
    return 0;
}

**1 <= N ,a <= $10^4$ **

判断题

1. 如果在第72行输出my.size()，其输出-1 {{ select(1) }}

• 正确
• 错误

2. 变量my内部元素ve不会变小 {{ select(2) }}

• 正确
• 错误

3. 程序第二次运行到第76行时，my数组占用的空间不会变大 {{ select(3) }}

• 正确
• 错误

4. 69行替换为 $MyHeap <int> my;$不影响结果 {{ select(4) }}

• 正确
• 错误

选择题

5. 该程序的时间复杂度为 {{ select(5) }}

• O(n)

• O ($n^2$)

• O ($n log n$)

• O($nlog^2n$)

6. 当输入为

5
1 2 3 4 5

时，输出为() {{ select(6) }}

• 33

• 40

• 15

• 0

7. 当输入为

1024
1 1 1 1 ..... 1 1 1 (共1024个1)

时，输出为() {{ select(7) }}

• 10500
• 10000
• 9976
• 10240

完善程序（单选题，每小题 3 分）

题目描述

科学家们在 Samuel 星球上的探险仍在继续。非常幸运的，在 Samuel 星球的南极附近，探险机器人发现了一个巨大的冰湖！机器人在这个冰湖中搜集到了许多 RNA 片段运回了实验基地。

科学家们经过几个昼夜的研究，发现这些 RNA 片段中有许多是未知的病毒！

每个 RNA 片段都是由 A、C、T、G 组成的序列。科学家们也总结出了 Samuel 星球上的“病毒模版片段”。一个模版片段是由 A、C、T、G 的序列加上通配符 * 和 ? 来表示。其中 * 的意思是可以匹配上 $0$ 个或任意多个字符，而 ? 的意思是匹配上任意一个字母。

如果一个 RNA 片段能够和“病毒模版片段”相匹配，那么这个 RNA 片段就是未知的病毒。

例如，假设 “病毒模版片段”为 A*G?C。RNA 片段：AGTC，AGTGTC 都是未知的病毒，而 RNA 片段 AGTGC 则不是病毒。

由于，机器人搜集的这些 RNA 片段中除去病毒的其他部分都具有非常高的研究价值。所以科学家们希望能够分辨出其中哪些 RNA 片段不是病毒，并将不是病毒的 RNA 片段运回宇宙空间站继续进行研究。

科学家将这项任务交给了小联。现在请你为小联编写程序统计哪些 RNA 片段不是病毒。

输入格式

共 $N+2$ 行输入。

第一行有一个字符串，由 A、C、T、G、*、? 组成，表示“病毒模版片段”。“病毒模版片段”的长度不超过 $1000$。

第二行有一个整数 $N$，表示机器人搜集到的 RNA 片段的数目。

随后的 $N$ 行，每一行有一个字符串，由 A、C、T、G 组成，表示一个 RNA 片段。

输出格式

只有一行输出，为整数 $M$，即不是病毒的 RNA 片段的数目。

样例 #1

样例输入 #1

A*G?C
3
AGTC
AGTGTC
AGTGC

样例输出 #1

1

提示

输入中的 RNA 片段 AGTGC 不是病毒。

对于所有数据，$0 < N < 500$。

特别的：

• 每个 RNA 片段的长度不超过 $500$；
• “病毒模版片段”和 RNA 片段的长度都至少为 $1$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int tire[250050][5], idx = 0;
int cnt[250050];
int change(char x) {
    switch (x) {
        case 'A':return 0;
        case 'G':return 1;
        case 'T':return 2;
        default:return 3;
    }
}
void insert(string s) {
    int now = 0;
    for(auto i : s) {
        int g = change(i);
        if(!tire[now][g]) {
            __1__
        }
        now = tire[now][g];
    }
    ++cnt[now];
}
string s,sp;
int n;
int vis[250050][510];
int find(int now,int place) {
    int sum = 0;
    if(vis[now][place]) __2__
    if (place == s.size()) { 
        __3__
        return sum;
    }
    if (s[place] == '?') {
        for (int i = 0; i <= 4; i++) {
            if (tire[now][i]) {
                sum += find(__4__, place + 1);
            }
        }
    } else if (s[place] == '*') {
        sum += find(now, place + 1);
        for (int i = 0; i <= 4; i++) {
            if (tire[now][i]) {
                sum += find(__4__, place + 1);
                sum += find(__4__, place);
            }
        }
    } else {
        int g = change(s[place]);
        if (tire[now][g]) {
            sum += find(__4__, place + 1);
        }
    }
    vis[now][place] = sum + 1;
    return sum;
}
signed main() {
    cin >> s >> n;
    for (int i = 0; i < n; i++) {
        cin >> sp;
        insert(sp);
    }
    cout << __5__;
    return 0;
}

1.1处应该填写（） {{ select(8) }}

• tire[now] [g] = ++idx;

• tire[now] [g] = idx++;

• tire[g] [now] = idx++;

• tire[g] [now] = ++idx;

2.2处应该填写（） {{ select(9) }}

• return 0;
• return vis[now] [place]
• return vis[tire[now] [g]] [place]
• return vis[tire[now] [g]] [place + 1]

3.3处应该填写（） {{ select(10) }}

• sum +=cnt[now], cnt[now]--;
• sum = cnt[now], cnt[now]++;
• return sum^=cnt[now], cnt[now]^=sum, sum;
• return sum |= cnt[now], cnt[now]|=sum, sum;

4.4处应该填写（） {{ select(11) }}

• tire[place] [i]
• i
• now
• tire[now] [i]

5.5处应该填写（） {{ select(12) }}

• find(0,0)
• n - find(1,1)
• n - find(0,0)
• find(1,1)