首页 > 其他分享 >题解：牛客周赛 Round 56（A-E）

题解：牛客周赛 Round 56（A-E）

时间：2024-08-19 15:08:09浏览次数：10  
标签：std 10 00 le 周赛 int 题解 56 xqq

A 面包店故事

题面

小镇上有一家面包店，面包以 \(x\) 元的价格出售，加 \(y\) 元可以多加几块培根。小歪带着 \(n\) 元来到了面包店，他想知道自己能不能买到加培根的面包？

输入

在一行上输入三个整数 \(x,y,n\left( 1 \le x,y,n\le 100\right)\) 代表面包的价格、培根的价格和小歪带的钱。

输出

如果小歪能加到培根，在一行上输出 YES ；否则，直接输出 NO 。

样例1

输入

3 1 5

输出

YES

说明

面包加培根一共 \(4\) 元，小歪带了 \(5\) 元，他可以吃到培根！

样例2

输入

10 1 10

输出

NO

说明

面包加培根一共 \(11\) 元，小歪带了 \(10\) 元，他吃不到培根 (⋟﹏⋞) 。

题解

直接比较是否 \(a+b>c\) 就好了

  • 是则吃不到
  • 否则吃得到

代码

#include <bits/stdc++.h>

int main(){
	int a,b,c;
	std::cin >> a >> b >> c;
	std::cout << (a+b > c ? "NO\n" : "YES\n");
	return 0;
}

B 放课后故事

题面

小S 想要举办一个纸飞机大赛，他最新研制出的纸飞机需要 \(k\) 张纸才能折成。
为了制作纸飞机，他向班里的 \(n\) 个人要了一些纸，第 \(i\) 个人提供了 \(a_i\) 张纸给 小S 研究纸飞机。
放学了，小S 终于折好了全部的纸飞机，现在有 \(m\) 个人留下来和 小S 一起飞纸飞机。
最多有多少个人能分到纸飞机。

输入

第一行输入三个整数 \(n,m,k\left(1\le n \le 10^5;\ 0\le m \le 10^5;\ 1\le k\le 10^9 \right)\) 代表班级同学数量、留下来的同学数量和叠一只纸飞机需要的纸的数量。 
第二行输入 \(n\) 个整数，代表每一个同学提供的纸的数量。

输出

在一行上输出一个整数，代表最多有多少个人能分到纸飞机。

样例1

输入

3 2 5
1 2 4

输出

1

说明

小S 一共收集到 \(7\) 张纸，只可以叠一架纸飞机。

样例2

输入

6 3 4
1 1 4 5 1 4

输出

4

说明

小S 一共收集到 \(16\) 张纸，可以叠 \(4\) 架纸飞机，每个人都能分到纸飞机。

题解

（简短版）在场的人包括留下来的 \(m\) 人和 小S 自己，所以实际上有 \(m+1\) 个人
（详细版）
小S 手中的所有纸，实际上就是 \(n\) 人给出的所有纸（也就是第二行的和）
小S 手中的飞机总数，也的确是纸的总数除以 \(k\)
但是，在场的人除了留下来的 \(m\) 人之外还有 小S 自己
所以实际上有 \(m+1\) 个人

代码

#include <bits/stdc++.h>

using i64 = long long;

const int N = 1e7 + 10;
int a[N];

int main(){
	i64 n,m,k;
	i64 ans = 0;
	std::cin >> n >> m >> k;
	for(int i = 0 ; i < n ; i ++) {
		std::cin >> a[i];
		ans += a[i];
	}
	std::cout << std::min(ans/k,m+1);
	return 0;
}

C 异或故事

题面

给定 \(t\) 组询问，\(\mathit{76}\) 每次询问都会给出一个正整数 \(a\) ，你需要在区间 \([1,10^9]\) 中找到两个正整数 \(b\) 和 \(c\) ，使得 \(b \oplus c = a\)。
\(\oplus\) 代表按位异或。

输入

每个测试文件均包含多组测试数据。第一行输入一个整数 \(T\ (1\le T\le 10^5)\) 代表数据组数，每组测试数据描述如下：
在一行上输入一个整数 \(a\ (\ 1 \leq a \leq 10^9\ )\) 代表 \(\mathit{76}\) 给出的初始数字。

输出

对于每一组测试数据，在一行上输出两个正整数，代表你找到的两个值。
如果存在多个解决方案，您可以输出任意一个。

样例1

输入

3
1
5
4

输出

2 3
3 6
74 78

说明

对于第一组测试数据，\((10)_2 \operatorname{xor} (11)_2=(01)_2\)
对于第二组测试数据，\((011)_2 \operatorname{xor} (110)_2=(101)_2\)

题解

这题我们主要是利用异或的性质
简单来说就是：

\[\begin{aligned} a \oplus b = c \\ a \oplus c = b \\ b \oplus c = a \end{aligned} \]

要证明也很容易

\[\begin{aligned} 1 \oplus 1 = 0 \\ 1 \oplus 0 = 1 \\ 1 \oplus 0 = 1 \\\\ 0 \oplus 0 = 0 \end{aligned} \]

这样应该直观一点啦

然后，我们可以取一个数作为异或的主要对象，比如本题的上限 \(1e9\)
但是要注意：异或之后得到的结果可能是 \(0\) 或者大于 \(1e9\)
所以要做一个特判：假如存在上述情况，就让异或的数字变成 \(1e9 \gg 1\)
（其实这一步特判是我guess的，没想到居然过了）
（自己测了一下从1到1e9的所有数，确实全都过了）

代码

#include <bits/stdc++.h>

int t = 1;

void solve() {
	int n;
	std::cin >> n;
	int q = n^((int)1e9 >> 1);
	if(q > 1e9) {
		q = n^(int)(1e9);
		std::cout << q << " " << (int)(1e9) << "\n";
	}
	else std::cout << q << " " << ((int)1e9 >> 1) << "\n";
}


int main(){
	std::cin >> t;
	while(t--){
		solve();
	}
	return 0;
}

D 构造故事

题面

小S 今天在数学课上学习了三角形，他回家立马拿出了自己的 \(n\) 根火柴，想知道从这 \(n\) 根火柴中任选 \(3\) 根，能否组成一个周长最大的三角形。
由于 小S 只会暴力枚举，所以他把这个问题交给了你，你能帮他解决这个问题吗？

输入

每个测试文件均包含多组测试数据。第一行输入一个整数 \(T\left(1\le T\le 20\right)\) 代表数据组数，每组测试数据描述如下：
第一行输入一个整数 \(n\left( 3\le n\le 10^4\right)\) 代表 小S 的火柴数量。
第二行输入 \(n\) 个整数 \(a_1,a_2,\dots,a_n \left( 1\le a_i \le 10^9\right)\) 代表每根火柴的长度

输出

对于每一组测试数据，在一行上输出一个整数，代表能组成周长最大三角形的周长；如果无论如何都无法组成三角形，直接输出 −1 。

样例1

输入

3
6
2 2 10 4 10 6
5
6 1 5 3 3
5
2 2 4 10 6

输出

3
6
2 2 10 4 10 6
5
6 1 5 3 3
5
2 2 4 10 6

说明

对于第一组测试数据，有两个合法的三角形 \((4,10,10)\) 和 \((6,10,10)\) 。

题解

这题.....怎么说呢，实际上就是一个小学数学题
根据三角形的性质：

两边之和大于第三边
两边之差小于第三边

我们采取一个贪心的思路

把他们排序一下（从小到大）
相邻的两根火柴，假设是第 \(i\) 根和第 \(i+1\) 根吧，长度分别为 \(a、b(a \ge b)\)
假如他们不能和第 \(i-1\) 根火柴（长度为 \(c\)）组成三角形
那么他们一定不能和更前面的火柴组成三角形

因为假如他们不能组成三角形
那么一定是 \(a - b > c\)
火柴长度比c小的同样不能和前两根火柴组成三角形

就算把 \(a\) 换成比 \(a\) 更大（也就是更后面的火柴）
那 \(a - b > c\) 同样成立
依然不能组成三角形

因此，要组成三角形，最优解应当是相邻三根火柴组成的三角形
我们只要从后到前依次遍历即可

注意：要记得开long long

代码

#include <bits/stdc++.h>

using i64 = long long;

const int N = 1e7 + 10;
int t = 1;
i64 a[N];

void solve() {
	int n;
	std::cin >> n;
	for(int i = 0 ; i < n ; i ++) {
		std::cin >> a[i];
	}
	std::sort(a,a+n);
	for(int i = n-2 ; i > 0 ; i --) {
		if(a[i+1] - a[i] < a[i-1]) {
			std::cout << a[i] + a[i-1] + a[i+1] << "\n";
			return;
		}
	}
	std::cout << -1 << "\n";
}


signed main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	std::cin >> t;
	while(t--){
		solve();
	}
	return 0;
}

E 约会故事

题面

情人节才刚刚过去没多久啊 (¯﹃¯∗) ，但是我们的 xqq 已经开始备战明年的情人节了。心灰意冷的他找到 小S 生成了一个虚拟对象 小C ，在一次次的模拟约会中达成“一起进入电影院”的人生成就。
xqq 决定向 小C 发送邀请。在设定中，下述情况的 小C 会残忍的拒绝 xqq 的邀请：

  • xqq 不在 00:00 后、01:59 前（含）这段 小C 的睡前手机时间里发送邀请；
  • xqq 如果在 小C 不开心时发送邀请；

接受了邀请还远远没有成功！在设定中，下述情况的 小C 会在进入电影院前离去：

  • xqq 到电影院的时间比 小C 晚；
  • xqq 给 小C 准备的奶茶不是她喜欢的。
     
    如果 小C 同意了邀请，且没有中途离去，我们视为 xqq 达成成就！让我们一起来判定——这一次， xqq 会成功吗。

输入

第一行输入两个整数 \(n,m\left( 1\le n,m\le 10^5\right)\) 代表 小C 感到开心的时间段数量和 小C 喜欢的奶茶数量。
此后 \(n\) 行，第 \(i\) 行输入两个长度为 \(5\) ，且形如 \(hh:mm\) 的字符串代表 小C 第 \(i\) 段感到开心的起止时间，保证每一段开心时间不超过 \(24\) 小时。除了这 \(n\) 个时间段外，剩余时间她都是不开心的。
第 \(n+1\) 行输入 \(m\) 个长度不超过 \(10\) 且由大小写字母混合构成的字符串 \(s_1,s_2,\dots,s_m\) 代表 小C 喜欢喝的奶茶名字。
第 \(n+2\) 行输入一个整数 \(q\left(1\le q\le 10^5\right)\) 代表 xqq 尝试次数，每次尝试描述如下：

  • 第一行输入一个长度为 \(5\) ，且形如 \(hh:mm\) 的字符串代表 xqq 发送邀请的时间点；
  • 第二行输入两个长度为 \(5\) ，且形如 \(hh:mm\) 的字符串代表 xqq 到达电影院的时间和 小C 到达电影院的时间，我们约定，他们会在同一天内到达；
  • 第三行输入一个长度不超过 \(10\) 且由大小写字母混合构成的字符串 \(t\) 代表 xqq 购买的奶茶名字。

本题中出现的时间格式均按照 ISO8601 的二十四小时格式标准，即形如 \(hh:mm\)，其中 \(hh(00≤hh<24)\) 代表小时数，\(mm(00≤mm<60)\) 代表分钟数。

输出

对于每一次尝试，如果 xqq 成功达成成就，在一行上输出 Winner xqq ；如果 xqq 成功邀请但是 小C 中途离开，在一行上输出 Joker xqq ；否则，直接输出 Loser xqq 。

样例1

输入

3 2
00:03 00:47
00:30 01:23
12:00 17:00
Lemonade Cappuccino
5
00:35
12:00 12:00
Cappuccino
01:23
13:00 12:59
Cappuccino
01:15
11:00 12:43
WaTer
01:24
09:24 11:00
Lemonade
23:59
08:00 07:43
LeMonade

输出

Winner xqq
Joker xqq
Joker xqq
Loser xqq
Loser xqq

说明

  • 对于第一次尝试：
    • xqq 在 \(00:35\) 发送邀请，此时在规定时间内，且 小C 是开心的，所以他的邀请会被接受；
    • xqq 在 \(12:00\) 到达电影院，此时不晚于 小C ，且携带了 小C 爱喝的 \(Cappuccino\) ，所以她不会中途离开。
  • 对于第二次尝试，由于迟到了，小C 中途离开；
  • 对于第三次尝试，由于带错了奶茶，小C 中途离开；
  • 对于第四次尝试，由于发送邀请时 小C 不开心，所以邀请失败；
  • 对于第五次尝试，由于发送邀请时不在规定时间内，所以邀请失败。

样例2

输入

3 1
00:00 00:00
22:47 23:59
23:58 00:17
AbCdEfGhIj
1
00:00
00:00 00:00
AbCdEfGhIj

输出

Winner xqq

说明

注意，当开心的起始时间和结束时间相等时，我们认为 小C 一整天都感到开心。

题解

这题主要是记录时间的时候容易 TLE ，判断尝试是否成功的时候是可以达到 \(O(1)\) 的时间复杂度的
由于对于一天的所有分钟总和数量不大，我们可以声明一个二维数组（如int time[12][60]，最好放大一点），讨论里面的某一分钟是否可以邀请 小C。
然后在第一波输入 小C 开心的时段要注意

  • 如果开始的时间比结束的时间小，说明这段时间在同一天之内
  • 如果开始的时间比结束的时间大，说明这一段时间从这一天跨越到了第二天
  • 如果开始时间和结束时间相同，说明整一天 小C 都是快乐的
  • 记录的时候在超过 \(01:59\) 的或者在 \(00:00\) 之前的就不要去记录了

最后比较的时候找到对应的数组元素去判断就好了。

代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define all(x) x.begin(),x.end()

using i64 = long long;
const int N = 1e7 + 10;
int t = 1;
int tag[50][70];

void solve() {
    int n,m;
    i64 sum = 0;
    std::map<std::string,int> mp;
    std::cin >> n >> m;
    std::string s[n*2];
    for(int i = 0 ; i < n*2 ; i ++) std::cin >> s[i];
    for(int i = 0 ; i < n*2 && sum <= 120; i +=2) {
        int a = (s[i][0] - '0')*10 + s[i][1] - '0';
        int b = (s[i][3] - '0')*10 + s[i][4] - '0';

        int a1 = (s[i+1][0] - '0')*10 + s[i+1][1] - '0';
        int b1 = (s[i+1][3] - '0')*10 + s[i+1][4] - '0';

        int en1 = (a < a1 || (a == a1 && b < b1) ? a : 0);
        int en2 = (a < a1 || (a == a1 && b < b1) ? a : 0);

        if(a == a1 && b == b1) {
            a = 0,b = 0;
            while(a <= 1) {
                if(tag[a][b] == 0) sum ++;
                tag[a][b]++;
                b ++;
                if(b == 60) {
                    b = 0;
                    a++;
                }
            }

            break;
        }

        bool jud = true;
        if(a1 > a) jud = true;
        else if(a1 == a) {
            if(b1 > b) jud = true;
            else jud = false;
        }
        else jud = false;

        if(jud) {
            while(a <= 1 && a >= 0) {
                if(tag[a][b] == 0) sum ++;
                tag[a][b]++;
                b ++;
                if(b == 60) {
                    b = 0;
                    a++;
                }
                if(a >= a1 && b > b1) break;
            }
        } else {
            while(a <= 1) {
                if(tag[a][b] == 0) sum ++;
                tag[a][b]++;
                b ++;
                if(b == 60) {
                    b = 0;
                    a++;
                }
            }

            a = 0,b = 0;

            while(a <= 1) {
                if(tag[a][b] == 0) sum ++;
                tag[a][b]++;
                b ++;
                if(b == 60) {
                    b = 0;
                    a++;
                }
                if(a >= a1 && b > b1) break;
            }
        }
    }
    for(int i = 0 ; i < m ; i ++) {
        std::string s;
        std::cin >> s;
        mp[s]++;
    }

    i64 p;
    std::cin >> p;
    while(p--) {
        std::string s1,s2,q1,q2;
        std::cin >> s1 >> q1 >> q2 >> s2;
        int a = (s1[0] - '0')*10 + s1[1] - '0';
        int b = (s1[3] - '0')*10 + s1[4] - '0';

        int a1 = (q1[0] - '0')*10 + q1[1] - '0';
        int b1 = (q1[3] - '0')*10 + q1[4] - '0';

        int a2 = (q2[0] - '0')*10 + q2[1] - '0';
        int b2 = (q2[3] - '0')*10 + q2[4] - '0';

        bool jud;
        if(a1 > a2) jud = false;
        else if(a1 == a2) {
            if(b1 <= b2) jud = true;
            else jud = false;
        }
        else jud = true;

        if(tag[a][b] > 0 && mp.count(s2) && jud) {
            std::cout << "Winner xqq\n";
        }
        else{
            std::cout << (tag[a][b] > 0 ? "Joker xqq\n" : "Loser xqq\n");
        }
    }
}


signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    //std::cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

题目来源
有什么建议或者意见的欢迎在评论区留言！

标签：std,10,00,le,周赛,int,题解,56,xqq
From： https://www.cnblogs.com/jiejiejiang2004/p/18367306

相关文章

  • P1540 [NOIP2010 提高组] 机器翻译 题解
    题目概括给定N个整数，和一个容量为M的“字典”，从头到尾依次翻译，每次翻译先看自家字典，没有的话再看别人的字典并存到自家字典，如果自家字典满了，当前单词的翻译会代替最早进入的。做题思路定义一个长度为M的字典数组，依次遍历N个数，每次翻译先检索字典数组，没有的话加入字典并......
  • 题解：P10844 [EGOI2024] Infinite Race / 无限赛跑
    题解：P10844[EGOI2024]InfiniteRace/无限赛跑有n个人在环形跑道上跑步，和q次超越别人或被别人超越，别人要么在Anika前面，要么在后面怎么说呢，建议降红由于只有重复超过一个人才肯定是跑过一圈的，所以一个数组就行了，每超过一次就打上标记，不然去掉标记。#include<bits/stdc......
  • 题解：AT_iroha2019_day1_f Head of The Dragon
    题目大意得知\(n\)和\(k\),求出\(n\)是否能分解出\(k\)个因数相乘，输出按字典序最小一种情况。步骤将\(n\)分解质因数。判断质因数个数是大于\(k\)，否则输出\(-1\)。按照分解出来的质因数从小到大输出。代码#include<bits/stdc++.h>#defineintlonglongus......
  • 牛客周赛 Round 56
    牛客周赛Round56\(A\)牛客NC277678面包店故事\(AC\)选择结构。点击查看代码intmain(){intx,y,n;cin>>x>>y>>n;if(x+y<=n){cout<<"YES"<<endl;}else{cout<<"NO&qu......
  • Big Clique Everywhere 题解
    给个链接：BigCliqueEverywhere。先说一下团（clique）是什么，其实就是完全图。考虑什么情况下不满足题意。我们可以先建出补图，下面的东西都在补图中完成。我们首先给出结论：如果该图中有奇环（不是二分图），则条件不成立，否则成立。这里证明一下：如果存在奇环，则把点集设为这个奇环中的点，那......
  • 题解：AT_abc367_c [ABC367C] Enumerate Sequences
    大致题意让你按照字典序输出一些长\(n\)的序列，序列中的数字有范围，且序列和需要为\(k\)。分析直接深搜。搜索的时候对从第一个元素开始，每个元素从小到大枚举所有可能的值，这样就保证答案按照字典序升序排列。用一个vector存储序列，到达边界之后计算一遍和，判断是否满足条件，然......
  • 2024百度之星决赛部分题解(难度排序前六题)
    前言手速6题，可惜第四题磨了几个小时没磨出来，多做一题就金了，还是实力差了点，最后银牌前列。下面的题解是根据代码回忆大概的题意，主要是给出来赛时的参考代码A.状压题意:学校集训队总的有\(n\)个人，保证\(n\)是3的倍数，每个人有个人实力\(a_i\)，每两个人之间有配合程度\(b_{i......
  • 洛谷P1983 [NOIP2013 普及组] 车站分级 题解
    思路由题可知，在一趟车次的区间内，停靠的站点的等级恒大于不停靠的站点。因此，对于每一趟车次的区间，给所有停靠的站点向所有不停靠的站点两两连有向边，然后求图中最长的路径长度，就能得到答案。实现因为可能出现重边，而且\(n\le1000\)，所以在处理车次连边的时候使用邻接矩阵，再改成邻......
  • LeetCode 556. 下一个更大元素 III（next_permutation()）
    题目：556.下一个更大元素III思路：用到next_permutation()，细节看注释。next_permutation、prev_permutationclassSolution{public:intnextGreaterElement(intn){ //转变为string类型，便于调用next_permutation()strings=to_string(n);......
  • P10660 BZOJ2759 一个动态树好题 题解
    从题目名字看出此题需要用动态树解决对于任意\(i\)，都有唯一的\(p_i\)与之对应，由\(p_i\)向\(i\)连边，\(n\)种关系显然构成一基环树森林。对于环上的节点，一个点可以自己表示自己，所以可以直接解出该点的权值，其他点从环上的点直接推出即可。考虑如何动态维护这个过程，一个点上......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99