CCF NOI Online2022
提高级
时间：2022年3月26日8:30∼12:00
题目名称丹钓战讨论如何正确地排序
题目类型传统型传统型传统型
输入文件名stack.in discuss.in sort.in
输出文件名stack.out discuss.out sort.out
每个测试点时限1.0秒1.0秒3.0秒
内存限制512MB512MB512MB
测试点数目201010
测试点是否等分是是是
提交源程序文件名
对于C++语言stack.cpp discuss.cpp sort.cpp
编译选项
对于C++语言-lm-O2
注意事项
1.文件名（程序名和输入输出文件名）必须使用英文小写。
2.C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。
3.提交的程序代码文件的放置位置请参考各省的具体要求。
4.因违反以上三点而出现的错误或问题，申述时一律不予受理。
5.若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。
6.程序可使用的栈空间内存限制与题目的内存限制一致。
7.全国统一评测时采用的机器配置为：Inter(R)Core(TM)i7-8700K CPU@3.70GHz，内存32GB。
上述时限以此配置为准。
8.只提供Linux格式附加样例文件。
9.评测在当前最新公布的NOI Linux下进行，各语言的编译器版本以此为准。
丹钓战（stack）
【题目描述】
有n个二元组(a i,b i)，编号为1到n。
有一个初始为空的栈S，向其中加入元素(a i,b i)时，先不断弹出栈顶元素直至栈空或栈顶元素(a j,b j)满足a i=a j且b i<b j，然后再将其加入栈中。
如果一个二元组入栈后栈内只有这一个元素，则称该二元组是“成功的”。
有q个询问[l i,r i]，表示若将编号在[l i,r i]中的二元组按编号从小到大依次入栈，会有多少个二元组是“成功的”。
询问之间相互独立。
【输入格式】
从文件stack.in中读入数据。
第一行两个正整数n,q。
第二行n个正整数表示a i。
第三行n个正整数表示b i。
少儿编程排名前十名接下来q行，每行两个正整数l i,r i，表示一组询问。
【输出格式】
输出到文件stack.out中。
q行，每行一个自然数表示一组询问的答案。
【样例输入】
104
3131233211
101029754761
14
78
710
18
【样例输出】
3
2
2
3
【样例解释】
以第一次询问[1,4]为例。
一开始栈为{}。
加入1号二元组后栈为{(3,10)}，栈中只有一个元素，该二元组是“成功的”。
加入2号二元组(1,10)时，栈顶的(3,10)的b值不大于2号二元组的，因此弹栈。此时栈空，2号二元组入栈，栈为{(1,10)}，该二元组是“成功的”。
加入3号二元组(3,2)，此时栈顶元素与之a值不同，b值比它更大，因而不需要弹栈，直接将3号二元组入栈，栈为{(1,10),(3,2)}，栈中有多个元素，该二元组不是“成功的”。
加入4号二元组(1,9)，此时栈顶元素(3,2)的b值比它小，弹栈。弹栈后栈顶元素(1,10)与(1,9)的a值相同，继续弹栈。此时栈空，4号二元组入栈，栈为{(1,9)}，该二元组是“成功的”。
共有3个二元组是“成功的”，因而答案为3。
【样例2,3,4】
见选手目录下的stack/stack*.in与stack/stack*.ans。
【数据范围与提示】
对于所有测试点：1≤n,q≤5×105，1≤a i,b i≤n，1≤l i≤r i≤n。
每个测试点的具体限制见下表：
测试点编号特殊限制
1∼3n,q≤1000
4∼6n≤5000
7∼10n,q≤105
11∼12b i=n−i+1
13∼15a i=i
16∼20无
讨论（discuss）
【题目描述】
有n个人正在打模拟赛，模拟赛有n道题目。
有两人都会的题目并且没有人会的题目包含另一个人时，两者之间才会讨论。
（定义第i个人会的题目的集合为S i，即当S x∩S y=∅∧S x⊈S y∧S y⊈S x时，第x人和第y 人会讨论）
为了让模拟赛的效果更好，希望你可以出一对会讨论的人或判断不存在。
【输入格式】
从文件discuss.in中读入数据。
第一行一个正整数T表示数据组数，对于每组数据：
第一行一个正整数n表示人数和题目数量。
接下来n行，第i行第一个自然数k i表示第i个人会k i道题。接下来k i个正整数，每个数x 表示第i个人会第x道题。
【输出格式】
输出到文件discuss.out中。
对于每组数据：
如果没有会讨论的人，输出NO。
否则第一行输出YES，第二行输出两个正整数x和y，表示第x人和第y人会讨论。
如果有多种方案，输出任意一种即可。
【样例1输入】
2
5
41235
3123
212
11
14
4
3123
3234
41234
【样例1输出】
NO
YES
12
【样例2】
见选手目录下的discuss/discuss2.in与discuss/discuss2.ans。【数据范围与提示】
对于所有测试点：令一组数据中m=∑
k i，则1≤T≤5，1≤
∑
n≤106，1≤
∑
m≤2×106，
0≤k i≤n。
每个测试点的具体限制见下表：
测试点编号特殊限制
1n≤300
2∼3n≤1000
4n≤5000
5∼7n≤5×104
8k i≤10
9∼10无

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。