首页 > 其他分享 >牛客小白月赛 61 题解

牛客小白月赛 61 题解

时间:2022-11-19 18:11:07浏览次数:62  
标签:cnt const 牛客 int 题解 61 vx vy dis

前言

以下内容转自官方

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

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

锅 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,距离数组分别记为 \(dis[0][i][j]\) 和 \(dis[1][i][j]\),需要注意的是 PLMM 进行 BFS 时有活动范围 \(r_1\)​ 的限制,而小喵进行 BFS 时没有活动范围 \(r_2\)​ 的限制。

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

时间复杂度:\(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<ec\),则无解输出 \(-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]}\)。

记 \(cnt[a_i]\) 表示 \(a_i\)​ 在序列 \(a\) 中的出现次数,可以使用 \(cnt[]\) 数组 \(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;
}

标签:cnt,const,牛客,int,题解,61,vx,vy,dis
From: https://www.cnblogs.com/I-am-yzh/p/16906674.html

相关文章

  • 牛客小白月赛61 B柜台结账
    原题链接#include<stdio.h>#include<string.h>#include<stdlib.h>constintN=1e5+10;chara1[N],a2[N];//分别为a1和a2的字符串intlena,lenb;//分别为a1和a2的字......
  • 题解 CF1759G【Restore the Permutation】
    problem给定长为\(n/2\)的数组\(b\),试求出字典序最小的排列\(p\)使得\(b_i=\max_{p_{2i-1},p_{2i}}\),或者报告无解。\(n\leq10^5\)。solution考虑显然的结论:\(p_......
  • CF755G PolandBall and Many Other Balls 题解
    老师潦草的笔记(题目大意给你$n$个球,让你选$m(1\lem\lek)$组球。每组只有$1$个球或$2$个相邻球。令选出$m$组球的方案数为$f_m$,现在让你输出$f_i(1\l......
  • arc136D Without Carry 题解
    这阵子没一道题能自己想出来,开道黄题以下找找信心qwq又一道比C简单的D。题意:给出\(n\)个\(6\)位及以下数字,问有几对数字的和在十进制下无进位。\(n\leq10^6\)......
  • 题解 Codeforces Round #834 (Div. 3) ABCDEF
    A.Yes-Yes?problem判断给定的字符串是否为无穷个YesYesYes拼接组成的字符串的连续子串。\(|S|\leq50\)。solution暴力。具体地,判断\(S,Ye+S,Y+S\)是否有一个是......
  • LTC1861HMS#TRPBF LTC1861HMS模数转换器 12 bit 250ksps ADC
    LTC1860/LTC1861是12位A/D转换器,提供MSOP和SO-8包,并在单个5V电源上工作。在250ksps时,电源电流只有850μA。由于LTC1860/LTC1861在转换之间自动降低到典型的1nA电源电流,所......
  • python(牛客)试题解析1 - 简单
    导航:一、NC103反转字符串二、NC141判断是否为回文字符串三、NC151最大公约数四、NC65斐波那契数列五、字符按排序后查看第k个最小的字母六、数组内取出下标相同......
  • CF1610H Squid Game
    题面传送门首先定\(1\)为根节点,然后我们发现,如果全部的限制都是弯的,也就是\(x_i\)与\(y_i\)均不是两个点的LCA,则直接选择一个根节点就可以解决。然后如果全部限制都是直......
  • 移动端点击穿透问题解决
    js解决方案1、只用touch把页面内所有click全部换成touch事件(touchstart、touchend、tap),需要特别注意a标签,a标签的href也是click,需要去掉换成js控制的跳转,或者直接改成......
  • Codeforces Round #829 A+B+C+D 题解
    A.TheUltimateSquare题意询问\(T\)次,给定\(n\)块木板,第\(i\)块为\(1\times\lceil\fraci2\rceil\)大小,求能拼出的最大正方形边长数据范围:\(1\len\le10^9,1......