师大附中集训-202-72jsoi200冬小营day4训练题

实战训练本次训练共４题，时间为4小时，满分400分对于输入数据较大的题目，使用 来提高文件的速度通过实战训练，加强基本功训练，提高正确率和稳定性，提高解决问题的能题目名最短等矩形覆朋友分寻找捷主文件输入文输出文测试点个各测试点分7时间限1111空间限【问题描述

少时间请你写一个程序，选择一条旅行路径使 在满足上面条件下车站等车时间最少【输入5个整数N，P，V，T1，T2，2<=N<=10001<=p<=100000,1<=V<=1000，1<=T1<=T2<=50,000。N表示车站的数目，P的数目，V是火车的数目，T1和T2的意思面已经了PS1，S2TS1到S2（反之亦然）需要T秒，1<=T<=600。接下来的V行，每行包含一辆火车的信息。第一个整数T0表示火车的出发时间，第二个数NS表示该火车的路径上有多少车站（包括起始站和终点站1<=NS<=1000。后面的NS个数按照顺序列出了火车将要经过的车站。火车到达终点站就停在那里不动了，所有【输出【样例4433012232434241242【问题描述Mickey坐在已经升空的飞机上俯瞰大地，他发现土地被分成了很多个不同的矩形状，且由于覆盖的植被不同而显出不同的颜色。Mickey想寻找一个最大的矩形，它里面只显出一种颜色。在以下几张图中你可以看见每个矩形为一种颜色，若有多个矩形覆盖，则以最后一个矩形颜色为准。样例中的几幅图，其中最终的答案区域已经被标记了出来。 请你编写一个程序计算一下所能看到的这样的矩形的面积，当然你可以放心，没有任何两块会互相，然而二个矩形之间允许有共同点或公共边。【输入第一行将包含一个数字N（1<=N<=2,500），它代表着土地上一共有N个矩形块。Y1、X2、Y2（0<=X1，Y1，X2，Y2<=1,000,000,000）围成的这样一个矩形块里显示出了颜 C（1<=C<=100）【输出Pascal的int64，C/C++的longlong以内。【样例】13【问题描述有n个人，为1～n，告诉你哪些人之间是不友好的。现在，让你将这n个人分成两组，使得每一组之内的人是互相友好的，如果可以分成两组，则输出如何分组的，如果不可以分成两组，那么，输出“IMPOSSIBLE”。【输入不友好的人的对数。以下m行每行两个数a和b，表示a与b是不友好的。【输出直接用一个空格隔开，最后一个之后没有空格。如果不能分成两组，输出54141524251234【样例说明有两种方案：“12345”和“12345”，两种方案的字典序相同，取第一组【数据范围40%的数据100%的数 n<=50,000，m<=500,000【问题描述

Mirek有一条每天从他家去大学工作的最喜欢的路。这个路径由若干个部分组成，且每个部分是10的直线。每一个部分是直线连接（没有拐弯）上一个部分或垂直连接上一Mirek会休息下欣赏美丽的自然景色。在他走路的过程之中，他不会重复一个地点。 除非他改变他平时走的路径。他计划找一条捷径（shortcut）但他希望捷径尽量的短。捷径必须是水平的或者是垂直的并且连接两个Mirek原先路径的休息的地点。请帮助Mrek找到最短的捷径。写一个程序：读入Mirek的路径，计算路径上面最短的捷径，输出结果。【输入文件第一行包含一个整数n（3<=n<=250000）作为路径的部分的个数。第二行包含一组长度为n的序列，每个字母为N，E，S或W，之间没有空格。每一个字母描述路径的一个部分。字母N，E，S或W表示Mirek向这些方向走了10米。你可以假设至少存在一个捷径。【输出文件第一行也就是唯一的一行包括l，b，e3个整数和一个字母d，用空格隔开。整型变量l是最短的捷径（以长度10为单位）。整数b和e是休息点的，也就是捷径的起点和终（Mirek的home的为0，大学的为n。字母d