A.婴儿学数

答案：2159

ACcode1(暴力）

时间复杂度 $O(cnt^4)$ ， $cnt$ 表示2、0、5的总个数

#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    string s;
    cin >> s;
    int n = s.size();
    vector<int> v;
    for(int i = 0; i < n; i++){
        if(s[i] == 'y'){
            // v.push_back(1);
            i++;
        }
        else if(s[i] == 'e'){
            v.push_back(2);
            i++;
        }
        else if(s[i] == 's'){
            if(s[i + 1] == 'a'){
                // v.push_back(3);
                i += 2;
            }
            else{
                // v.push_back(4);
                i++;
            }
        }
        else if(s[i] == 'w'){
            v.push_back(5);
            i++;
        }
        else if(s[i] == 'l'){
            if(s[i + 2] == 'u'){
                // v.push_back(6);
                i += 2;
            }
            else{
                v.push_back(0);
                i += 3;
            }
        }   
        else if(s[i] == 'q'){
            // v.push_back(7);
            i++;
        }
        else if(s[i] == 'b'){
            // v.push_back(8);
            i++;
        }
        else{
            // v.push_back(9);
            i += 2;
        }
    }
    int m = v.size();
    int cnt = 0;
    // for(int i = 0; i < m; i++) cout << v[i];
    for(int i = 0; i < m; i++){
        for(int j = i + 1; j < m; j++){
            for(int k = j + 1; k < m; k++){
                for(int l = k + 1; l < m; l++){
                    if(v[i] == 2 && v[j] == 0 && v[k] == 2 && v[l] == 5) cnt++;
                }
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

ACcode2(动态规划)

时间复杂度: $O(n)$

#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    string s;
    cin >> s;
    int n = s.size();
    vector<int> v;
    for(int i = 0; i < n; i++){
        if(s[i] == 'y'){
            v.push_back(1);
            i++;
        }
        else if(s[i] == 'e'){
            v.push_back(2);
            i++;
        }
        else if(s[i] == 's'){
            if(s[i + 1] == 'a'){
                v.push_back(3);
                i += 2;
            }
            else{
                v.push_back(4);
                i++;
            }
        }
        else if(s[i] == 'w'){
            v.push_back(5);
            i++;
        }
        else if(s[i] == 'l'){
            if(s[i + 2] == 'u'){
                v.push_back(6);
                i += 2;
            }
            else{
                v.push_back(0);
                i += 3;
            }
        }   
        else if(s[i] == 'q'){
            v.push_back(7);
            i++;
        }
        else if(s[i] == 'b'){
            v.push_back(8);
            i++;
        }
        else{
            v.push_back(9);
            i += 2;
        }
    }
    int m = v.size();
    int cnt2 = 0, cnt20 = 0, cnt202 = 0, cnt2025 = 0;
    for(int i = 0; i < m; i++){
        if(v[i] == 2){
            cnt202 += cnt20;
            cnt2++;
        }
        if(v[i] == 0) cnt20 += cnt2;
        if(v[i] == 5) cnt2025 += cnt202;
    } 
    cout << cnt2025 << endl;
    return 0;
}

B.数列之和

答案：1996488764

这题很容易认为第 $n$ 个数就是 $4n - 2$ ，但手搓几组数发现没有那么简单，所以用高中的数学知识计算一下。

根据高中的数学知识可以算出第 $l$ 个数到第 $r$ 个数的和是 $sum = \frac {a_l +a_r}2(r-l+1)=(r+l-2)(r-l+1)$

让我们从奇偶性的角度来分析这个式子：若 $l, r$ 都为奇数或都为偶数，则第一项为偶数，第二项为奇数；若 $l, r$ 一个是奇数一个是偶数，则第一项为奇数，第二项为偶数。即 $sum$ 总是一个奇数乘以偶数。

哪些数字不能分解成奇数乘以偶数的形式？形如 $2^p$ 的整数都不可以。唯一一个例外是 $2=1\times2$ ，因为此时奇数可以取 $1$ （这对应了 $r - l + 1 = 1$ ），可以验证其它 $2^p$ 都不能像这样拆成 $2^p$ 和 1 相乘。

综上，结论是：除了形如 $2^p \ (p > 1)$ 的整数不能表示，其他数字都可以表示。

问题也就转换成了找第 $n$ 个非 $2^p(p>1)$ 形式的偶数，写法很多，可以推公式，可以打表找规律，也可以二分答案。

这题打表按题意把前几十几百个数找出来，是很容易能看出来不符合 $4n-2$ 的位置和 $2^p$ 有关的

ACcode1：二分答案

$x$ - (不超过 $x$ 的 $2^p (p>1)$ 数) $\le$ （输入的 $k$ ）

#include <iostream>
#define endl '\n'
using namespace std;
using LL = long long;

int n;

bool check(LL mid){
    LL x = 4;
    LL cnt = 0;
    while(x <= mid){
        cnt++;
        x *= 2;
    }
    return mid / 2 - cnt >= n;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    LL l = 1, r = 3e18;
    while(l < r){
        LL mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
}

ACcode2

#include <iostream>
#define endl '\n'
using namespace std;
using LL = long long;

LL n;

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    n *= 2;
    for(LL i = 4; i <= n; i *= 2){
        if(n >= i) n += 2;
    }
    cout << n << endl;
}

ACcode3

#include <iostream>
#define endl '\n'
using namespace std;
using LL = long long;

int n;

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    if (n == 1) cout << 2 << endl;
    else{
        int y = 1, i = 1;
        while (i < n){
            i += pow(2, y) - 1;
            y++;
        }
        cout << n * 2 + (y - 1) * 2 << endl;
    }
    cout << l << endl;
}

C.简单题

对于一个偶数 $n$ ，他一定能除 $2$ ，一直将其除 $2$ ，除到不能除时 $n$ 一定是个奇数，就是要求的底数 $o$ ，除 $2$ 的次数就是指数 $p$
对于一个奇数 $n$ ，其本身就等于 $o$ ，无法除 $2$ ， $p=0$ ，不满足条件，一定输出 $-1$

时间复杂度 $O(logn)$

ACcode

#include <iostream>
#define endl '\n'
using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    int cnt = 0;
    while(n % 2 == 0){
        n /= 2;
        cnt++;
    }
    if(cnt != 0) cout << n << ' ' << cnt << endl;
    else cout << -1 << endl;
    return 0;
}

D.最小好进制

暴力骗分Code

暴力的话， $k$ 进制只有从 $2$ ~ $n-1$ 这几种可能，那就从 $2$ ~ $n-1$ 遍历一下 $k$ ，判断一下当前进制是不是好进制，因为答案要最小的好进制，所以第一个好进制就是答案，直接输出即可。

判断是不是好进制只需要把 $n$ 表示成它的 $k$ 进制，将每一位一一取出看是不是 $1$ 即可，取位的过程就是用 $while$ 循环，每次让 $t = n\%k$ ,再 $n/=k$ 即可， $t$ 就是 $k$ 进制的每一位。

时间复杂度：最坏 $O(n * logn)$

#include <iostream>
#define endl '\n'
using namespace std;
using LL = long long;

bool is_good(LL n, LL k){ // 看k是不是n的好进制：看k进制下n是不是每一位都是1
	while(n){
		if(n % k != 1) return false;
		n /= k;
	}
	return true;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	LL n;
	cin >> n;
	if(n == 1){
		cout << 2 << endl;
		return 0;
	}
	for(LL i = 2; i < n; i++){
		if(is_good(n, i)){
			cout << i << endl;
			return 0;
		}
	}
	return 0;
}

ACcode：二分答案 + 进制转换

$10^{18}$ 对应的二进制是 57 位。即 $n$ 取到最大， $k$ 取到最小，所得 $k$ 进制序列也就是 57 位。

$k$ 越小，相当于所得 $k$ 进制序列越长。因此可以倒序枚举最终序列的长度 $len$ ，问：是否有某个进制 $k$ ，使得最终序列为 $len$ 个 1，若存在，则返回找到的 $k$ ，若不存在，则 $len$ 自减后继续询问，直至 $len = 1$ ;

问题转化成了：给定十进制数 $n$ ，和 $len$ ，问是否有某个 $k$ ，将 $n$ 转成 $k$ 进制后为 $len$ 个 1，记为 $t$ 。

二分 $k$ ，通过进制转换算法求出 $n$ 的 $k$ 进制序列 $y$

$y = t$ : 找到答案 $k$ ，因为全为1的 $k$ 进制序列是唯一的，直接返回答案即可。 $y > t$ : 进制数 $k$ 选小了， $l = mid + 1$ $y < t$ : 进制数 $k$ 选大了， $r = mid - 1$

但两个 $k$ 进制数 $y$ 和 $t$ 比较大小不好实现，所以可以逆向思维：将 $k$ 进制的 $t$ 转换为 10 进制得到 $z$ ，然后与 $n$ 比较。

$z = n$ : 找到答案 $k$
$z > n$ : 进制数 $k$ 选大了， $r = mid - 1$
$z < n$ : 进制数 $k$ 选小了， $l = mid + 1$

数据范围比较大，需要加一些特判防止越界(简单点说就是知道在某一步 $sum$ 会超过 $n$ 就直接返回)

时间复杂度： $O\left( \sum_{len=2}^{60} len \cdot \log n \right) = O(1829logn)$

#include <iostream>
#include <cmath>
#define endl '\n'
using namespace std;
using LL = long long;

int check(LL n, LL k, LL len){ // 进制转换函数，看k进制下len个1转换成10进制和n相等不相等
    LL sum = 0;
    LL p = 1;
    for(int i = 0; i < len; i++){
        sum += p;
        if(sum > n) return 0; // 大于n就直接返回，不继续往下算了，防止越界
        if(i < len - 1){
            if(p > n / k) return 0; // p * k > n就不继续乘了，防止越界，
            p *= k;
        }
    }
    if(sum == n) return 1; 
    return 2;
} // 0:进制数大了 1:进制数刚好 2:进制数小了

LL get(LL n, LL len){ // 能不能找到k进制下:n是len个1
	LL l = 2;
	LL r = n - 1;
	while(l <= r){ // 二分从2 ~ n - 1找k
		LL mid = l + r >> 1;
		int t = check(n, mid, len);
		if(t == 0) r = mid - 1; // k大了
		else if(t == 1) return mid; // 如果找到了就直接把进制k返回
		else l = mid + 1; // k小了
	}
	return -1; // 找不到就返回-1
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	LL n;
	cin >> n;
	if(n == 1){
		cout << 2 << endl;
		return 0;
	}
	for(int i = 60; i >= 2; i--){ // 位数越大，满足条件的进制数就越小，倒序枚举
		LL k = get(n, i);
		if(k != -1){
            cout << k << endl; // 第一次找到的好进制k一定是最小的
            return 0;
        } 
	}
	return 0;
}

这题还有用数学的二项式定理等定理推公式的解法，过程比较繁琐，感兴趣可以去自己查。

E.分配宝藏

暴力Code1 -> next_permutation

暴力枚举数组下标 $0$ ~ $n-1$ 的全排列作为队伍的排列顺序，按题意按顺序计算每种排列顺序的答案，取最小值即可。

时间复杂度： $O(n!)$

#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;
using LL = long long;
const int N = 25;

struct Node{
	int l, r;
}p[N];

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	int ll, rr;
	cin >> ll >> rr;
	for(int i = 0; i < n; i++){
		cin >> p[i].l >> p[i].r;
	}
	LL ans = 1e18;
	int idx[N];
	for(int i = 0; i < n; i++) idx[i] = i;
	do{
		LL sum = ll;
		LL res = 0;
		for(int i = 0; i < n; i++){
			res = max(res, sum / p[idx[i]].r);
			sum *= p[idx[i]].l;
		}
		ans = min(ans, res);
	}while(next_permutation(idx, idx + n));
	cout << ans << endl;
	return 0;
}

暴力Code2 -> dfs排列型枚举

同上，就是将 $next\_permutation$ 求全排列换成了 $dfs$ 求全排列

时间复杂度： $O(n!)$

#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;
using LL = long long;
const int N = 25;

struct Node{
	int l, r;
}p[N];

LL ans;
int idx[N];
bool st[N];
int n, ll, rr;

void dfs(int x){
	if(x > n){
		LL sum = ll;
		LL res = 0;
		for(int i = 1; i <= n; i++){
			res = max(res, sum / p[idx[i]].r);
			sum *= p[idx[i]].l;
		}
		ans = min(ans, res);
		return;
	}
	for(int i = 0; i < n; i++){
		if(!st[i]){
			idx[x] = i;
			st[i] = true;
			dfs(x + 1);
			idx[x] = 0;
			st[i] = false;
		}
	}
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	cin >> ll >> rr;
	for(int i = 0; i < n; i++){
		cin >> p[i].l >> p[i].r;
	}
	ans = 1e18;
	dfs(1);
	cout << ans << endl;
	return 0;
}

ACcode:贪心

贪心，设左手上的数字是 $a$ ,右手上的数字是 $b$ ，结论是：将所有水手按 $a\times b$ 从小到大排序，就是最终顺序。

时间复杂度: $O(n)$

#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;
using LL = long long;
const int N = 25;

struct Node{
	int l, r;
}p[N];

bool cmp(Node a, Node b){
	return a.l * a.r < b.l * b.r;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	int ll, rr;
	cin >> ll >> rr;
	for(int i = 0; i < n; i++){
		cin >> p[i].l >> p[i].r;
	}
	sort(p, p + n, cmp);
	LL sum = ll;
	LL res = 0;
	for(int i = 0; i < n; i++){
		res = max(res, sum / p[i].r);
		sum *= p[i].l;
	}
	cout << res << endl;
	return 0;
}

简单好理解的证明：

我们考虑两个大臣 $p1,p2$ ，它们站在国王 $p0$ 的身后，则这两个大臣有两种排列方案：

person	left	right
p0	a0	b0
p1	a1	b1
p2	a2	b2

person	left	right
p0	a0	b0
p2	a2	b2
p1	a1	b1

对于第一种情况，答案 $ans_1 = \max \left( \frac{a_0}{b_1}, \frac{a_0 a_1}{b_2} \right)$

对于第二种情况，答案 $ans_2 = \max \left( \frac{a_0}{b_2}, \frac{a_0 a_2}{b_1} \right)$

显然，
$\frac{a_0 a_1}{b_2} > \frac{a_0}{b_2}, \quad \frac{a_0 a_2}{b_1} > \frac{a_0}{b_1}$

若 $ans_1 < ans_2$ , $\because \frac{a_0 a_2}{b_1} > \frac{a_0}{b_1}, \therefore \frac{a_0 a_2}{b_1}$ 必须 $> \frac{a_0 a_1}{b_2}$

即 $\frac{a_2}{b_1} > \frac{a_1}{b_2}$ 即 $a_1 b_1 < a_2 b_2$

因此，若 $a_1 b_1 < a_2 b_2$ ，就有 $p_1$ 排在 $p_2$ 前更优。

严密的证明：

我们先来证明

对任意相邻两项，其依照二者 $a, b$ 之积升序排列所得的结果小于等于降序排列所得的结果( $\sigma$ )

不妨设现有水手 $i, i+1$

设在第1到 $i-1$ 位中的最大值为 $maximum$ ，则

第1到第 $i+1$ 位中的最大值 $\alpha$ 为

$max(maximum, \frac{\prod_{j=0}^{i-1} a_j}{b_i}, \frac{\prod_{j=0}^{i-1} a_j}{b_{i+1}})$

（设 $r = \frac{\prod_{j=0}^{i-1} a_j}{b_i}$ ， $s = \frac{\prod_{j=0}^{i-1} a_j}{b_{i+1}}$ ）

要使得 $\alpha$ 小于 $i$ 与 $i+1$ 交换后的最大值 $\beta$ , 当且仅当 $\beta = max(maximum, \frac{\prod_{j=0}^{i-1} a_j}{b_{i+1}}, \frac{\prod_{j=0}^{i-1} a_j}{b_{i}\times a_i}) < \alpha$

（设 $t = \frac{\prod_{j=0}^{i-1} a_j}{b_{i+1}}$ ， $u = \frac{\prod_{j=0}^{i-1} a_j}{b_{i}\times a_i}$ ）

若 $maximum = \alpha$ , 则显然有欲达到之效果

否则：

$\therefore \prod_{p=0}^{i-1} a_p < \prod_{p=0}^{i} a_p$

$\therefore s > t$

若 $\alpha = s, \beta = t$ , 则可达到欲达到之效果

$\therefore \frac{\prod_{j=0}^{i-1} a_j}{a_i} < \prod_{p=0}^{i+1} a_p$

$\therefore u > r$

若 $\alpha = r$ , 则不可能达到欲达到之效果

$\therefore \alpha$ 只可能等于 $s$

又：当 $\alpha = s, \beta = t$ , 可达到欲达到之效果

$\therefore \alpha < \beta \iff s < u \iff \frac{\prod_{j=0}^{i-1} a_j}{b_{i+1}} < \frac{\prod_{j=0}^{i-1} a_j}{b_{i}\times a_i}\iff \frac{1}{b_{i+1}} < \frac{a_{i+1}}{a_i \times b_i} \iff a_i \times b_i < a_{i+1} \times b_{i+1}$

又： $i+1$ 位之后的情况与 $i, i+1$ 的排列方式无关

故 ( $\sigma$ ) 得证

接下来我们证明要使前 $n$ 项奖励的最大值最小，必有对于所有第 $i$ 项 ( $i \in [1, n] \bigcap N$ ) 依据 $a_i \times b_i$ 排序

先看一个引理( $\ast$ ):

若长度为 $s$ 的数列不是一个不严格单调递增序列, 则必存在 $i \in [1, s] \bigcap N$ 使得 $r_i > r_{i+1}$

证明如下：

若不存在这样的规则:

对于任意 $m_1, m_2 \in [1, s] \bigcap N$ , 当 $m_1 < m_2$ 时，有 $r_{m_1} \leq r_{m_1+1} \leq ... \leq r_{m_2}$

$\therefore r$ 是一个不严格单调递增序列(矛盾)

故引理( $\ast$ ) 得证

若前 $n$ 项没有依照 $a_i \times b_i$ 排序, 且入取到最小值, 则:

由( $\ast$ ), 必有 $q_1 \in [1, n] \bigcap N, q_2 = q_1 + 1 st$ .

$a_{q_1} \times b_{q_1} > a_{q_2} \times b_{q_2}$

由( $\sigma$ ), 交换 $q_1, q_2$ 的位置所得到的 $N$ ＜现有的 (矛盾)

故命题得证。

F.魔法迷宫

只要部分分Code：bfs模板

$bfs$ 走迷宫的模板，不会写就多练

时间复杂度： $O(nm)$

#include <iostream>
#include <cstring>
#include <queue>
#define endl '\n'
using namespace std;
using LL = long long;
typedef pair<int, int> PII;
const int N = 1005;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int n, m, k;
char p[N][N];
int dist[N][N];

int bfs(){
    memset(dist, -1, sizeof dist);
    queue<PII> q;
    dist[1][1] = 0;
    q.push({1, 1});
    while(!q.empty()){
        auto t = q.front();
        q.pop();
        for(int i = 0; i < 4; i++){
            int a = t.first + dx[i], b = t.second + dy[i];
            if(a <= 0 || b <= 0 || a > n || b > m) continue;
            if(p[a][b] != '.') continue;
            if(dist[a][b] >= 0) continue;
            dist[a][b] = dist[t.first][t.second] + 1;
            if(a == n && b == m) return dist[a][b];
            q.push({a, b});
        }
    }
    return -1;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> p[i][j];
        }
    }
    cout << bfs() << endl;
    return 0;
}

ACcode：多维bfs

就是在原来 $bfs$ 的基础上加了几维状态，需要记录当前的 $x$ 、 $y$ 坐标、禁止移动的方向、当前用没用魔法、当前的步数，可以用一个结构体来表示。

虽然题中说魔法只能在起点用，但你在起点是不知道哪个墙在你的最短路上的。所以可以在起点先决定用不用魔法，用的话就禁用一个方向，把四种状态入队；不用的话就不禁用，再把不用的状态入队，然后 $bfs$ 遍历能走到的每一个点，如果当前点是空地就直接走，如果是障碍就判断在起点选择用不用魔法，如果不用就走不了，直接跳过这个位置；如果选择用就再看一下当前摧毁没摧毁过方块，如果已经摧毁过了，就直接跳过；如果没摧毁过，可以直接跳过，也可以摧毁这个方块并走到这个方块，把新的状态（到这个点、用魔法、并且已经摧毁过方块了）入队，一直这样走下去，到终点了就返回步数即可。

if(不用魔法){
    if(当前格子是'.') 走;
    else continue;
}

else{
    if(当前格子是'.') 走;
    else{
        if(摧毁过方块) continue;
        else{
            1.摧毁;
            2.不摧毁, continue;
        }
    }
}

还有一个处理的技巧（下面的代码没用，可以自己尝试一下），对于所有情况我们可以直接视其用魔法，不用魔法的情况就是摧毁不了格子，在起点直接将其已经摧毁过障碍并且不禁用方向的状态入队即可，这样状态表示就可以减少一维。

时间复杂度： $O(nm)$

#include <iostream>
#include <cstring>
#include <queue>
#define endl '\n'
using namespace std;
using LL = long long;
typedef pair<int, int> PII;
const int N = 1005;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int n, m, k;
char p[N][N]; // 存地图
bool st[N][N][2][5]; // 判断当前状态到没到过：st[x][y][摧毁没摧毁过障碍][禁用的方向]

struct Node{
    int x, y, dis, ban, used; // x, y, dis:到当前状态的步数, ban:禁用的方向(0,1,2,3表示上右下左，4表示不禁用), used:摧毁没摧毁过障碍(0:没摧毁过; 1:摧毁过)
};

int bfs(){
    memset(st, false, sizeof st);
    queue<Node> q;
    if(k == 0){ // 不让用魔法
        q.push({1, 1, 0, 4, 1}); // (1, 1), dis=0, 不禁用方向,已经摧毁过障碍
        st[1][1][0][4] = true;
    }
    else{ // 让用魔法
        for(int i = 0; i < 5;i++){ // 用魔法，遍历禁用的四个方向/用魔法
            q.push({1, 1, 0, i, 0});// (1, 1), dis=0, 禁用i方向, 没摧毁过障碍
            st[1][1][0][i] = true;
        }
    }
    while(!q.empty()){
        auto t = q.front();
        q.pop();
        int x = t.x, y = t.y, dis = t.dis, ban = t.ban, used = t.used;
        if(x == n && y == m) return dis; // bfs第一次走到终点就是最优解，直接返回
        for(int i = 0; i < 4; i++){ // 向上右下左走
            if(i == ban) continue;
            int a = x + dx[i], b = y + dy[i];
            if(a <= 0 || b <= 0 || a > n || b > m) continue; // 越界
            if(p[a][b] == '.'){ // 如果是空地就走
                if(st[a][b][used][ban]) continue; // 以这个状态走过了
                st[a][b][used][ban] = true;
                q.push({a, b, dis + 1, ban, used}); // dis + 1,其他不变
            }
            else{ // 如果是障碍，摧毁他
                if(ban == 4) continue; // 不用魔法就直接跳过
                if(used) continue; // 摧毁过障碍了也跳过
                if(st[a][b][1][ban]) continue; // 当前状态走过了也跳过
                st[a][b][1][ban] = true; 
                q.push({a, b, dis + 1, ban, 1}); // dis + 1, 过魔法
            }
        }
    }
    return -1; // 到不了(n, m)就返回-1
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> p[i][j];
        }
    }
    cout << bfs() << endl;
    return 0;
}

G.算数城的难题

暴力骗分Code

四重 $for$ 循环枚举题目序列的所有的子数组和每个子数组的子数组（枚举左右端点），如果当前子数组的子数组的和为 $0$ ，当前子数组就不是好数组，直接 $break$ 看下一个子数组，如果当前子数组的所有子数组的和都不为 $0$ ,当前子数组就是好数组，就给答案 $+1$ ，区间和用前缀和处理。

时间复杂度： $O(n^4)$

#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;
using LL = long long;
const int N = 2e5 + 10;

int n;
LL pre[N];

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        pre[i] = pre[i - 1] + x;
    }
    int cnt = 0;
    for(int l = 1; l <= n; l++){ // 子数组的左端点
        for(int r = l; r <= n; r++){ // 子数组的右端点
            bool flag = false;
            for(int i = l; i <= r; i++){ // 子数组的子数组的左端点
                for(int j = i; j <= r; j++){ // 字数组的子数组的右端点
                    if(pre[j] - pre[i - 1] == 0){
                        flag = true;
                        break;
                    }
                }
                if(flag) break;
            }
            if(!flag) cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

ACcode：双指针+前缀和。

这个问题其实就是找每个子数组的区间和都不为0的子数组个数，也就是对于一个子数组的每个子数组 $[l$ ~ $r]$ ，都不存在 $pre[r] - pre[l - 1]=0$ ,也就是 $pre[r] \neq pre[l - 1]$ ，由此看出一个数组是好数组的充要条件是其对应的前缀和序列中没有重复值，也就是对于子数组 $[l,r]$ 来说，其对应的前缀和序列：

$pre[l - 1], pre[l], pre[l + 1], ..., pre[r - 1], pre[r]$ 都互不相同。

可以用双指针和 $set$ 或 $map$ 来动态地维护当前区间内的前缀和是否有重复。

每次固定左端点 $l$ 后，尝试尽可能向右扩展窗口，即增大 $r$ 的值。

如果 $pre[r + 1]$ 不在集合中，就可以向右拓展区间( $r++$ )，并将 $pre[r + 1]$ 加入集合

如果 $pre[r + 1]$ 在集合中，就要左端点右移收缩窗口( $l++$ )，并将 $pre[l]$ 从集合中删除，这个时候，对于当前的左端点，有 $r - l$ 个满足条件的右端点，所以 $res += r - l$

时间复杂度: $O(nlogn)$

#include <iostream>
#include <cstring>
#include <queue>
#include <set>
#define endl '\n'
using namespace std;
using LL = long long;
using namespace std;
const int N = 2e5 + 10;

LL pre[N];

int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        int x; 
        cin >> x;
        pre[i] = pre[i - 1] + x;
    }
    LL res = 0;
    set<LL> s = {0};
    for(int l = 0, r = 0; l < n; l++){
        while(r < n && !s.count(pre[r + 1])){
            r++;
            s.insert(pre[r]);
        }
        res += r - l;
        s.erase(pre[l]);
    }
    cout << res << endl;
}

H.神秘数列的密码

暴力骗分Code1：最纯粹的暴力

首先你要知道一个小学数学的结论: $lcm(a, b) = \frac{a \times b} {gcd(a, b)}$

还有 $lcm(a, b, c) = lcm(lcm(a, b), c)$

然后就可以用四重 $for$ 循环去枚举所有的 $(a, b,c, d)$ 四元组，判断每一个是不是满足 $lcm(a, b, c) = d$ 了

时间复杂度： $O(n^4logM)$ , $M$ 为所有数的最大值

#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;
using LL = long long;

LL lcm(LL a, LL b) {
    return a / __gcd(a, b) * b;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n;
    int a[1010];
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    LL cnt = 0;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            for(int k = j + 1; k < n; k++){
                for(int l = k + 1; l < n; l++){
                    if(a[l] == lcm(lcm(a[i], a[j]), a[k])){
                        cnt++;
                    }
                }
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

暴力骗分Code2：

将序列中所有出现的数和其下标存起来，首先遍历第四个数 $d$ ，然后用一个 $vector$ 将所有 $d$ 的因数找出来，三重 $for$ 循环遍历其所有的因数，然后二分在 $d$ 的下标序列中查找第一个比 $c$ 大的下标，后面的 $d$ 就都满足条件，直接累加到答案即可。

因为加了很多特判和 $continue$ ，并且有判重，每次还只看因子，对于 ${1 1 1 ...1 1 1}$ 这种序列，总时间复杂度可以降到 $O(n^3(logn+logM))$ ，对于大部分数都不相同的序列，由于没什么因子，更是可以将总复杂度降到接近 $O(n^2(logn+logM))$ ，虽然遇到 ${1, 2, 4, 8, 16,32...}$ 这种序列时间复杂度会特别高，但该代码可以卡过很多数据弱的点。

时间复杂度：最坏情况下 $O(n^4(logn+logM))$ ，一部分情况 $O(n^3(logn+logM))$ , $M$ 为所有数的最大值

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#define endl '\n'
using namespace std;
using LL = long long;

LL lcm(LL a, LL b) {
    return a / __gcd(a, b) * b;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n;
    int a[1010];
    cin >> n;
    unordered_map<int, vector<int>> pos;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        pos[a[i]].push_back(i); // pos[i]是一个vector,里面存的是序列中所有i的下标
    }
    LL res = 0;
    for(auto e : pos){ // 遍历所有数作为第四个数
        int d = e.first; // d:第四个数
        vector<int> v; // 存d的所有因子的下标
        for(int i = 0; i < n; i++){
            if(d % a[i] == 0) v.push_back(i);
        }
        int m = v.size();
        for(int i = 0; i < m; i++){ // 遍历第一个数:a
            int t1 = a[v[i]];
            for(int j = i + 1; j < m; j++){ // 遍历第二个数:b
                int t2 = a[v[j]];
                LL lcm_ab = lcm(t1, t2); // 计算lcm(a, b)
                if(lcm_ab > d) continue; // 如果比d大就不用再找第三个数c了
                for(int k = j + 1; k < m; k++){ // 遍历第三个数:c
                    int t3 = a[v[k]];
                    LL lcm_abc = lcm(lcm_ab, t3); // 计算lcm(a, b, c)
                    if(lcm_abc == d){ // 等于d的话就在d的下标序列中二分找第一个大于当前c的下标的位置
                        vector<int>& vv = e.second;
                        auto it = upper_bound(vv.begin(), vv.end(), v[k]);
                        res += (vv.end() - it); // 后面的所有d都满足
                    }
                } 
            }
        }
    }
    cout << res << endl;
    return 0;
}

ACcode:前缀处理、二分

将序列中所有出现的数和其下标存起来，再用一个哈希表( $unordered\_map$ ) $pre$ 动态存当前所有的 $lcm(a, b)$ 和其出现次数，遍历每个数作为四元组中第三个数 $c$ ，然后对于每个 $c$ ，遍历 $pre$ 中每一对 $lcm(a, b)$ 和出现次数 $cnt\_ab$ ，和当前 $c$ 计算 $lcm(a, b, c)$ ，再在当前 $c$ 的后面所有数中二分查找有几个 $d = lcm(a, b, c)$ ，记为 $cnt\_d$ 将 $cnt\_ab *cnt\_d$ 累加到答案，然后遍历当前 $c$ 前面的每一个数，将 $lcm(a[j], c)$ 加到 $pre$ 中，继续遍历下一个 $c$ 。

加一个优化：记录一下序列中所有数的最大值，如果算出的 $lcm$ 已经比最大值大了，就一定不可能找到 $d$ 了，直接 $continue$ 跳过

时间复杂度： $O(n^2logn)$

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#define endl '\n'
using namespace std;
using LL = long long;

int n;
int a[1010];
unordered_map<int, vector<int>> pos;

LL lcm(LL a, LL b) {
    return a / __gcd(a, b) * b;
}

LL query(LL x, int l, int r){ // 二分查找a[l], a[l + 1], ..., a[r]中有多少个x
    auto it = pos.find(x); // 找x的下标序列
    if(it == pos.end()) return 0; // 没有x
    vector<int> v = it -> second; // x的下标序列
    auto left = lower_bound(v.begin(), v.end(), l); // 第一个 >=l 的位置
    auto right = upper_bound(v.begin(), v.end(), r); // 第一个 >r 的位置
    return right - left; // 下标在[l, r]中的x的数量
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    int maxn = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        maxn = max(maxn, a[i]); // 找序列中所有数的最大值
        pos[a[i]].push_back(i); // pos[i]是一个vector,里面存的是序列中所有i的下标
    }
    LL res = 0;
    unordered_map<int, LL> pre;
    for(int i = 1; i <= n; i++){ // 遍历每个数作为第三个数c
        for(auto e : pre){ // 遍历当前c前面所有的lcm(a, b)
            LL lcm_ab = e.first; // lcm(a, b)
            LL cnt_ab = e.second; // 数量
            LL lcm_abc = lcm(lcm_ab, a[i]); // 计算lcm(a, b, c) 
            if(lcm_abc > maxn) continue; // 如果比最大值大了，说明找不到满足lcm(a, b, c) = d的d,直接返回
            int cnt_d = query(lcm_abc, i + 1, n); // 二分查找所有满足条件的d的数量
            res += cnt_ab * cnt_d; // 将当前(a, b)的数量和当前d的数量的乘积累加到答案
        }
        for(int j = 1; j < i; j++){ // 遍历a[i]前面的所有数，计算lcm(a[j], a[i])，更新pre
            LL lcm_ab = lcm(a[j], a[i]);
            if(lcm_ab <= maxn) pre[lcm_ab]++;
        }
    }
    cout << res << endl;
    return 0;
}

这题还可以处理约数+dp做，会的话可以尝试一下

沈阳化工大学蓝桥杯模拟赛题解

A.婴儿学数

答案：2159

ACcode1(暴力）

ACcode2(动态规划)

B.数列之和

答案：1996488764

ACcode1：二分答案

ACcode2

ACcode3

C.简单题

ACcode

D.最小好进制

暴力骗分Code

ACcode：二分答案 + 进制转换

E.分配宝藏

暴力Code1 -> next_permutation

暴力Code2 -> dfs排列型枚举

ACcode:贪心

简单好理解的证明：

严密的证明：

F.魔法迷宫

只要部分分Code：bfs模板

ACcode：多维bfs

G.算数城的难题

暴力骗分Code

ACcode：双指针+前缀和。

H.神秘数列的密码

暴力骗分Code1：最纯粹的暴力

暴力骗分Code2：

ACcode:前缀处理、二分