第七届蓝桥杯省赛 C++ B组代码
试题A 煤球数目
#include <iostream>
using namespace std;
int main() {
int a[110];
int s[110];
a[1] = 1;
s[1] = 1;
for (int i = 2; i <= 100; i++) {
a[i] = a[i - 1] + i;
s[i] = a[i] + s[i - 1];
}
printf("%d\n", s[100]);
return 0;
}
答案:171700
试题B 生日蜡烛
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int s[N];
int main() {
for (int i = 1; i <= 100; i++) {
s[i] = i;
s[i] += s[i - 1];
}
for (int i = 1; i < 100; i++)
for (int j = 1; j <= 100; j++)
if ((s[j] - s[i - 1]) == 236)
printf("%d\n", i);
return 0;
}
试题C 凑算式
#include <iostream>
using namespace std;
const int N = 15;
bool st[N];
double a[N];
int res = 0;
void dfs(int u) {
if (u > 9) {
if (a[1] + a[2] / a[3] + (a[4] * 100 + a[5] * 10 + a[6]) / (a[7] * 100 + a[8] * 10 + a[9]) == 10)
res++;
return;
}
for (int i = 1; i <= 9; i++) {
if (!st[i]) {
st[i] = true;
a[u] = i;
dfs(u + 1);
st[i] = false;
}
}
}
int main() {
dfs(1);
printf("%d\n", res);
return 0;
}
试题D 快速排序
#include <stdio.h>
void swap(int a[], int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
int partition(int a[], int p, int r) {
int i = p;
int j = r + 1;
int x = a[p];
while (1) {
while (i < r && a[++i] < x);
while (a[--j] > x);
if (i >= j) break;
swap(a, i, j);
}
swap(a, p, j);
return j;
}
void quicksort(int a[], int p, int r) {
if (p < r) {
int q = partition(a, p, r);
quicksort(a, p, q - 1);
quicksort(a, q + 1, r);
}
}
int main() {
int i;
int a[] = {50, 49, 48, 48, 47, 46, 1, 3, 5, 2, 4, 6, 30, 30, 30, 30};
int N = 16;
quicksort(a, 0, N - 1);
for (i = 0; i < N; i++) printf("%d.", a[i]);
printf("\n");
return 0;
}
试题E 抽签
#include <stdio.h>
#define N 6
#define M 5
#define BUF 1024
void f(int a[], int k, int m, char b[]) {
int i, j;
if (k == N) {
b[M] = 0;
if (m == 0) printf("%s\n", b);
return;
}
for (i = 0; i <= a[k]; i++) {
for (j = 0; j < i; j++) b[M - m + j] = k + 'A';
f(a, k + 1, m - j, b);
}
}
int main() {
int a[N] = {4, 2, 2, 1, 1, 3};
char b[BUF];
f(a, 0, M, b);
return 0;
}
试题F 方格填数
#include <iostream>
#include <algorithm>
using namespace std;
int a[3][4];
int res;
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
bool check() {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 4; j++) {
if (i == 0 && j == 0 || i == 2 && j == 3) continue;
for (int k = 0; k < 8; k++) {
int x = i + dx[k];
int y = j + dy[k];
if (x < 0 || y < 0 || x >= 3 || y >= 4) continue;
if (x == 0 && y == 0 || x == 2 && y == 3) continue;
if (abs(a[i][j] - a[x][y]) == 1) return false;
}
}
}
return true;
}
int main() {
string s = "0123456789";
do {
int t = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 4; j++) {
if (i == 0 && j == 0 || i == 2 && j == 3) continue;
a[i][j] = s[t++] - '0';
}
}
if (check()) res++;
} while (next_permutation(s.begin(), s.end()));
cout << res << endl;
return 0;
}
答案:1580 运行时间:3s
试题G 剪邮票
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int g[3][4];
int res;
int order[12] = {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1};
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void dfs(int x, int y) {
g[x][y] = 0;
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= 3 || b < 0 || b >= 4) continue;
if (g[a][b]) {
dfs(a, b);
}
}
};
bool check() {
for (int i = 0; i < 3; i++)
for (int j = 0; j < 4; j++)
g[i][j] = order[i * 4 + j];
int cnt = 0;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 4; j++) {
if (g[i][j] == 1) {
dfs(i, j);
cnt++;
}
}
return cnt == 1;
}
int main() {
do {
if (check()) res++;
} while (next_permutation(order, order + 12));
printf("%d\n", res);
return 0;
}
试题H 四平方定理
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2500010;
int cnt;
int n;
struct Node {
int a, b, s;
bool operator< (const Node &o) const {
if (s != o.s) return s < o.s;
if (a != o.a) return a < o.a;
return b < o.b;
}
} node[N];
int main() {
scanf("%d", &n);
for (int i = 0; i * i <= n; i++)
for (int j = i; i * i + j * j <= n; j++)
node[cnt++] = {i, j, i * i + j * j};
sort(node, node + cnt);
for (int i = 0; i * i <= n; i++)
for (int j = i; i * i + j * j <= n; j++) {
int t = n - i * i - j * j;
int l = 0, r = cnt - 1;
while (l < r) {
int mid = l + r >> 1;
if (t <= node[mid].s) r = mid;
else l = mid + 1;
}
if (node[l].s == t) {
printf("%d %d %d %d", i, j, node[l].a, node[l].b);
return 0;
}
}
return 0;
}
试题I 交换瓶子
法一: 双重for循环
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10010;
int a[N];
int n;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int res = 0;
for (int i = 0; i < n; i++) {
int min = i;
for (int j = i; j < n; j++)
if (a[j] < a[min]) min = j;
if (min != i) {
swap(a[i], a[min]);
res++;
}
}
printf("%d\n", res);
return 0;
}
法二 置换群
#include <iostream>
using namespace std;
const int N = 10010;
int a[N];
bool st[N];
int n;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
int res = 0;
for (int i = 1; i <= n; i++) {
if (!st[i]) {
res ++;
for (int j = i; !st[j]; j = a[j])
st[j] = true;
}
}
printf("%d\n", n - res);
}