数字之和

题意

字符串$s$和字符串"zhixin"有多少处索引（即下标）不同。

题解

遍历字符串，逐一对比即可。

#include<bits/stdc++.h>
using namespace std;
int main() {
    int j, l;
    cin >> j;
    while(j--) {
        string p = "zhixin", s;
        cin >> s;
        l = 0;
        for(int y = 0; y < 6; y++)if(s[y] != p[y])l++;
        cout << l << '\n';
    }
    return 0;
}

最长零区间

题意

二进制字符串，求最长的零区间。

题解

遍历字符串，并记录当前零区间的长度。当遇到0时，则增加当前零区间的长度，每当遇到1时，检查当前零区间是否比之前最长的零区间长。如果是，则更新最长零区间的长度。最后，返回最长零区间的长度。

该算法的时间复杂度为$O(n)$。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        int c = 0;
        int g = 0;
        int x;
        for(int i = 0; i < n; i++) {
            cin >> x;
            if(x == 0)
                c++;
            else {
                g = max(g, c);
                c = 0;
            }
        }
        cout << max(g, c) << endl;
    }
    return 0;
}

升级大招

题意

给出打怪所花时间和所获得技能，问获得1、2技能的最短时间是多少。

题解

你可以把这些野怪分为四类:“00”、“01”、“10”、“11”。有两种情况：

• 取用时最少的“01”和用时最少的“10”。
• 取用时最少的“11”。

在这些选项中，输出最少的一个。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
    ll q;
    cin >> q;
    while(q--) {
        ll n, a = 1e9, b = 1e9, c = 1e9, x;
        string s;
        cin >> n;
        for(int i = 0; i < n; i++) {
            cin >> x >> s;
            if(s == "11")a = min(a, x);
            if(s == "10")b = min(b, x);
            if(s == "01")c = min(c, x);
        }
        if(a != 1e9 || (b != 1e9 && c != 1e9))
            cout << min(a, b + c) << "\n";
        else
            cout << "-1\n";
    }
    return 0;
}

分石子

题意

$n$个石子，按$1:2$比例分堆，问能否得到$m$个石子。

题解

我们可以递归地解决这个问题。设当前堆有$n$个石子。

• 如果$n=m$，那么我们就可以得到一个恰好有$m$个石子的堆，不需要做任何操作。
• 如果$n$不是$3$的倍数，那么就不可能再分了，因为一次操作我们会把$n$分为$x$和$2x$，那么$n=x+2x=3x$，对于某个整数$x$，这意味着$n$一定是3的倍数。
• 最后，如果$n$是$3$的倍数，那么我们就可以把这一堆分成两堆，分别为$\frac{n}{3}$和$\frac{2n}{3}$。我们可以递归地检查是否能得到恰好有$m$个石子的堆。

#include<bits/stdc++.h>
using namespace std;
int n, m;
bool dfs(int n) {
    return n == m ? 1 : (n < m || n % 3) ? 0 : (dfs(n / 3) || dfs(n * 2 / 3));
}
int main() {
    int t;
    cin >> t;
    while(t--) {
        cin >> n >> m;
        cout << (dfs(n) ? "YES" : "NO") << endl;
    }
    return 0;
}

湖水总量

题意

上下左右连通，求最大的连通块。

题解

我们可以在给定的网格上使用深度优先搜索(DFS)（也就是我们学过的递归）或广度优先搜索(BFS)来解决这个问题。

其想法是将网格的每个单元视为湖泊的潜在起点，并通过上下左右移动来探索所有可到达的单元，而不踩到任何深度为0的单元。如果我们到达边界，或者一个深度为0的单元格，我们就折回，尝试另一个方向。

在这个探索过程中，我们记录了我们访问过的所有单元格的深度总和。这个总和就是现在湖泊的体积。当我们从一个起点探索了所有可到达的细胞后，我们将这个湖的水量与之前找到的最大水量进行比较，并在必要时更新最大水量。

为了实现这种方法，我们可以使用一个嵌套循环来遍历网格的所有单元格。对于每个单元格，我们检查其深度是否大于0和没有在之前的湖泊中出现过。如果满足这些条件，我们将从该单元启动DFS/BFS，并更新到目前为止找到的最大水量。该算法的时间复杂度为$O (mn)$。

#include<bits/stdc++.h>
using namespace std;
int t, a, b, c, d[1005][1005];
int p2(int x, int y, int tot) {
    if(d[x][y] == 0)
        return 0;
    int s = d[x][y];
    d[x][y] = 0;
    if(x > 1)
        s += p2(x - 1, y, ++tot);
    if(x < a)
        s += p2(x + 1, y, ++tot);
    if(y > 1)
        s += p2(x, y - 1, ++tot);
    if(y < b)
        s += p2(x, y + 1, ++tot);
    return s;
}
int main() {
    cin >> t;
    while(t--) {
        c = 0;
        cin >> a >> b;
        for(int i = 1; i <= a; i++)
            for(int j = 1; j <= b; j++)
                cin >> d[i][j];
        for(int i = 1; i <= a; i++) {
            for(int j = 1; j <= b; j++) {
                c = max(c, p2(i, j, 0));
            }
        }
        cout << c << endl;
    }
    return 0;
}

雪花形状

题意

给你一个雪花图，问有多少个中间顶点和每个中间顶点有几个边缘顶点。

题解

$中心顶点个数=边总数-度为1的点总数$

$所连边缘顶点个数=度为1的点总数/中心顶点个数$

#include<bits/stdc++.h>
using namespace std;
int c[205];
int main() {
    int t;
    cin >> t;
    while(t--) {
        int n, m;
        cin >> n >> m;
        for(int i = 0; i < 205; i++)
            c[i] = 0;
        int cnt = 0;
        for(int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            c[a]++;
            c[b]++;
        }
        for(int i = 1; i <= n; i++)
            if(c[i] == 1)
                cnt++;
        cout << m - cnt << " " << cnt / (m - cnt) << endl;
    }
    return 0;
}

赢可乐

题意

给你一个金字塔，扔中某个单元格，则其会倒下，上面对应的单元格也会倒，问倒下的单元格编号总和。

题解

若$f[i][j]$被击倒，则$f[i-1][j-1]$和$f[i-1][j]$对应会被击倒。

• 若$f[i-1][j-1]$被击倒，则$f[i-2][j-2]$和$f[i-2][j-1]$对应会被击倒。
• 若$f[i-1][j]$被击倒，则$f[i-2][j-1]$和$f[i-2][j]$对应会被击倒。

因此，$f[i-2][j-1]$被重复计算了，要减去。

最终，$f[i][j] = k * k + f[i - 1][j] + f[i - 1][j - 1] - f[i - 2][j - 1];$

#include<iostream>
using namespace std;
const int N = 2005, M = 1e6 + 10;

int t, n;
long long f[N][N], ans[M];

int main() {
    cin >> t;
    f[1][1] = ans[1] = 1;
    long long k = 2;
    for(int i = 2; i < N && k < M; i++) {
        for(int j = 1; j <= i && k < M; j++) {
            f[i][j] = k * k + f[i - 1][j] + f[i - 1][j - 1] - f[i - 2][j - 1];
            ans[k] = f[i][j];
            k++;
        }
    }
    while(t--) {
        cin >> n;
        cout << ans[n] << endl;
    }
    return 0;
}