前言

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

锅 1:B 题是出题人在读 CSAPP 时想到的一道小模拟,但在题目描述时出了问题,应该是离 a1.a2a1.a2 最近的偶数。

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

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

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

Problem A. 超市里扫货

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

时间复杂度:O(n)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. 柜台结账

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

支付的金额与原价格相比不变的情况只有一种,即 a2=0a_2=0

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

​ ① 0.a2>0.50.a_2>0.5

​ ② 0.a2=0.50.a_2=0.5a1a_1 为奇数

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

时间复杂度:O(a2)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,距离数组分别记为 dis[0][i][j]dis[0][i][j]dis[1][i][j]dis[1][i][j],需要注意的是 PLMM 进行 BFS 时有活动范围 r1r_1 的限制,而小喵进行 BFS 时没有活动范围 r2r_2 的限制。

记小喵的初始位置为 (mx,my)(mx,my),枚举 PLMM 的终止位置 (i,j)(i,j) 满足 imx+jmyr2|i-mx|+|j-my|\leq r_2,答案即为 min(dis[0][i][j]+dis[1][i][j])min(dis[0][i][j] + dis[1][i][j])

时间复杂度:O(nm)O(nm)

#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<ecs<ec,则无解输出 1-1

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

具体细节请见代码。

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

时间复杂度:O(n)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. 排队

aiaja_i \not= a_j,则考虑 (ai,aj)(a_i,a_j) 对答案的贡献。

由于是随机排列,所以有 n!2\frac{n!}{2} 种排列使得 (ai,aj)(a_i,a_j) 对答案产生 11 的贡献。

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

cnt[ai]cnt[a_i] 表示 aia_i 在序列 aa 中的出现次数,可以使用 cnt[]cnt[] 数组 O(n)O(n) 求出 1i<jn[aiaj]\sum_{1\leq i < j \leq n}[a_i \not= a_j]

时间复杂度:O(n)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][l,r] 可以满足 mm 个条件,那么区间 [l,r+1][l,r+1] 也一定可以满足 mm 个条件。

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

时间复杂度:O(n+m)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;
}