2024年3月7日发(作者：)

NOIP模拟题bronze

刘启鹏

竞赛时间:2010年11月13日 8:30-11:30

注意:最终测试时,所有编译命令均不打开任何优化开关。

Linear T riple

【问题描述】

一个线性三元组是指一个满足如下关系有序三元组(s1,s2,s3:s3-s2=s2-s1.如(1,2,3,(2,4,6,(14,21,28都是满足条件的线性三元组.

对于给定的一个S个元素的集合(元素值在1..100间,请输出可以组成的线性三元组的数目。

【输入格式】

第一行:一个整数,S (3 <= S <= 30。

第二行:S个用空格隔开的整数.

【输出格式】

仅一行,包含一个整数,可以组成的线性三元组的数量,保证在长整形范围内。

【样例输入1】

7

1 2 3 4 6 8 9

【样例输出1】

5

【数据说明】

这些三元组是:

1 2 3

2 3 4

2 4 6

3 6 9

4 6 8。

NOIP模拟题bronze 刘启鹏P vs NP

P vs NP

【问题描述】

P/NP问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题,它被“克雷数学研究所”(Clay Mathematics Institute, 简称CMI在千禧年大奖难题中收录。P/NP问题中包含了复杂度类P与NP的关系。1971年Stephen A. Cook 和Leonid

Levin 相对独立的提出了下面的问题,即是否两个复杂度类P和NP是恒等的(P=NP?。

这个问题似乎难了点,放在NOIP第一题不太人道。放心,你需要解决的只是一个简化版的问题:P=N*P?

【输入格式】

输入的第一行包含两个数,分别为N和P。

【输出格式】

如果P=N*P,输出True。否则输出False。

【样例输入1】

1 7235792357924234

【样例输出1】

True

【样例输入2】

-3.979323846264338327959937510 0

【样例输出2】

True

【数据说明】

保证读入不会超过0.1s。保证数据是十进制。不可能出现+12,13., --108,.12345等表示方式。

NOIP模拟题bronze 刘启鹏Brick Break Game

Brick Break Game

【问题描述】

很久很久很久很久很久以前,有一个有趣的游戏。这个游戏是这样的,地上有一些砖块,保证每一块的长度都是{1,2,3,4}的一个整数。每次你有两种操作,拿走n个长度为n的砖块,或者把一个长度大于1的砖块分为两个长度大于等于0的砖块。如果某个玩家无法操作,就算这位玩家输。

现在给出你一些局面,判断这个游戏是先手必胜还是后手必胜。

【输入格式】

输入的第一行包含一个整数T,表示数据组数。

接下来有T组,每组四个整数a b c d,表示长度为1 2 3 4的砖块分别有多少个。

【输出格式】

输出T行,每行一个一个整数,1表示先手必胜,0表示后手必胜。

【样例输入】

3

4 2 1 0

0 0 1 0

7 0 1 0

【样例输出】

1

1

【数据说明】

30%数据满足:a+2b+3c+4d≤10

70%数据满足:max{a, b, c, d}≤14

100%数据满足:T≤10, max{a, b, c, d}≤1010000

NOIP 模拟题 bronze 刘启鹏 数池塘 数池塘 【问题描述】 农夫约翰的农场可以表示成 N*M（1<=N<=100,1<=M<=100）个方格组成的 矩形。由于近日的降雨，在约翰农场上的不同地方形成了池塘。每一个方格或者 有积水（'W'）或者没有积水（'.'） 。农夫约翰打算数出他的农场上共形成了多少 池塘。 一个池塘是一系列相连的有积水的方格， 每一个方格周围的八个方格都被认 为是与这个方格相连的。

现给出约翰农场的图样，要求输出农场上的池塘数。 【输入格式】 第 1 行：由空格隔开的两个整数：N 和 M 第 2..N+1 行：每行 M 个字符代表约翰农场的一排方格的状态。每个字符或 者是'W'或者是'.'，字符之间没有空格。 【输出格式】 第 1

行：约翰农场上的池塘数。 【样例输入 1】 10 12

W........WW. .WWW ....WW...WW. .........WW. .........W.. ..W......W.. .WW. W.W. .W. ..W.......W. 【样例输出 1】 3 第6页 共6页