挖土机 CSP-J 模拟赛 ~ 第十二场

金蝉脱壳

#include <bits/stdc++.h>
using namespace std;
int n, a, b, c;
int main()
{
	freopen("jin.in", "r", stdin);
	freopen("jin.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    a = n % 10;
    b = n / 10 % 10;
    c = n / 100 % 10;
    int ans = 0;
    for (int x = 0; x <= 9; x++)
        for (int y = 0; y <= 9; y++)
            for (int z = 0; z <= 9; z++)
                if (x - y == a - b && b - c == y - z && z != 0)
                    ans++;
    cout << ans;
    return 0;
}

关门捉贼

注意到题目没有要求放最少的稻草人，所以给一个合法方案就好。那么稻草人放在第一行、最后一行、第一列、最后一列是最方便的，不用担心和猫的位置冲突。

显然因为还有稻草人数量要求，所以只给有猫的那些行列放稻草人即可。

#include <bits/stdc++.h>
using namespace std;
int n, m;
int x[505], y[505];
int main()
{
    freopen("guan.in", "r", stdin);
    freopen("guan.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> y[i];
    sort(x + 1, x + n + 1);
    sort(y + 1, y + n + 1);
    // 计数
    int cnt = 2;
    for (int i = 2; i <= n; i++)
        if (x[i] != x[i - 1])
            cnt += 2;
    cnt += 2;
    for (int i = 2; i <= n; i++)
        if (y[i] != y[i - 1])
            cnt += 2;
    cout << cnt << "\n";
    // 输出
    cout << x[1] << " " << 1 << "\n";
    cout << x[1] << " " << m << "\n";
    for (int i = 2; i <= n; i++)
        if (x[i] != x[i - 1])
        {
            cout << x[i] << " " << 1 << "\n";
            cout << x[i] << " " << m << "\n";
        }
    cout << 1 << " " << y[1] << "\n";
    cout << m << " " << y[1] << "\n";
    for (int i = 2; i <= n; i++)
        if (y[i] != y[i - 1])
        {
            cout << 1 << " " << y[i] << "\n";
            cout << m << " " << y[i] << "\n";
        }
    return 0;
}

远交近攻

首先显然二叉搜索树的中序遍历就是完整的顺序，所以可以生成中序遍历后拿最远的 $\frac{n}{2}$ 个点。

我这里给另一个做法，直接在 dfs 的过程中，得到每个结点的排名。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n, ans;
int a[MAXN + 5];
int l[MAXN + 5], r[MAXN + 5];
int rnk[MAXN + 5]; // i 号点排名 rnk[i]
// 到了 u 这个点，父节点方向小于它的有 cnt 个
// 返回子树大小
int dfs(int u, int cnt)
{
    int siz = 0;
    if (l[u] != 0)
    {
        siz += dfs(l[u], cnt);
        cnt += siz;
    }
    siz += 1;
    rnk[u] = cnt + 1;
    if (r[u] != 0)
        siz += dfs(r[u], cnt + 1);
    return siz;
}
int main()
{
	freopen("yuan.in", "r", stdin);
	freopen("yuan.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    int root = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        root = root ^ i;
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> l[i] >> r[i];
        root = root ^ l[i];
        root = root ^ r[i];
    }
    dfs(root, 0);
    ans = 0;
    for (int i = 1; i <= n; i++)
        if (n - rnk[i] + 1 <= n / 2)
        {
            ans += a[i];
        }
    cout << ans;
    return 0;
}

假道伐虢

显然每次走能走到的点中最小的那个是最有选项。这题给的数据范围直接暴力找就好。

如果你想到了用个优先队列优化这个查找，那么很好，你将很快学会 Prim 最小生成树算法。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1000;
const int MAXM = MAXN * (MAXN - 1) / 2;
int n, m, power;
int a[MAXN + 5];
bool vis[MAXN + 5];         // 走没走过
bool can[MAXN + 5];         // 能不能走到
bool e[MAXN + 5][MAXN + 5]; // 是否相连
signed main()
{
    freopen("jia.in", "r", stdin);
    freopen("jia.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u][v] = e[v][u] = true;
    }
    can[1] = true;
    power = 0;
    bool flag = true; // 还要不要找
    int cnt = 0;      // test
    while (flag)
    {
        flag = false;
        for (int i = 1; i <= n; i++)
        {
            if (!vis[i] && can[i] && (i == 1 || power >= a[i]))
            {
                vis[i] = true;
                power += a[i];
                cnt++;
                // 相连的都能走了
                for (int j = 1; j <= n; j++)
                    if (e[i][j])
                        can[j] = true;
                flag = true; // 可能还要找
            }
        }
    }
    cout << power << "\n";
    return 0;
}