首页 › 题库 › C/C++编程考级 › 4 位运算

C/C++编程四级 题库

共 16 道题 · 按题型筛选,点「查看答案」核对解析
1 单选题 适中 C/C++编程考级 ·C/C++编程四级 · 4 位运算

将某位设置为1的操作是?( )

A
x & mask
B
x | mask
C
x ^ mask
D
x >> mask
答案与解析
正确答案:B

按位或 | 可以用来将某位设为 1:

mask 对应位置为 1,其他位为 0。

题目详情
2 单选题 适中 C/C++编程考级 ·C/C++编程四级 · 4 位运算

0x0F | 0xF0 的结果是?( )

A
0xFF
B
0x00
C
0x0F
D
0xF0
答案与解析
正确答案:A

0x0F | 0xF0结果为:0xFF。

题目详情
3 单选题 适中 C/C++编程考级 ·C/C++编程四级 · 4 位运算

以下代码的输出是?( )

int a = 12; 
int b = 10; 
cout << (a ^ b);
A
6
B
12
C
10
D
14
答案与解析
正确答案:A

1100

| 1010

------

  0110??

即十进制:6。

题目详情
4 单选题 适中 C/C++编程考级 ·C/C++编程四级 · 4 位运算

交换 a 和 b 的值,可用异或实现,以下语句的正确顺序是?( )

(1)a^=b;

(2)b^=a;

A
1 2 1
B
1 2 2
C
2 2 1
D
2 2 1
答案与解析
正确答案:A

交换b值可以用三条异或语句完成:

a ^= b;

b ^= a;

a ^= b;

题目详情
5 单选题 适中 C/C++编程考级 ·C/C++编程四级 · 4 位运算

分析以下程序片段的时间复杂度是?( )

int cal(int n) {
    if (n <= 0) return 1;
    return cal(n - 1) + cal(n - 1);
}
A
O(n)
B
O(2^n)
C
O(n^2)
D
O(n log n)
答案与解析
正确答案:B

递归调用两次:cal(n - 1),调用次数和2的n次方有关,时间复杂度是:O(2^n)。

题目详情
6 判断题 偏易 C/C++编程考级 ·C/C++编程四级 · 4 位运算

C++ 中,右移运算符`>>`对于有符号数,会在低位补符号位。( )

A
对
B
错
答案与解析
正确答案:错
分析右移运算符对有符号数的操作机制:右移时,高位补符号位,低位按位移规则舍弃;补位方式由符号位决定,符号位为1则高位补1,为0则补0;该行为依赖于编译器实现定义的算术右移机制,具体表现由目标平台的指令集和C++标准中未明确规定的部分共同决定。
题目详情
7 判断题 偏易 C/C++编程考级 ·C/C++编程四级 · 4 位运算

按位或运算满足交换律和结合律。( )

A
对
B
错
答案与解析
正确答案:对

交换律:a | b 与 b | a 结果相同;

结合律:(a | b) | c 与 a | (b | c) 结果相同。

题目详情
8 判断题 偏易 C/C++编程考级 ·C/C++编程四级 · 4 位运算

x | 0 的结果是0。( )

A
对
B
错
答案与解析
正确答案:错

错误,x | 0 的结果是x。

题目详情
9 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 4 位运算

数字组合

有n个正整数,找出其中和为t(t也是正整数)的可能的组合方式。如: n=5,5个数分别为1,2,3,4,5,t=5; 那么可能的组合有5=1+4和5=2+3和5=5三种组合方式。

时间限制:1000

内存限制:65536

输入

输入的第一行是两个正整数n和t,用空格隔开,其中1<=n<=20,表示正整数的个数,t为要求的和(1<=t<=1000) 接下来的一行是n个正整数,用空格隔开。

输出

和为t的不同的组合方式的数目。

样例输入

5 5
1 2 3 4 5

样例输出

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

int a[25],n,t,ans;

void dfs(int i,int sum){
	if(i==n){
		if(t==sum){
			ans++;
		}
		return;
	}
	i++;
	dfs(i,sum+a[i]);
	dfs(i,sum);
}

int main(){
	cin>>n>>t;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dfs(0,0);
	cout<<ans;
	return 0;
}
//解法2 背包问题
#include <bits/stdc++.h>
using namespace std;
int n,t;
int a[22],f[1005];
int main()
{	
	cin >> n >> t;  // 从标准输入读取两个整数 n 和 t
	for (int i = 1; i <= n; i++)
		cin >> a[i];  // 从标准输入读取 n 个整数,并存储到数组 a 中
	f[0] = 1;  // 将数组 的第 0 个元素置为 1,表示容积为 0 时的方式数量为 1
	for (int i = 1; i <= n; i++) {
		for (int j = t; j >= a[i]; j--)
			f[j] += f[j - a[i]];  // 动态规划转移方程,累加之前容积 j 和当前物品体积之差的容积的方式数量
	}
	cout << f[t];  // 输出数组 f 中第 t 个元素,表示容积为 t 时的方式数量
	return 0;
}
//解法3 递归求解
#include <bits/stdc++.h>  
using namespace std; 
int n, t; 
int a[22];  
int f(int sum, int p) {
	if (sum == t)
		return 1;  // 如果当前总和等于目标值 t,则返回1 表示找到一种组合方式。
	if (sum > t || p > n)
		return 0;  // 如果当前总和大于目标值 t 或已经遍历完所有物品,则返回 0 表示没有合适的组合方式。
	// 递归调用 f 函数,分别尝试选取下一个物品和不选取下一个物品两种情况,并累加它们的结果
	return f(sum + a[p], p + 1) + f(sum, p + 1);
}
int main() {
	cin >> n >> t;  // 从标准输入读取两个整数 n 和 t	
	for (int i = 1; i <= n; i++)
		cin >> a[i];  // 从标准输入读取 n 个整数,并存储到数组 a 中
	cout <<f(0, 1);  // 调用函数 f,初始总和为 0,从第一个物品开始选取	
	return 0;
}
题目详情
10 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 4 位运算

核电站

一个核电站有N个放核物质的坑,坑排列在一条直线上。如果连续M个坑中放入核物质,则会发生爆炸,于是,在某些坑中可能不放核物质。

任务:对于给定的N和M,求不发生爆炸的放置核物质的方案总数

时间限制:6000

内存限制:131072

输入

只一行,两个正整数N,M( 1 < N < 50,2 ≤ M ≤ 5 )

输出

一个正整数S,表示方案总数。

样例输入

4 3

样例输出

13
答案与解析
参考答案
//样例代码  动态规划
#include <bits/stdc++.h>
using namespace std;
int n,m;
long long dp[55][7];//前i个坑现在已经连续埋了j个的方案
int main()
{	
	cin>>n>>m;
	dp[1][1]=1;//第1个放
	dp[1][0]=1;//第1个不放
	for(int i=2;i<=n;i++){
		for(int j=0;j<m;j++){
			if(j==0){//第j个不放
				for(int k=0;k<m;k++)//0~m-1的位置都可放可不放
					dp[i][j]+=dp[i-1][k];
			}
			else //第j个放
				dp[i][j]+=dp[i-1][j-1];
		}
	}
	long long ans=0;
	for(int i=0;i<m;i++)
		ans+=dp[n][i];
	cout<<ans;	
	return 0;
}


题目详情
11 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 4 位运算

那就别担心了

下图转自“英式没品笑话百科”的新浪微博 —— 所以无论有没有遇到难题,其实都不用担心。

博主将这种逻辑推演称为“逻辑自洽”,即从某个命题出发的所有推理路径都会将结论引导到同一个最终命题(开玩笑的,千万别以为这是真正的逻辑自洽的定义……)。现给定一个更为复杂的逻辑推理图,本题就请你检查从一个给定命题到另一个命题的推理是否是“逻辑自洽”的,以及存在多少种不同的推理路径。例如上图,从“你遇到难题了吗?”到“那就别担心了”就是一种“逻辑自洽”的推理,一共有 3 条不同的推理路径。

时间限制:7000

内存限制:65536

输入

输入首先在一行中给出两个正整数 N(1 < N ≤ 500)和 M,分别为命题个数和推理个数。这里我们假设命题从 1 到 N 编号。 接下来 M 行,每行给出一对命题之间的推理关系,即两个命题的编号 S1 S2,表示可以从 S1 推出 S2。题目保证任意两命题之间只存在最多一种推理关系,且任一命题不能循环自证(即从该命题出发推出该命题自己)。 最后一行给出待检验的两个命题的编号 A B。

输出

在一行中首先输出从 A 到 B 有多少种不同的推理路径,然后输出 Yes 如果推理是“逻辑自洽”的,或 No 如果不是。 题目保证输出数据不超过 109。

样例输入

样例1:

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

样例2:

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

样例输出

样例1:

3 Yes

样例2:

3 No
答案与解析
参考答案
//参考代码1 C++
#include 
using namespace std;
const int N = 510;
 
int n, m;
int way[N][N];
int cnt[N], st, en;
bool st1[N], flag = false;
void dfs(int u) {
    if (u == en) {
        cnt[en] ++;
        return;
    }
    if (way[u][0] == 0) flag = true;
    for (int i = 1; i <= way[u][0]; i ++ ) {
        int j = way[u][i];
        if (!st1[j]) {
            dfs(j);
            st1[j] = true;
        }
        cnt[u] += cnt[j];
    }
}
 
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i ++ ) {
        int a, b;
        cin >> a >> b;
        way[a][0] ++;
        way[a][way[a][0]] = b;
    }
    cin >> st >> en;
    dfs(st);
    if (flag) cout << cnt[st] << " No";
    else cout << cnt[st] << " Yes";
}
//参考代码2 C语言
#include 
#include 

#define MAX_NODES 502

int N, M, S1, S2, A, B, consistency, laneNum[MAX_NODES];
int Edge[MAX_NODES][MAX_NODES];

int dfs(int index) {
    if (laneNum[index] != 0) return laneNum[index];
    
    for (int i = 0; i < MAX_NODES; i++) {
        if (Edge[index][i] != 0) {
            if (laneNum[i] == 0) dfs(i);
            laneNum[index] += laneNum[i];
        }
    }
    
    if (laneNum[index] == 0) consistency = 1;
    return laneNum[index];
}

int main() {
    scanf("%d %d", &N, &M);
    
    for (int i = 0; i < M; ++i) {
        scanf("%d %d", &S1, &S2);
        Edge[S1][S2] = 1;
    }
    
    scanf("%d %d", &A, &B);
    laneNum[B] = 1;
    dfs(A);
    
    printf("%d %s", laneNum[A], (consistency ? "No" : "Yes"));

    return 0;
}
题目详情
12 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 4 位运算

最长峰形线

在科学研究中,很多时候需要从一大堆原始数据中找出一条最好的“峰形线”。所谓长度为 L 的“峰形线”,是指 L 个数字组成的有序序列 { D1, …, DL },满足条件:存在下标 i(1 < i < L)使得 D1 < … < Di-1 < Di > Di+1 > … > DL。

顺次给出 n 个数字,你可以从中删掉部分数字,使得剩下的数字能构成峰形线。要求构造出来的峰形线是最长的。当最长峰形线不唯一时,你要输出最对称(即升序和降序两部分长度之差为最小)的那条。

时间限制:7000

内存限制:262144

输入

输入第一行给出一个正个整数 n (3 ≤ n ≤ 104),随后一行给出 n 个在区间 [-10000, 10000] 内的整数,以空格分隔。

输出

首先在一行中输出最长峰形线的长度、峰顶数字的序号(从 1 开始)和它的值,数字间以 1 个空格分隔。如果解不存在,则在一行中输出 `No peak shape`。裁判数据保证输出是唯一的。


样例输入

样例#1:

20

1 3 0 8 5 -2 29 20 20 4 10 4 7 25 18 6 17 16 2 -1

样例#2:

5

-1 3 8 10 20

样例输出

样例#1:

10 14 25

样例#2:

No peak shape

答案与解析
参考答案
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    if (n < 3) {
        cout << "No peak shape" << endl;
        return 0;
    }
 
    // LIS dp (Longest Increasing Subsequence from the left)
    vector<int> lis(n, 1);  // lis[i] 表示以 arr[i] 为结尾的最长上升子序列长度
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                lis[i] = max(lis[i], lis[j] + 1);
            }
        }
    }
 
    // LDS dp (Longest Decreasing Subsequence from the right)
    vector<int> lds(n, 1);  // lds[i] 表示以 arr[i] 为开始的最长下降子序列长度
    for (int i = n - 1; i >= 0; i--) {
        for (int j = n - 1; j > i; j--) {
            if (arr[i] > arr[j]) {
                lds[i] = max(lds[i], lds[j] + 1);
            }
        }
    }
 
    int maxLength = 0;
    int bestIndex = -1;
    int bestValue = INT_MIN;
    int bestDiff = INT_MAX;
 
    // 查找峰形线
    for (int i = 1; i < n - 1; i++) {
        // 如果 arr[i] 是峰顶
        if (lis[i] > 1 && lds[i] > 1) {
            int length = lis[i] + lds[i] - 1;  // 总长度
            int diff = abs(lis[i] - lds[i]);   // 升降长度差
 
            if (length > maxLength || (length == maxLength && diff < bestDiff)) {
                maxLength = length;
                bestIndex = i;
                bestValue = arr[i];
                bestDiff = diff;
            }
        }
    }
 
    // 输出结果
    if (maxLength == 0) {
        cout << "No peak shape" << endl;
    } else {
        cout << maxLength << " " << bestIndex + 1 << " " << bestValue << endl;
    }
 
    return 0;
}
题目详情
13 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 4 位运算

红蓝串

小红有两条珠串,一条有 A 只红色珠子,另一条有 B 只蓝色珠子。她想用下列步骤做一条红蓝珠子的串:

- 她会从两条珠串上一步一步地取下珠子。

- 第 i 步时,她会从一条珠串上取下 i 颗珠子,穿到结果串上。

- 她最后要得到一条有 n 颗珠子的串。

小红有可能得到多少种不同的结果呢?

如果小红在至少某一步中选择了不同颜色的串来取珠子,那么两条结果串就被认为是不同的。

时间限制:6000

内存限制:262144

输入

输入在一行中给出 3 个整数:n (0 < n ≤ 2 × 105)、A、B (0≤ A, B ≤ 105),其定义如题面所述。

输出

在一行中输出小红有可能得到多少条有 n 颗珠子的串。因为结果可能是很大的数字,所以你要输出对 1000000007 (109 + 7) 取模后的结果。


样例输入

10 4 7

样例输出

4

提示

小红能得到的 4 种不同的结果如下图所示。 

答案与解析
参考答案
#include 
#include 
#include 
using namespace std;

const int MOD = 1000000007;

int main() {
    long long n, A, B;
    cin >> n >> A >> B;
    
    long long D = 8 * n + 1;
    long long m = sqrt(D);
    if (m * m != D || m % 2 == 0) {
        cout << 0 << endl;
        return 0;
    }
    long long k = (m - 1) / 2;
    
    long long low = max(n - B, 0LL);
    long long high = min(A, n);
    
    if (low > high) {
        cout << 0 << endl;
        return 0;
    }
    
    vector dp(n + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= k; ++i) {
        for (int s = n; s >= i; --s) {
            dp[s] = (dp[s] + dp[s - i]) % MOD;
        }
    }
    
    long long ans = 0;
    for (int s = low; s <= high; ++s) {
        ans = (ans + dp[s]) % MOD;
    }
    
    cout << ans << endl;
    return 0;
}
题目详情
14 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 4 位运算

总异或和

image1.png

image2.png

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    ll ans = 0;
    // 遍历每一位 0~30
    for (int k = 0; k <= 30; ++k)
    {
        ll mod = 1LL << (k + 1);
        ll half = 1LL << k;
        vector<ll> rem;
        for (ll x : a)
            rem.push_back(x % mod);
        sort(rem.begin(), rem.end());
        ll cnt = 0;
        int l = 0, r = n - 1;
        // 统计 r_i + r_j >= half 且 < mod
        for (; r >= 0; --r)
        {
            while (l < n && rem[l] + rem[r] < half)
                l++;
            cnt += n - max(l, r + 1);
        }
        // 统计 r_i + r_j >= mod + half
        l = 0, r = n - 1;
        for (; r >= 0; --r)
        {
            while (l < n && rem[l] + rem[r] < mod + half)
                l++;
            cnt += n - max(l, r + 1);
        }
        if (cnt % 2 == 1)
            ans |= half;
    }
    cout << ans << endl;
    return 0;
}
题目详情
15 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 4 位运算

三数之和

image3.png

image4.png

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

// 两个字符串大数相加
string add(string s1, string s2)
{
    vector<int> res;
    int i = s1.size() - 1, j = s2.size() - 1, carry = 0;
    while (i >= 0 || j >= 0 || carry)
    {
        int a = i >= 0 ? s1[i--] - '0' : 0;
        int b = j >= 0 ? s2[j--] - '0' : 0;
        int sum = a + b + carry;
        carry = sum / 10;
        res.push_back(sum % 10);
    }
    string ans;
    reverse(res.begin(), res.end());
    for (int num : res) ans += (char)('0' + num);
    return ans;
}

int main()
{
    string a, b, c;
    cin >> a >> b >> c;
    string total = add(add(a, b), c);
    cout << total << endl;
    return 0;
}


题目详情
16 简答题 偏难 C/C++编程考级 ·C/C++编程四级 · 4 位运算

二进制串的评分

对于一个给定的二进制串 s(即仅由字符 0 和 1 组成的串),其评分是这样计算的:将原串切分为若干段,使得每段包含的字符是一样的,且相邻两段包含的字符是不一样的。该字符串的评分定义为各段长度的异或值(如果只有一段,评分就是这段的长度)。

异或(Exclusive OR,简称 XOR)是一种数学运算符,用于计算机中的位运算。当且仅当两个输入值不同时,异或运算输出为真(1),否则输出为假(0)。

例如,串 "10001100001" 可以切分为 5 段,即 "1"、"000"、"11"、"0000"、"1",其评分就是 1 ^ 3 ^ 2 ^ 4 ^ 1 = 5。

假设每一步我们可以交换 2 个相邻的字符,并且可以这样执行任意多步(当然也可以执行 0 步)。对每个可能的评分 x,你能得到多少个不同的串?将原串 s 通过交换操作变成评分为 x 的串,所用的最少步骤是多少次?

时间限制:1000

内存限制:65536

输入

输入在一行中给出非空的原始二进制串 s,其长度不超过 64。

输出

对每个可能的评分,在一行中输出 3 个空格分隔的整数,依次为:评分值、对 s 执行任意多步交换后能得到的不同串的个数、将 s 通过交换操作变成该评分的串所需要的最少步骤数。 按评分的升序输出。


样例输入

010

样例输出

1 1 0
3 2 1
答案与解析
参考答案
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <queue>

// 计算二进制串的评分
int calcScore(const std::string& s) {
    int score = 0, count = 1;
    for (int i = 1; i <= s.size(); ++i) {
        if (i == s.size() || s[i] != s[i - 1]) {
            score ^= count;
            count = 1;
        } else {
            ++count;
        }
    }
    return score;
}

// 广度优先搜索
void bfs(const std::string& start, std::unordered_map<int, std::pair<int, int>>& res) {
    std::unordered_map<std::string, int> minSteps;
    std::queue<std::string> q;
    q.push(start);
    minSteps[start] = 0;

    while (!q.empty()) {
        std::string s = q.front();
        q.pop();
        int score = calcScore(s);
        int steps = minSteps[s];

        if (res.find(score) == res.end()) {
            res[score] = {1, steps};
        } else {
            res[score].first++;
            res[score].second = std::min(res[score].second, steps);
        }

        for (int i = 0; i < s.size() - 1; ++i) {
            std::string newStr = s;
            std::swap(newStr[i], newStr[i + 1]);
            if (minSteps.find(newStr) == minSteps.end()) {
                minSteps[newStr] = steps + 1;
                q.push(newStr);
            }
        }
    }
}

int main() {
    std::string s;
    std::cin >> s;
    std::unordered_map<int, std::pair<int, int>> res;
    bfs(s, res);

    std::vector<int> scores;
    for (const auto& p : res) {
        scores.push_back(p.first);
    }
    std::sort(scores.begin(), scores.end());

    for (int score : scores) {
        std::cout << score << " " << res[score].first << " " << res[score].second << std::endl;
    }

    return 0;
}
题目详情