首页 › 题库 › C/C++编程考级 › C/C++编程六级

C/C++编程六级 题库

共 76 道题 ,第 3 / 4 页 · 按题型筛选,点「查看答案」核对解析
41 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 2 链表

区块反转

给定一个单链表 L,我们将每 K 个结点看成一个区块(链表最后若不足 K 个结点,也看成一个区块),请编写程序将 L 中所有的区块链反转。例如:给定 L 为 1→2→3→4→5→6→7→8,K 为 3,则输出应该为 7→8→4→5→6→1→2→3。

时间限制:6000

内存限制:65535

输入

每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N (≤ 105)、以及正整数 K (≤ N),即区块的大小。结点的地址是 5 位非负整数,NULL 地址用 -1 表示。 接下来有 N 行,每行格式为: Address Data Next 其中 Address 是结点地址,Data 是该结点保存的整数数据,Next 是下一结点的地址。

输出

对每个测试用例,顺序输出反转后的链表,其上每个结点占一行,格式与输入相同。

样例输入

00100 8 3
71120 7 88666
00000 4 99999
00100 1 12309
68237 6 71120
33218 3 00000
99999 5 68237
88666 8 -1
12309 2 33218

样例输出

71120 7 88666
88666 8 00000
00000 4 99999
99999 5 68237
68237 6 00100
00100 1 12309
12309 2 33218
33218 3 -1
答案与解析
参考答案
#include <iostream>
#include <vector>
using namespace std;
struct node {
    int data, next;
}A[100001];
vector<int> L, ans, E[100001];
int s, n , a, t, k, mark, cnt, c;
int main() {
    cin >> s >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a;
        cin >> A[a].data >> A[a].next;
    }
    t = s;
    while (t != -1) {
        L.push_back(t);
        t = A[t].next;
    }
    n = L.size();
    for (int i = 0; i < n; i++) {
        E[c].push_back(L[i]);
        cnt++;
        if (cnt == k && i != n - 1) {
            cnt = 0;
            c++;
        }
    }
    for (int i = c; i >= 0; i--)
        for (auto it : E[i]) 
            ans.push_back(it);
    for (int i = 1; i < n; i++) 
        printf("%05d %d %05d\n", ans[i - 1], A[ans[i - 1]].data, ans[i]);
    printf("%05d %d -1", ans.back(), A[ans.back()].data);
    return 0;
}
题目详情
42 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 6 组合数学

彩虹瓶

彩虹瓶的制作过程(并不)是这样的:先把一大批空瓶铺放在装填场地上,然后按照一定的顺序将每种颜色的小球均匀撒到这批瓶子里。

假设彩虹瓶里要按顺序装 N 种颜色的小球(不妨将顺序就编号为 1 到 N)。现在工厂里有每种颜色的小球各一箱,工人需要一箱一箱地将小球从工厂里搬到装填场地。如果搬来的这箱小球正好是可以装填的颜色,就直接拆箱装填;如果不是,就把箱子先码放在一个临时货架上,码放的方法就是一箱一箱堆上去。当一种颜色装填完以后,先看看货架顶端的一箱是不是下一个要装填的颜色,如果是就取下来装填,否则去工厂里再搬一箱过来。

如果工厂里发货的顺序比较好,工人就可以顺利地完成装填。例如要按顺序装填 7 种颜色,工厂按照 7、6、1、3、2、5、4 这个顺序发货,则工人先拿到 7、6 两种不能装填的颜色,将其按照 7 在下、6 在上的顺序堆在货架上;拿到 1 时可以直接装填;拿到 3 时又得临时码放在 6 号颜色箱上;拿到 2 时可以直接装填;随后从货架顶取下 3 进行装填;然后拿到 5,临时码放到 6 上面;最后取了 4 号颜色直接装填;剩下的工作就是顺序从货架上取下 5、6、7 依次装填。

但如果工厂按照 3、1、5、4、2、6、7 这个顺序发货,工人就必须要愤怒地折腾货架了,因为装填完 2 号颜色以后,不把货架上的多个箱子搬下来就拿不到 3 号箱,就不可能顺利完成任务。

另外,货架的容量有限,如果要堆积的货物超过容量,工人也没办法顺利完成任务。例如工厂按照 7、6、5、4、3、2、1 这个顺序发货,如果货架够高,能码放 6 只箱子,那还是可以顺利完工的;但如果货架只能码放 5 只箱子,工人就又要愤怒了……

本题就请你判断一下,工厂的发货顺序能否让工人顺利完成任务。

时间限制:6000

内存限制:65536

输入

输入首先在第一行给出 3 个正整数,分别是彩虹瓶的颜色数量 N(1 < N ≤ 103)、临时货架的容量 M(< N)、以及需要判断的发货顺序的数量 K。 随后 K 行,每行给出 N 个数字,是 1 到N 的一个排列,对应工厂的发货顺序。 一行中的数字都以空格分隔。

输出

对每个发货顺序,如果工人可以愉快完工,就在一行中输出 YES;否则输出 NO。

样例输入

7 5 3
7 6 1 3 2 5 4
3 1 5 4 2 6 7
7 6 5 4 3 2 1

样例输出

YES
NO
NO
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int N, M, K, temp, need, num, Stack[1002];
int main() {
    cin >> N >> M >> K;
    for (int i = 0; i < K; i++) {
        need = 1, num = 1;
        for (int j = 0; j < N; j++) {
            cin >> temp;
            if (temp == need) {
                need++;
                while (Stack[num - 1] == need) need++, num--;
            } else if (num <= M) Stack[num++] = temp;
        }
        printf("%s\n", num == 1 ? "YES" : "NO");
    }
    return 0;
}
题目详情
43 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

智能陪护

智能陪护系统是一个自动为老人们分配机器人护工的系统。系统中有若干个机器人排队候选,当有老人下单时,系统自动将队列最前面的机器人派送给老人,该机器人就在老人下单的当天上岗了。当老人结算时,这个机器人就立刻结束任务,回到队列末尾排队等待下一次任务,必要时可以在当天就开始接任务。

本题就请你实现这样一个自动分配功能。

时间限制:6000

内存限制:65536

输入

输入在第一行中给出 2 个正整数:N(≤ 104)是机器人护工的数量—— 这里假设所有机器人护工从 1 到 N 编号,且一开始按照编号升序在系统队列中排队;K(≤ 105)是系统订单信息的条数。随后 K 行,每行给出一条订单信息,格式为: 老人ID 指令 日期 其中 老人ID是一个长度不超过 5 的字符串,由英文小写字母和数字组成;指令 为 1 表示下单,为 0 表示结算;日期是按照 年年年年月月日日 格式给出的,保证是一个 2022 年 1 月 1 日到 3022 年 12 月 31 日 之间的合法日期。 题目保证所有数据合理,即对每位老人,结算一定发生在下单之后,结算了一单才允许下另一单,且不存在只有下单没有结算、或只有结算没有下单的数据。

输出

按照下单的时间顺序,输出机器人护工的分配信息,每行输出一条,格式为: 老人ID - 机器人护工编号 如果同一天有多位老人下单或结算,保证先处理结算的,使得机器人能及时回到队列。对于同时下达相同指令的,则按照老人ID的升序排队处理。如果一位老人下单时,系统中没有机器人护工了,则需要等待。如果到老人结算时,都没有等到一位护工,则对应输出 老人ID - NONE 最后在一行中顺序输出队列中的机器人护工的编号。要求数字间以 1 个空格分隔,行首尾不得有多余空格。

样例输入

3 10
a01 0 20220202
a04 1 20220103
a02 1 20220101
a05 0 20220202
a03 1 20220101
a03 0 20220202
a04 0 20220201
a02 0 20220102
a05 1 20220101
a01 1 20220101

样例输出

a01 - 1
a02 - 2
a03 - 3
a05 - 2
a04 - NONE
1 3 2
答案与解析
参考答案
#include <cstdio>
#include <iostream>
#include <queue>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int K = 1e5 + 10;
int n, k;
queue<int> que;
struct Order {
    string name;
    int type, dt;

    bool operator<(const Order& o) const {
        if (dt != o.dt) return dt < o.dt;
        if (type != o.type) return type < o.type;
        return name < o.name;
    }

    friend ostream& operator<<(ostream& out, const Order& o) {
        out << o.name << " " << o.type << " " << o.dt;
        return out;
    }
} orders[K];
unordered_map<string, int> mp;
queue<Order> wt_que;
unordered_map<string, bool> waiting;

int _ = []() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    return 0;
}();

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) que.push(i);
    for (int i = 0; i < k; ++i) {
        cin >> orders[i].name >> orders[i].type >> orders[i].dt;
    }
    sort(orders, orders + k);
    for (int i = 0; i < k; ++i) {
        const Order& u = orders[i];
        // cout << u << "\n";
        if (u.type) {
            if (!que.empty()) {
                mp[u.name] = que.front();
                cout << u.name << " - " << que.front() << '\n';
                que.pop();
            } else {
                wt_que.push(u);
                waiting[u.name] = true;
            }
        } else {
            if (mp.find(u.name) != mp.end()) {
                while (!wt_que.empty() && !waiting[wt_que.front().name]) wt_que.pop();
                if (!wt_que.empty()) {
                    const Order& v = wt_que.front(); wt_que.pop();
                    mp[v.name] = mp[u.name];
                    cout << v.name << " - " << mp[u.name] << '\n';
                } else que.push(mp[u.name]);
                mp.erase(u.name);
            } else {
                cout << u.name << " - NONE\n";
                waiting[u.name] = false;
            }
        }
    }
    while (!que.empty()) {
        cout << que.front(); que.pop();
        cout << (que.empty() ? "\n" : " ");
    }


    return 0;
}
题目详情
44 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

词频统计

请编写程序,对一段英文文本,统计其中所有不同单词的个数,以及词频最大的前10%的单词。

所谓“单词”,是指由不超过80个单词字符组成的连续字符串,但长度超过15的单词将只截取保留前15个单词字符。而合法的“单词字符”为大小写字母、数字和下划线,其它字符均认为是单词分隔符。

时间限制:8000

内存限制:65536

输入

输入给出一段非空文本,最后以符号#结尾。输入保证存在至少10个不同的单词。

输出

在第一行中输出文本中所有不同单词的个数。注意“单词”不区分英文大小写,例如“PAT”和“pat”被认为是同一个单词。 随后按照词频递减的顺序,按照词频:单词的格式输出词频最大的前10%的单词。若有并列,则按递增字典序输出。

样例输入

This is a test.
The word “this” is the word with the highest frequency.
Longlonglonglongword should be cut off, so is considered as the same as longlonglonglonee. But this_8 is different than this, and this, and this…#
this line should be ignored.

样例输出

23
5:this
4:is

提示

(注意:虽然样例里单词the也出现了4次,但因为我们只要输出前10%(即23个单词中的前2个)单词,而按照字母序,the排第3位,所以不输出。)

答案与解析
参考答案
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>

using namespace std;
typedef pair<string, int> PII;
map<string,int> mp;
map<string,int>::iterator it;
vector<PII> q;

bool cmp(PII a,PII b)  //   自定义排序方式
{
    if(a.second!=b.second) return a.second>b.second;  //  出现的次数
    else
        return a.first<b.first;    //   字母序
}

int main()
{
    string s;
    char x;
    while(~scanf("%c",&x)&&x!='#')  //  一个字符一个字符的读  遇到 # 结束
    {
        if( (x>='A'&&x<='Z') || (x>='a'&&x<='z') || (x>='0'&&x<='9') || x=='_')
        {
            if(x>='A'&&x<='Z') x=x-'A'+'a';   // 都转化成小写
            if(s.size()<15) s+=x;        //   如果大于 长度15   只要前十五个
        }
        else     //  遇到非合法字符
        {
            if(s.size()>0) mp[s]++,s.clear();   //  存到map<string,int> 中去
        }
    }
    for(it=mp.begin();it!=mp.end();it++)      //  把map  中的信息转入到  vector中去   也可转到结构体中  用结构体解决
        q.push_back({it->first,it->second});
    
    sort(q.begin(),q.end(),cmp);    // 按定义的方式排序
    
    cout<<q.size()<<endl;        //  输出一共单词个数
    int l=q.size()/10;
    
    for(int i=0;i<l;i++)      // 遍历前10%
        cout<<q[i].second<<':'<<q[i].first<<endl;
        
    return 0;
}
题目详情
45 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

小白鼠再排队2(2024-3-6级)

N只小白鼠(1 < N < 100),每只鼠头上戴着一顶有颜色的帽子。现在称出每只白鼠的重量,要求按照白鼠重量从小到大的顺序输出它们头上帽子的颜色。帽子的颜色用 “red”,“blue”等字符串来表示。不同的小白鼠可以戴相同颜色的帽子。白鼠的重量用整数表示。

时间限制:1000

内存限制:65536

输入

输入第一行为一个整数N,表示小白鼠的数目。 下面有N行,每行是一只白鼠的信息。第一个为正整数,表示白鼠的重量,不超过整型范围;第二个为字符串,表示白鼠的帽子颜色,字符串长度不超过10个字符。 注意:白鼠的重量各不相同。

输出

按照白鼠的重量从小到大的顺序输出白鼠的帽子颜色。


样例输入

3
30 red
50 blue
40 green

样例输出

red
green
blue
答案与解析
参考答案
//参考代码1
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <vector>

using namespace std;
struct sb {
  int z;
  char s[15];
} a[105];
bool cmp(sb a, sb b) { return a.z < b.z; }
int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].z >> a[i].s;
  }
  sort(a + 1, a + 1 + n, cmp);
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < strlen(a[i].s); j++) {
      cout << a[i].s[j];
    }
    cout << endl;
  }
  return 0;
}
//参考代码2
#include <bits/stdc++.h>

using namespace std;
struct shu
{
    int n;
    string s;
}a[100010];
bool cmp(shu a,shu b)
{
    return a.n<b.n;
}
int main()
{
    int N;
    cin>>N;
    for(int i=0;i<N;i++)
    {
        cin>>a[i].n>>a[i].s;
    }
    sort(a,a+N,cmp);
    for(int i=0;i<N;i++)
    {
        cout<<a[i].s<<endl;
    }
}


题目详情
46 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

扩号匹配问题(2024-3-6级)

在某个字符串(长度不超过 100)中有左括号、 右括号和大小写字母;规定(与常见的算数式子一样) 任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。 写一个程序, 找到无法匹配的左括号和右括号, 输出原来字符串, 并在下一行标出不能匹配的括号。 不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注.

时间限制: 3000

内存限制: 65536

输入

输入包括多组数据, 每组数据一行, 包含一个字符串, 只包含左右括号和大小写字母, 字符串长度不超过 100

输出

对每组输出数据, 输出两行, 第一行包含原始输入字符, 第二行由"$","?"和空格组成, "$"和"?"表示与之对应的左括号和右括号不能匹配。


样例输入

((ABCD(x)
)(rttyy())sss)(

样例输出

((ABCD(x)
$$       
)(rttyy())sss)(
?            ?$
答案与解析
参考答案
// 就近原则匹配:栈
// 遍历字符串
// 遇到左括号,将其下标入栈
// 右括号则先判断栈内元素情况
// 1.空,则将其下表记录到数组中
// 2.非空,则栈顶元素弹出(匹配到了)
// 将字符串便遍历后,将栈内元素记录入另一个数组
// 用两数组内的对应下标分别改成对应字符
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
string s;
char ans[N]; // 第二排的输出数组
stack<int> st;
int a[N], cnt = 1; // 未匹配的右括号的下标存储
int b[N], cnn = 1; // 未匹配的左括号的下标存储
int main() {
  while (getline(cin, s)) { // 输入不结束
    memset(ans, 0, sizeof(ans));
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    cnt = 1;
    cnn = 1; // 数据初始化
    for (int i = 0; i < s.size(); i++) {
      if (s[i] == '(') {
        st.push(i); // 左括号统一入栈
      }
      if (s[i] == ')') {
        if (!st.empty()) {
          st.pop(); // 若栈非空,则可以匹配
        } else {
          a[cnt++] = i; // 否则无法匹配,记录
        }
      }
    }
    if (!st.empty())
      while (!st.empty()) {
        b[cnn++] = st.top();
        st.pop();
      } // 栈内数据(下标)的出栈
    for (int i = 1; i < cnn; i++) {
      ans[b[i]] = '$'; // 在ans内标记
    }
    for (int i = 1; i < cnt; i++) {
      ans[a[i]] = '?'; // 在ans内标记
    }
    cout << s << endl;
    for (int i = 0; i < s.size(); i++) {
      if (ans[i] == 0)
        cout << " ";
      if (ans[i] == '$')
        cout << "$";
      if (ans[i] == '?')
        cout << "?"; // 格式转化
    }
    cout << endl;
  }
  return 0;
}
//解法2:递归
#include <bits/stdc++.h>
using namespace std;
#define N 105
char s[N], sign[N];
int si, len;
void find()//找下一个右括号 如果找到,si指向右括号 如果没找到,做标记 
{
    int lp = si;//当前左括号的下标 
    si++;
    while(si < len)
    {
        if(s[si] == ')')
            return;
        else if(s[si] == '(')
            find();
        si++;
    }
    sign[lp] = '$';//没有找到右括号,左括号的位置标记为$ 
}
int main()
{
 while(cin >> s)
 {
     len = strlen(s);
  for(int i = 0; i < len; ++i)//初始化sign字符串为空格 
            sign[i] = ' ';
        sign[len] = '\0';
        si = 0;
        while(si < len)
        {
            if(s[si] == ')')//右括号的位置标记为? 
                sign[si] = '?';
            else if(s[si] == '(')
                find();
            si++;
        }
        cout << s << endl << sign << endl;
 }
 return 0;
}


题目详情
47 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

stack or queue(2024-3-6级)

栈和队列都是常用的线性结构,它们都提供两个操作:

Push:加入一个元素。

Pop:弹出一个元素。

不同的是,栈是”先进后出”,而队列则是”先进先出”。

给出一个线性结构的进出顺序,判定这个结构是栈还是队列。

时间限制:1000

内存限制:65535

输入

第一行输入一个整数t,代表有t组测试数据 对于每组测试数据,第一行输入一个整数n,代表操作的次数。 随后输入n行,每行包含两个整数 type val。 当type = 1时,表示该次操作为push操作,val表示进入的数字。当type=2时,表示该次操作为pop操作,val代表出来的数字。 3<=n<=2000

输出

每组测试数据输出一行。 输出该组数据对应的线性结构,”Stack” 或者 “Queue”。 题目保证是栈或者队列的一种。


样例输入

2
6
1 1
1 2
1 3
2 3
2 2
2 1
4
1 1
1 2
2 1
2 2

样例输出

Stack
Queue
答案与解析
参考答案
//参考代码1
#include <deque>
#include <iostream>

using namespace std;
int main() {
  int t;
  scanf("%d", &t);
  deque<int> ds; // imitating stack
  for (int i = 0; i < t; i++) {
    int n;
    bool tag = false;
    scanf("%d", &n);
    for (int j = 0; j < n; j++) {
      int type, val;
      scanf("%d%d", &type, &val);
      if (tag)
        continue;
      if (type == 1) {
        ds.push_back(val);
      } else {
        int s = ds.back();
        ds.pop_back();
        if (s != val) {
          printf("Queue\n");
          tag = true;
        }
      }
    }
    if (!tag)
      printf("Stack\n");
    ds.clear();
  }
}
//参考代码2
#include <bits/stdc++.h>

using namespace std;
string Struct;
bool H;
int push[2005];
int pop[2005];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,type,val,Innum=0,Outnum=0;
		cin>>n;
		for(int i=0;i<n;++i)
		{
			cin>>type>>val;
			if(type==1)
			{
				push[Innum++]=val;
			}
			else
			{
				pop[Outnum++]=val;
			}
		}
		int num=min(Innum,Outnum);
		H=false;
		for(int i=0;i<num;++i)
		{
			if(push[i]!=pop[i])
			{
				Struct="Stack";
				H=true;
				break;
			}
		}
		if(!H) Struct="Queue";
		cout<<Struct<<endl;
	} 
	return 0;
}


题目详情
48 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

利用队列进行数字排序(2024-3-6级)

对于 N 个数字, 有人提出了如下的排序策略:

例如, 对于数字 53、 47、 85、 38、 64、 23

先建立 10 个队列(0 到 9) , 用于存放数字的大小, 将这 N 个数字依个位存放入各自的队列之中, 然后再按队列 0 到队列 9 依次出队。

例如, 对于上面的数字, 依次进队后, 结果如下:

队列 3: 53、 23 队列 4: 64 队列 5: 85 队列 7: 47 队列 8: 38

将其依次出队后, 结果为 53,23,64,85,47,38

然后, 再将方才出队后的队对, 依照十位放入各自的队列之中, 然后再按队列 0 到队列 9 依次出队

例如, 对于上面刚刚出队的序列 53,23,64,85,47,38, 将其依次进队,结果如下:

队列 2: 23 队列 3: 38 队列 4: 47 队列 5: 53 队列 6: 64 队列 8: 85

将其依次出队后, 结果为 23,38,47,53,64,85.因为这组数字最大只是两位数, 所以排序结束。

如果还有更大的数字, 那么, 接下来就是其百位、 千位……(如果位数不够, 就补 0.比如最大的数字是四位数, 那么数字 23 就当成 0023处理)

请根据上述算法, 对这些数字进行排序

时间限制: 1000

内存限制: 65535

输入

分为两行, 第一行为一个数字 N(1 <= N <= 1000), 表示数字的个数第二行为 N 个数字(都是非负数) , 以空格相隔, 最大的数字不超过9999

输出

输出两个部分 第一个部分为第一次进队出队的结果, 先显示一行:Step1. 之后用Queue0:...表示, 共 10 行, 结果用空格分隔, 下同 之后为第二次进队出队的结果(如果需要第二次进队出队的话) , 先显示一行: Step2. 之后仍然用 Queue0:...表示, 共 10 行 之后如果需要的话, 则分别显示第三次、 第四次的进队出队结果 第二部分为一行,即将数字排序后的结果(升序排序)


样例输入

20
41 67 34 0 69 24 78 58 62 64 5 45 81 27 61 91 95 42 27 36

样例输出

Step1.
Queue0:0
Queue1:41 81 61 91
Queue2:62 42
Queue3:
Queue4:34 24 64
Queue5:5 45 95
Queue6:36
Queue7:67 27 27
Queue8:78 58
Queue9:69
Step2.
Queue0:0 5
Queue1:
Queue2:24 27 27
Queue3:34 36
Queue4:41 42 45
Queue5:58
Queue6:61 62 64 67 69
Queue7:78
Queue8:81
Queue9:91 95
0 5 24 27 27 34 36 41 42 45 58 61 62 64 67 69 78 81 91 95
答案与解析
参考答案
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#define ElemType int
#define MaxSize 2000
typedef struct ss {
  ElemType data[MaxSize];
  int front, rear;
} SqQueue;
void InitQueue(SqQueue *&q) {
  q = (SqQueue *)malloc(sizeof(SqQueue));
  q->front = q->rear = -1;
}
void DestoryQueue(SqQueue *&q) { free(q); }
bool QueueEmpty(SqQueue *q) { return (q->front == q->rear); }
bool enQueue(SqQueue *&q, ElemType e) {
  if (q->rear == MaxSize - 1)
    return false;
  q->rear++;
  q->data[q->rear] = e;
  return true;
}
bool deQueue(SqQueue *&q, ElemType &e) {
  if (q->rear == q->front)
    return false;
  q->front++;
  e = q->data[q->front];
  return true;
}
int Num(int h) // 返回h的位数
{
  int i = 0;
  if (h == 0)
    return 1;
  while (h > 0) {
    i++;
    h /= 10;
  }
  return i;
}
int data(int g, int num) // 返回num的第g位数字
{
  int result, i = 1;
  int k = Num(num); // 获取位数
  if (num == 0 || g > k)
    return 0;
  else if (num <= 9 && g == 1)
    return num;

  while (num >= 10 && i < g) {
    num /= 10;
    i++;
  }
  result = num % 10;
  return result;
}
int main() {
  int n, i = 0, j, a[100], max = 0, k = 0, e, t = 0;
  scanf("%d\n", &n);
  SqQueue *q[10];
  for (i = 0; i < 10; i++) {
    InitQueue(q[i]);
  }

  for (i = 0; i < n; i++) {
    if (i != n - 1)
      scanf("%d ", &a[i]);
    else
      scanf("%d", &a[i]);
  }                       // a[i]='\0';
  for (i = 0; i < n; i++) // 找出最大值
  {
    k = Num(a[i]);
    if (k > max)
      max = k;
  }
  //  printf("%d\n",max);
  for (i = 1; i <= max; i++) //
  {
    printf("Step%d.\n", i);

    for (j = 0; j < 10; j++) { // 建立0-9的队对应的数字并输出
      for (k = 0; k < n; k++) {
        if (data(i, a[k]) == j)
          enQueue(q[j], a[k]);
      }
    }
    t = 0;
    for (j = 0; j < 10; j++) {
      printf("Queue%d:", j);
      while (!QueueEmpty(q[j])) {
        deQueue(q[j], e);
        a[t++] = e;
        printf("%d ", e);
      }
      printf("\n");
    }
    // printf("\n");
  }
  for (i = 0; i < n; i++) {
    printf("%d ", a[i]);
  }
  printf("\n");
  system("pause");
  return 0;
}


题目详情
49 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 2 链表

重链重排

给定一个单链表 L1→L2→…→Ln-1→Ln,请编写程序将链表重新排列为 Ln→L1→Ln-1→L2→…。例如:给定L为1→2→3→4→5→6,则输出应该为6→1→5→2→4→3。

时间限制:1000

内存限制:65536

输入

每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数,即正整数N (≤ 105)。结点的地址是5位非负整数,NULL地址用-1表示。 接下来有N行,每行格式为: Address Data Next 其中`Address`是结点地址;`Data`是该结点保存的数据,为不超过105的正整数;`Next`是下一结点的地址。题目保证给出的链表上至少有两个结点。

输出

对每个测试用例,顺序输出重排后的结果链表,其上每个结点占一行,格式与输入相同。

样例输入

00100 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

样例输出

68237 6 00100
00100 1 99999
99999 5 12309
12309 2 00000
00000 4 33218
33218 3 -1
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
#define MAX 100005

struct LinkNode
{
    int address;   //当前结点的地址
    int data;      //当前结点的数据
    int next;      //下一结点的地址
}node[MAX];

int main()
{
    int Head,N;   //头结点Head、结点总个数N
    cin >> Head >> N;
    for(int i = 0; i < N; i++)
    {
        int temp;
        cin >> temp;
        node[temp].address = temp;
        cin >> node[temp].data >> node[temp].next;
    } 
    vector<LinkNode> v,ans;
    for(int i = Head; i != -1; i = node[i].next)  //先根据地址来将链表排序
    {
        v.push_back(node[i]);
    }
    int l = 0, r = v.size()-1;
    while(true)   //链表重排
    {
        ans.push_back(v[r]);
        r--;
        if(r < l) break;  //当r出现在l左侧时说明链表重排完成
        ans.push_back(v[l]);
        l++;
        if(r < l) break;  //当r出现在l左侧时说明链表重排完成
    }
    for(int i = 0; i < ans.size(); i++)
    {
        if(i != ans.size()-1)
        {
            printf("%05d %d %05d\n",ans[i].address,ans[i].data,ans[i+1].address);
        }
        else
        {
            printf("%05d %d -1\n",ans[i].address,ans[i].data);
        }
    }
    return 0;
}


题目详情
50 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

堆宝塔

堆宝塔游戏是让小朋友根据抓到的彩虹圈的直径大小,按照从大到小的顺序堆起宝塔。但彩虹圈不一定是按照直径的大小顺序抓到的。聪明宝宝采取的策略如下:

- 首先准备两根柱子,一根 A 柱串宝塔,一根 B 柱用于临时叠放。

- 把第 1 块彩虹圈作为第 1 座宝塔的基座,在 A 柱放好。

- 将抓到的下一块彩虹圈 C 跟当前 A 柱宝塔最上面的彩虹圈比一下,如果比最上面的小,就直接放上去;否则把 C 跟 B 柱最上面的彩虹圈比一下:

-- 如果 B 柱是空的、或者 C 大,就在 B 柱上放好;

-- 否则把 A 柱上串好的宝塔取下来作为一件成品;然后把 B 柱上所有比 C 大的彩虹圈逐一取下放到 A 柱上,最后把 C 也放到 A 柱上。

重复此步骤,直到所有的彩虹圈都被抓完。最后 A 柱上剩下的宝塔作为一件成品,B 柱上剩下的彩虹圈被逐一取下,堆成另一座宝塔。问:宝宝一共堆出了几个宝塔?最高的宝塔有多少层?

时间限制:1000

内存限制:262144

输入

输入第一行给出一个正整数 N(≤ 103),为彩虹圈的个数。第二行按照宝宝抓取的顺序给出 N 个不超过 100 的正整数,对应每个彩虹圈的直径。

输出

在一行中输出宝宝堆出的宝塔个数,和最高的宝塔的层数。数字间以 1 个空格分隔,行首尾不得有多余空格。

样例输入

11
10 8 9 5 12 11 4 3 1 9 15

样例输出

4 5

提示

样例解释: 

宝宝堆成的宝塔顺次为: - 10、8、5 - 12、11、4、3、1 - 9 - 15、9

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
int max(int a,int b)
{
	return a>b?a:b;
}
int main()
{
	int n;
	cin>>n;
	stack<int>A,B;
	int count=0;
	int max1=0;
	while(n--)
	{
		int C;
		cin>>C;
		if(A.empty()||C<A.top())
			A.push(C);
		else
		{
			if(B.empty()||C>B.top())
				B.push(C);
			else
			{
				max1=max(max1,A.size());
				while(A.size())
					A.pop();
				count++;
				while(!B.empty()&&B.top()>C)
				{
					A.push(B.top());
					B.pop();
				}
				A.push(C);
			}
		}
	}
	if(!A.empty())
	{
		max1=max(max1,A.size());
		count++;
		while(!A.empty())
		{
			A.pop();
		}
	}
	if(!B.empty())
	{
		max1=max(max1,B.size());
		count++;
		while(!B.empty())
		{
			B.pop();
		}
	}
	cout<<count<<" "<<max1;
}
题目详情
51 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

一头进两头出

某队列允许在其两端进行出队操作,但仅允许在一端进行入队操作。现给定入队的序列,请你判断一系列出队序列是否可能。例如按 1、2、3、4、5 的顺序入队,则 1、3、2、5、4 这样的出队序列是可以得到的,但 5、1、3、2、4 就是不可能得到的。

时间限制:1000

内存限制:262144

输入

输入首先在一行中给出两个正整数 N 和 K(≤ 10),分别是入队元素的个数和待查验的序列个数。随后一行给出 N 个两两不同的整数组成的入队序列;再跟着 K 行,每行给出由 N 个入队整数组成的出队序列。同行整数间以空格分隔。

输出

对每个需要查验的出队序列,如果是可能的,则在一行中输出 `yes`,否则输出 `no`。

样例输入

5 4
10 2 3 4 5
10 3 2 5 4
5 10 3 2 4
2 3 10 4 5
3 5 10 4 2

样例输出

yes
no
yes
yes
答案与解析
参考答案

整理中……

题目详情
52 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

学生课表

某大学有 40000 名学生,开了 2500 门课。给定所有课程的选课名单,你的任务是为每一位前来查询的学生打印其选课的课表。

时间限制:2000

内存限制:262144

输入

输入第一行给出 2 个正整数:N(≤ 40000)为查询课表的学生人数;K(≤ 2500)为课程总数。 下面给出每门课的选课名单(课程从 1 到 K 编号),格式为: 课程编号 选课人数 学生姓名1 学生姓名2 ... 其中 选课人数 不超过 200 人。学生姓名由 3 个英文大写字母和 1 位数字组成。 最后一行给出 N 个前来查询的学生姓名。 一行中的数字和姓名都以空格分隔。

输出

对每个前来查询的学生,在一行中输出学生的姓名、选课门数、升序输出的课程编号,其间以 1 个空格分隔。行首尾不得有多余空格。

样例输入

11 5
4 7
BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1
1 4
ANN0 BOB5 JAY9 LOR6
2 7
ANN0 BOB5 FRA8 JAY9 JOE4 KAT3 LOR6
3 1
BOB5
5 9
AMY7 ANN0 BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1
ZOE1 ANN0 BOB5 JOE4 JAY9 FRA8 DON2 AMY7 KAT3 LOR6 NON9

样例输出

ZOE1 2 4 5
ANN0 3 1 2 5
BOB5 5 1 2 3 4 5
JOE4 1 2
JAY9 4 1 2 4 5
FRA8 3 2 4 5
DON2 2 4 5
AMY7 1 5
KAT3 3 2 4 5
LOR6 4 1 2 4 5
NON9 0
答案与解析
参考答案
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

// 比较函数,用于对课程编号进行升序排序
bool compareCourse(const int& a, const int& b) {
    return a < b;
}

int main() {
    int N, K;
    cin >> N >> K;

    // 使用哈希表存储每门课程的选课学生姓名
    unordered_map<int, vector<string>> courseToStudents;

    // 读取每门课程的选课名单
    for (int i = 0; i < K; ++i) {
        int courseId, numStudents;
        cin >> courseId >> numStudents;

        vector<string> students;
        for (int j = 0; j < numStudents; ++j) {
            string studentName;
            cin >> studentName;
            students.push_back(studentName);
            courseToStudents[courseId].push_back(studentName);
        }
    }

    // 读取前来查询的学生姓名
    vector<string> queryStudents;
    for (int i = 0; i < N; ++(i)) {
        string studentName;
        cin >> studentName;
        queryStudents.push_back(studentName);
    }

    // 为每个查询的学生打印课表
    for (const string& studentName : queryStudents) {
        vector<int> selectedCourses;

        // 遍历所有课程,查找该学生所选的课程
        for (const auto& coursePair : courseToStudents) {
            const vector<string>& students = coursePair.second;
            if (find(students.begin(), students.end(), studentName)!= students.end()) {
                selectedCourses.push_back(coursePair.first);
            }
        }

        // 对所选课程进行升序排序
        sort(selectedCourses.begin(), selectedCourses.end(), compareCourse);

        // 输出学生课表信息
        cout << studentName << " " << selectedCourses.size() << " ";
        for (int courseId : selectedCourses) {
            cout << courseId << " ";
        }
        cout << endl;
    }

    return 0;
}
题目详情
53 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

删除字符串

image1.png

image2.png

答案与解析
参考答案
#include <iostream>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s, stk;
    cin >> s;
    for (char c : s) {
        stk.push_back(c);
        // 长度够3个字符才可以校验XYZ
        if (stk.size() >= 3) {
            int len = stk.size();
            if (stk[len - 3] == 'X' && stk[len - 2] == 'Y' && stk[len - 1] == 'Z') {
                // 弹出末尾三位
                stk.pop_back();
                stk.pop_back();
                stk.pop_back();
            }
        }
    }
    cout << stk << '\n';
    return 0;
}
题目详情
54 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

空间折叠

image3.png

image4.png

image5.png

image6.png

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;

int H, W;
char grid[MAXN][MAXN];
int dist[MAXN][MAXN];
// 普通四方向步行偏移
int dir4[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> H >> W;
    int ch, cw, dh, dw;
    cin >> ch >> cw >> dh >> dw;
    // 输入下标1转0
    int sx = ch - 1, sy = cw - 1;
    int tx = dh - 1, ty = dw - 1;
    for (int i = 0; i < H; i++) cin >> grid[i];

    memset(dist, 0x3f, sizeof dist);
    dist[sx][sy] = 0;
    deque<pii> dq;
    dq.emplace_back(sx, sy);

    while (!dq.empty())
    {
        auto [x, y] = dq.front();
        dq.pop_front();
        int curCost = dist[x][y];
        // 到达终点直接提前输出答案
        if (x == tx && y == ty) break;
        // 行动1:步行,代价0
        for (auto &d : dir4)
        {
            int nx = x + d[0], ny = y + d[1];
            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if (grid[nx][ny] == '#') continue;
            if (dist[nx][ny] > curCost)
            {
                dist[nx][ny] = curCost;
                dq.emplace_front(nx, ny);
            }
        }
        // 行动2:空间折叠,5*5范围,代价+1
        for (int dr = -2; dr <= 2; dr++)
        {
            for (int dc = -2; dc <= 2; dc++)
            {
                int nx = x + dr, ny = y + dc;
                if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
                if (grid[nx][ny] == '#') continue;
                if (dist[nx][ny] > curCost + 1)
                {
                    dist[nx][ny] = curCost + 1;
                    dq.emplace_back(nx, ny);
                }
            }
        }
    }
    int ans = dist[tx][ty];
    cout << (ans == INF ? -1 : ans) << '\n';
    return 0;
}
题目详情
55 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

宝可梦

image7.png

image8.png

答案与解析
参考答案
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    ll dp0 = 0, dp1 = -INF;
    for (int i = 0; i < n; ++i)
    {
        ll x;
        cin >> x;
        ll nd0 = dp0, nd1 = dp1; // 不放走:原样继承
        // 选择击败进行状态更新
        nd0 = max(nd0, dp1 + 2 * x);
        nd1 = max(nd1, dp0 + x);
        dp0 = nd0; dp1 = nd1;
    }
    cout << max(dp0, dp1) << '\n';
    return 0;
}
题目详情
56 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

L形硬币

image9.png

image10.png

答案与解析
参考答案
#include <iostream>
#include <string>
using namespace std;
const int MAXN = 2005;
int row[MAXN], col[MAXN];
string grid[MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        cin >> grid[i];
        for(int j = 0; j < n; ++j)
        {
            if(grid[i][j] == 'o')
            {
                row[i]++;
                col[j]++;
            }
        }
    }
    long long ans = 0; // 防止int溢出,2000*2000量级乘积会超int范围
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            if(grid[i][j] == 'o')
                ans += 1LL * (row[i] - 1) * (col[j] - 1);
        }
    }
    cout << ans << '\n';
    return 0;
}
题目详情
57 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

能量槽

题目描述

在实验室中,有一个“能量槽”和 n 个待处理的能量块。第i个能量块的能级为ai,其蕴含的能量为2ai。

实验需按顺序执行n次操作,第i次操作流程如下:

(1)将第i个能量块放入堆槽的顶部。

(2)随后启动“自动融合程序”,重复执行以下检查,直到无法继续:

若槽中能量块数量≤1,停止融合。

若顶部第 1 个与第 2 个能量块的能级不同,停止融合。

若顶部两个能量块能级相同,则将它们从槽中移除,并向顶部放入一个能级为原能级 + 1的新能量块,其能量为两者之和。

再次回到检查步骤,继续尝试融合。

求 n 次操作全部完成后,槽中剩余的能量块总数。

输入格式

第一行,一个整数n。

接下来 n 行,每行一个整数 ai。

输出格式

输出 n 次操作结束后槽中剩余能量块的数量。

输入样例#1

7
2
1
1
3
5
3
3

输出样例#1

3

输入样例#2

5
0
0
0
1
2

输出样例#2

4

说明提示:

1≤n≤2×10^5,0≤ai≤10^9,输入均为整数。

限制:

时间限制:1000ms,内存限制:256MiB

答案与解析
参考答案
#include <iostream>
#include <stack>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n;
	cin >> n;
	stack<long long> st;  // 存储能级,用 long long 防止溢出
	
	while (n--) {
		long long x;
		cin >> x;
		st.push(x);
		
		// 循环合并栈顶两个相同的元素
		while (st.size() >= 2) {
			// 取出栈顶两个
			long long a = st.top(); st.pop();
			long long b = st.top(); st.pop();
			
			if (a == b) {
				// 相同则合并成 +1 级,重新压入
				st.push(a + 1);
			} else {
				// 不同则放回,停止合并
				st.push(b);
				st.push(a);
				break;
			}
		}
	}
	
	// 最终栈大小就是答案
	cout << st.size() << endl;
	return 0;
}
题目详情
58 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 3 搜索算法

星际探险

题目描述

星际探险队计划从 n 名候选者中挑选队员组成小队,每名候选者只能入选一次。

飞船上有 m 个关键系统,第 i 名候选者的加入会对第 j 个系统的状态值产生 (ai, j) 的影响,影响可正可负。

探险安全条例要求,最终小队组成后,每个系统的状态值总和都必须不低于 0,否则飞船无法维持安全航行。

在满足该要求的前提下,希望小队的人数尽可能多,请输出这个最大人数。若不存在任何满足条件的选人方案,输出0。

输入格式

第一行:两个整数表示 n 与 m;

第二行到第 n+1 行:第 i+1 行有 m 个整数,表示 (ai,1)、(ai,2)、……、(ai,m)。

输出格式

单个整数:表示答案。

输入样例

4 3
1 1 -2
1 -2 1
-2 1 1
2 2 2

输出样例

4

说明提示:

1≤n、m≤16,1,000,000≤ (ai, j) ≤1,000,000。

限制:

时间限制:1000ms,内存限制:256MiB

答案与解析
参考答案
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    // 存储每个人对m个系统的贡献
    vector<vector<long long>> a(n, vector<long long>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
        }
    }

    int max_people = 0;

    // 枚举所有子集:mask 二进制第i位=1表示选第i个人
    for (int mask = 1; mask < (1 << n); ++mask) {
        int cnt = __builtin_popcount(mask); // 选中的人数
        if (cnt <= max_people) continue;    // 剪枝:人数更少直接跳过

        vector<long long> sum(m, 0);
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) { // 选了第i个人
                for (int j = 0; j < m; ++j) {
                    sum[j] += a[i][j];
                }
            }
        }

        // 检查所有系统是否都 ≥ 0
        bool ok = true;
        for (long long s : sum) {
            if (s < 0) {
                ok = false;
                break;
            }
        }

        if (ok) {
            max_people = cnt;
        }
    }

    cout << max_people << endl;
    return 0;
}
题目详情
59 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

博弈游戏

题目描述

两位玩家进行回合制博弈游戏,游戏总计进行 n 轮。每一轮,双方都要从1、2、3三个数字中选择一个出招,胜负规则如下:

(1)若双方选择的数字相同,本轮为平局;

(2)若数字不同,胜负遵循固定克制关系:1克制2,2克制3,3克制1,被克制的一方本轮落败,克制的一方本轮获胜。

其中一位玩家提前掌握了对手的完整出招顺序——对手在第 i 轮选择的数字为 si,所有 si 组成一个长度为 n 的序列。

该玩家需要规划自己每一轮的出招,满足以下全部条件:

(1)任何一轮都不能落败(即每一轮只能获胜或平局);

(2)不能连续两轮选择相同的数字出招;

(3)在满足前两个条件的前提下,尽可能多地获得轮次的胜利。

请计算该玩家最多能赢得的轮次数量。

输入格式

第一行:一个整数表示n。

第二行:n 个整数,表示s1、s2、……、sn,每个数为1、2或3。

输出格式

输出一个整数,表示玩家最多能赢得的游戏轮数。

输入样例#1

6
3 1 2 2 1 2

输出样例#1

5

输入样例#2

24
2 3 1 3 2 1 1 1 1 1 3 3 1 3 1 3 2 2 1 2 3 1 2 2

输出样例#2

18

说明提示:

1≤n≤200,000,si∈{1,2,3}

限制:

时间限制:1000ms,内存限制:256MiB

答案与解析
参考答案
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> s(n);
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
    }

    int ans = 0;
    int last = 0; // 上一轮出的数

    for (int x : s) {
        int win;    // 能赢的数
        int draw = x; // 能平的数

        // 计算克制关系:1克2,2克3,3克1
        if (x == 1) win = 3;
        else if (x == 2) win = 1;
        else win = 2;

        // 优先选赢的,只要不和上一轮重复
        if (win != last) {
            ans++;
            last = win;
        }
        // 不能赢 → 只能平
        else {
            last = draw;
        }
    }

    cout << ans << endl;
    return 0;
}
题目详情
60 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 5 数论

作品选拔

题目描述

创新大赛组委会收到了 n 件学生参赛作品,每件作品都有对应的综合评审得分,其中第 i 件作品的得分为 ai。

根据赛事章程,组委会需从所有备选作品中选出 m 件作品晋级市级终评。为保障终评作品的整体质量,要求选出的 m 件作品中,至少有 k 件作品的综合得分不低于赛事划定的基准线 x。

请你帮助组委会计算,一共有多少种符合要求的作品遴选方案?由于答案数值可能过大,请输出方案数对998244353取模后的结果。

输入格式

第一行,两个正整数n、m;

第二行,n 个正整数,分别表示 a1、a2、……、an;

第三行,两个正整数 k、x。

输出格式

输出满足条件的方案数对 998244353 取模后的结果。

输入样例#1

3 2

10 20 30

1 20

输出样例#1

3

输入样例#2

4 2

5 10 15 20

1 12

输出样例#2

5

说明提示:

对于50%的数据,1≤n≤20;

对于100%的数据,1≤n≤1000,1≤k≤m≤n,1≤ai、x≤10^9。

限制:

时间限制:1000ms,内存限制:256MiB

答案与解析
参考答案
#include <iostream>
#include <algorithm>
using namespace std;

const int MOD = 998244353;
const int MAX = 1005;
long long C[MAX][MAX];

// 预处理组合数 C(n, k)
void init() {
	C[0][0] = 1;
	for (int i = 1; i < MAX; i++) {
		C[i][0] = 1;
		for (int j = 1; j <= i; j++) {
			C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
		}
	}
}

int main() {
	init();
	
	// 第一步:读 n, m
	int n, m;
	cin >> n >> m;
	
	// 第二步:读 n 个分数
	int a[MAX];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	
	// 第三步:读 k, x
	int k, x;
	cin >> k >> x;
	
	// 统计高分、低分数量
	int high = 0, low = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] >= x) high++;
		else low++;
	}
	
	// 计算答案
	long long ans = 0;
	int max_t = min(high, m);
	for (int t = k; t <= max_t; t++) {
		int need = m - t;
		if (need < 0 || need > low) continue;
		ans = (ans + C[high][t] * C[low][need]) % MOD;
	}
	
	cout << ans << endl;
	return 0;
}
题目详情