「一家人」杯程序设计竞赛 文字版题目

（文字版题目用于没法查看 PDF 版本题目者使用。能查看 PDF 版本的，请不要查看该版本。）

梦境奇遇 第一届「一家人」杯程序设计竞赛

(2010年6月6日，14:30:00 – 17:40:00)

出题人：Ceeji & LXYXYNT

审题人：LXYXYNT & Ceeji

特别说明：

一、文件名（程序名和输入输出文件名）必须使用小写。
二、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。
三、统一评测时采用的机器参考配置为：CPU AMD 2.7GHz 双核，内存 2 GB，使用虚拟机环境测试。
四、关于使用Pascal语言与编译结果的说明
1．对于Pascal语言的程序，当使用IDE和fpc编译结果不一致时，以fpc的编译结果为准。
2．允许使用数学库(uses math子句)，以及ansistring。但不允许使用编译开关（最后测试时pascal的范围检查开关默认关闭：{$R-,Q-,S-}），也不支持与优化相关的选项。
五、关于C++语言中模板使用的限制说明
不限制使用标准库算法和各种头文件。

六、请使用「\n」作为 C/C++语言的换行符**。**

0**．**前言

梦这个字，无疑在每个人心目中都是重要的。从小，父母和社会就给我们灌输「要树立远大理想」的号召，然而对于梦，我们印象最深的，恐怕却是睡觉中实际所做的一个个梦境。在梦境中，我们可以实现自己多年的渴望。

俗话说，「日有所思，夜有所梦」。但是，在很多情况下，常常是「日有所思而不得，夜有所梦而无缘」。有一首诗这样写：

在梦中，我回到了远古，

没有地沟油，也没有三聚氰胺，

没有考试和竞赛，也没有下岗，

没有高楼大厦，也进不了富士康，

有的，只是山水的旖旎，和你的温柔。

就这样，幸福

却被写模拟赛的闹钟惊醒

——Ceeji

1**．**排队出发

(1.pas/c/cpp | 內存 128 MB)

【问题描述】

神牛岛是传说中的一个岛屿，凡是成功到那里游历，完成探险并返回的人，都会成为神牛。但是，现实中却没有人知道如何到达神牛岛。

这天夜里，笃志者睡着之后，不久就进入了梦乡。他突然看到有人在问，「有人想去神牛岛的吗？」神牛岛之旅的牌子前，就开始有不少勇士报名要去冒险探索。

「我们会把勇士安排在前，带领大家一起去神牛岛。下面开始点名！」管理队伍的LXY神牛说。其实说实话，给学生排队这种工作是最让神牛头疼的了。因为同学们都有自尊心，都不愿意排后面。共有n个同学要排成一列，每个同学有两个属性：影响力和承受能力。给一个同学造成的心理创伤指数等于所有在他前面同学的影响力之和减去他的承受能力。现在请你帮忙安排一下点名顺序，尽量使受到心理创伤最大的同学少受创伤。

【输入】

输入文件1.in包含_n_+1行：

第1行是整数_n_，表示同学的个数。

第2~n+1行每行两个自然数，分别是该同学的影响力和承受能力。

【输出】

输出文件1.out包含1行，为你安排的顺序中受到心理创伤最大的同学受到的创伤。

【输入输出样例】

1.in

1.out

3

10 3

2 5

3 3

2

【数据规模】

对于100％的数据，1<=n<=50000，1<=影响力<=10000，1<=承受能力<=1,000,000,000。

2**．自动做作业机**

(2.pas/c/cpp | 內存 128 MB)

【问题描述】

就在大家要出发的那一刻，笃志者想起昨天的作业还没有写完…为了解决这个问题，神牛给笃志者和其它有类似情况的人们准备了一个新发明：自动做作业机。这项发明能够帮助大家做作业。。但是它非常非常非常费电。如果大家都毫无节制的用的话，很快就会因为用电严重超标而无法继续。因此在用之前，你必须想办法最小化耗电量。

假设现在有N项作业，每项作业会有两个关键字Ti(耗时)和Fi(重要度)，我们所要做的是将作业分成若干块（顺序不能改变）依次给机器去做。每一块中作业的完成时间为这一块中所有作业完成的时间，而每一块开始前必须有S的时间让机器准备启动。做作业机的耗电量就等于每项作业的完成时间乘以重要度之和。这次任务必须在0.2秒内解决。

【输入】

输入文件2.in的第一行为N，为作业的个数。

第二行为S，为准备时间。

接下来有N行，第i+2行为两个整数：Ti和Fi。

【输出】

输出文件2.out只有一行，为做作业机的最小耗电量。

【输入输出样例】

2.in

2.out

5

1

1 3

3 2

4 3

2 3

1 4

153

【输入输出样例解释】

样例共有5个作业，应该分成｛1,2｝｛3｝｛4,5｝。作业的完成时间分别为｛5,5,10,14,14｝。

【数据规模】

对于40％的数据，1<=n<=2000。

对于100％的数据，1<=n<=10000。

对于100％的数据,1<=S<=50,1<=Fi<=100,1<=Ti<=100，保证最后的结果不大于2^31-1。

3**．鬼火闪闪**

(3.pas/c/cpp | 內存 128 MB)

【问题描述】

队伍即将到达神牛岛时，突然一片黑暗的路边开始鬼火连连。这些特殊的鬼火有明有暗，安静地排列在路的右边。他们排成一条直线，似乎在恐吓人们，不要继续前进。

突然，前面出现一个键盘，恐怖的声音传了过来：「是自己人吗？请输入密码。」

大家猜了半天也没有猜到密码，这时，笃志者想，这个密码如果不简单，那么他们自己人怎么能背会呢？由于是数字密码，是不是这个密码有什么玄机的？

望着旁边的鬼火，笃志者开始计算起来。突然，他输入一个数字，键盘破解了。

原来，从左到右，明亮的鬼火和暗淡的鬼火是有玄机的。笃志者发现，旁边有30个鬼火，用L表示亮，P表示不亮。假设亮鬼火所在位置为W（位置从右到左，从0开始计数），对于各个鬼火位置，二的W次方的和就是结果。

过了一会儿，竟然又出现了键盘，在键盘旁边有一张小纸条，上面有一个数字，但是这时候却看不见鬼火的明暗了。这次机关的破解难多了，过了三个小时，笃志者终于明白了规律。小纸条的数字，隐含着鬼火的排列情况，假设亮鬼火所在位置为W（位置从右到左，从0开始计数），对于各个鬼火位置，二的W次方的和就是结果。

例如某次键盘上的小纸条的数字是1，反推可得位置0是亮鬼火，其它位置都是暗鬼火，这样就反推出了鬼火的情况。

然后，将从左到右的前14个鬼火最前面补两个空位，和后16个鬼火进行交换，上例交换后，第14个鬼火为亮，其余都是暗。如下所示：

交换前：

从左到右前十四：空 空 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗

从左到右后十六：暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 亮

交换后：

从左到右前十六：暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 亮

从左到右后十四：空 空 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗 暗

在这样的鬼火排列中，假设亮鬼火所在位置为W（位置从右到左，从0开始计数），对于各个鬼火位置，二的W次方的和就是结果。

也就是说，如果小纸条上的数字是1，交换后，从右到左的第16个鬼火为亮，那么你应该输入的密码，就是216的值。

可是再往后，键盘越来越多，计算方法却都和刚刚的那次一样。繁琐的工作就交给大家来做吧。

【输入】

输入文件3.in的第一行为N，为纸条的个数。

接下来有N行，每行一个数，为小纸条上的数字。

【输出】

输出文件3.out有N行，为每行对应的密码。

【输入输出样例】

3.in

3.out

1

7494574

1538130034

【数据规模】

对于100％的数据，1<=n<=600,000。

4**．险象丛生**

(4.pas/c/cpp | 內存 128 MB)

【问题描述】

到达神牛岛之后，一行人疯狂地庆祝了一番。神牛岛上什么都有，港口、超市一应俱全。然后就准备返回出发地。可是，这并不是一件容易的事情。因为，来的时候，他们有密码；回去的时候，他们才发现，纸条都让他们随手给仍了，已经没有办法输入正确的密码。他们只好渡河到另一个港口。可是，到了渡河处，他们才发现这里的河波涛汹涌，但船却都很小，每个船都只能坐一个人。更恐怖的是，水中有一种叫做「有去无回」的怪物，不定什么时候就会爬到某个船上，将其销毁。为了防止这种情况，必须有人死死盯住周围，一旦有东西爬上，先下手为强，将其弄死。

另一方面，这些船非常小，坐一个人就吃水很深，让人觉得很不安全。为此，笃志者想到了赤壁之战。于是，他就动员大家找了一些结实的材料，将一部分船连接在一起。由于材料很难找，连接都很短，从一艘船可以直接跳到另一艘船上，而且由于人们很聪明地节约材料，他们保证了去掉某两船的连接后，一定会导致至少一艘船脱离连环船。即使这样节约，也不能让所有船都连在一起，只能成为一组一组的连环船。

现在已经连接好了一组组的连环船。由于担心万一船禁不住沉了或遇到「有去无回」怪物破坏船只导致某船沉没，就有人没地方坐了，所以，每组船可以不坐满，少坐人，这样就会让更多的船成为无人的「备用船」，以备不测。但却必须保证每艘船都能被人看守住（每艘船或其直接连接的船二者至少有一船坐人），以便看住「有去无回」怪物，保障船的安全。同时，由于面临很多未知数，笃志者希望大家乘坐的连环船的组数越多越好，一旦某组连环船沉没，人们还可以逃生到另一组连环船。「船多力量大」嘛！笃志者想知道，在这样的条件下，他们最多可以安全控制住多少组连环船。

数据保证人数<=船数。

【输入】

输入文件4.in的第一行为三个正整数N M P，分别为船的条数、队员的人数和边数。

接下来有P行，每行两个数i和j，表示这两搜船直接相连，编号从1开始，不会输入重复的连接，船的连接不分方向。

【输出】

输出文件4.out只有一行，为队员最多可以安全控制的连环船的组数。

【输入输出样例】

4.in

4.out

6 2 3

2 5

3 5

2 6

2

【输入输出样例解释】

由于只有两个人，可以控制船5所在的连环船（一个人坐船5，一个人坐船6，即可看住所有侵犯的「有去无回」），此时只能控制一组连环船。也可以控制船1和船4，此时则控制了两组独立的连环船，所以，答案为后者，2。

【数据规模】

对于100％的数据，1<=M<=N<=5000。

题外话：我帮你整理了包括 AI 写作、绘画、视频（自媒体制作）零门槛 AI 课程 + 国内可直接顺畅使用的软件。想让自己快速用上 AI 工具来降本增效，辅助工作和生活？限时报名。