师大附中集训

1、中山市市队 NOI2011 模拟赛第一试命题人竞赛时间：2011 年 7 月 xx 日上午 8:00-13:00提交源程序须加后缀注意：最终测试时，所有编译命令均不打开任何优化开关对于 Pascal 语言killassequence.passquares.pas对于 C语言killer.csequence.csquares.c对于 C+语言killer.cppsequence.cppsquares.cpp题目名称序列完全平方数目录killersequenquares可执行文件名killersequenquares输入文件名killer.insequence.insquares.in输出文件名k

2、iller.outsequence.outsquares.out每个测试点时限1 秒1 秒1 秒内存限制512 兆512 兆512 兆测试点数目101010每个测试点分值101010是否有部分分无无无题目类型传统传统传统第一题【问题描述】一位冷血的潜入 Na-wiat，并假装成平民。希望能在 N 个人里面，查出谁是。能够对每一个人进行查证，假如查证的对象是平民，他会告诉，他认识的人，谁是，谁是平民。假如查证的对象是将会把干掉。现在掌握了每一个人认识谁。每一个人都有可能是，可看作他们是的概率是相同的。问：根据最优的情况，保证少？自身安全并知道谁是的概率最大是多【输入文件】输入文件 killer.

3、in，第一行有两个整数 N,M。接下来有 M 行，每行两个整数 x,y，表示 x 认识 y（y 不一定认识 x,例如胡）。【输出文件】输出文件 killer.out 仅包含一行一个实数，保留小数点后面 6 位，表示最大概率。【输入样例】5111142345【输出样例】0.800000第 2 页 共 6 页第一题【样例解释】只需要查证 1。假如 1 是，就会被杀。假如 1 不是，他会告诉警但没被杀的概察 2,3,4,5 谁是率是 0.8。而 1 是的概率是 0.2,所以能知道谁是【数据规模】对于 30%的数据有 1N 10,0M 10对于 100%的数据有 1N 10 0000,0M30 000

4、0第 3 页 共 6 页第二题 序列序列【问题描述】小 W 很喜欢序列，尤其喜欢“W”形的和“M”形的序列。定义“M”形的序列为一个长度为 T 的序列Si，满足：存在 1 x y z N，使得 S1 . . Sy . . ST。一天他看到了一个长度为 N 的整数序列Ai，他想通过一些修改把序列变成 “M”形的。但这时小 X 过来了，说这个序列是他的，小 W 如果想要修改就要支付一定的费用。每支付一 的费用，小 W 都可以进行这样的操作：将一段连续的数同时加上 1，即选定 i, j 满足 1 i j N 并令 Ai, Ai+1, ., Aj 均加上 1。小 W 想用最小的费用将序列变成“M”形的

5、。但是有个条件：如果他修改成的目标是序列Bi满足 B1 . . By . . BN，那么必须有 Ay=By。现在，他希望你来帮他计算最小费用。【输入文件】输入文件 sequence.in 第一行包含一个整数 N，表示序列 A 的长度。第二行有 N 个整数给出初始的序列Ai。【输出文件】输出文件 sequence.out 仅包含一行，为最小的花费。【输入样例】52 1 2 2 3【输出样例】4【数据规模】对于 30%的数据满足 N 1 000；对于 100%的数据满足 5 N 100 000，0 Ai 109。第 4 页 共 6 页第三题 完全平方数完全平方数【问题描述】小 X 自幼就很喜欢数。

6、但奇怪的是，他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。这天是小 X 的生日，小 W 想送一个数给他作为生日。当然他不能送一个小 X 讨厌的数。他列出了所有小 X 不讨厌的数，然后选取了第 K 个数送给了小 X。小 X 很开心地收下了。然而现在小 W 却记不起送给小 X 的是哪个数了。你能帮他一下吗？【输入文件】输入文件 squares.in 包含多组测试数据。文件第一行有一个整数 T，表示测试数据的组数。第 2 至第 T+1 行每行有一个整数 Ki，描述一组数据，含义如题目中所描述。【输出文件】输出文件 squares.out 含 T 行，分别对每组数据作出回答。第 i 行输出相应的第 Ki 个不是完全平方数的正整数倍的数。【输入样例】41131001234567【输出样例】1