C/C++编程四级 题库
将某位设置为1的操作是?( )
按位或 | 可以用来将某位设为 1:
mask 对应位置为 1,其他位为 0。
以下代码的输出是?( )
int a = 12; int b = 10; cout << (a ^ b);
1100
| 1010
------
0110??
即十进制:6。
交换 a 和 b 的值,可用异或实现,以下语句的正确顺序是?( )
(1)a^=b;
(2)b^=a;
交换b值可以用三条异或语句完成:
a ^= b;
b ^= a;
a ^= b;
分析以下程序片段的时间复杂度是?( )
int cal(int n) {
if (n <= 0) return 1;
return cal(n - 1) + cal(n - 1);
}递归调用两次:cal(n - 1),调用次数和2的n次方有关,时间复杂度是:O(2^n)。
C++ 中,右移运算符`>>`对于有符号数,会在低位补符号位。( )
按位或运算满足交换律和结合律。( )
交换律:a | b 与 b | a 结果相同;
结合律:(a | b) | c 与 a | (b | c) 结果相同。
数字组合
有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;
}核电站
一个核电站有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;
}那就别担心了
下图转自“英式没品笑话百科”的新浪微博 —— 所以无论有没有遇到难题,其实都不用担心。

博主将这种逻辑推演称为“逻辑自洽”,即从某个命题出发的所有推理路径都会将结论引导到同一个最终命题(开玩笑的,千万别以为这是真正的逻辑自洽的定义……)。现给定一个更为复杂的逻辑推理图,本题就请你检查从一个给定命题到另一个命题的推理是否是“逻辑自洽”的,以及存在多少种不同的推理路径。例如上图,从“你遇到难题了吗?”到“那就别担心了”就是一种“逻辑自洽”的推理,一共有 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++ #includeusing 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; }
最长峰形线
在科学研究中,很多时候需要从一大堆原始数据中找出一条最好的“峰形线”。所谓长度为 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;
}红蓝串
小红有两条珠串,一条有 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; }
总异或和


#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;
}三数之和


#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;
}二进制串的评分
对于一个给定的二进制串 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;
}