牛客小白月赛61 题解

超市里扫货

https://ac.nowcoder.com/acm/contest/46597/A

前言

首先，十分抱歉给大家带来了不好的比赛体验，下面是比赛中出的大锅。

锅 1：B 题是出题人在读 CSAPP 时想到的一道小模拟，但在题目描述时出了问题，应该是离 $a 1. a 2$ 最近的偶数。

锅 2：C 题题面叙述不清，存在歧义，让选手做得很难受。

锅 3：由于出题人最近对红警比较上头，因此有了 D 题，本质上是模拟。但由于 “这模拟” 坑点过多，最终成了 “折磨你”，对小白极不友好。

这是出题人第一次出全网比赛，虽然赛前进行了重重检验，但赛时还是出了诸多问题，十分抱歉。

Problem A. 超市里扫货

顺序扫描所有货物，维护购物车的剩余容积。若购物车的剩余容积不足以装下当前货物，则新推一辆购物车。此外需要注意，由于 $max(V)=2^{30}$ ，所以两个物品的体积相加可能超过INT_MAX。

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

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

void work()
{
    int n, v; scanf("%d %d", &n, &v);
    int rem = v, cnt = 1;
    for (int i = 1, a; i <= n; ++i) {
        scanf("%d", &a);
        if (rem >= a) rem -= a;
        else ++cnt, rem = v - a;
    }
    printf("%d\n", cnt);
}

int main()
{
    work();
    return 0;
}

Problem B. 柜台结账

分类讨论一下所有情况，我们可以发现：

支付的金额与原价格相比不变的情况只有一种，即 $a_{2} = 0$ 。

支付的金额与原价格相比多了的情况有两种：

① $0. a_{2} > 0.5$

② $0. a_{2} = 0.5$ 且 $a_{1}$ 为奇数

其余情况则说明支付的金额与原价格相比少了。

时间复杂度： $O (∣ a_{2} ∣)$ 。

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

void work()
{
    string a1, a2; cin >> a1 >> a2;
    
    auto cmp = [](const string &s) {
        if (s[0] > '5') return 1;
        if (s[0] < '5') return -1;
        for (size_t i = 1; i < s.size(); ++i)
            if (s[i] != '0') return 1;
        return 0;
    };
    
    if (a2 == "0") cout << "PLMM\n";
    else if (cmp(a2) == 1 || (cmp(a2) == 0 && (a1.back()&1))) cout << "Happy birthday to MFGG\n";
    else cout << "Happy birthday to YXGG\n";
}

int main()
{
    work();
    return 0;
}

Problem C. 小喵觅食

以 PLMM 和小喵的初始位置分别做 BFS，距离数组分别记为 $d i s [0] [i] [j]$ 和 $d i s [1] [i] [j]$ ，需要注意的是 PLMM 进行 BFS 时有活动范围 $r_{1}$ 的限制，而小喵进行 BFS 时没有活动范围 $r_{2}$ 的限制。

记小喵的初始位置为 $(m x, m y)$ ，枚举 PLMM 的终止位置 $(i, j)$ 满足 $|i-mx|+|j-my|\leq r_2$ ，答案即为 $m i n (d i s [0] [i] [j] + d i s [1] [i] [j])$ 。

时间复杂度： $O (n m)$ 。

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

const int M = (int)1e3;
const int inf = 0x3f3f3f3f;

int n, m, r1, r2;
char s[M + 5][M + 5];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int dis[2][M + 5][M + 5];

void bfs(int u, int x, int y, int r)
{
    queue<pair<int, int>> q;
    dis[u][x][y] = 0;
    q.push({x, y});
    while (!q.empty()) {
        auto [ux, uy] = q.front(); q.pop();
        for (int i = 0; i < 4; ++i) {
            int vx = ux + dx[i], vy = uy + dy[i];
            if (vx < 1 || vx > n || vy < 1 || vy > m || s[vx][vy] == '*' || dis[u][vx][vy] < inf) continue;
            if ((int)abs(vx - x) + (int)abs(vy - y) > r) continue;
            dis[u][vx][vy] = dis[u][ux][uy] + 1;
            q.push({vx, vy});
        }
    }
}

void work()
{
    scanf("%d %d %d %d", &n, &m, &r1, &r2);
    memset(dis, inf, sizeof dis);
    for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
    int mx = 0, my = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (s[i][j] == 'P') bfs(0, i, j, r1);
            else if (s[i][j] == 'M') bfs(1, i, j, inf), mx = i, my = j;
    int mi = inf;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if ((int)abs(i - mx) + (int)abs(j - my) <= r2)
                mi = min(mi, dis[0][i][j] + dis[1][i][j]);
    printf("%d\n", mi == inf ? -1 : mi);
}

int main()
{
    work();
    return 0;
}

Problem D. 石油大亨

模拟题，做法因人而异，下面是出题人的做法。

首先，若 $s < e c$ ，则无解输出 $- 1$ 。

$i$ 遍历 $1,2,\cdots,n$ 枚举工程师， $cur\_time_i$ 表示第 $i$ 个工程师开始训练的时间，答案即为 $cur\_time_n+et+t[n]$ 。通过维护当前金额和油田个数，使用 $cur\_time_{i-1}$ 计算出 $cur\_time_i$ 。

具体细节请见代码。

PS：由于金额可能会爆long long，因此需要特判一下。

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

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

typedef long long ll;

const int M = (int)1e5;
const ll linf = 0x3f3f3f3f3f3f3f3f;

int n, ec, et, p; ll s;
int t[M + 5];

void work()
{
	scanf("%d %d %d %d %lld", &n, &ec, &et, &p, &s);
	for (int i = 1; i <= n; ++i) scanf("%d", &t[i]);
	if (s < ec) return printf("-1\n"), void();
	queue<ll> q; //存储工程师占领油田的时间
	ll cur_time = 0;
	for (int i = 1, oil_cnt = 0; i <= n; ++i) {
		ll next_time = (i == 1 ? 0 : cur_time + et); //下一次开始训练工程师的最小时间戳
		while (!q.empty() && q.front() <= next_time) { //计算从当前到next_time的金额收益
			if(s < linf) s += oil_cnt * (q.front() - cur_time) * p;
			cur_time = q.front();
			q.pop();
			++oil_cnt;
		}
		if (cur_time < next_time) {
			if(s < linf) s += oil_cnt * (next_time - cur_time) * p;
			cur_time = next_time;
		}
		if (s < ec) { //金额不足以训练工程师
			while (!q.empty() && s + oil_cnt * (q.front() - cur_time) * p < ec) {
				s += oil_cnt * (q.front() - cur_time) * p;
				cur_time = q.front();
				q.pop();
				++oil_cnt;
			}
			ll wait_time = (ec - s + (ll)oil_cnt * p - 1) / oil_cnt / p; //需要等待wait_time的时间
			s += oil_cnt * wait_time * p;
			cur_time += wait_time;
		}
		s -= ec;
		q.push(cur_time + et + t[i]);
	}
	printf("%lld\n", cur_time + et + t[n]);
}

int main()
{
	work();
	return 0;
}

Problem E. 排队

若 $a_i \not= a_j$ ，则考虑 $(a_{i}, a_{j})$ 对答案的贡献。

由于是随机排列，所以有 $\frac{n!}{2}$ 种排列使得 $(a_{i}, a_{j})$ 对答案产生 $1$ 的贡献。

因此答案为 $\frac{n!}{2}\sum_{1 \leq i < j \leq n}{[a_i \not= a_j]}$ 。

记 $c n t [a_{i}]$ 表示 $a_{i}$ 在序列 $a$ 中的出现次数，可以使用 $c n t []$ 数组 $O (n)$ 求出 $\sum_{1\leq i < j \leq n}[a_i \not= a_j]$ 。

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

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

typedef long long ll;

const int M = (int)1e5;
const int mod = (int)1e9 + 7;

int cnt[M + 5];

void work()
{
    int n; scanf("%d", &n);
    int ans = 0;
    for (int i = 1, a; i <= n; ++i) {
        scanf("%d", &a);
        (ans += i - ++cnt[a]) %= mod;
    }
    for (int i = 3; i <= n; ++i) ans = (ll)ans * i % mod;
    printf("%d\n", ans);
}

int main()
{
    work();
    return 0;
}

Problem F. 选座椅

容易想到，如果区间 $[l, r]$ 可以满足 $m$ 个条件，那么区间 $[l, r + 1]$ 也一定可以满足 $m$ 个条件。

对区间 $[l, r]$ 进行尺取，维护每个位置被使用的情况和满足的条件个数。对于每个 $l$ 求出满足 $m$ 个条件的最小的 $r$ ，使用差分数组求出不考虑顺序的方案数，再乘以阶乘即为答案。

时间复杂度： $O (n + m)$ 。

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

const int M = (int)1e5;
const int mod = (int)1e9 + 7;

int n, m;
vector<int> v[M + 5];
int cnt[M + 5], tot;
int d[M + 5];

void work()
{
    scanf("%d %d", &n, &m);
    for(int _ = 0; _ < 3; ++_)
        for(int i = 1, a; i <= m; ++i) {
            scanf("%d", &a);
            v[a].push_back(i);
        }
    auto add = [&](int p) {
        for(const int& x: v[p])
            if(++cnt[x] == 1)
                ++tot;
    };
    
    auto del = [&](int p) {
        for(const int &x: v[p])
            if(--cnt[x] == 0)
                --tot;
    };
    
    for(int l = 1, r = 0; l <= n; ++l) {
        while(r + 1 <= n && tot < m) add(++r);
        if(tot == m) ++d[r - l + 1], --d[n - l + 2];
        del(l);
    }
    
    for(int i = 1, fac = 1; i <= n; ++i) {
        fac = (long long)fac * i % mod;
        d[i] += d[i - 1];
        printf("%lld%c", (long long)fac * d[i] % mod, " \n"[i == n]);
    }
}

int main()
{
    work();
    return 0;
}