实验三 文字或算式题目的解题技巧（二）
题目 1：赛软件 × 比赛 = 软件比拼
题目描述
#include <stdio.h>
int main() {
int a, b, c, d, e; // a赛 b软 c件 d比 e拼
for (a = 1; a <= 9; a++)
for (b = 1; b <= 9; b++)
for (c = 0; c <= 9; c++)
for (d = 1; d <= 9; d++)
for (e = 0; e <= 9; e++) {
int x = a * 100 + b * 10 + c;
int y = d * 10 + a;
int z = b * 1000 + c * 100 + d * 10 + e;
if (x * y == z) printf("%d*%d=%d\n", x, y, z);
}
return 0;
}
题目 2：古堡算式 ABCDE × ? = EDCBA
题目描述
#include <stdio.h>
int main() {
int a, b, c, d, e, f;
for (a = 1; a <= 9; a++)
for (b = 0; b <= 9; b++)
for (c = 0; c <= 9; c++)
for (d = 0; d <= 9; d++)
for (e = 1; e <= 9; e++)
for (f = 1; f <= 9; f++) {
int x = a*10000 + b*1000 + c*100 + d*10 + e;
int z = e*10000 + d*1000 + c*100 + b*10 + a;
if (x*f == z && a!=b && a!=c && a!=d && a!=e
&& b!=c && b!=d && b!=e && b!=f
&& c!=d && c!=e && c!=f
&& d!=e && d!=f && e!=f)
printf("%d*%d=%d\n", x, f, z);
}
return 0;
}
题目 3：马虎的算式 ab × cde = adb × ce
题目描述
#include <stdio.h>
int main() {
int a, b, c, d, e, cnt = 0;
for (a = 1; a <= 9; a++)
for (b = 1; b <= 9; b++)
for (c = 1; c <= 9; c++)
for (d = 1; d <= 9; d++)
for (e = 1; e <= 9; e++) {
int x = a*10+b, y = c*100+d*10+e;
int z = a*100+d*10+b, l = c*10+e;
if (x*y == z*l && a!=b && a!=c && a!=d && a!=e
&& b!=c && b!=d && b!=e
&& c!=d && c!=e && d!=e)
printf("%d*%d=%d*%d\n", x, y, z, l), cnt++;
}
printf("cnt=%d\n", cnt);
return 0;
}
题目 4：三羊献瑞
题目描述
#include <stdio.h>
int main() {
int a, b, c, d, e, f, g, h;
for (a = 1; a <= 9; a++) for (b = 0; b <= 9; b++)
for (c = 0; c <= 9; c++) for (d = 0; d <= 9; d++)
for (e = 1; e <= 9; e++) for (f = 0; f <= 9; f++)
for (g = 0; g <= 9; g++) for (h = 0; h <= 9; h++) {
if (a!=b && a!=c && a!=d && a!=e && a!=f && a!=g && a!=h
&& b!=c && b!=d && b!=e && b!=f && b!=g && b!=h
&& c!=d && c!=e && c!=f && c!=g && c!=h
&& d!=e && d!=f && d!=g && d!=h
&& e!=f && e!=g && e!=h && f!=g && f!=h && g!=h) {
int n1 = a*1000+b*100+c*10+d;
int n2 = e*1000+f*100+g*10+b;
int n3 = e*10000+f*1000+c*100+b*10+h;
if (n1+n2 == n3) { printf("三羊献瑞 = %d\n", n2); return 0; }
}
}
return 0;
}
题目 5：立方和问题
题目描述
#include <stdio.h>
int main() {
int a, b, c, d;
for (a = 1; a < 30; a++)
for (b = a+1; b < 30; b++)
for (c = b+1; c < 30; c++)
for (d = c+1; d < 30; d++)
if (a*a*a + d*d*d == b*b*b + c*c*c)
printf("%d,%d,%d,%d\n", a, b, c, d);
return 0;
}
题目 6：类似 625 的数字
题目描述
#include <stdio.h>
int main() {
for (int n = 100; n <= 999; n++) {
long long square = (long long)n * n;
if (square % 1000 == n) printf("%d\n", n);
}
return 0;
}
实验四 数组的具体应用及其解题技巧（一）
题目 A：求平均值及大于平均值的个数
题目描述
#include <stdio.h>
int main() {
int a[10], sum = 0, cnt = 0;
for (int i = 0; i < 10; i++) { scanf("%d", &a[i]); sum += a[i]; }
int avg = sum / 10;
for (int i = 0; i < 10; i++) if (a[i] > avg) cnt++;
printf("%d\n", cnt);
return 0;
}
题目 B：日期是该年的第几天
题目描述
#include <stdio.h>
int main() {
int y, m, d;
int month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
while (scanf("%d/%d/%d", &y, &m, &d) != EOF) {
int sum = 0;
for (int i = 0; i < m; i++) sum += month[i];
sum += d;
if (m > 2 && (y%4==0 && y%100!=0 || y%400==0)) sum++;
printf("%d\n", sum);
}
return 0;
}
题目 C：绝对值最小的数与最后一个数交换
题目描述
#include <stdio.h>
#include <math.h>
int main() {
int a[10], min = 0;
for (int i = 0; i < 10; i++) scanf("%d", &a[i]);
for (int i = 1; i < 10; i++)
if (abs(a[i]) < abs(a[min])) min = i;
int t = a[min]; a[min] = a[9]; a[9] = t;
for (int i = 0; i < 10; i++) printf("%d ", a[i]);
return 0;
}
题目 D：插入数到有序数组
题目描述
#include <stdio.h>
int main() {
int a[10], x, i;
for (i = 0; i < 9; i++) scanf("%d", &a[i]);
scanf("%d", &x);
for (i = 8; i >= 0 && a[i] > x; i--) a[i+1] = a[i];
a[i+1] = x;
for (i = 0; i < 10; i++) printf("%d\n", a[i]);
return 0;
}
题目 E：判断回文串
题目描述
#include <stdio.h>
#include <string.h>
int main() {
char s[256];
gets(s);
int len = strlen(s), flag = 1;
for (int i = 0, j = len-1; i < j; i++, j--)
if (s[i] != s[j]) { flag = 0; break; }
printf(flag ? "Y" : "N");
return 0;
}
题目 F：字符串颠倒
题目描述
#include <stdio.h>
#include <string.h>
int main() {
char s[256];
gets(s);
for (int i = strlen(s)-1; i >= 0; i--) putchar(s[i]);
return 0;
}
实验五 数组的具体应用及其解题技巧（二）
题目 A：矩阵中绝对值最大的元素
题目描述
#include <stdio.h>
#include <math.h>
int main() {
int n, i, j, max = 0, i1 = 0, j1 = 0;
scanf("%d", &n);
int a[n][n];
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) scanf("%d", &a[i][j]);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (abs(a[i][j]) > abs(max)) { max = a[i][j]; i1 = i; j1 = j; }
printf("%d %d %d", max, i1+1, j1+1);
return 0;
}
题目 B：每行最大值位置放该行总和
题目描述
#include <iostream>
using namespace std;
int main() {
int m, n, a[101][101];
while (cin >> n >> m) {
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) cin >> a[i][j];
for (int i = 0; i < n; i++) {
int sum = 0, t = 0, max = a[i][0];
for (int j = 0; j < m; j++) {
sum += a[i][j];
if (max < a[i][j]) { max = a[i][j]; t = j; }
}
a[i][t] = sum;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) cout << a[i][j] << " ";
cout << endl;
}
}
return 0;
}
题目 C：判断矩阵是否对称
题目描述
#include <stdio.h>
int main() {
int n, a[100][100];
while (scanf("%d", &n) != EOF) {
int flag = 1;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) scanf("%d", &a[i][j]);
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++)
if (a[i][j] != a[j][i]) { flag = 0; break; }
printf(flag ? "Yes!\n" : "No!\n");
}
return 0;
}
题目 D：矩阵转置
题目描述
#include <iostream>
using namespace std;
int main() {
int m, n, a[20][20], b[20][20];
cin >> m >> n;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) { cin >> a[i][j]; b[j][i] = a[i][j]; }
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) cout << b[i][j] << " ";
cout << endl;
}
return 0;
}
题目 E：去掉字符串中的空格
题目描述
#include <stdio.h>
int main() {
char a[100];
while (fgets(a, sizeof(a), stdin) != NULL)
for (int i = 0; a[i] != '\0'; i++)
if (a[i] != ' ') putchar(a[i]);
return 0;
}
题目 F：字符串编码（Run-Length Encoding）
题目描述
#include <iostream>
#include <string>
using namespace std;
int main() {
int n; cin >> n;
while (n--) {
string str; cin >> str;
str += '*';
int cnt = 0;
for (int i = 0; i < (int)str.size(); i++) {
if (str[i] != str[i+1]) {
if (cnt) cout << cnt+1;
if (str[i] != '*') cout << str[i];
cnt = 0;
} else cnt++;
}
cout << endl;
}
return 0;
}
题目 G：回文数加法步骤
题目描述
#include <iostream>
using namespace std;
int ishw(int m) {
int a[20], n = 0;
for (int i = 0; m; i++) { a[i] = m % 10; m /= 10; n = i; }
for (int j = 0; j < n; j++, n--)
if (a[j] != a[n]) return 0;
return 1;
}
int newnum(int m) {
int n = 0;
while (m) { n = n*10 + m%10; m /= 10; }
return n;
}
int main() {
int n, m; cin >> n;
while (n--) {
cin >> m;
int i;
for (i = 0; i < 8; i++) {
if (ishw(m)) break;
m = m + newnum(m);
}
cout << (i < 8 ? i : 0) << endl;
}
return 0;
}
实验六 函数的定义及其应用
题目 A：判断水仙花数（函数实现）
题目描述
#include <iostream>
using namespace std;
int panduan(int n) {
int a = n%10, b = n/10%10, c = n/100;
return (a*a*a + b*b*b + c*c*c == n) ? 1 : 0;
}
int main() {
int n; cin >> n;
cout << panduan(n) << endl;
return 0;
}
题目 B：数字间加空格输出（函数实现）
题目描述
#include <iostream>
using namespace std;
void myfun(int n) {
int a = n%10, b = n/10%10, c = n/100%10, d = n/1000%10;
printf("%d %d %d %d\n", d, c, b, a);
}
int main() {
int n; cin >> n;
myfun(n);
return 0;
}
题目 C：字符串反序（函数实现）
题目描述
#include <iostream>
#include <cstring>
using namespace std;
void myreverse(char s[]) {
int len = strlen(s);
for (int i = 0, j = len-1; i < j; i++, j--) {
char t = s[i]; s[i] = s[j]; s[j] = t;
}
}
int main() {
char s[100]; cin >> s;
myreverse(s);
cout << s;
return 0;
}
题目 D：统计字符类型（函数实现）
题目描述
#include <iostream>
using namespace std;
void myfun(char s[], int cnt[]) {
for (int i = 0; s[i] != '\0'; i++) {
if (s[i]>='a'&&s[i]<='z' || s[i]>='A'&&s[i]<='Z') cnt[0]++;
else if (s[i]>='0'&&s[i]<='9') cnt[1]++;
else if (s[i]==' ') cnt[2]++;
else cnt[3]++;
}
}
int main() {
char s[200]; int cnt[4] = {0};
scanf("%[^\n]", s);
myfun(s, cnt);
for (int i = 0; i < 4; i++) cout << cnt[i] << " ";
return 0;
}
题目 E：最大最小数与首尾交换（函数实现）
题目描述
#include <cstdio>
#include <algorithm>
using namespace std;
void input(int a[]) { for (int i = 0; i < 10; i++) scanf("%d", &a[i]); }
void deal(int a[]) {
int max = 0, min = 0;
for (int i = 1; i < 10; i++) {
if (a[i] > a[max]) max = i;
if (a[i] < a[min]) min = i;
}
swap(a[0], a[min]);
if (max == 0) max = min;
swap(a[9], a[max]);
}
void output(int a[]) { for (int i = 0; i < 10; i++) printf("%d ", a[i]); }
int main() {
int a[10];
input(a); deal(a); output(a);
return 0;
}
题目 F：循环移位（函数实现）
题目描述
#include <cstdio>
unsigned int move(unsigned int value, int n) {
const int BITS = 32;
if (n > 0) return (value >> n) | (value << (BITS - n));
else { n = -n; return (value << n) | (value >> (BITS - n)); }
}
int main() {
unsigned int x; int n;
scanf("%u%d", &x, &n);
printf("%u\n", move(x, n));
return 0;
}
实验七 递归函数的定义及其应用
题目 1：输出 begin 到 end 之间的数
题目描述
#include <iostream>
using namespace std;
void fun(int begin, int end) {
if (begin > end) return;
cout << begin << endl;
fun(begin + 1, end);
}
int main() {
int a, b; cin >> a >> b;
fun(a, b);
return 0;
}
题目 2：递归求 1 到 n 之和
题目描述
#include <iostream>
using namespace std;
int mysum(int n) {
if (n == 0) return 0;
return mysum(n-1) + n;
}
int main() {
int n; cin >> n;
cout << mysum(n) << endl;
return 0;
}
题目 3：递归求最大公约数
题目描述
#include <iostream>
using namespace std;
int gcd(int m, int n) {
if (m % n == 0) return n;
return gcd(n, m % n);
}
int main() {
int m, n; cin >> m >> n;
cout << gcd(m, n) << endl;
return 0;
}
题目 4：递归求数组前 n 项之和 (mysum1)
题目描述
#include <iostream>
using namespace std;
int mysum1(int a[], int n) {
if (n == 0) return 0;
return a[n-1] + mysum1(a, n-1);
}
int main() {
int n, a[100]; cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
cout << mysum1(a, n) << endl;
return 0;
}
题目 5：递归求数组 L 到 R 项之和 (mysum2)
题目描述
#include <iostream>
using namespace std;
int mysum2(int a[], int L, int R) {
if (L > R) return 0;
return a[L] + mysum2(a, L+1, R);
}
int main() {
int n, a[100]; cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
cout << mysum2(a, 0, n-1) << endl;
return 0;
}
题目 6：递归判断回文串
题目描述
#include <iostream>
#include <cstring>
using namespace std;
int fun(char s[], int L, int R) {
if (L >= R) return 1;
if (s[L] != s[R]) return 0;
return fun(s, L+1, R-1);
}
int main() {
char s[100]; gets(s);
cout << (fun(s, 0, strlen(s)-1) ? "yes" : "no") << endl;
return 0;
}
实验八 快速幂和二分法应用技巧
题目 1：P2249 查找（二分查找）
题目描述
#include <bits/stdc++.h>
using namespace std;
int binsearch(int a[], int n, int x) {
int L = 0, R = n;
while (L < R) {
int mid = (L + R) / 2;
if (x > a[mid]) L = mid + 1;
else R = mid;
}
return L;
}
int a[1000002];
int main() {
int m, n, x;
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> a[i];
while (m--) {
cin >> x;
int pos = binsearch(a, n, x);
if (a[pos] == x) cout << pos+1 << " ";
else cout << -1 << " ";
}
return 0;
}
题目 2：2163 查找最接近的元素
题目描述
#include <bits/stdc++.h>
using namespace std;
int binsearch(int a[], int n, int x) {
int L = 0, R = n;
while (L < R) {
int mid = (L + R) / 2;
if (x > a[mid]) L = mid + 1;
else R = mid;
}
if (L == 0) return a[0];
if (L == n) return a[n-1];
if (x - a[L-1] < a[L] - x) return a[L-1];
else return a[L];
}
int a[100002];
int main() {
int m, n, x;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
while (m--) {
scanf("%d", &x);
printf("%d\n", binsearch(a, n, x));
}
return 0;
}
题目 3：2088 快速幂
题目描述
#include <iostream>
using namespace std;
typedef long long LL;
LL qpow(LL a, LL b, LL p) {
LL res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
int main() {
LL a, b; int p;
cin >> a >> b >> p;
cout << qpow(a, b, p) << endl;
return 0;
}
题目 4：2513 序列的第 k 个数
题目描述
#include <iostream>
using namespace std;
typedef long long LL;
const LL MOD = 200907;
LL qpow(LL a, LL b) {
LL res = 1;
while (b) { if (b&1) res = res*a%MOD; a = a*a%MOD; b >>= 1; }
return res;
}
int main() {
int T; cin >> T;
while (T--) {
LL a, b, c, k;
cin >> a >> b >> c >> k;
if (b - a == c - b) { // 等差数列
LL d = b - a;
cout << (a + (k-1)*d % MOD + MOD) % MOD << endl;
} else { // 等比数列
LL q = b / a;
cout << a * qpow(q, k-1) % MOD << endl;
}
}
return 0;
}
实验九 二分法的应用扩展——二分答案
题目 1：1885 分巧克力
题目描述
#include <iostream>
using namespace std;
int n, k, h[100005], w[100005];
int check(int len) {
int sum = 0;
for (int i = 0; i < n; i++) sum += (h[i]/len) * (w[i]/len);
return sum >= k;
}
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> h[i] >> w[i];
int L = 1, R = 100000;
while (L < R) {
int mid = (L + R + 1) / 2;
if (check(mid)) L = mid;
else R = mid - 1;
}
cout << L;
return 0;
}
题目 2：P2440 木材加工
题目描述
#include <iostream>
using namespace std;
int n, k, h[100005];
int check(int len) {
int sum = 0;
for (int i = 0; i < n; i++) sum += h[i] / len;
return sum >= k;
}
int main() {
cin >> n >> k;
int L = 0, R = 0;
for (int i = 0; i < n; i++) {
cin >> h[i];
if (h[i] > R) R = h[i];
}
while (L < R) {
int mid = (L + R + 1) / 2;
if (check(mid)) L = mid;
else R = mid - 1;
}
cout << L;
return 0;
}
题目 3：P1824 进击的奶牛
题目描述
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, x[100005];
int check(int d) {
int cnt = 1, last = x[0];
for (int i = 1; i < n; i++)
if (x[i] - last >= d) { cnt++; last = x[i]; }
return cnt >= m;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> x[i];
sort(x, x + n);
int L = 1, R = x[n-1] - x[0];
while (L < R) {
int mid = (L + R + 1) / 2;
if (check(mid)) L = mid;
else R = mid - 1;
}
cout << L;
return 0;
}
题目 4：P1182 数列分段 Section II
题目描述
#include <iostream>
using namespace std;
int n, m, a[100005];
int check(int mid) {
int cnt = 1, sum = 0;
for (int i = 0; i < n; i++) {
if (sum + a[i] > mid) { cnt++; sum = a[i]; }
else sum += a[i];
}
return cnt <= m;
}
int main() {
cin >> n >> m;
int L = 0, R = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
if (a[i] > L) L = a[i];
R += a[i];
}
while (L < R) {
int mid = (L + R) / 2;
if (check(mid)) R = mid;
else L = mid + 1;
}
cout << L;
return 0;
}
实验十 STL 应用技巧（一）
问题 A：重排序列
题目描述
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v1;
int n, k1, kn; cin >> n;
while (n--) {
cin >> k1; v1.push_back(k1);
for (int i = 1; i <= 8; i++) {
cin >> kn;
if (kn > k1) v1.push_back(kn);
else v1.insert(v1.begin(), kn);
}
for (auto x : v1) cout << x << " ";
cout << endl;
v1.clear();
}
return 0;
}
问题 B：s01 串变换
题目描述
#include <bits/stdc++.h>
using namespace std;
int main() {
string s1 = "0", s2;
int n; cin >> n;
while (n--) {
for (char ch : s1)
s2 += (ch == '0' ? "1" : "01");
s1 = s2; s2 = "";
}
cout << s1;
return 0;
}
问题 C：统计单词出现次数
题目描述
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, cnt = 0;
string s1, s2; cin >> n >> s1 >> m >> s2;
int pos = s1.find(s2);
while (pos != -1) { cnt++; pos = s1.find(s2, pos+1); }
cout << cnt;
return 0;
}
问题 D：去重 + 排序
题目描述
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, x; set<int> s1;
cin >> n;
for (int i = 0; i < n; i++) { cin >> x; s1.insert(x); }
cout << s1.size() << endl;
for (auto it : s1) cout << it << " ";
return 0;
}
问题 E：集合操作
题目描述
#include <bits/stdc++.h>
using namespace std;
int main() {
set<int> s;
int k; cin >> k;
while (k--) {
int op, x; cin >> op >> x;
if (op == 1) s.insert(x);
else cout << (s.count(x) ? "True" : "False") << endl;
}
return 0;
}
问题 F：集合并集
题目描述
#include <bits/stdc++.h>
using namespace std;
int main() {
set<int> s1;
int n, m, x;
while (cin >> n >> m) {
for (int i = 0; i < n+m; i++) { cin >> x; s1.insert(x); }
for (auto it : s1) cout << it << " ";
cout << endl; s1.clear();
}
return 0;
}
实验十一 STL 应用技巧（二）
问题 A：统计自然数出现次数（map）
题目描述
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, x; map<int, int> mp;
cin >> n;
while (n--) { cin >> x; mp[x]++; }
for (auto it : mp) cout << it.first << " " << it.second << endl;
return 0;
}
问题 B：删除重复元素（DelPack）
题目描述
#include <bits/stdc++.h>
using namespace std;
void DelPack(string &s) {
map<char, int> mp;
for (char ch : s) mp[ch]++;
string s1;
for (char ch : s) if (mp[ch] == 1) s1 += ch;
s = s1;
}
int main() {
string s; getline(cin, s);
DelPack(s); cout << s;
return 0;
}
问题 C：统计单词数量
题目描述
#include <bits/stdc++.h>
using namespace std;
int main() {
string s1, word; getline(cin, s1);
stringstream ss; ss << s1;
vector<string> v1;
while (ss >> word) v1.push_back(word);
cout << v1.size() << endl;
return 0;
}
问题 D：统计不同单词个数
题目描述
#include <bits/stdc++.h>
using namespace std;
int main() {
string s1, word; getline(cin, s1);
stringstream ss; ss << s1;
set<string> mys1;
while (ss >> word) mys1.insert(word);
cout << mys1.size() << endl;
return 0;
}
问题 E：输出最长单词
题目描述
#include <bits/stdc++.h>
using namespace std;
int main() {
string s1, word; getline(cin, s1);
stringstream ss; ss << s1;
vector<string> v1;
while (ss >> word) v1.push_back(word);
int maxlen = 0, k = 0;
for (int i = 0; i < (int)v1.size(); i++)
if ((int)v1[i].size() > maxlen) { maxlen = v1[i].size(); k = i; }
cout << v1[k];
return 0;
}
问题 F：倒数第二小的数
题目描述
#include <bits/stdc++.h>
using namespace std;
int main() {
int a[200], t, n; cin >> t;
while (t--) {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n);
cout << a[1] << endl;
}
return 0;
}
实验十二 STL 应用技巧（三）
问题 A：合并链表（按学号排序）
题目描述
#include <bits/stdc++.h>
using namespace std;
int main() {
map<int, int> mp;
int n, m, num, score; cin >> n >> m;
for (int i = 0; i < n+m; i++) { cin >> num >> score; mp[num] = score; }
for (auto x : mp) cout << x.first << " " << x.second << endl;
return 0;
}
问题 B：1 到 n 的全排列
题目描述
#include <bits/stdc++.h>
using namespace std;
int main() {
int a[10] = {1,2,3,4,5,6,7,8,9,10}, n;
cin >> n;
do {
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << endl;
} while (next_permutation(a, a+n));
return 0;
}
问题 C：求排列序号
题目描述
#include <bits/stdc++.h>
using namespace std;
int main() {
string s1, s2; int n = 0;
cin >> s1; s2 = s1;
sort(s1.begin(), s1.end());
do {
if (s1 == s2) { cout << n << endl; break; }
n++;
} while (next_permutation(s1.begin(), s1.end()));
return 0;
}
问题 D：求第 n 个全排列
题目描述
#include <bits/stdc++.h>
using namespace std;
int main() {
string s1 = "0123456789";
int n, cnt = 0; cin >> n;
do {
cnt++;
if (cnt == n) { cout << s1 << endl; break; }
} while (next_permutation(s1.begin(), s1.end()));
return 0;
}
问题 E：7254 等式
题目描述
#include <bits/stdc++.h>
using namespace std;
int main() {
int a[9] = {1,2,3,4,5,6,7,8,9};
do {
int x = a[0]*1000 + a[1]*100 + a[2]*10 + a[3];
int y = a[4]*10 + a[5], z = a[6]*100 + a[7]*10 + a[8];
if (x == y*z) printf("%d = %d x %d\n", x, y, z);
int x1 = a[0]*1000 + a[1]*100 + a[2]*10 + a[3];
int y1 = a[4], z1 = a[5]*1000 + a[6]*100 + a[7]*10 + a[8];
if (x1 == y1*z1) printf("%d = %d x %d\n", x1, y1, z1);
} while (next_permutation(a, a+9));
return 0;
}
问题 F：后缀子串排序
题目描述
#include <bits/stdc++.h>
using namespace std;
int main() {
string s1;
while (cin >> s1) {
vector<string> v1;
int len = s1.size();
for (int i = 0; i < len; i++) v1.push_back(s1.substr(i));
sort(v1.begin(), v1.end());
for (auto x : v1) cout << x << endl;
v1.clear();
}
return 0;
}
问题 G：括号匹配
题目描述
#include <bits/stdc++.h>
using namespace std;
int main() {
stack<char> st;
char ch;
while ((ch = getchar()) != '@') {
if (ch == '(') st.push(ch);
else if (ch == ')') {
if (st.empty()) { cout << "NO" << endl; return 0; }
st.pop();
}
}
cout << (st.empty() ? "YES" : "NO") << endl;
return 0;
}
实验十三 并查集及其应用技巧
问题 A：判断图是否连通
题目描述
#include <iostream>
using namespace std;
int father[100003];
void Init(int n) { for (int i = 1; i <= n; i++) father[i] = i; }
int Find(int x) { return x == father[x] ? x : Find(father[x]); }
void Union(int x, int y) {
int rx = Find(x), ry = Find(y);
if (rx != ry) father[rx] = ry;
}
int main() {
int n, m, x, y;
while (cin >> n >> m) {
if (n==0 && m==0) break;
Init(n);
while (m--) { cin >> x >> y; Union(x, y); }
int cnt = 0;
for (int i = 1; i <= n; i++) if (i == father[i]) cnt++;
cout << (cnt == 1 ? "YES" : "NO") << endl;
}
return 0;
}
问题 B：畅通工程
题目描述
#include <iostream>
using namespace std;
int father[100003];
void Init(int n) { for (int i = 1; i <= n; i++) father[i] = i; }
int Find(int x) { return x == father[x] ? x : Find(father[x]); }
void Union(int x, int y) {
int rx = Find(x), ry = Find(y);
if (rx != ry) father[rx] = ry;
}
int main() {
int n, m, x, y;
while (cin >> n && n) {
Init(n); cin >> m;
while (m--) { cin >> x >> y; Union(x, y); }
int cnt = 0;
for (int i = 1; i <= n; i++) if (i == father[i]) cnt++;
cout << cnt - 1 << endl;
}
return 0;
}
问题 C：亲戚关系判断
题目描述
#include <iostream>
using namespace std;
int father[100003];
void Init(int n) { for (int i = 1; i <= n; i++) father[i] = i; }
int Find(int x) { return x == father[x] ? x : father[x] = Find(father[x]); }
void Union(int x, int y) {
int rx = Find(x), ry = Find(y);
if (rx != ry) father[rx] = ry;
}
int main() {
int n, m, q, x, y;
cin >> n >> m; Init(n);
while (m--) { scanf("%d%d", &x, &y); Union(x, y); }
cin >> q;
while (q--) {
scanf("%d%d", &x, &y);
printf(Find(x) == Find(y) ? "Yes\n" : "No\n");
}
return 0;
}
问题 D：小区网络通信判断
题目描述
#include <iostream>
using namespace std;
int father[100003];
void Init(int n) { for (int i = 1; i <= n; i++) father[i] = i; }
int Find(int x) { return x == father[x] ? x : Find(father[x]); }
void Union(int x, int y) {
int rx = Find(x), ry = Find(y);
if (rx != ry) father[rx] = ry;
}
int main() {
int n, m, x, y;
cin >> n >> m; Init(n);
while (m--) { cin >> x >> y; Union(x, y); }
cin >> x >> y;
cout << (Find(x) == Find(y) ? "Yes" : "No") << endl;
return 0;
}
实验十四 动态规划算法初步（一）
题目 1：1400 教学楼的楼梯（记忆化搜索）
题目描述
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL f[100] = {0};
LL myfun(int n) {
if (n == 1 || n == 2) return 1;
if (f[n] != 0) return f[n];
return f[n] = myfun(n-1) + myfun(n-2);
}
int main() {
int t, n; cin >> t;
while (t--) { cin >> n; cout << myfun(n) << endl; }
return 0;
}
题目 2：P1464 Function（记忆化搜索）
题目描述
#include <iostream>
using namespace std;
typedef long long LL;
LL p[21][21][21];
LL w(LL a, LL b, LL c) {
if (a <= 0 || b <= 0 || c <= 0) return 1;
if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);
if (p[a][b][c] != 0) return p[a][b][c];
if (a < b && b < c)
return p[a][b][c] = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c);
return p[a][b][c] = w(a-1,b,c) + w(a-1,b-1,c) + w(a-1,b,c-1) - w(a-1,b-1,c-1);
}
int main() {
LL a, b, c;
while (cin >> a >> b >> c && !(a==-1 && b==-1 && c==-1))
printf("w(%lld, %lld, %lld) = %lld\n", a, b, c, w(a, b, c));
return 0;
}
题目 3：P1216 数字三角形（记忆化搜索）
题目描述
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXR = 1005;
int a[MAXR][MAXR], mem[MAXR][MAXR], r;
int dfs(int i, int j) {
if (i == r) return a[i][j];
if (mem[i][j] != -1) return mem[i][j];
return mem[i][j] = a[i][j] + max(dfs(i+1, j), dfs(i+1, j+1));
}
int main() {
fill(&mem[0][0], &mem[MAXR][0], -1);
cin >> r;
for (int i = 1; i <= r; i++)
for (int j = 1; j <= i; j++) cin >> a[i][j];
cout << dfs(1, 1) << endl;
return 0;
}
实验十五 动态规划算法初步（二）
问题 A：数字三角形（递推法）
题目描述
#include <iostream>
using namespace std;
const int N = 105;
int a[N][N], dp[N][N];
int main() {
int t, n; cin >> t;
while (t--) {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++) cin >> a[i][j];
for (int j = 1; j <= n; j++) dp[n][j] = a[n][j];
for (int i = n-1; i >= 1; i--)
for (int j = 1; j <= i; j++)
dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1]);
cout << dp[1][1] << endl;
}
return 0;
}
问题 B：最大子段和
题目描述
#include <iostream>
using namespace std;
const int N = 100005;
int a[N], dp[N];
int main() {
int n; cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
dp[0] = a[0];
int maxv = dp[0];
for (int i = 1; i < n; i++) {
dp[i] = max(dp[i-1] + a[i], a[i]);
if (dp[i] > maxv) maxv = dp[i];
}
cout << maxv;
return 0;
}
问题 C：最长不下降子序列（LIS）
题目描述
#include <iostream>
using namespace std;
const int N = 10006;
int a[N], dp[N];
int main() {
int n; cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
dp[i] = 1;
for (int j = 1; j < i; j++)
if (a[i] >= a[j]) dp[i] = max(dp[i], dp[j] + 1);
}
int maxv = dp[1];
for (int i = 2; i <= n; i++)
if (dp[i] > maxv) maxv = dp[i];
cout << maxv;
return 0;
}
0.0分
0 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复