oi提高杯模拟赛

1、提交源程序需加后缀最终测试时，所有编译命令均不打开任何优化开关。测试环境：Cena 0.8.1 Windows 7 Home Premium 64-bit Edition C/C+ 语言使用 GCC 版本 4.6.1 进行编译。Pascal 语言使用 FPC 版本 2.0.2 进行编译。附注：在第二题中要用到积的概念。对于集合 A 和集合 B ，它们的积（又称直积）表示为 A B 。其定义为 A B : (x, y) | x A y B 。对于 Pascal 语言alternate.pasd.pasangel.pas对于 C 语言alternate.cd.cangel.c对于 C+ 语言alt

2、ernate.cppd.cppangel.cpp题目名称交替和最优指令天使玩偶程序文件名alternatedangel输入文件名alternate.ind.inangel.in输出文件名alternate.oommand.outangel.out每个测试点时限1 秒1 秒20 秒内存限制512 MB512 MB512 MB测试点数目101020每个测试点分值10105是否有部分分无无无交替和(alternate.pas/ p)定义域为, n 内的整数，值域为实数集的函数f :, n R 又被称为有限序n列。而 f 的交替和定义为 A( f ) : ()k f (k ) 。现在k 一种特殊的数列

3、 L的交n,b替和。Ln,b 是这样生成的：假设序列 L 一开始是“空的”。之后，按照从小到大的顺序将, n中的整数在b 进制中的表示，从到低位逐位“添加”进序列 L 。最后得到的 L 即为 Ln,b 。举例来说，在2 进制下5 表示为101，那么 L, 即为数列,。这是将数,在 2 进制下的表示,逐位“添加”的结果。现在对于给定的整数b, n ，你需要计算 A(Ln,b ) 的值。输入格式输入文件包含一行两个整数b, n 。输出格式输出一个整数表示 A(Ln,b ) 的值。样例输入2 5样例输出1数据范围与约定对于 20% 的数据，满足 n 。对于 100% 的数据，满足 n ， b 。最优

4、指令(d.pas/p)现在来 一种 机 器的抽 象 模型。 这 种机器 有 一个有 限 的状态 集S s , s, s , sn 和一个有限的指令集C c , c, c , cm 。机器在任意时刻都处于某一种状态 s S 。同时，机器还有一个转移函数 f : S C S ，表示机器在当前状态下接到某个指令之后会转移到的状态，亦即机器在状态 s 下接到指令c 后状态会变成 f (s, c) 。现在对于一个机器的实例，你需要计算一个最短的指令序列，使得对于任意一个状态 s ，按照顺序经过序列中的所有指令之后机器一定会处于状态 s 。输入格式第一行包含两个整数 S和 C。之后 S行，每行 C个整数。

5、若输入文件中的行和列均从 1 开始标号，那么第i 行第 j 列的数为 k 就表示 f (si , c j) sk ( k S ) 。输出格式输出你求得的最短指令序列。你需要将指令的下标连续输出，并且输出下标的十六进制值，表示法中的字母用小写字母表示。若最短的序列不唯一，输出任一个即可。若这样的序列不存在，输出 im sible。样例输入30116210201002002212样例输出03数据范围与约定对于全部数据，保证 S ，C ，输入数据保证是合法的。 天使玩偶(angel.pas/p)Ayu 在七年前曾经收到过一个天使玩偶，当时她把它当作时间囊埋在了的今天，Ayu 却忘了她把天使玩偶埋在了

6、哪里，所以她决定仅凭一点模糊的。而七年后来寻找它。把 Ayu 生活的小镇看作一个二维平面坐标系，而 Ayu 会不定时地记起可能在某个点(x, y) 埋下了天使玩偶；或者 Ayu 会询问你，假如她在(x, y) ，那么她离最近的天使玩偶可能埋下的地方有多远。因为 Ayu 只会沿着平行坐标轴的方向来行动，所以在这个问题里定义两个点之间的距离为 dist( A, B) Ax Bx Ay By。其中 Ax 表示点 A 的横坐标，其余类似。输入格式第一行包含两个整数 n 和m ，在刚开始时，Ayu 已经知道有 n 个点可能埋着天使玩偶，接下来 Ayu 要进行 m 次操作接下来 n 行，每行两个非负整数

7、xi , yi ，表示初始 n 个点的坐标。再接下来 m 行，每行三个非负整数t, xi , yi 。如果t ，则表示 Ayu 又回忆起了一个可能埋着玩偶的点(xi , yi ) 。如果t ，则表示 Ayu 询问如果她在点(xi , yi ) ，那么在已经回忆出来的点里，离她最近的那个点有多远输出格式对于每个t 的询问，在单独的一行内输出该询问的结果。样例输入212212313134232样例输出12数据范围与约定各组数据的范围如下表。n,mxi,yit250050001,21 000100 0001,24650 0001 5001,28100 0002 0001,210500 000500 0001,212100 000100 000200020001,20001,220300 0001 000 0001,219300 0001 00