福建2010Noip夏令营day4

测试时间：14:00-16:30 16:30之后提交的程序一概不收

提交方式不变

问题名称 谁是赢家 最小值 红牌 文件名 winner min red 输入文件 winner.in min.in red.in 内存限制均为256M

输出文件 winner.out min.out red.out 时限 分值 1s 100 1s 100 1s 100 谁是赢家(winner)

问题描述：

Nic和Susan在玩一个有趣的游戏：在游戏开始前，他们先约定一个正整数n，同时令m=1。游戏过程中，每个人都可以将m的值扩大2到9中的任意倍数。第一个使得m≥n的人就是最后的赢家。

假设Nic和Susan都十分聪明，并且游戏过程中都使用最佳的策略，问谁会是最后的赢家（Nic总是第一个先玩）。

数据输入：

一个正整数n（1≤n≤2^32-1）。

数据输出： 在使用最佳的策略的情况下，如果Nic必胜，则输出“Nic”。如果Susan必胜，则输出“Susan”。否则输出“God”。

样例输入： 9

样例输出： Nic

最小和(min)

题目描述：

N个数排成一排，你可以任意选择连续的若干个数，算出它们的和。问该如何选择才能使得和的绝对值最小。

如：N=8时，8个数如下:

1 2 3 4 5 6 7 8

-20 90 -30 -20 80 -70 -60 125

如果我们选择1到4这4个数，和为20，还可以选择6到8这3个数，和为-5，|-5|=5,该方案获得的和的绝对值最小。

输入格式：

第一行输入N，表示数字的个数。接下来N行描述这N个数字。

输出格式：

第一行输出一个整数，表示最小绝对值的和，第二行包含一个整数表示形成该绝对值和最长序列的长度。

数据说明：

40%的数据 N<=4000

对于许多数据，最长序列的长度唯一。

100%的数据 N<=100000,|每个数字的值|<=10^10 样例输入： 8 -20 90 -30 -20 80 -70 -60 125

样例输出：

5 3

红牌(red)

题目描述 ：

某地临时居民想获得长期居住权就必须申请拿到红牌。获得红牌的过程是相当复杂 ，一共包括N个步骤。每一步骤都由政府的某个工作人员负责检查你所提交的材料是否符合条件。为了加快进程，每一步政府都派了M个工作人员来检查材料。不幸的是，并不是每一个工作人员效率都很高。尽管如此，为了体现“公开政府”的政策，政府部门把每一个工作人员的处理一个申请所花天数都对外界公开。

为了防止所有申请人都到效率高的工作人员去申请。这M*N个工作人员被分成M个小组。每一组在每一步都有一个工作人员。申请人可以选择任意一个小组也可以更换小组。但是更换小组是很严格的，一定要相邻两个步骤之间来更换，而不能在某一步骤已经开始但还没结束的时候提出更换，并且也只能从原来的小组I更换到小组I+1,当然从小组M可以更换到小组1。对更换小组的次数没有限制。

例如：下面是3个小组，每个小组4个步骤工作天数：

小组1 2 6 1 8 小组2 3 6 2 6

小组3 4 2 3 6

例子中，可以选择小组1来完成整个过程一共花了2+6+1+8=17天，也可以从小组2开始第一步，然后第二步更换到小组2，第三步到小组1，第四步再到小组2，这样一共花了3+2+1+6=12天。你可以发现没有比这样效率更高的选择。

你的任务是求出完成申请所花最少天数。

输入格式：

第一行是两个整数N(1<=N<=2000)和M(1<=M<=1000),表示步数和小组数。接下来有M行，每行N个整数，第i+1(1<=i<=M)行的第j个数表示小组i完成第j步所花的天数，天数都不超过1000000。

输出格式：

输出完成所有步所需最少天数。

样例输入： 4 3 2 6 1 8 3 6 2 6 4 2 3 6 样例输出： 12

本文来源：https://www.bwwdw.com/article/wv1d.html