试题 A: 组队

题意：在给定的20个人中，分别选五个人放到五个不同位置上，使得最后权值最大
暴力就完事了，对 $5$ 个位置进行 $dfs$ ，并在搜索过程中记录最大值即可。~~当然也可以五重循环暴力跑一下~~

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
const int mod = 1000000009;
typedef long long ll;
vector<int> id[7];
bitset<32> vis;
int ans = 0;
void dfs(int s, int value) {
    if(s == 6) {
        ans = max(ans, value);
        return;
    }
    for(int i = 0; i < id[s].size(); ++i) {
        if(!vis[i]) {
            vis[i] = 1;
            dfs(s + 1, value + id[s][i]);
            vis[i] = 0;
        }
    }
}
signed main() {
    for(int i = 1; i <= 20; ++i) {
        int tmp;
        scanf("%d", &tmp);
        for(int j = 1; j <= 5; ++j) {
            scanf("%d", &tmp);
            id[j].push_back(tmp);
        }
    }
    dfs(1, 0);
    cout << ans << endl;//490
    return 0;
}

试题 B: 年号字串

题意：将2019转换成符合题意的字符串
$1$ 对应 $A$ ， $2$ 对应 $B$ ... $AA$ 对应 $26+1$ 。可以看出这是一道进制转换题，不过最低位不是 $0$ ，而是 $1$ ，所以在转换进制时要注意一点
也就是说，它的按权展开为： $n = a_0 + 26a_1+26^2a_2 +\cdots+ 26^na_n$ 。其中： $1\le a_i \le 26$ ，而不是： $0 \le a_i \le 25$

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
const int mod = 1000000009;
typedef long long ll;
signed main() {
    int n;
    cin >> n;
    string s = "";
    while(n) {
        n -= 1;//注意这里
        s += n % 26 + 'A';
        n /= 26;
    }reverse(s.begin(), s.end());
    cout << s << endl;//BYQ
    return 0;
}

试题 C: 数列求值

题意：**求对应数列 $a_{20190324}$ 的最后 $4$ **位
直接递推取余就好，求最后 $4$ 位， $mod = 1e4$

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
const int mod = 10000;
typedef long long ll;
signed main() {
    ll a, b, c;
    a = b = c = 1;
    for(int i = 4; i <= 20190324; ++i) {
        ll tmp = c;
        c = (a + b + c) % mod;
        a = b;
        b = tmp;
    }cout << c << endl;//4659
    return 0;
}

试题 D: 数的分解

题意：将2019分解为三个不同的正整数有多少种方法
很明显的是暴力，但是因为题目说了：分解为三个不同的正整数，并且不计次序
所以设： $i < j < k$ ，就不会有重复计数问题了，然后再跑一边暴力统计即可

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
const int mod = 1000000009;
typedef long long ll;
bool check(int x) {
    bool flag = 0;
    while(x) {
        if(x % 10 == 2 || x % 10 == 4) flag = 1;
        x /= 10;
    }return flag;
}
signed main() {
    ll ans = 0;
    for(int i = 1; i <= 673; ++i) {//673 * 3 = 2019
        if(check(i)) continue;
        for(int j = i + 1; j <= 2019 - i; ++j) {
            if(check(j)) continue;
            for(int k = j + 1; k <= 2019 - i - j; ++k) {
                if(check(k)) continue;
                if(i + j + k == 2019) {
                    ++ans;
                }
            }
        }
    }cout << ans << endl;//40785
    return 0;
}

试题 E: 迷宫

题意：输出最少步数下的最小字典序走法
看到最少步数就应该想到 $bfs$ ，然后又因为是最小的字典序走法，所以走的时候按字典序进行搜索，最后第一个到达终点的就是答案了
记录走法的时候可以开个回溯的数组进行复原步骤，这里就直接全部存下来了

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
const int mod = 1000000009;
typedef long long ll;
char G[64][64];
char step[] = {'D','L','R','U'};
int    dx[] = {1, 0, 0, -1};
int    dy[] = {0, -1, 1, 0};
bitset<64> vis[64];
struct node {
    int x, y;
    string now = "";
};
queue<node> q;
bool check(int x, int y) {
    bool flag = 1;
    if(x > 30 || x < 1) flag = 0;
    if(y > 50 || y < 1) flag = 0;
    if(flag) {
        if(G[x][y] == '1') flag = 0;
    }
    return flag;
}//判断合法性
signed main() {
    for(int i = 1; i <= 30; ++i) {
        for(int j = 1; j <= 50; ++j) {
            int tmp;
            scanf(" %c", &tmp);
            G[i][j] = tmp;
        }
    }
    q.push({1,1,""});
    vis[1][1] = 1;
    while(!q.empty()) {
        int x = q.front().x, y = q.front().y;
        string now = q.front().now;
        if(x == 30 && y == 50) {
            cout << now << endl;
            break;
        }
        q.pop();
        for(int i = 0; i < 4; ++i) {
            int tx = x + dx[i], ty = y + dy[i];
            if(check(tx, ty) && !vis[tx][ty]) {
                vis[tx][ty] = 1;
                q.push({tx, ty, now + step[i]});
            }
        }
    }
    return 0;
}
/*结果为：DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
走了186步
*/

试题 F: 特别数的和

题意：**给定数字 $n$ ，求 $[1,n]$ 中含 $2,1,0,9$ 数位的数字和为多少**
上来先看 $n$ 的范围， $1\le n \le 1e4$ ，数据比较小，加上数位分解的时间也完全够。
所以可以直接暴力，遍历 $i$ ， $1\le i \le n$ ，对 $i$ 进行暴力分解，合法就加，否则继续

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
const int mod = 1000000009;
typedef long long ll;
bool check(int x) {
    bool flag = 0;
    while(x && !flag) {
        int tmp = x % 10;
        if(tmp == 0 || tmp == 1 || tmp == 2 || tmp == 9) flag = 1;
        x /= 10;
    }return flag;
}
signed main() {
    ll ans = 0;
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        if(check(i)) ans += i;
    }cout << ans << endl;
    return 0;
}

试题 G：完全二叉树的权值

题意：给定一颗二叉树，求相同深度的权值和最大的深度编号，如果有多个，输出最小的深度
思路：对每一深度进行放入数组统计，排序可得最大权值和。并且值得注意的是有多个相同权值时，输出最小的深度。这里的处理是将其深度编号记录下来，但是如果不做任何改变就是求到了最大深度。所以需要将深度编号取反，才能在排序后将最小深度找到
并且二叉树的每一层有的节点数为： $2^{depth - 1}$ ，此处 $depth$ 依题意从 $1$ 开始

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
const int mod = 1000000009;
typedef long long ll;
int n, tot = 0;
pair<ll,int> arr[64];
signed main() {
    scanf("%d", &n);
    int cnt = 1;//记录目前输入的个数
    while(cnt <= n) {
        ll value = 0;
        for(int i = 1; i <= (1 << tot) &&  cnt <= n; ++i) {
            int tmp;
            scanf("%d", &tmp);
            value += tmp;
            ++cnt;
        }
        ++tot;//深度编号
        arr[tot].first  = value;
        arr[tot].second = -tot;//取编号最小的
    }
    sort(arr + 1, arr + 1 + tot);
    cout << -arr[tot].second << endl;
    return 0;
}

试题 H: 等差数列

题意：**给定长度为 $n$ 的数列，为一个等差数列的一部分。要使得等差数列项数最小，求出最小值**
假设给定的数列为： $a_1, a_2, a_3, \cdots, a_n$ 。并且设 $a_n$ 单增
我们要使得包含这些数的等差数列项数最小，就要使其公差尽可能的大，并且要包含所有的数字
所以数列可变形为： $a_1, a_1 + k_1 d , a_1 + k_2 d,\cdots, a_1 + k_{n-1} d$ 。其中 $k_i$ 为常数，设： $b_i = a_{i+1} - a_i$
即： $b_1 = k_1 d, b_2 = k_2 d,\cdots,b_{n-1} = k_{n-1} d$ 。我们要使公差尽可能大，那么 $k_i$ 就要尽可能小，也就是说，对于 $b_{n-1}$ 而言，我们要求出一个最大的 $d$ ，使得它在所有 $b_i$ 中都能分解出来。那么毫无疑问： $d = gcd(b_1,b_2,\cdots, b_{n-1})$
求出最大公差之后，由于 $a_n = a_1 + (n-1)d$ ，那么可得： $n = \frac {a_n - a_1} {d} + 1$
但是要注意一点： $d$ 有可能为 $0$ 的情况（即为 $0$ 常数列），不能套上面的公式，此时最大项数就为 $n$

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
const int mod = 1000000009;
typedef long long ll;
ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);}
int n;
ll a[N], b[N];
signed main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%lld", a + i);
    sort(a + 1, a + 1 + n);
    for(int i = 2; i <= n; ++i) b[i] = a[i] - a[i-1];
    ll d = b[2];
    for(int i = 2; i <= n; ++i) d = gcd(d, b[i]);
    if(d) cout << (a[n] - a[1]) / d + 1 << endl;
    else  cout << n << endl;
    return 0;
}

试题 I: 后缀表达式

题意：**给定 $N$ 个加号， $M$ 个减号， $N+M+1$ 个数字，求最后运算结果的最大值**
我们知道，任意一个后缀表达式都可以与相应的带括号的中缀表达式相互转换。所以题目意思也就是说：求在带括号的中缀表达式下，最后运算结果的最大值。
首先，只要存在一个减号，就可以依靠：这种式子，将其转换为有且仅有一个减号的情况，并且可以拓展到存在任意个减号的情况。此时，可以看出与负数的数量相关性较大，所以我们来讨论一下（设负数数量为：）
- $ne \le M$ 时，所有的负数都可以转换为正数，并且所有多余的减号都可以依靠上述做法转换为正号。
- $ne > M$ 时，所有的负数也都可以由上述式子转换为正数。
- 但是负号最少只有一个，当所有的数均为非负数时，必须减去一个最小的数，才能使得最后的结果最大
- 并且可以看到，我们默认了 $a_k$ 为非负值，但如果所有的值均为负数时， $a_k < 0$ ，那么 $a_k$ 为负无法改变，但其余的负数均可以改为正数。所以，直接选取当前序列中的最大值作为 $a_k$ 进行运算
反正，如果没有任何一个减号，则整个式子不论何种运算顺序，结果都是固定的。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
const int mod = 1000000009;
typedef long long ll;
ll a[N], n, m;
signed main() {
    scanf("%lld%lld", &n, &m);
    ll ne = 0;//统计负数个数
    for(int i = 1; i <= n + m + 1; ++i) {
        scanf("%lld", a + i);
        if(a[i] < 0) ++ne;
    }
    sort(a + 1, a + 1 + n + m + 1);
    ll ans = 0;
    if(m) {
        ans = a[n + m + 1] - a[1];//选取当前最大值作为a_k
        for(int i = 2; i < n + m + 1; ++i) ans += abs(a[i]);
    }else {
        for(int i = 1; i <= n + m + 1; ++i) ans += a[i];
    }
    cout << ans << endl;
    return 0;
}

试题 J: 灵能传输

题意：**给定序列，可以任意的在非头尾处选择任意多次进行传输，最后使得 $max_{i=1}^{n} |a_i|$ 最小**
~~阴间题目~~。可以看出，传输操作较为复杂，并且在传输过程中，总和不变。所以我们考虑转换为和的方向去看。
假设序列为： $a_1, a_2, a_3 ,\cdots, a_{i-1}, a_i, a_{i+1}, \cdots, a_{n-1}, a_n$ 。
如果对 $a_i$ 进行操作，则原序列变为： $a_1,a_2, a_3 ,\cdots, a_{i-1} + a_i, -a_i, a_{i+1} + a_i, \cdots, a_{n-1}, a_n$ 。
则前缀和变成了： $s_1, s_2, s_3, \cdots, s_i, s _{i-1}, s_{i+1}, \cdots, s_n$ ，可以看出传输操作仅对 $s_{i-1},s_{i}$ 进行了对换，比原来的传输操作更好操作。
所以题目就转换为了：**任意交换 $s_i,s_j$ 其中 $1\le i < j \le n-1$ ，任意多次。使得最后的序列中 $max_{i=1}^n |s_i - s_{i-1}|$ 最小**
题目中，仅有 $s_n$ 不能移动，加入 $s_0 = 0$ 使得其同样不能移动，使得前缀和满足通式，且形成对称结构。

对于 $s_0, s_n$ 而言，可以任选一个作为起始，另一个作为终止位置，对题目没有任何影响。然后对前缀和的大小进行排序

假设： $s_0 \le s_n$ 。并且先将 $s_0, s_n$ 填入起始、终止位置。

从 $1$ 开始，填入比 $s_0$ 小的元素。从 $n-1$ 开始，填入比 $s_n$ 大的数。最后再将二者由剩余元素衔接起来。并且在填入的基础上要使得相邻元素的差值的绝对值最小

那么如何使得其成立呢？可以看出，我们先处理了最值部分，在衔接时，我们需要在填入前预留一个数字，使得最值形成的谷、峰尽可能的对称。则谷、峰两侧相应位置的元素必然是相邻元素，这样才能使得两侧的差值不过大。
那么选取方法也就出来了：对于 $< s_0$ 和 $> s_n$ 的元素，隔一个取一个，并且分别在头、尾插入。然后标记哪些元素被选取，哪些未被选取，最后由小到大将头尾衔接起来即可
最后对生成的序列跑一遍，取最大值即可

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
const int mod = 1000000009;
typedef long long ll;
ll n, t;
ll prefix[N], tmp[N];
bitset<N> vis;
signed main() {
    scanf("%lld", &t);
    while(t--) {
        memset(prefix, 0, sizeof(ll) * (n + 1));
        memset(tmp   , 0, sizeof(ll) * (n + 1));
        vis.reset();
        scanf("%lld", &n);
        for(int i = 1; i <= n; ++i) scanf("%lld", &prefix[i]);
        for(int i = 1; i <= n; ++i) prefix[i] += prefix[i-1];
        ll ans = 0, sn = prefix[n], s0 = 0;
        sort(prefix, prefix + 1 + n);
        if(sn < s0) swap(sn, s0);
        int l = 0, r = n;//头、尾指针
        for(int i = lower_bound(prefix, prefix + 1 + n, s0) - prefix; i >= 0; i -= 2) tmp[l++] = prefix[i], vis[i] = 1;//< s_0
        for(int i = lower_bound(prefix, prefix + 1 + n, sn) - prefix; i <= n; i += 2) tmp[r--] = prefix[i], vis[i] = 1;//> s_n
        for(int i = 0; i <= n; ++i) {
            if(!vis[i]) tmp[l++] = prefix[i];//衔接
        }
        for(int i = 1; i <= n; ++i) {
            ans = max(ans, abs(tmp[i] - tmp[i-1]));
        }
        cout << ans << endl;
    }
    return 0;
}

第十届蓝桥杯C/C++ B组 —— 2019

试题 A: 组队

试题 B: 年号字串

试题 C: 数列求值

试题 D: 数的分解

试题 E: 迷宫

试题 F: 特别数的和

试题 G：完全二叉树的权值

试题 H: 等差数列

试题 I: 后缀表达式

试题 J: 灵能传输