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

C/C++编程三级 题库

共 126 道题 ,第 5 / 7 页 · 按题型筛选,点「查看答案」核对解析
81 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 5 数学库函数

谁是你的潜在朋友

“臭味相投”——这是我们描述朋友时喜欢用的词汇。两个人是朋友通常意味着他们存在着许多共同的兴趣。然而作为一个宅男,你发现自己与他人相互了解的机会并不太多。幸运的是,你意外得到了一份北大图书馆的图书借阅记录,于是你挑灯熬夜地编程,想从中发现潜在的朋友。 首先你对借阅记录进行了一番整理,把N个读者依次编号为1,2,…,N,把M本书依次编号为1,2,…,M。同时,按照“臭味相投”的原则,和你喜欢读同一本书的人,就是你的潜在朋友。你现在的任务是从这份借阅记录中计算出每个人有几个潜在朋友。

时间限制:1000

内存限制:65536

输入

第一行两个整数N,M,2 <= N ,M<= 200。接下来有N行,第i(i = 1,2,…,N)行每一行有一个数,表示读者i-1最喜欢的图书的编号P(1<=P<=M)

输出

包括N行,每行一个数,第i行的数表示读者i有几个潜在朋友。如果i和任何人都没有共同喜欢的书,则输出“BeiJu”(即悲剧,^ ^)

样例输入

4  5
2
3
2
1

样例输出

1
BeiJu
1
BeiJu
答案与解析
参考答案
#include<iostream>

using namespace std;

const int N = 210;

int n, m;
int q[N], cnt[N];

int main(){
    
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> q[i], cnt[q[i]]++;
        
    for(int i = 1; i <= n; i++)
        if(cnt[q[i]] == 1) puts("BeiJu");
        else cout << cnt[q[i]] - 1 << endl;
    
    return 0;
}


题目详情
82 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 1 函数定义与调用

课程冲突

小 A 修了 n 门课程, 第 i 门课程是从第 ai 天一直上到第 bi 天。

定义两门课程的冲突程度为 : 有几天是这两门课程都要上的。

例如 a1=1,b1=3,a2=2,b2=4 时, 这两门课的冲突程度为 2。

现在你需要求的是这 n 门课中冲突程度最大的两门课的冲突程度。

时间限制:1000

内存限制:65536

输入

第一行一个正整数 n 表示课程数量。 接下来 n 行,每行两个正整数 ai,bi。 2 ≤ n≤ 1000, 1 ≤ ai ≤ bi ≤ 1000。

输出

输出一个整数表示最大的冲突程度

样例输入

3
1 3
2 4
5 5

样例输出

2
答案与解析
参考答案
//参考答案1
#include <bits/stdc++.h>
using namespace std;
//#define PPYDEBUG
struct lesson{
 int no; //课程编号
 int a;  //课程开始a天
 int b;  //课程结束b天
};

int max_chongtu(lesson x, lesson y){
 int r = min(x.b, y.b) - max(x.a, y.a) + 1;
 if(r < 0){
  r = 0;
 }
#ifdef PPYDEBUG
 printf("%d = x[%d,%d] - y[%d,%d]\n", r, x.a, x.b, y.a, y.b);
#endif
 return r;
}
int main() {
#ifdef LOCAL
 freopen("202209_3_1.in", "r", stdin);
#endif
 int n;
 scanf("%d", &n);
 lesson le[1010];
 for(int i = 0; i < n; i++){
  le[i].no = i + 1;
  scanf("%d%d", &le[i].a, &le[i].b);
 }
 int r = 0;
 for(int i = 0; i < n; i++){
  for(int j = i + 1; j < n; j++){
   r = max(r, max_chongtu(le[i], le[j]));
  }
 }
 printf("%d", r); 
 return 0;
}
//参考答案2
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct project {
    int start;
    int end;
    project(int a,int b):start(a),end(b){}
    bool operator <(const project A)const {
        if (start == A.start)
            return end < A.end;
        else
            return start < A.start;
    }
};
int main() {
    int n;
    cin >> n;
    vector<project>alls;
    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        alls.push_back(project(a, b));
    }
    sort(alls.begin(), alls.end());
    int result = 0;
    for (int i = 0; i < n; i++) {
        if (alls[i].end - alls[i].start < result)//剪枝
            continue;
        for (int j = i + 1; j < n; j++) {
            if (alls[j].start > alls[i].end)
                break;
            int t = min(alls[i].end, alls[j].end) - alls[j].start + 1;
            result = max(t, result);
        }
    }
    cout << result << endl;
    return 0;
}


题目详情
83 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 5 数学库函数

踩方格(2023.9)

有一个方格矩阵,矩阵边界在无穷远处。我们做如下假设:

a.    每走一步时,只能从当前方格移动一格,走到某个相邻的方格上;

b.    走过的格子立即塌陷无法再走第二次;

c.    只能向北、东、西三个方向走;

请问:如果允许在方格矩阵上走n步,共有多少种不同的方案。2种走法只要有一步不一样,即被认为是不同的方案。

时间限制:1000

内存限制:65536

输入

允许在方格上行走的步数n(n <= 20)

输出

计算出的方案数量

样例输入

2

样例输出

7
答案与解析
参考答案
//解法1:以第i步总走法数量为状态
#include <bits/stdc++.h>
using namespace std;

int main()
{
 int n, f[25];
 cin >> n;
 f[0] = 1, f[1] = 3;
 for(int i = 2; i <= n; ++i)
  f[i] = 2*f[i-1] + f[i-2];
 cout << f[n];
 return 0;
}
//解法2:以第i步向左、右、上方向走法数量为状态
#include <bits/stdc++.h>
using namespace std;
#define N 25

int main()
{
 int n, l[N], r[N], u[N];
 l[1] = r[1] = u[1] = 1;
 cin >> n;
 for(int i = 2; i <= n; ++i)
 {
     l[i] = l[i-1] + u[i-1];
     r[i] = r[i-1] + u[i-1];
     u[i] = l[i-1] + r[i-1] + u[i-1];
    }
 cout << l[n] + r[n] + u[n];
 return 0;
}
//解法3:
#include<iostream> 
#include<cstring>
using namespace std;

int a[30];
int main()
{
    int n,i;
    cin>>n;
    a[1]=3;
    a[2]=7;
    for(i=3;i<=n;i++)
        a[i]=2*a[i-1]+a[i-2];
    cout<<a[n]<<endl;
    return 0;

}
题目详情
84 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 5 数学库函数

迷信的病人(2023.9)

医院为了方便对患者进行建档和管理,引入了9位整数ID号来标识每个病人。最近医院入住了一个迷信的病人,他认为ID号的好坏直接决定了自己的命运。他对ID号x有如下要求:

(1)x的前三位数构成的整数是素数

(2)x的后三位数构成的整数是平方数(所谓平方数,是指它是某一个正整数的平方,e.g. 1,4,9,16...)

(3)x中不包含"13"

为了避免不必要的医患矛盾,医院须尽量满足他的需求。现给定正整数区间[m,n],请你判断存在几个满足病人需求的ID号。

时间限制:1000

内存限制:65536

输入

两个正整数m,n,以空格隔开。(999999999>=n>=m>=111111111)

输出

一个整数(满足要求的ID的个数)。

样例输入

157689476 157689687

样例输出

5

提示

存在5个满足要求的ID:157689484,157689529,157689576,157689625,157689676

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;

bool su(int x){
 for(int i=2;i<x;i++){
  if(x%i==0)
   return false;
 }
 return true;
}
bool pf(int x){
 int n=sqrt(x);
 if(n*n==x)
  return true;
 return false;
}
int main(){
 int m,n,ans=0;
 cin>>m>>n;
 for(int i=m;i<=n;i++){
  int q,h;
  q=i/1000000;
  h=i%1000;
  int flag=0,k=i;
  while(k){
   if(k%10==3&&k/10%10==1)
    flag=1;
   k/=10;
  }
  if(flag==0&&su(q)&&pf(h))
   ans++;
 }
 cout<<ans;
 return 0;
}
题目详情
85 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 1 函数定义与调用

Pell数列

Pell数列a1, a2, a3, ...的定义是这样的,a1 = 1, a2 = 2, ... , an = 2 * an − 1 + an - 2 (n > 2)。 给出一个正整数k,要求Pell数列的第k项模上32767是多少。

时间限制:3000

内存限制:65536

输入

第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数k (1 ≤ k < 1000000)。

输出

n行,每行输出对应一个输入。输出应是一个非负整数。

样例输入

2
1
8

样例输出

1
408
答案与解析
参考答案
//解法1:递推
#include <bits/stdc++.h>
using namespace std;
int a[1000005];
int main()
{
    int n, x; 
 a[1] = 1, a[2] = 2;
 for(int i = 3; i <= 1000000; ++i)
  a[i] = (2*a[i-1] + a[i-2])%32767;
 cin >> n;
 for(int i = 1; i <= n; ++i)
 {
  cin >> x;
  cout << a[x] << endl;
 }
 return 0;
}
//解法2:迭代
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int ct, p;
    cin >> ct;
    for(int i = 1; i <= ct; ++i)
    {
        cin >> p;
        if(p <= 2)
            cout << p << endl;//第1项是1,第2项是2 
        else 
        {
            int a = 1, b = 2, t;
            for(int j = 3; j <= p; ++j)
            {
                t = b;
                b = (2*b + a)%32767;
                a = t;
            }
            cout << b << endl;
        }
    }
    return 0;
}
//解法3:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define N 1000010
#define k 32767

using namespace std;
int a[N];
int f(int x)
{
 if(a[x]!=0) return a[x];
 if(x==1) return 1;
 if(x==2) return 2;
 return a[x]=(2*(f(x-1))%k+(f(x-2))%k)%k;
}
int main()
{
    int n,a;
 cin>>n;
 for(int i=1;i<=n;i++)
 {
  cin>>a; 
  cout<<f(a)<<endl;
 }
 return 0;
}
题目详情
86 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 5 数学库函数

我家的门牌号(2024.3三级)

我家住在一条短胡同里,这条胡同的门牌号从1开始顺序编号。

若所有的门牌号之和减去我家门牌号的两倍,恰好等于n,求我家的门牌号及总共有多少家。

数据保证有唯一解。

时间限制:1000

内存限制:65536

输入

一个正整数n。n < 100000。

输出

一行,包含两个正整数,分别是我家的门牌号及总共有多少家,中间用单个空格隔开。


样例输入

100

样例输出

10 15
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int plass(int n) { return (1 + n) * n / 2; }
int main() {
  int n;
  int sum, my;

  cin >> n;
  for (sum = 1; sum > 0; sum++) {
    for (my = 1; my <= sum; my++) {
      if (plass(sum) - (2 * my) == n) {
        cout << my << " " << sum;
        return 0;
      }
    }
  }
}
题目详情
87 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 5 数学库函数

最接近的分数

分母不超过 N 且 小于 A/B 的最大最简分数是多少?

时间限制:10000

内存限制:65536

输入

三个正整数 N,A,B,相邻两个数之间用单个空格隔开。1 <= A < B <N <= 1000。

输出

两个正整数,分别是所求分数的分子和分母,中间用单个空格隔开。


样例输入

100 7 13

样例输出

50 93
答案与解析
参考答案
#include <iostream>
 
using namespace std;
 
int main()
{
    int n, a, b, p, q, x, y;
 
    scanf("%d%d%d", &n, &a, &b);
 
    // 分子x从1-n,分母y从n-1;结果p/q,开始时1/n(最小值)
    p = 1, q = n;
    for(x=1; x<=n; x++)
        for(y=n; y>=1; y--)
            if(b * x < a * y && x * q > p * y)
                p = x, q = y;
 
    printf("%d %d\n", p, q);
 
    return 0;
}
题目详情
88 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 5 数学库函数

菲波那契数列(2024.3三级)

菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1,接下来每个数都等于前面2个数之和。 给出一个正整数a,要求菲波那契数列中第a个数对10000取模的结果是多少。

时间限制:1000

内存限制:65536

输入

第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数a(1 <= a <= 1000000)。

输出

n行,每行输出对应一个输入。输出应是一个正整数,为菲波那契数列中第a个数对10000取模得到的结果。


样例输入

4
5
2
19
1

样例输出

5
1
181
1
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  int num;

  int a, b, c;

  while (n--) {
    scanf("%d", &num);
    a = 1;
    b = 1;
    c = 2;

    if (num == 1 || num == 2) {
      printf("1\n");
    } else if (num == 3) {
      printf("2\n");
    } else {
      num -= 3;
      while (num--) {
        a = b;
        b = c;
        c = (a + b) % 1000;
      }
      printf("%d\n", c);
    }
  }

  return 0;
}

题目详情
89 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 5 数学库函数

表达式求值(2024.3三级)

输入一个布尔表达式,请你输出它的真假值。

比如:( V | V ) & F & ( F | V )

V表示true,F表示false,&表示与,|表示或,!表示非。

上式的结果是F

时间限制:1000

内存限制:65536

输入

输入包含多行,每行一个布尔表达式,表达式中可以有空格,总长度不超过1000

输出

对每行输入,如果表达式为真,输出"V",否则出来"F"


样例输入

( V | V ) & F & ( F| V)
!V | V & V & !F & (F | V ) & (!F | F | !V & V)
(F&F|V|!V&!F&!(F|F&V))

样例输出

F
V
V
答案与解析
参考答案
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>

using namespace std;
char s[1005];
stack<bool> B;
stack<char> C;
int main() {
  while (cin.getline(s, 1000, '\n')) {
    int len = strlen(s);
    while (!B.empty())
      B.pop();
    while (!C.empty())
      C.pop();
    for (int i = 0; i < len; ++i) {
      if (s[i] == ' ')
        continue;
      if (s[i] == 'V') {
        bool tmp = true;
        while (!C.empty() && C.top() == '!') {
          C.pop();
          tmp = !tmp;
        }
        B.push(tmp);
      } else if (s[i] == 'F') {
        bool tmp = false;
        while (!C.empty() && C.top() == '!') {
          C.pop();
          tmp = !tmp;
        }
        B.push(tmp);
      } else if (s[i] == '(' || s[i] == '!') {
        C.push(s[i]);
      } else if (s[i] == ')') {
        while (C.top() != '(') {
          char op = C.top();
          C.pop();
          bool tmp1 = B.top();
          B.pop();
          bool tmp2 = B.top();
          B.pop();
          if (op == '&')
            B.push(tmp2 && tmp1);
          else if (op == '|')
            B.push(tmp2 || tmp1);
        }
        C.pop();
        while (!C.empty() && C.top() == '!') {
          bool tmp = B.top();
          B.pop();
          B.push(!tmp);
          C.pop();
        }
      } else if (s[i] == '&') {
        while (!C.empty() && C.top() == '&') {
          C.pop();
          bool tmp1 = B.top();
          B.pop();
          bool tmp2 = B.top();
          B.pop();
          B.push(tmp1 && tmp2);
        }
        C.push(s[i]);
      } else if (s[i] == '|') {
        while (!C.empty() && (C.top() == '|' || C.top() == '&')) {
          bool tmp1 = B.top();
          B.pop();
          bool tmp2 = B.top();
          B.pop();
          char op = C.top();
          C.pop();
          if (op == '&')
            B.push(tmp1 && tmp2);
          else if (op == '|')
            B.push(tmp1 || tmp2);
        }
        C.push(s[i]);
      }
    }
    while (!C.empty()) {
      bool tmp1 = B.top();
      B.pop();
      bool tmp2 = B.top();
      B.pop();
      char op = C.top();
      C.pop();
      if (op == '&')
        B.push(tmp1 && tmp2);
      else if (op == '|')
        B.push(tmp1 || tmp2);
    }
    if (B.top())
      cout << "V" << endl;
    else
      cout << "F" << endl;
  }
  return 0;
}
题目详情
90 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 5 数学库函数

广义格雷码(2024.3三级)

在一组数的编码中,若任意两个相邻(首尾也视为相邻)的代码只有一位二进制数不同,则称这种编码为格雷码。如四位格雷码:

0000、0001、0011、0010、0110、0111、0101、0100、1100、1101、1111、1110、1010、1011、1001、1000

现在将格雷码扩展至其他进制,仍然是相邻两个数只能有一位不同。输入两个正整数n,m分别表示长度和进制,每行输出一个n位m进制数,输出任意一种编码即可。(提示:putchar输出效率更高)

时间限制:1000

内存限制:65536

输入

一行,两个整数n,m。其中 2 ≤ n ≤ 12 ,2 ≤ m ≤ 10 且mn ≤ 500000

输出

任意一种编码方案,每个编码一行。相邻两个编码相差一位。第一个编码和最后一个编码算相邻


样例输入

2 3

样例输出

00
10
20
21
01
11
12
22
02
答案与解析
参考答案
//答案仅供参考,来源于csdn,有部分错误 
#include <cstring> //memset(flag,0,sizeof(bool)*12*50010);
#include <iostream>
#include <queue>

using namespace std;
string a[12][50010];
bool flag[12][50010];
queue<string> q;
int n, m;
int main() {
  cin >> n >> m;
  string temp = "";
  // n为1的时候
  if (n == 1) {
    for (int i = 0; i < m; i++) {
      cout << i << endl;
    }
    return 0;
  }
  // n大于2的时候
  for (int i = 0; i < m; i++) {
    //      cout<<(temp+char(i+48))<<endl;
    q.push(temp + char(i + 48)); // i=0,把字符0入队
  }
  for (int time = 2; time <= n; time++) {
    memset(flag, 0, sizeof(bool) * 12 * 50010);
    int size = q.size(), l = 0; // l这里赋值0  因为要从1开始
    while (!q.empty()) {
      a[0][++l] = q.front();
      //      cout<<a[0][l]<<" ";
      q.pop();
    }
    // 复制一份 其他行数的
    for (int i = 1; i < m; i++) {
      for (int j = 1; j <= size; j++) {
        a[i][j] = a[0][j];
      }
    }
    // 添加前面一个值: 0—(m-1)
    for (int i = 0; i < m; i++) {
      for (int j = 1; j <= size; j++) {
        a[i][j] = char(i + 48) + a[i][j];
        //        cout<<a[i][j]<<" ";
        flag[i][j] = true;
      }
      //      cout<<endl;
    }
    // 蛇形取值
    int t = size * m; // t表示当前总个数
    // 保存第一行到q队列中
    for (int i = 1; i <= size; i++) {
      q.push(a[0][i]);
      flag[0][i] = false;
      t--;
    }
    //    cout<<q.size()<<endl;
    int x = 0, y = size;
    while (t > 0) {
      while (flag[x + 1][y] && t > 0) {
        flag[++x][y] = false;
        q.push(a[x][y]);
        t--;
      } // 向下

      if (flag[x][y - 1] && t > 0) {
        flag[x][--y] = false;
        q.push(a[x][y]);
        t--;
      } // 向左一位

      while (flag[x - 1][y] && t > 0) {
        flag[--x][y] = false;
        q.push(a[x][y]);
        t--;
      } // 向上

      if (flag[x][y - 1] && t > 0) {
        flag[x][--y] = false;
        q.push(a[x][y]);
        t--;
      } // 再向左一位
    }
  }
  // 输出
  while (!q.empty()) {
    cout << q.front() << endl;
    q.pop();
  }
  return 0;
}


题目详情
91 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 5 数学库函数

谷歌的招聘

2004年7月,谷歌在硅谷的101号公路边竖立了一块巨大的广告牌用于招聘。内容超级简单,就是一个以 .com 结尾的网址,而前面的网址是一个 10 位素数,这个素数是自然常数 e 中最早出现的 10 位连续数字。能找出这个素数的人,就可以通过访问谷歌的这个网站进入招聘流程的下一步。

自然常数 e 是一个著名的超越数,前面若干位写出来是这样的:e = 2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921… 其中粗体标出的 10 位数就是答案。

本题要求你编程解决一个更通用的问题:从任一给定的长度为 L 的数字中,找出最早出现的 K 位连续数字所组成的素数。

时间限制:7000

内存限制:65535

输入

输入在第一行给出 2 个正整数,分别是 L(不超过 1000 的正整数,为数字长度)和 K(小于10的正整数)。接下来一行给出一个长度为 L 的正整数 N。

输出

在一行中输出 N 中最早出现的 K 位连续数字所组成的素数。如果这样的素数不存在,则输出“404”。注意,原始数字中的前导零也计算在位数之内。例如在 200236 中找 4 位素数,0023 算是解;但第一位 2 不能被当成 0002 输出,因为在原始数字中不存在这个 2 的前导零。

样例输入

样例1:

20 5
23654987725541023819

样例2:

10 3
2468024680

样例输出

样例1:

49877

样例2:

404
答案与解析
参考答案
//参考代码1 C++
#include<bits/stdc++.h>

using namespace std;

bool prime(int num)
{
    if(num <= 1)
        return false;
    for(int i=2; i<=sqrt(num); i++)
    {
        if(num%i == 0)
            return false;
    }
    return true;
}

int main()
{
    int L,K;
    string str;
    cin>>L>>K>>str;
    bool flag = false;//没有找到的标记
    for(int i=0; i<=L-K; i++)
    {
    	//提取字符串
        string temp(str,i,K);
        //转成数字
        stringstream ss(temp);
        int num;
        ss>>num;
        //判断
        if(prime(num))
        {
            flag = true;
            cout<<temp;
            break;
        }
    }
    if(!flag)
        cout<<"404";
    return 0;
}
//参考代码2 C语言
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int isPrime(long long n) {
    if (n < 2) {
        return 0;
    }
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

int main() {
    int l, k;
    scanf("%d %d", &l, &k);

    char s[1001];
    scanf("%s", s);

    int pos = 0;
    for (int i = 0; i <= l - k; i++) {
        char w[11];
        strncpy(w, s + i, k);
        w[k] = '\0';
        long long ans = atoll(w);
        if (isPrime(ans)) {
            printf("%s", w);
            return 0;
        }
        pos++;
    }

    printf("404");
    return 0;
}
题目详情
92 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 1 函数定义与调用

吉利矩阵

所有元素为非负整数,且各行各列的元素和都等于 7 的 3x3 方阵称为“吉利矩阵”,因为这样的矩阵一共有 666 种。

本题就请你统计一下,把 7 换成任何一个 [2, 9] 区间内的正整数 L,把矩阵阶数换成任何一个 [2, 4] 区间内的正整数 N,满足条件“所有元素为非负整数,且各行各列的元素和都等于 L”的 NxN 方阵一共有多少种?

时间限制:6000

内存限制:65535

输入

输入在一行中给出 2 个正整数 L 和 N,意义如题面所述。数字间以空格分隔。

输出

在一行中输出满足题目要求条件的方阵的个数。

样例输入

7 3

样例输出

666
答案与解析
参考答案
//参考代码1 C语言
#include <stdio.h>

int res = 0;
int sum_row[4] = {0};
int sum_col[4] = {0};

void dfs(int x, int sum, int width) {
    if (x == width * width) {
        ++res;
        return;
    }

    for (int i = 0; i <= sum; i++) {
        if (x % width == width - 1 && i != sum - sum_row[x / width]) continue;
        if (x / width == width - 1 && i != sum - sum_col[x % width]) continue;
        if (sum_row[x / width] + i <= sum && sum_col[x % width] + i <= sum) {
            sum_col[x % width] += i;
            sum_row[x / width] += i;
            dfs(x + 1, sum, width);
            sum_col[x % width] -= i;
            sum_row[x / width] -= i;
        }
    }
}

int main() {
    int sum, width;
    scanf("%d %d", &sum, &width);

    dfs(0, sum, width);
    printf("%d\n", res);

    return 0;
}
//参考代码2
#include<iostream>
using namespace std;
const int N=20;
int a[N][N];
int main(){
int l,n;cin>>l>>n;
a[2][2]=3;
a[2][3]=21;
a[2][4]=282;
a[3][2]=4;
a[3][3]=55;
a[3][4]=2008;
a[4][2]=5;
a[4][3]=120;
a[4][4]=10147;
a[5][2]=6;
a[5][3]=231;
a[5][4]=40176;
a[6][2]=7;
a[6][3]=406;
a[6][4]=132724;
a[7][2]=8;
a[7][3]=666;
a[7][4]=381424;
a[8][2]=9;
a[8][3]=1035;
a[8][4]=981541;
a[9][2]=10;
a[9][3]=1540;
a[9][4]=2309384;
cout<<a[l][n];
}
题目详情
93 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 5 数学库函数

胖达与盆盆奶

大熊猫,俗称“胖达”,会排队吃盆盆奶。它们能和谐吃奶的前提,是它们认为盆盆奶的分配是“公平”的,即:更胖的胖达能吃到更多的奶,等胖的胖达得吃到一样多的奶。另一方面,因为它们是排好队的,所以每只胖达只能看到身边胖达的奶有多少,如果觉得不公平就会抢旁边小伙伴的奶吃。

已知一只胖达每次最少要吃 200 毫升的奶,当另一份盆盆奶多出至少 100 毫升的时候,它们才能感觉到是“更多”了,否则没感觉。

现在给定一排胖达的体重,请你帮饲养员计算一下,在保持给定队形的前提下,至少应该准备多少毫升的盆盆奶?

时间限制:6000

内存限制:65535

输入

输入首先在第一行给出正整数 n(≤ 104),为胖达的个数。随后一行给出 n 个正整数,表示 n 只胖达的体重(公斤)。每个数值是不超过 200 的正整数,数字间以空格分隔。

输出

在一行中输出至少应该准备多少毫升的盆盆奶。

样例输入

10
180 160 100 150 145 142 138 138 138 140

样例输出

3000

提示

样例解释: 盆盆奶的分配量顺序为: 400 300 200 500 400 300 200 200 200 300

答案与解析
参考答案
//参考代码1 C++
#include <iostream>
using namespace std;
int n, ans, A[10005], L[10005], R[10005];
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> A[i];
    for (int i = 1; i < n; i++) {
        int j = i;
        while(j + 1 <= n && A[j] >= A[j + 1]) {
            if (A[j] > A[j + 1]) ++L[i];
            ++j;
        }
    }
    for (int i = n; i > 1; i--) {
        int j = i;
        while(j - 1 >= 1 && A[j] >= A[j - 1]) {
            if (A[j] > A[j - 1]) ++R[i];
            --j;
        }
    }
    for (int i = 1; i <= n; i++) ans += max(L[i], R[i]) * 100 + 200;
    cout << ans;
    return 0;
}
//参考代码2 C语言
#include <stdio.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int n, ans = 0;
    int A[10005], L[10005] = {0}, R[10005] = {0};

    // 读取胖达的个数
    scanf("%d", &n);

    // 读取每只胖达的体重
    for (int i = 1; i <= n; i++) {
        scanf("%d", &A[i]);
    }

    // 计算 L 数组
    for (int i = 1; i < n; i++) {
        int j = i;
        while (j + 1 <= n && A[j] >= A[j + 1]) {
            if (A[j] > A[j + 1]) ++L[i];
            ++j;
        }
    }

    // 计算 R 数组
    for (int i = n; i > 1; i--) {
        int j = i;
        while (j - 1 >= 1 && A[j] >= A[j - 1]) {
            if (A[j] > A[j - 1]) ++R[i];
            --j;
        }
    }

    // 计算总量
    for (int i = 1; i <= n; i++) {
        ans += max(L[i], R[i]) * 100 + 200;
    }

    // 输出结果
    printf("%d\n", ans);

    return 0;
}
题目详情
94 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 1 函数定义与调用

加号放哪里

给定任一个正整数 N,我们要从它开始,经过一系列操作得到一个个位数。操作方法是在 N 的各位数字之间放置一个加号,然后执行这个加法计算,得到一个新的数字 N1,再对 N1 执行同样操作,得到 N2 …… 以此类推,直到最后得到的数字只有 1 位,则停止。

例如我们从 N=1234567890 出发,在 5 和 6 之间放置加号,计算 12345+67890=80235;然后在 0 和 2 之间放置加号,计算 80+235=315;然后在 1 和 5 之间放置加号,计算 31+5=36;最后在 3 和 6 之间放置加号,得到 3+6=9 而停止。这样我们通过 4 次计算得到了一个个位数 9。

本题就请你为任一给定的正整数计算:最少需要多少次加号放置可以得到个位数?

注意:加号必须放置在两个数字之间,不可放置在数字的首尾。

时间限制:7000

内存限制:65536

输入

输入在一行中给出一个正整数 n(≤ 1020)。

输出

在一行中首先输出将输入的整数变为个位数,需要放置加号的最少次数;随后输出最后得到的那个个位数。如果最后得到的个位数不唯一,输出最小的那个。 数字间以 1 个空格分隔,行首尾不得有多余空格。

样例输入

1234567890

样例输出

3 9

提示

样例解释: 最优划分是: 1. 12345678+90=12345768 2. 1234+5768=7002 3. 7+002=9

答案与解析
参考答案
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

long ansfqy = __LONG_MAX__;
int ansnum = 10;

void justdfs(long n, long frequency);
void exceeddfs(char *n, long frequency);

void justdfs(long n, long frequency) {
    if (ansfqy < frequency) {
        return;
    }

    if (n < 10 && (n < ansnum || frequency < ansfqy)) {
        ansnum = n;
        ansfqy = frequency;
        return;
    }

    long temp = 10;
    while (n / temp > 0) {
        long nleft = n / temp;
        long nright = n % temp;
        temp *= 10;
        justdfs(nleft + nright, frequency + 1);
    }
}

void exceeddfs(char *n, long frequency) {
    if (ansfqy < frequency) {
        return;
    }

    for (int i = 1; i < strlen(n); i++) {
        char BIleft[1025], BIright[1025];
        strncpy(BIleft, n, i);
        BIleft[i] = '\0';
        strncpy(BIright, n + i, strlen(n) - i);
        BIright[strlen(n) - i] = '\0';

        long sum = atol(BIleft) + atol(BIright);
        char temp[1025];
        sprintf(temp, "%ld", sum);

        if (strlen(temp) < 19) {
            justdfs(sum, frequency + 1);
        } else {
            exceeddfs(temp, frequency + 1);
        }
    }
}

int main() {
    char n[1025];
    scanf("%s", n);

    if (strlen(n) < 19) {
        justdfs(atol(n), 0);
    } else {
        exceeddfs(n, 0);
    }

    printf("%ld %d\n", ansfqy, ansnum);

    return 0;
}
题目详情
95 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 5 数学库函数

三足鼎立

当三个国家中的任何两国实力之和都大于第三国的时候,这三个国家互相结盟就呈“三足鼎立”之势,这种状态是最稳定的。

现已知本国的实力值,又给出 n 个其他国家的实力值。我们需要从这 n 个国家中找 2 个结盟,以成三足鼎立。有多少种选择呢?

时间限制:10000

内存限制:65536

输入

输入首先在第一行给出 2 个正整数 n(2 ≤ n ≤ 105)和 P(≤ 109),分别为其他国家的个数、以及本国的实力值。随后一行给出 n 个正整数,表示n 个其他国家的实力值。每个数值不超过 109,数字间以空格分隔。

输出

在一行中输出本国结盟选择的个数。

样例输入

7 30
42 16 2 51 92 27 35

样例输出

9

提示

样例解释: 能联合的另外 2 个国家的 9 种选择分别为: {16, 27}, {16, 35}, {16, 42}, {27, 35}, {27, 42}, {27, 51}, {35, 42}, {35, 51}, {42, 51}。

答案与解析
参考答案
//参考代码1 C++
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const int N = 1e5 + 10;
 
int n, p;
int a[N];
ll s;
 
int main() {
    cin >> n >> p;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    
    sort(a + 1, a + n + 1);
 
    for (int i = 1; i <= n; i ++) {
        int l = i + 1, r = n;
        int minn = abs(a[i]-p), maxx = a[i] + p;
        int n1, n2; // 记录下标
        if (l>r) break;
 
        while (l <= r) { // 找到大于最小值的数
            int mid = (l + r) / 2;
            if (a[mid] <= minn) 
                l = mid + 1;
            else
                r = mid - 1;
        }
        n1 = l;
        
        l = i + 1, r = n;
        while (l <= r) { // 找到小于最大值的数
            int mid = (l + r) / 2;
            if (a[mid] < maxx)
                l = mid + 1;
            else
                r = mid - 1;
        }
        n2 = r;
 
        s += (n2 - n1) + 1;
    }
    
    cout << s;
    return 0;
}
//参考代码2 C语言
#include <stdio.h>
#include <stdlib.h>

long long n, x, cnt;
int a[100005];

int cmpfunc(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int upper_bound(int arr[], int n, int x) {
    int l = 0;
    int r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] <= x) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return l;
}

int lower_bound(int arr[], int n, int x) {
    int l = 0;
    int r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] < x) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return l;
}

int main() {
    scanf("%lld %lld", &n, &x);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
    
    qsort(a, n, sizeof(int), cmpfunc);
    
    for (int i = 0; i < n - 1; ++i) {
        int l, r;
        if (a[i] < x) {
            l = upper_bound(a + i + 1, n - i - 1, x - a[i]);
        } else {
            l = upper_bound(a + i + 1, n - i - 1, a[i] - x);
        }
        r = lower_bound(a + i + 1, n - i - 1, a[i] + x) - 1;
        
        if (l == n - i - 1) {
            continue;
        }
        
        cnt += (r - l + 1);
    }
    
    printf("%lld\n", cnt);
    return 0;
}
题目详情
96 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 5 数学库函数

最近的斐波那契数

斐波那契数列 Fn 的定义为:对 n ≥ 0 有 Fn+2 = Fn+1 + Fn,初始值为 F0 = 0 和 F1 = 1。所谓与给定的整数 N 最近的斐波那契数是指与 N 的差之绝对值最小的斐波那契数。

本题就请你为任意给定的整数 N 找出与之最近的斐波那契数。

时间限制:1000

内存限制:65536

输入

输入在一行中给出一个正整数 N(≤ 108)。

输出

在一行输出与 N 最近的斐波那契数。如果解不唯一,输出最小的那个数。

样例输入

305

样例输出

233

提示

样例解释 部分斐波那契数列为 { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ... }。可见 233 和 377 到 305 的距离都是最小值 72,则应输出较小的那个解。

答案与解析
参考答案
#include<iostream>
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
int main(){
	int n[101];
	n[0]=0,n[1]=1;
	for(int i=2;i<43;i++){
		n[i]=n[i-1]+n[i-2];
		
	}
	int N;
	cin>>N;
	int min_diff=9999999;
	int temp[101]={0},j=0;
	for(int i=0;i<43;i++){
		if(abs(n[i]-N)<min_diff){
			min_diff=abs(n[i]-N);
			temp[j++]=n[i];
		}
	}
	cout<<temp[j-1];
	return 0;
}
题目详情
97 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 5 数学库函数

构造性证明

关于数学定理证明,也有高下之分。最暴力的证明方法是“构造性证明”,即当需要证明某种解存在时,直接把解构造出来,而不是仅通过推理证明解之存在。

下面有一个定理:

设 ai(i=1, … , 5)均为正实数。则一定存在 4 个互不相同的下标 i、j、k、l,使得 |ai / aj - ak / al| < 1/2。

作为程序员,就请你编写程序构造出正确的下标,验证这个结论。

时间限制:1000

内存限制:65536

输入

输入在一行中顺序给出 5 个正实数。为保证计算中不产生浮点溢出,我们令输入的数字在 [10-10, 1010] 区间内,且小数点后不超过 10 位小数。

输出

在一行中首先输出使得定理结论成立的下标有多少套,随后输出最小的一套下标。数字间以 1 个空格分隔,行首尾不得有多余空格。 注:所谓下标集 {i1, …, i4} 小于下标集 {j1, …, j4},是指存在 1 ≤ k ≤ 4 使得 il=jl 对所有 l < k 成立,且 ik < jk。

样例输入

3.12 5.27 0.0007 9825.4413 10

样例输出

18 1 4 3 2

提示

样例解释: 易验证 |a1/a4-a3/a2|=|3.12/9825.4413 - 0.0007/5.27| < 1/2。满足条件的解有 18 个,例如 5、4、3、2 就是另一套解。

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

const double EPS = 1e-9;

// 比较两个双精度浮点数是否相等(考虑精度误差)
bool doubleEqual(double a, double b) {
    return fabs(a - b) < EPS;
}

int main() {
    vector<double> nums(5);
    for (int i = 0; i < 5; ++i) {
        cin >> nums[i];
    }
    int count = 0;
    vector<int> result(4);
    // 四重循环遍历所有可能的四个下标组合
    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < 5; ++j) {
            if (i == j) continue;
            for (int k = 0; k < 5; ++k) {
                if (k == i || k == j) continue;
                for (int l = 0; l < 5; ++l) {
                    if (l == i || l == j || l == k) continue;
                    double val = fabs(nums[i] / nums[j] - nums[k] / nums[l]);
                    if (val < 0.5) {
                        count++;
                        if (count == 1) {
                            result = {i + 1, j + 1, k + 1, l + 1};
                        }
                    }
                }
            }
        }
    }
    cout << count << " ";
    for (int idx : result) {
        cout << idx << " ";
    }
    return 0;
}
题目详情
98 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 5 数学库函数

环形公路出口

一条环形高速路上有 N 个出口。给定任意一对出口,请你算出这两个出口之间的最短距离。

时间限制:1000

内存限制:65536

输入

输入第一行给出区间 [3,105] 内的整数 N,以及 N 个整数距离 D1 D2 … DN,其中 Di 是第 i 和第 i+1 个出口之间的距离,DN 是第 N 和第 1 个出口之间的距离。同行数字间以空格分隔。 第二行给出正整数 M (≤ 104)。随后 M 行,每行给出一对出口的编号(出口从 1 到 N 顺序编号)。题目保证公路全长不超过 107。

输出

输出 M 行,每行给出对应输入的一对出口之间的最短距离。

样例输入

5 1 2 4 14 9
3
1 3
2 5
4 1

样例输出

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

int main() {
    int N;
    cin >> N;
    vector<int> distances(N);
    for (int i = 0; i < N; ++i) {
        cin >> distances[i];
    }
    vector<int> prefixSum(N + 1, 0);
    for (int i = 0; i < N; ++i) {
        prefixSum[i + 1] = prefixSum[i] + distances[i];
    }

    int M;
    cin >> M;
    for (int i = 0; i < M; ++i) {
        int start, end;
        cin >> start;
        cin >> end;
        if (start > end) {
            swap(start, end);
        }
        int sum = prefixSum[end - 1] - prefixSum[start - 1];
        int total = prefixSum.back();
        cout << min(sum, total - sum) << endl;
    }

    return 0;
}
题目详情
99 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 4 字符数组

子串与子列

子串是一个字符串中连续的一部分,而子列是字符串中保持字符顺序的一个子集,可以连续也可以不连续。例如给定字符串 atpaaabpabtt,pabt 是一个子串,而 pat 就是一个子列。

现给定一个字符串 S 和一个子列 P,本题就请你找到 S 中包含 P 的最短子串。若解不唯一,则输出起点最靠左边的解。

时间限制:1000

内存限制:65536

输入

输入在第一行中给出字符串 S,第二行给出 P。S 非空,由不超过 104 个小写英文字母组成;P 保证是 S 的一个非空子列。

输出

在一行中输出 S 中包含 P 的最短子串。若解不唯一,则输出起点最靠左边的解。

样例输入

atpaaabpabttpcat
pat

样例输出

pabt
答案与解析
参考答案
#include <stdio.h>
#include <string.h>
int main(){
    char s[10001], p[10001];
    int i, j, t = 0, len, min = 10001, m, n, k = 0, flag = 0;
    scanf("%s\n%s", s, p);
	   while(1){
        for(i = 0;i < strlen(p);i++){
           if(!i){
               for(j = t + k;j < strlen(s);j++){
                   if(s[j] == p[i]){
                       k = 1;
                       break;
                   }
               }
               t = j;
           }else{
                for(j++;j < strlen(s);j++){
                    if(s[j] == p[i]) break;
                }
           }
           if(j == strlen(s)){ 
              flag = 1;
              break;
           }
        }
        if(flag == 1) break;
        len = j - t + 1;
        if(len < min){
            min = len;
            m = t;
            n = j;
        }
    }
    for(i = m;i <= n;i++) printf("%c", s[i]);
    return 0;
}
题目详情
100 简答题 偏难 C/C++编程考级 ·C/C++编程三级 · 5 数学库函数

拼大数

如何随机生成一个有 n 位数的大数呢?一种方法是,找到 n 个小朋友,每人发一张卡片,卡片一面写着编号(这里假设小朋友们从 1 到 n 编号),另一面让他们随便写下一个 1 位数字。然后让小朋友们把自己的卡片在墙上钉成一排,要求一张挨着一张,按他们的编号升序排列,显示他们自己写的数字。

但是,让十万个孩子都按指令行动,可太难了。结果是卡片乱七八糟满墙都是,有些甚至显示的不是正确的面。例如第 23 号小朋友在卡片上写了 8,我们应该在墙上看到 8,但是却看到了 23…… 你的任务就是把这些卡片整理好,得到我们真想要拼成的大数。

时间限制:6000

内存限制:65536

输入

输入第一行给出一个正个整数 n (≤ 105),随后 n 行,每行按 n1 n2的格式给出一张卡片两面的数字。

输出

在一行中输出我们真想要拼成的 n 位大数。 如果卡片两面都是 1 位数,那么就很难说哪个数字是编号,哪个数字是小朋友自己写的,所以解可能是不唯一的。这时候需要输出能得到的最小的数字。

样例输入

12
7 11
8 9
3 1
2 12
4 6
10 0
5 1
2 5
6 8
1 4
7 2
9 3

样例输出

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

int main() {
    int n;
    cin >> n;
    vector<priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>> pq(n + 1);
    vector<pair<int, int>> cards(n);

    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        cards[i].first = a;
        cards[i].second = b;

        // Check if a is a valid id and b is a valid digit
        if (a >= 1 && a <= n && b >= 0 && b <= 9) {
            pq[a].emplace(b, i);
        }
        // Check if b is a valid id and a is a valid digit
        if (b >= 1 && b <= n && a >= 0 && a <= 9) {
            pq[b].emplace(a, i);
        }
    }

    vector<bool> used(n, false);
    vector<int> result(n + 1, -1);

    for (int i = 1; i <= n; ++i) {
        while (!pq[i].empty()) {
            auto [d, idx] = pq[i].top();
            pq[i].pop();
            if (!used[idx]) {
                used[idx] = true;
                result[i] = d;
                break;
            }
        }
        if (result[i] == -1) {
            cout << "No solution" << endl;
            return 0;
        }
    }
题目详情