简单的测试题

题目来源于USACO月赛,数据范围有所加强

题目概述

项目名称 排序 录制 #加法解释 #新挑战*
文件名 sort.* record.* interpreter.* challenge.*
时间限制 2s 1s 1s 5s
空间限制 512MB 512MB 512MB N/A
测试点数量 20 10 14 3
测试点分值 5 10 7~8 N/A
额外的编译选项 -O2 -O2 …
类型 传统 传统 传统 交互
比较方式 全文 SPJ 全文 全文
部分分

注意事项

  1. 所有题目中程序允许创建临时文件(仅供参考)。在C/C++中建议使用tmpfile函数创建临时文件,在关闭文件后将自动删除。
1
2
3
4
5
6
#include<stdio.h>
FILE *tmpfile( void );
//C
#include<cstdio>
std::FILE* std::tmpfile();
//C++
  1. 新挑战*为附加题,同时测试交互题的情况。
  2. 对于#标的题,请注意常数因子对于程序效率的影响(标程最长运行时间超过时限的一半)。

1.排序

题目描述

有n($n\le50000$)个物品,编号为$1\ldots n$,物品i的重量为$w_i$,每个物品的重量各不相同。现在需要对这n个物品按照重量排序,已经用天平进行了m($m\le200000$)次比较,一次比较结果用(i,j)表示。求至少再进行多少次比较才能完成排序。

输入格式

第一行两个整数n,m

接下来m行,每行两个整数i,j,表示$w_i>w_j$

输出格式

一个整数表示至少再进行多少次比较才能完成排序,如果给出的条件自相矛盾输出-1

输入样例

1
2
3
4
5
6
5 5
2 1
1 5
2 3
1 4
3 4

输出样例

1
3

样例解释

有5个物品,已经比较了5次。因为$w_2>w_1>w_5,w_2>w_3>w_4$,所以物品2是最重的。但是,还需要比较物品1和物品3的重量,才能知道第二重的物品。同理,还需要比较物品4和物品5,物品5和物品3,才能完成排序。

数据范围

  • 对于30%的数据,$n\le500,m\le5000$

  • 对于60%的数据,$n\le3000$

  • 对于100%的数据,$n\le50000,m\le200000$

2.录制

题目描述

一场运动会中有n($n\le100000$)个项目需要录制,编号为$1\ldots n$,其中第i个项目的时间$s_i\ldots t_i(0\le s_i\le t_i\le10^9)$。现在有k($k\le n$)台录像机,编号为$1\ldots k$,两个项目i,j可以被同一台录像机录制,仅当$s_j\ge t_i$。求出最多可以录制的项目数量,并任意输出一种可行解(有SPJ)。

输入格式

第一行两个整数n,k

接下来n行,每行两个整数$s_i,t_i$

输出格式

第一行一个整数,表示最多可以录制的项目数量

接下来k行,第一个整数t表示该台录像机录制的项目数量,接下来t个整数表示该台录像机录制的项目编号

注意:项目编号应该按时间升序输出

输入样例

1
2
3
4
5
6
7
6 2
0 3
6 7
3 10
1 5
2 8
1 9

输出样例

1
2
3
4
2 4 2
2 1 3

样例解释

有6个项目,2台录像机。最多只能录制4个项目,比如在第一台录像机上录制项目2、4,在第二台录像机上录制项目1、3.需要注意的是,解不唯一,如交换两台录像机录制的项目也是可行解。

数据范围

测试点编号 n的范围 k的范围
1 $n\le10$ k=1
2 $n\le150$ k=1
3 $n\le100000$ k=1
4 $n\le150$ k=2
5 $n\le100000$ k=2
6 $n\le1000$ $k\le10$
7 $n\le100000$ $k\le10$
8 $n\le10$ $k\le n$
9 $n\le100000$ $k\le n$
10 $n\le100000$ $k\le n$

部分分

  • 如果你的答案不正确,得分为0

  • 如果你的答案正确,但没有输出可行解或可行解错误,得分为5

  • 如果你的答案正确,且输出正确的解,得分为10

3.加法解释

题目描述

PL/S是一种简单高效的语言,有两个主要的功能:加法和循环。由于多次加法可能会溢出,因此规定所有加法运算都对$10^9+7$取模。更加高级的是循环功能,能够执行一段代码若干次。当然,循环是可以嵌套的。

现在给出一个PL/S语言的源代码,请输出其执行结果。

输入格式

给出的PL/S代码不超过100行,每行不超过350个字符。PL/S语言有三种语句(注意空格):

1
2
3
4
5
6
7
<variable> = <expression>

<literal> LOOP {
<list of statements>
}

PRINT <variable>

有三种类型的表达式:

1
2
3
4
5
<literal>

<variable>

<expression> + <expression>

其中variable是长度不超过10的变量名,全部为小写字母。

literal是不超过100000的正整数。

数据保证没有变量在定义前被使用,PRINT语句只出现在程序最后一行。

习惯上语法描述均不翻译

输出格式

一个正整数表示PRINT语句后变量的值。

输入样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#1:
x = 1
10 LOOP {
x = x + x
}
PRINT x
#2:
n = 1
nsq = 1
100000 LOOP {
100000 LOOP {
nsq = nsq + n + n + 1
n = n + 1
}
}
PRINT nsq

输出样例

1
2
3
4
#1:
1024
#2:
4761

样例解释

样例#1中PL/S程序计算了$2^{10}$

样例#2中PL/S程序计算了$(100000*100000+1)^2\mod(10^9+7)$

数据范围

  • 测试点#1~#4,LOOP循环不嵌套

  • 测试点#5~#9,程序中只有一个变量,但LOOP循环可以嵌套

  • 测试点#10~#14,没有特殊限制

4.新挑战*

背景描述

本题不来自USACO月赛

还记得WC 2017第二题挑战吗?这是我的新挑战系列的第二题,第一题在我的创新题目中。

这次,仍然让我们来排序吧,只不过现在排序的是浮点数而已。

题目描述

有n($n\le10^8$)个32位单精度浮点数(C/C++中的float,Pascal中的single),请在规定的限制下给这些数排序。

输入格式

由于本题输入输出规模非常大,所以使用交互库输入输出。

四个32位整数a,b,x,n。

交互库原型

1
2
3
void init(int a,int b,int x);
float readNext(void);
int writeNext(float x);
1
2
3
procedure init(a,b,x:longint);
function readNext:single;
function writeNext(x:single):longint;

首先调用init(a,b,x),然后调用n次readNext得到n个浮点数,最后按顺序调用n次writeNext

注意:请务必在调用完所有readNext后再调用writeNext,否则可能会导致答案错误。

输出格式

一个32位整数,为最后一次调用writeNext函数的返回值。

输入样例

1
148781241 333135714 547124561 6

输出样例

1
1282166852

样例解释

6个浮点数分别为5.73938e-018,1.92782e+034,-4.63247e+008,-3.8978e+030,2.16839e-035,-54.5559。

数据范围

测试点编号 n的范围 内存限制 分值
1 $n=200000$ 4MB 20
2 $n=2*10^7$ 4MB 40
3 $n=10^8$ 1GB 40

保证输入数据中没有NaN和-0,但可能有0、inf和-inf。

交互库说明

交互库的名称为specio(special I/O library)。

C/C++选手

  • 找到MinGW安装的位置,设为%mingw
  • specio.h复制到%mingw\%arch\include目录下,其中%arch为编译器的目标体系,如x86_64-w64-mingw32,不同版本目录可能不同。
  • libspecio.a(C语言为libcspecio.a)复制到%mingw\%arch\lib目录下。
  • 在程序开头#include<specio.h>
  • 编译程序时,加上-lspecio选项即可。

Pascal选手

  • 找到Free Pascal安装的位置,设为%fpc
  • specio.ospecio.ppu复制到%fpc\units\i386-win32目录下。
  • 在程序开头加上uses specio;