河南省高中组选拔赛试题（一试）
河南省信息学奥林匹克竞赛试题（高中组选拔赛一试）
地市 学校 考号 姓名
考试时间：210分钟（3小时半） 文件命名：文件名为标题英文文件名 所有测试点时限：1s 存放位置：由机房负责人确定程序存放的地方。
第一题 数字序列(sequence)
现在我们有一个长度为n的整数序列A。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。
【输入文件sequence.in 】
第一行包含一个数n，接下来n个整数按顺序描述每一项的键值。
【输出文件sequence.out 】
第一行一个整数表示最少需要改变多少个数。
第二行一个整数，表示在改变的数最少的情况下，每个数改变的绝对值之和的最小值。
【样例输入】 4 5 2 3 5 【样例输出】 1 4
河南省高中组选拔赛试题（一试）
【数据范围】 90%的数据n<=6000。 100%的数据n<=35000。 保证所有数列是随机的。
第二题 旅行(comf)
Z小镇是一个景色宜人的地方，吸引来自各地的观光客来此旅游观光。Z小镇附近共有N个景点（编号为1,2,3,…,N），这些景点被M条道路连接着，所有道路都是双向的，两个景点之间可能有多条道路。也许是为了保护该地的旅游资源，Z小镇有个奇怪的规定，就是对于一条给定的公路Ri，任何在该公路上行驶的车辆速度必须为Vi。速度变化太快使得游客们很不舒服，因此从一个景点前往另一个景点的时候，大家都希望选择行使过程中最大速度和最小速度的比尽可能小的路线，也就是所谓最舒适的路线。
【输入文件comf.in 】
第一行包含两个正整数，N和M。
接下来的M行每行包含三个正整数：x，y和v。表示景点x到景点y之间有一条双向公路，车辆必须以速度v在该公路上行驶。
最后一行包含两个正整数s，t，表示想知道从景点s到景点t最大最小速度比最小的路径。s和t不可能相同。
【输出文件comf.out 】
如果景点s到景点t没有路径，输出“IMPOSSIBLE”。否则输出一个数，表示最小的速度比。如果需要，输出一个既约分数。
【样例输入】 4 2 1 2 1 3 4 2 1 4
河南省高中组选拔赛试题（一试）
【样例输出】 IMPOSSIBLE
【样例输入】 3 3 1 2 10 1 2 5 2 3 8 1 3
【样例输出】 5/4
【样例输入】 3 2 1 2 2 2 3 4 1 3
【样例输出】 2
【数据范围】 1 1≤x,y≤N，0 第三题 受欢迎的牛(cow) 每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。这种关系是具有传递性的，如果A认为B 河南省高中组选拔赛试题（一试） 受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。 【输入文件cow.in 】 第一行两个数N,M。 接下来M行，每行两个数A,B，意思是A认为B是受欢迎的（给出的信息有可能重复，即有可能出现多个A,B） 【输出文件cow.out 】 一个数，即有多少头牛被所有的牛认为是受欢迎的。 【样例输入】 3 3 1 2 2 1 2 3 【样例输出】 1 【数据范围】 10%的数据N<=20, M<=50 30%的数据N<=1000,M<=20000 70%的数据N<=5000,M<=50000 100%的数据N<=10000,M<=50000