牛客小白月赛56题解

大概6月份想尝试出一出小白月赛。
想了几个题给兰子看，兰子毙了一个最难的，加了个签到。
现在的F原来的条件，意识到是假做法，然后自己毙了，就成了现在的模样。

感觉我的std都好麻烦，大家的代码都好简短。
F题我是按照分层图去想的，内测时大部分人都是一个简短的建图搞过去...

赛时有人指出B题，没说输出怎么分割（空格？逗号？....）谢罪。

A、阿宁的柠檬

最小值，每个柠檬取最小酸度和最小甜度。
最大值，每个柠檬取最大酸度和最大甜度。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int a, b, n;

int main() {
    cin >> a >> b >> n;
    cout << n << ' ' << (LL)(a + b) * n << endl;
    return 0;
}

B、阿宁与猫咪

$m> 1$ 时，数组全是 $1$ ， $u$ 和 $v$ 都是 $1$ 。如果选择其它的构造方式， $u$ 至少加 $1$ ， $v$ 最少等于 $0$ 。所以数组全是 $1$ 为最优的策略。

$m= 1$ 时， $u$ 是 $1$ ， $v$ 是 $0$ 。

#include <bits/stdc++.h>
using namespace std;

int m;    

int main() {
    cin >> m;
    cout << m << endl;
    for (int i = 1; i <= m; ++i) {
        cout << 1 << " ";
    }
    return 0;
}

C、阿宁吃粽子

贪心，美味值越大的粽子，应该放到 $i\%10$ 越大的位置。

先将余数是 0,1,2,3 ... 9 的位置，分别有多少个先算出来，再把粽子分类。在把每个位置的粽子对应出一个顺序，输出。

#include <bits/stdc++.h>
using namespace std;

const int N = 3 + 2e5;

int n, a[N];
vector<int> b[10];
int c[10];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    sort(a + 1, a + n + 1);

    int p;

    for (int i = 1; i <= 10; ++i) {  // 算每个余数有多少个坑
        p = i % 10;
        c[p] = n / 10;
        if (i <= n % 10) ++c[p];
    }

    p = 0;

    for (int i = 1; i <= n; ++i) {  // 按美味值从小到大放每个粽子
        if (b[p].size() == c[p]) p = (p + 1) % 10;
        b[p].push_back(a[i]);
    }

    p = 0;

    for (int i = 0; i < b[1].size(); ++i) {
        for (int j = 1; j <= 10; ++j) {
            if (i < b[j % 10].size()) a[++p] = b[j % 10][i];
        }
    }

    for (int i = 1; i <= n; ++i) {
        cout << a[i] << ' ';
    }
    return 0;
}

D、阿宁的质数

先使用 $O(nlogn)$ 的方法（线性筛也行）筛出质数，打表。后面的判断质数都通过查表。

从左往右预处理答案，假设当前是 $i$ 。维护一个变量 $now$ ，表示区间 $[1,i]$ 的答案（最小未出现的质数）。还要维护一个 $set$ ，存区间 $[1,i]$ 的质数。
当 $a_i$ 是质数，就把 $a_i$ 放到 $set$ 里面。然后判断 $now$ 满足：是不是出现在 $set$ 里面或者是不是质数。如果满足则 $now$ 加 $1$ 。 $now$ 是只增不减的，单次的加 $1$ 复杂度是 $log$ 。

#include <bits/stdc++.h>
using namespace std;

const int N = 3 + 2e5;

int n, q, a[N];
bool p[N * 20];
int pre[N];
set<int> st;

// 第2e5个质数 2750159
// 至少要第2e5+1个质数

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    memset(p, true, sizeof(p));
    p[1] = false;
    for (int i = 2; i < N * 20; ++i) {
        if (p[i]) {
            for (int j = i + i; j < N * 20; j += i) {
                p[j] = false;
            }
        }
    }

    int now = 1;
    for (int i = 1; i <= n; ++i) {
        if (a[i] < N * 20 && p[a[i]]) st.insert(a[i]);
        while (!p[now] || st.count(now)) ++now;
        pre[i] = now;
    }

    while (q--) {
        int x;
        cin >> x;
        cout << pre[x] << endl;
    }

    return 0;
}

E、阿宁睡大觉

将字符串分割，连续大写 'Z' 放一段，小写 'z' 放一段。比如 "zzzzZZzZZZZzzzZZZ"分割为["zzzz","ZZ","z","ZZZZ",'zzz','ZZZ']。

删除一段小写，使得两段大写合并，总权值才会加 $2\times2$ 。为了节省操作次数，很明显我们应该优先将短的小写段删除。比如前面的例子，我们应该先删除 'z'，再删除 'zzz'。

#include <bits/stdc++.h>
using namespace std;

const int N = 3 + 2e5;

int n, k;
char s[N];
vector<int> b;

int main() {
    cin >> n >> k;
    cin >> s + 1;
    int ans = 0;
    while (n && s[n] == 'z') {
        --n;
    }
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }
    for (int i = 1; i <= n; ++i) {
        if (s[i] == 'z') continue;
        int j = i;
        while (j + 1 <= n && s[j + 1] == 'Z') ++j;
        // i 到 j 是一段大写的 'Z'
        ans += 4 * (j - i); // 这一段产生的贡献

        j = j + 1;
        i = j;
        if (i > n) break;

        while (j + 1 <= n && s[j + 1] == 'z') ++j; 
        // 如果删除这一段小写 'z'，两端大写合并产生的贡献是 4
        // 因为这样写，所以前面有先把后缀的小写 'z' 删掉
        b.push_back(j - i + 1);
        i = j;
    }
    sort(b.begin(), b.end());
    for (auto &i : b) {
        if (i <= k) { // 贪心先将长度小的段删掉
            ans += 4;
            k -= i;
        }
    }
    cout << ans << endl;
    return 0;
}

F、阿宁去游玩

最短路，定义一下状态，跑dijkstra。

状态定义： $d_{u,i,j}$ 从 $1$ 号从到 $u$ 号城市的最短路，并且， $i$ 次膜法对 $u$ 号城市生效，在 $u$ 号城市使用了 $j$ 次膜法。
因为使用两次膜法相当没使用，因此 $i$ 、 $j$ 都 $\% 2$ 。

转移：

在 $u$ 号城市使用膜法： $d_{u,i,0} → d_{u,i,1}$
从 $u$ 号城市前往 $v$ 号城市： $d_{u,i,j} → d_{v,(i+j)\%2,0}$
对 $u$ 号城市生效的膜法也对 $v$ 号城市生效，还有在 $u$ 号城市使用的膜法。

根据定义的状态就可以知道 $u$ 和 $v$ 之间是不是同样的属性，从而知道边权。

（在 $u$ 使用膜法，不会对来 $u$ 城市之前的城市产生影响，权值变大了，回不去了...或者说最短路每个点只会走一次...）

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int N = 3 + 2e5;

struct Node {
    int x, i, j;
    LL d;
    bool operator<(const Node &b) const { return d > b.d; }
};

int n, m, x, y, z;
int a[N];
vector<int> edge[N];
LL d[N][2][2];
bool vis[N][2][2];
priority_queue<Node> q;

int main() {
    cin >> n >> m;
    cin >> x >> y >> z;

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    while (m--) {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }

    memset(d, 0x3f, sizeof(d));
    d[1][0][0] = 0;
    q.push({1, 0, 0, 0LL});
    while (q.size()) {
        auto node = q.top();
        int &u = node.x, &i = node.i, &j = node.j;
        q.pop();

        if (u == n) {
            cout << d[u][i][j] << endl;
            return 0;
        }

        if (vis[u][i][j]) continue;
        vis[u][i][j] = true;

        if (j == 0) {
            if (d[u][i][1] > d[u][i][0] + z) { // 使用一次倒转膜法
                d[u][i][1] = d[u][i][0] + z;
                q.push({u, i, 1, d[u][i][1]});
            }
        }

        for (int &v : edge[u]) {
            int w = 0;
            if ((i + a[u]) % 2 == (i + j + a[v]) % 2) { // 和下一个点状态是否相同
                w = x;
            } else {
                w = y;
            }
            if (d[v][(i + j) % 2][0] > d[u][i][j] + w) {
                d[v][(i + j) % 2][0] = d[u][i][j] + w;
                q.push({v, (i + j) % 2, 0, d[v][(i + j) % 2][0]});
            }
        }
    }

    assert(false);

    return 0;
}