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

偷梁换柱

注意数据范围，就是简单的模拟即可。

#include <bits/stdc++.h>
using namespace std;
int n, m;
int l[5005], r[5005];
int typ[5005];
int main()
{
    freopen("tou.in", "r", stdin);
    freopen("tou.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> l[i] >> r[i];

    for (int i = 1; i <= n; i++)
        typ[i] = 0;
    for (int i = 1; i <= m; i++)
        for (int j = l[i]; j <= r[i]; j++)
            typ[j] = i;
    sort(typ + 1, typ + n + 1);
    /*
    for (int i = 1; i <= n; i++)
        cout << typ[i];
    cout << "\n";
    */
    int ans = (typ[1] != 0);
    for (int i = 2; i <= n; i++)
        if (typ[i] != typ[i - 1])
            ans++;
    cout << ans;
    return 0;
}

指桑骂槐

手推几个例子，很容易推出来标程这个结论。

#include <bits/stdc++.h>
using namespace std;
int n;
int a, b, c, d;
int A, B, C, D;
string s;
int main()
{
    freopen("zhi.in", "r", stdin);
    freopen("zhi.out", "w", stdout);
    cin >> n;
    cin >> a >> b >> c >> d;
    cin >> s;
    A = B = C = D = 0;
    for (int i = 0; i < s.size(); i++)
        if (s[i] == 'A')
            A++;
        else if (s[i] == 'B')
            B++;
        else if (s[i] == 'C')
            C++;
        else if (s[i] == 'D')
            D++;
    cout << min(a, A) + min(b, B) + min(c, C) + min(d, D);
    return 0;
}

假痴不癫

有一点点简单的博弈。首先所有质数局面以及小于 $2$ 时都是先手必胜的。

否则就需要看后续能不能变为一个先手必败的状态。如果当前局面操作完只能变为先手必胜的状态，那么当前就是先手必败的。否则只要当前局面能操作到一个先手必败的状态，那么当前操作的人就会这么做，来让自己必胜。

#include <bits/stdc++.h>
using namespace std;
int n, k;
bool flag[5005];
int main()
{
    freopen("jia.in", "r", stdin);
    freopen("jia.out", "w", stdout);
    flag[0] = flag[1] = true;
    for (int i = 2; i <= 5000; i++)
    {
        bool now = true;
        for (int j = 2; j < i; j++)
            if (i % j == 0)
                now = false;
        flag[i] = now;
    }
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        if (flag[i])
            continue;
        for (int j = i - 1; j >= max(1, i - k); j--)
            if (!flag[j])
                flag[i] = true;
    }
    if (flag[n])
        cout << "33DAI";
    else
        cout << "Kitten";
    return 0;
}

上屋抽梯

一个简单的树上搜索。显然如果要断开子树 $u$，要么断开 $u$ 到父节点那条边，要么断掉所有 $u$ 的子节点。

#include <bits/stdc++.h>
using namespace std;
const int INF = 5000 * 5000 + 5;
int n;
vector<pair<int, int>> e[5005];
int dis[5005];
void dfs(int u, int fa)
{
    int sum = 0;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i].first;
        int w = e[u][i].second;
        if (v == fa)
            continue;
        dis[v] = w;
        dfs(v, u);
        sum += dis[v];
    }
    if (sum != 0)
        dis[u] = min(dis[u], sum);
}
int main()
{
    freopen("shang.in", "r", stdin);
    freopen("shang.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back(make_pair(v, w));
        e[v].push_back(make_pair(u, w));
    }
    dis[1] = INF;
    dfs(1, 0);
    cout << dis[1];
    return 0;
}