day1
- 格式：pdf
- 大小：154.88 KB
- 文档页数：5
NOI2012江苏省集训队第一轮选拔
第一试
（请选手仔细阅读本页内容）
一．题目概况
中文题目名称凸”字形
英文题目与子目录名
可执行文件名
输入文件名
输出文件名
每个测试点时限秒秒秒秒测试点数目
每个测试点分值
二．提交源程序文件名
对C++语言
对C语言
对PASCAL语言
三．编译命令（不包含任何优化开关）
对C++语言-o food
food.cpp-lm
-o style
style.cpp-lm
-o bottle
bottle.cpp-lm
-o sw
sw.cpp-lm
对C语言-o food
food.c-lm
-o style
style.c-lm
-o bottle
bottle.c-lm
-o sw
sw.c-lm
对PASCAL语言
四．运行内存限制
内存上限
注意事项：
文件名（程序名和输入输出文件名）必须使用英文小写。
C/C++中函数 main()的返回值类型必须是int，程序正常结束时返回值必须是0。
1．打饭
【问题描述】
一天中午，星星去食堂吃午饭，如往常一样，食堂里已经排起了长长的队伍。
然而今天有一个很奇特的现象：队伍中的同学全都是星星的好朋友。
众所周知，食堂的饭菜是乏善可陈的，星星只对某几种菜感兴趣。
为了能打到自己喜欢的菜，星星只好采取一种不良方案——插队。
虽然星星的朋友都很乐意让他插队到他们前面以便一起探讨“学术”问题，但星星还是不想影响到太多的同学。
星星通过某种方式得知了队伍中每个同学对每种菜的需求量，以及食堂每种菜的剩余量。
由于星星数学不好，他会告诉你他自己对每种饭菜的需求量，希望你能编写一个程序告诉他在第几个同学前插队刚好能打到所需菜。
【输入】
第一行，两个整数：M，N。
M表示今日食堂提供的饭菜的种类数。
N表示队伍中一共有多少同学。
第二行，M个整数，其中第j个数A j表示食堂今日第j种菜的供应量。
第三行，M个整数，其中第j个数B j表示星星对第j种菜的需求量，B j=0表示星星对第j种菜不感兴趣。
接下来N行，每行M个整数，第i（1<=i<=N）行第j（1<=j<=M）个数C ij，表示队伍中第i个同学对第j种菜的需求量。
其中1<=N<=100，1<=M<=10，0<=A j,B j,C ij<=100。
【输出】
一个整数i，表示星星插队在第i个同学之前能打到所需的菜，并且插队在第i个同学之后就无法打到所需的菜。
若星星无论如何都无法打到所需的菜，输出-1，若无需插队就能打到所需的菜，输出N+1。
【样例输入】
23
1010
55
23
78
22
【样例输出】
2
注：
每位同学打菜时，即使第j种菜剩余量不足他所需时，也会打走剩余的所有第j种菜，然而星星希望轮到他的时候，他感兴趣的菜都剩余足够的份量。
2. “凸”字形
【问题描述】
有一个两行N列的长矩阵，其中的数有正有负，均不超出整数的范围。
小明想从这个长矩阵中圈出一个“凸”字形（可正可倒），使得这个“凸”字形中的所有数之和尽可能大，请问能达到的最大值是多少？
【输入】
输入第一行包含一个整数N，即矩阵的列数，N小于1000000。
以下两行，每行包含N 个数，用来描述这个矩阵。
所有数都在整数范围内。
【输出】
输出包含一行一个数，即求出的最大值。
【样例输入】
4
1-111
-4111
【样例输出】
4
3.瓶子
【问题描述】
TOM去火星旅行，但是准备回地球的时候，他发现飞船的燃料不够了。
于是TOM去向火星人借燃料，火星人答应了，但要TOM用他飞船上的瓶子来交换。
TOM的飞船上共有N个瓶子(1<=N<=1000)，经过协商，火星人只要其中的K个(1<=K<=N)。
TOM将K个瓶子交给火星人之后，火星人用他们装一些燃料给TOM。
所有的瓶子都没有刻度，只是在瓶口标注了容量，第i个瓶子的容量为V i(V i为整数，并满足1<=V i<=1,000,000,000)。
火星人比较吝啬，他们并不会把所有的瓶子都装满燃料。
他们拿到瓶子后，会跑到燃料库里鼓捣一通，弄出一小点燃料来交差。
TOM当然知道他们会来这一手，于是事先了解了火星人鼓捣的具体内容。
火星人在燃料库里只会做如下的3种操作：
（1）将某个瓶子装满燃料；
（2）将某个瓶子中的燃料全部倒回燃料库；
（3）将燃料从瓶子a倒向瓶子b，直到瓶子b满或者瓶子a空。
燃料倾倒过程中的损耗可以忽略。
火星人拿出的燃料，当然是这些操作所能得到的最小正体积。
TOM知道，对于不同的瓶子组合，火星人可能会被迫给出不同体积的燃料。
TOM希望找到最优的瓶子组合，使得火星人给出尽量多的燃料。
【输入】
第一行：2个整数，N，K
第2..N+1行：每行1个整数，第i+1行的整数为V i
【输出】
仅一行，一个整数，表示火星人给出燃料的最大值。
【样例输入】
32
3
4
4
【样例输出】
4
4.喜羊羊和灰太狼
【问题描述】
小AA和小YY得到了《喜羊羊和灰太狼》的电影票，都很想去观看，但是电影票只有一张，于是他们用智力游戏决定胜负，赢得游戏的人可以获得电影票。
在N*M的迷宫中有一个棋子，小AA首先任意选择棋子放置的位置。
然后，小YY和小AA轮流将棋子移动到相邻的格子里。
游戏的规则规定，在一次游戏中，同一个格子不能进人两次，且不能将棋子移动到某些格子中去。
当玩家无法继续移动棋子时，游戏结束，最后一个移动棋子的玩家赢得了游戏。
例如下图所示的迷宫迷宫中”．”表示棋子可以经过的格子，而”＃”表示棋子不可以经过
的格子：
.##
...
#.#
若小AA将棋子放置在（1,1），则小AA则无论如何都无法赢得游戏。
而若小AA将棋子放置在（3，2）或（2，3），则小AA能够赢得游戏。
例如，小AA 将棋子放置在（3，2），小YY只能将它移动到（2，2），此时小AA再将棋子移动到（2，3），就赢得了游戏。
小AA和小YY都是绝顶聪明的小朋友，且从不失误。
小AA到底能不能赢得这场游戏，从而得到珍贵的电影票呢？
【输入】
第一行两个整数N，M，表示了迷宫的边长。
1<=N，M<=100。
接下来N行，每行M个字符，描述了迷宫。
【输出】
若小AA能够赢得游戏，则输出一行”WIN”（不包含引号，大写），然后输出所有可以赢得游戏的起始位置，按行优先顺序输出，每行一个。
否则输出一行”LOSE”（不包含引号，大写）。
【样例输入】
33
.##
...
#.#
【样例输出】
WIN
23
32。
