A、组队
作为篮球队教练，你需要从以下名单中选出 1 号位至 5 号位各一名球员，
组成球队的首发阵容。
每位球员担任 1 号位至 5 号位时的评分如下表所示。请你计算首发阵容 1
号位至 5 号位的评分之和最大可能是多少？
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e6 + 7;
int num[25][8];
bool vis[25];
int main() {
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
for (int i = 1; i <= 20; ++i)
for (int j = 0; j <= 5; ++j)
scanf("%d", &num[i][j]);
int ans = -1;
for (int a = 1; a <= 20; ++a) {
vis[a] = 1;
for (int b = 1; b <= 20; ++b) {
if (vis[b]) continue;
vis[b] = 1;
for (int c = 1; c <= 20; ++c) {
if (vis[c]) continue;
vis[c] = 1;
for (int d = 1; d <= 20; ++d) {
if (vis[d]) continue;
vis[d] = 1;
for (int e = 1; e <= 20; ++e) {
if (vis[e]) continue;
ans = max(ans, num[a][1] + num[b][2] + num[c][3] + num[d][4] + num[e][5]);
}
vis[d] = 0;
}
vis[c] = 0;
}
vis[b] = 0;
}
vis[a] = 0;
}
printf("%d\n", ans); //490
return 0;
}
//Plan B
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e6 + 7;
int num[25][8];
bool vis[25];
int a[8];
int ans = -1;
void dfs(int dep) {
if (dep == 6) {
int tmp = 0;
for (int i = 1; i <= 5; ++i)
tmp += num[a[i]][i];
ans = max(ans, tmp);
return;
}
for (int i = 1; i <= 20; ++i) {
if (vis[i]) continue;
vis[i] = 1;
a[dep] = i;
dfs(dep + 1);
vis[i] = 0;
}
}
int main() {
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
for (int i = 1; i <= 20; ++i)
for (int j = 0; j <= 5; ++j)
scanf("%d", &num[i][j]);
dfs(1);
printf("%d\n", ans); //490
return 0;
} B、年号字串
小明用字母 A 对应数字 1，B 对应 2，以此类推，用 Z 对应 26。对于 27
以上的数字，小明用两位或更长位的字符串来对应，例如 AA 对应 27，AB 对
应 28，AZ 对应 52，LQ 对应 329。
请问 2019 对应的字符串是什么？
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e6 + 7;
int main() {
int n = 2019;
while (n) {
int m = n % 26;
putchar('A' + m - 1);
printf("%d\n", m);
n /= 26;
}
// BYQ 2*26*26 + 25*26 + 17 = 2019
return 0;
} C、数列求值
给定数列 1, 1, 1, 3, 5, 9, 17, …，从第 4 项开始，每项都是前 3 项的和。求
第 20190324 项的最后 4 位数字。
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 20190324;
ll a[N + 7];
int main() {
a[1] = a[2] = a[3] = 1;
for (int i = 4; i <= N; ++i)
a[i] = (a[i - 1] + a[i - 2] + a[i - 3])%10000;
cout << a[N] << endl; // 4659
return 0;
} D、数的分解
把 2019 分解成 3 个各不相同的正整数之和，并且要求每个正整数都不包
含数字 2 和 4，一共有多少种不同的分解方法？
注意交换 3 个整数的顺序被视为同一种方法，例如 1000+1001+18 和
1001+1000+18 被视为同一种。
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 20190324;
bool check(int x) {
while (x) {
if (x % 10 == 2 or x % 10 == 4) return false;
x /= 10;
}
return true;
}
int main() {
int cnt = 0;
for (int i = 1; i < 2019; ++i) {
for (int j = i + 1; j + i < 2019; ++j) {
int k = 2019 - i - j;
if (k <= max(i, j)) continue;
if (check(i) and check(j) and check(k)) {
++cnt;
cout << i << ' ' << j << ' ' << k << endl;
}
}
}
cout << cnt << endl; //40785
return 0;
}
E、迷宫
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可
以通行的地方。
010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这
个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫，
一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。
对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式，
其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。
请注意在字典序中D<L<R<U。
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 20190324;
int dir[][2] = { 1,0,0,-1,0,1,-1,0 };
char tmp[] = { 'D','L','R','U' };
char s[35][55];
bool vis[35][55];
string ans[35][55];
struct Node {
int x, y;
};
int main() {
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int n = 30, m = 50;
for (int i = 1; i <= n; ++i)
scanf("%s", s[i] + 1);
queue<Node> q;
q.push({ 1,1 });
vis[1][1] = 1;
while (q.size()) {
Node now = q.front(); q.pop();
int x = now.x, y = now.y;
for (int i = 0; i < 4; ++i) {
int dx = x + dir[i][0], dy = y + dir[i][1];
if (dx <= 0 or dx > n or dy <= 0 or dy > m or vis[dx][dy] or s[dx][dy] == '1')
continue;
ans[dx][dy] = ans[x][y] + tmp[i];
q.push({ dx,dy });
vis[dx][dy] = 1;
if (dx == n and dy == m) {
cout << ans[n][m] << endl;
return 0;
}
}
}
/*
DDDDRRURRRRRRDRRRRDDDLDDRDDDDDD
DDDDDDRDDRRRURRUURRDDDDRDRRRRRR
DRRURRDDDRRRRUURUUUUUUULULLUUUU
RRRRUULLLUUUULLUUULUURRURRURURR
RDDRRRRRDDRRDDLLLDDRRDDRDDLDDDL
LDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
*/
return 0;
} F、特别数的和
小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到
40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。
请问，在 1 到 n 中，所有这样的数的和是多少？
【输入格式】
输入一行包含两个整数 n。
【输出格式】
输出一行，包含一个整数，表示满足条件的数的和。
【样例输入】
40
【样例输出】
574
【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ n ≤ 10。
对于 50% 的评测用例，1 ≤ n ≤ 100。
对于 80% 的评测用例，1 ≤ n ≤ 1000。
对于所有评测用例，1 ≤ n ≤ 10000。
#include <cstdio>
using namespace std;
char s[] = "2019";
bool check(int x) {
while (x) {
int tmp = x % 10;
x /= 10;
for (int i = 0; i < 4; ++i) {
if (tmp == s[i] - '0')
return true;
}
}
return false;
}
int main() {
int n;
scanf("%d", &n);
long long ans = 0; //爆int记得longlong
for (int i = 1; i <= n; ++i) {
if (check(i))
ans += i;
}
printf("%lld\n", ans); // max = 4e9
return 0;
}
G、完全二叉树的权值
#include <cstdio>
#include <algorithm>
using namespace std;
#define pai pair<long long,int>
const int N = 1e5 + 7;
struct Node {
long long val;
int id;
bool operator < (const Node A) const {
if (val != A.val) return val > A.val;
return id < A.id;
}
}p[30];
int main() {
int n;
scanf("%d", &n);
int tmp = 1, dep = 1;
for (int i = 1; i <= n; ++i) {
int x; scanf("%d", &x);
p[dep].val += x;
p[dep].id = dep;
if (i == tmp) {
tmp = tmp << 1 | 1;
++dep;
}
}
sort(p + 1, p + 30);
printf("%d\n", p[1].id);
return 0;
}
H、等差数列
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一
部分的数列，只记得其中 N 个整数。
现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有
几项？
【输入格式】
输入的第一行包含一个整数 N。
第二行包含 N 个整数 A1, A2, · · · , AN。(注意 A1 ∼ AN 并不一定是按等差数
列中的顺序给出)
【输出格式】
输出一个整数表示答案。
【样例输入】
5
2 6 4 10 20
【样例输出】
10
【样例说明】
包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、
18、20。
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一
部分的数列，只记得其中 N 个整数。
现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有
几项？
【输入格式】
输入的第一行包含一个整数 N。
第二行包含 N 个整数 A1, A2, · · · , AN。(注意 A1 ∼ AN 并不一定是按等差数
列中的顺序给出)
【输出格式】
输出一个整数表示答案。
【样例输入】
5
2 6 4 10 20
【样例输出】
10
【样例说明】
包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、
18、20。
【评测用例规模与约定】
对于所有评测用例，2 ≤ N ≤ 100000，0 ≤ Ai ≤ 1e9。
/*
91分
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 7;
int a[N], n;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", a + i);
sort(a + 1, a + 1 + n);
int d = a[2] - a[1];
for (int i = 3; i <= n; ++i)
d = min(d, a[i] - a[i - 1]);
printf("%d\n", (a[n] - a[1]) / d + 1);
return 0;
}
*/
//100分
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 7;
int a[N];
int gcd(int x, int y) {
return y == 0 ? x : gcd(y, x % y);
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", a + i);
sort(a + 1, a + 1 + n);
int d = a[2] - a[1];
for (int i = 3; i <= n; ++i)
d = gcd(d, a[i] - a[i - 1]);
if (d == 0)
printf("%d\n", n);
else
printf("%d\n", (a[n] - a[1]) / d + 1);
return 0;
}
I、后缀表达式
/*
36分
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 7;
int a[N], n, m;
int main() {
long long sum = 0;
int mini = 1e9 + 7;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n + m + 1; ++i) {
scanf("%d", a + i);
sum += a[i];
mini = min(mini, a[i]);
}
printf("%lld\n", sum - 2 * mini); // (a+b+c) - (d-e-f)
return 0;
}
*/
//100分
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e5 + 7;
int a[N];
int main() {
int n, m, cnt = 0, mini = 1e9 + 7;
scanf("%d %d", &n, &m);
long long sum = 0;
for (int i = 1; i <= n + m + 1; ++i) {
scanf("%d", a + i);
sum += a[i];
if (a[i] < 0) ++cnt;
}
if (m == 0)
return printf("%lld\n", sum), 0;
sort(a + 1, a + 1 + n + m + 1);
if (cnt == 0)
sum -= 2 * a[1];
else {
if (cnt == n + m + 1)
sum = -sum, sum += 2 * a[n + m + 1];
else {
for (int i = 1; i <= cnt; ++i)
sum -= 2 * a[i];
}
}
printf("%lld\n", sum);
return 0;
} 
京公网安备 11010502036488号