简单的测试题

发表于 更新于 阅读次数： 本文字数： 3.5k 阅读时长 ≈ 3 分钟

题目来源于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.o和specio.ppu复制到%fpc\units\i386-win32目录下。
  • 在程序开头加上uses specio;。