SYZOJ 480【WQH大佬的逃♂离】 的题解

2024-02-11 18:20
文章标签 大佬 题解 480 syzoj wqh

本文主要是介绍SYZOJ 480【WQH大佬的逃♂离】 的题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这道题是我在英语课的时候感觉无聊,而又看到WQH大佬,于是突发灵感,想出了这道水题。

题目描述

众所周知,WQH大佬非常NB,所以经常有很多人来找WQH大佬问问题或者Van♂游戏。

但是WQH不能在别人身上花太多时间,因为他还有一个【数据删除】,WQH每天需要抽一些时间陪【数据删除】van♂游戏。

WQH每天有t个单位时间,而每天都有n个人来找WQH大佬,第i个人会在l[i],r[i]的单位时间段内围在WQH大佬身边,假如在某个时间段WQH大佬身边没有人,他就可以陪【数据删除】van♂游戏。但是因为来找WQH大佬的人实在是太多了,所以WQH决定找一个“性♂运”学生,让这个“性♂运”学生改天再来,从而让自己有更多的时间来陪【数据删除】van♂游戏。

但是WQH大佬和【数据删除】van♂的太多了,所以WQH大佬感到一丝虚♂弱,所以就来找你帮忙,将哪一个学生作为“性♂运”学生可以让WQH大佬陪【数据删除】的时间最多。如果无解,则输出 ”and*kgou“。 无解情况指无论让哪个学生作为性♂运学生,都不能使WQH大佬陪【数据删除】van♂的时间更多.

WQH大佬:“你有毒吧?”。

本蒟蒻第一次出题,真·原创题,可能比较水,数据也是随机数。如果有错误,欢迎指正!
感谢@door♂阳提供的5组毒瘤数据(你们T掉的点都是他出的!)和样例解释!

输入格式

第一行一个整数T,表示有T组数据

接下来的T组测试数据:

第一行有2个整数n,t,用空格隔开,分别表示有多少个人来找WQH大佬,而WQH大佬有t各单位时间。

接下来n行,每行2个整数l,r,用空格隔开,分别表示第i个人在l,r单位时间段会在WQH大佬身边。

友情提示:最好~~(必须)~~加一个快读

输出格式
T行。

两个整数分别代表 “性♂运”学生的编号 和 把那个学生作为“性♂运”学生可以获得陪【数据删除】van♂游戏的时间。

如果无解,则输出 ”and*kgou“

(因为Andy真的可gou)

样例:

input

1
3 8
1 8
2 4
5 7

output

1 3

样例解释

图中红色曲线部分为选中的人,直线上红色区域为空闲时间。

input

4
10 23
4 15
16 19
15 18
18 18
7 11
20 22
20 21
23 23
14 21
7 85 35
32 32
5 25
27 32
7 27
15 2010 45
2 15
38 42
15 42
32 41
26 35
42 45
14 43
6 33
13 14
19 456 38
32 35
23 38
21 30
6 26
6 28
24 38

output

1 6
3 5
1 4
and*kgou

说明:

对于20%的数据 n<=100,t<=1000

对于40%的数据 n<=10000,t<=100000

对于100%的数据 n<=5000000,t<=5000000,T<=10;

思路:

经过一番摸♂索,便会发现,要找到的那个学生只要是独自占有时间最长就好了,因为把这个学生赶走后,他独自占有的时间就回变成WQH大佬的空闲时间。所以只需求出来这个学生是谁就可以了!如果每个学生都没有独自占有时间,那就是无解啦!(即每个时间段都被覆盖了两次!)

做法:

用差分数组求出每个时间段的人数。
再用前缀和求出每个时间段只被一个人占用的时间是多少。
最后枚举每个人的占用时间段,看谁独自占用时间最多就是它啦!
如果没有人有独自占用时间,那就是无解啦!

代码很简单:

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005int n,t,T;
long long sum[maxn],l[maxn],r[maxn];
long long a[maxn],b[maxn],ansNum,ansT;int main()
{
//	freopen("test11.out","w",stdout);
//	freopen("test11.in","r",stdin);cin>>T;while(T--){scanf("%d%d",&n,&t);for(int i=1;i<=n;i++){cin>>l[i]>>r[i];b[l[i]]++;b[r[i]]--;	}for(int i=1;i<=t;i++) a[i]=a[i-1]+b[i];for(int i=1;i<=t;i++) if(a[i] > 1) a[i]=0;for(int i=1;i<=t;i++) sum[i]=sum[i-1]+a[i];for(int i=1;i<=n;i++)if(sum[r[i]-1]-sum[l[i]-1] > ansT){ansT=sum[r[i]-1]-sum[l[i]-1];ansNum=i;}if(ansNum==0 && ansT==0)printf("and*kgou\n");elsecout<<ansNum<<" "<<ansT<<endl;		ansNum=0;ansT=0;memset(b,0,sizeof(b));}return 0;
}
写在后面:

这是本蒟蒻第一次出题,出不了太高妙的题。
自己出数据的时候经历了很多磨♂难,明白了出数据也是充满艰辛的!
不过自己出题还真是挺有趣♂的。
挺难忘的一次经历!

这篇关于SYZOJ 480【WQH大佬的逃♂离】 的题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/700505

相关文章

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

C - Word Ladder题解

C - Word Ladder 题解 解题思路: 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数(也就是需要变换多少次) 开始替换时: tips: 字符串下标以0开始 我们定义两个变量a和b,用于记录当前遍历到的字符 首先是判断:如果这时a已经==b了,那么就跳过,不用管; 如果a大于b的话:那么我们就让s中的第i项替换成b,接着就直接输出S就行了。 这样

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题,笔试真题 会在第一时间跟新 🍄 题面描述等均已改编,如果和你笔试题看到的题面描述

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析

LabVIEW程序员是怎样成长为大佬

成为一名LabVIEW编程领域的“大佬”需要时间、实践、学习和解决复杂问题的经验。尽管LabVIEW作为一种图形化编程语言在初期可能相对容易上手,但要真正成为精通者,需要在多个层面上深入理解。以下是LabVIEW程序员如何逐步成长为“大佬”的路径: 1. 打好基础 LabVIEW的大佬们通常在初期会打下非常坚实的基础,理解LabVIEW编程的核心概念,包括: 数据流编程模型:Lab

牛客小白月赛100部分题解

比赛地址:牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>

P2858 [USACO06FEB] Treats for the Cows G/S 题解

P2858 题意 给一个数组。每天把最左或者最右的东西卖掉,第 i i i个东西,第 d a y day day天卖出的价格是 a [ i ] ∗ d a y a[i]*day a[i]∗day。 记忆化搜索 void dfs(int l,int r,int day,ll sum){if(v[l][r]>=sum)return;v[l][r]=sum;if(l>r)//这就是dp答案{

【C++题解】1272. 郭远摘苹果

欢迎关注本专栏《C++从零基础到信奥赛入门级(CSP-J)》 问题:1272. 郭远摘苹果 类型:二维数组 题目描述: 郭远有一天走到了一片苹果林,里面每颗树上都结有不同数目的苹果,郭远身上只能拿同一棵树上的苹果,他每到一棵果树前都会把自己身上的苹果扔掉并摘下他所在树上的苹果并带走(假设郭远会走过每一棵苹果树),问在郭远摘苹果的整个过程中,他身上携带的最多苹果数与最小苹果数的差是多少?

【最新华为OD机试E卷-支持在线评测】机器人活动区域(100分)多语言题解-(Python/C/JavaScript/Java/Cpp)

🍭 大家好这里是春秋招笔试突围 ,一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-E/D卷的三语言AC题解 💻 ACM金牌🏅️团队| 多次AK大厂笔试 | 编程一对一辅导 👏 感谢大家的订阅➕ 和 喜欢💗 🍿 最新华为OD机试D卷目录,全、新、准,题目覆盖率达 95% 以上,支持题目在线评测,专栏文章质量平均 94 分 最新华为OD机试目录: https://blog.