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

A 面包店故事

题面

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

输入

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

输出

如果小歪能加到培根，在一行上输出 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(1≤n≤10⁵; 0≤m≤10⁵; 1≤k≤10⁹) 代表班级同学数量、留下来的同学数量和叠一只纸飞机需要的纸的数量。  第二行输入 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 组询问，76 每次询问都会给出一个正整数 a ，你需要在区间 [1, 10⁹] 中找到两个正整数 b 和 c ，使得 b ⊕ c = a。 ⊕ 代表按位异或。

输入

每个测试文件均包含多组测试数据。第一行输入一个整数 T (1 ≤ T ≤ 10⁵) 代表数据组数，每组测试数据描述如下： 在一行上输入一个整数 a ( 1 ≤ a ≤ 10⁹ ) 代表 76 给出的初始数字。

输出

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

样例1

输入

3
1
5
4

输出

2 3
3 6
74 78

说明 对于第一组测试数据，(10)₂xor (11)₂ = (01)₂ 对于第二组测试数据，(011)₂xor (110)₂ = (101)₂

题解

这题我们主要是利用异或的性质 简单来说就是： $$ \begin{aligned} a \oplus b = c \\ a \oplus c = b \\ b \oplus c = a \end{aligned} $$

要证明也很容易 $$

$$ 这样应该直观一点啦

然后，我们可以取一个数作为异或的主要对象，比如本题的上限 1e9 但是要注意：异或之后得到的结果可能是 0 或者大于 1e9 所以要做一个特判：假如存在上述情况，就让异或的数字变成 1e9 ≫ 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(1≤T≤20) 代表数据组数，每组测试数据描述如下： 第一行输入一个整数 n(3≤n≤10⁴) 代表 小S 的火柴数量。 第二行输入 n 个整数 a₁, a₂, …, a_n(1≤a_i≤10⁹) 代表每根火柴的长度

输出

对于每一组测试数据，在一行上输出一个整数，代表能组成周长最大三角形的周长；如果无论如何都无法组成三角形，直接输出 −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 ≥ 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(1≤n,m≤10⁵) 代表 小C 感到开心的时间段数量和 小C 喜欢的奶茶数量。 此后 n 行，第 i 行输入两个长度为 5 ，且形如 hh : mm 的字符串代表 小C 第 i 段感到开心的起止时间，保证每一段开心时间不超过 24 小时。除了这 n 个时间段外，剩余时间她都是不开心的。 第 n + 1 行输入 m 个长度不超过 10 且由大小写字母混合构成的字符串 s₁, s₂, …, s_m 代表 小C 喜欢喝的奶茶名字。 第 n + 2 行输入一个整数 q(1≤q≤10⁵) 代表 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;
}

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