1. 领土划分

【问题描述】

著名的女王,阳姐•查兰•伊丽莎白一世有两个宠物,一个叫大黄,一个叫小
昊。女王赐予了这两个宠物一份 N×M 的土地。这片土地由 N×M 个长度为一单
位的小正方形构成,每一个小正方形种植水稻或者小麦,但种植的量可能不同。
大黄喜欢吃饭,也就是说,他希望他的领地里的水稻种植量多,类似的,小
昊喜欢吃面,所以他希望他的领地里的小麦种植量多。为了这片土地的划分,大
黄与小昊经常发生狗咬狗、相煎何太急的惨剧。
现在女王决定,派出一辆推土机,这辆推土机从左上角开始,每次向右向下
或者向右下移动一个格子,直到走到土地的右下角为止,推土机经过的格子将变
为废墟。这样就会将土地分成上下两块,其中右上的那一块归小昊,左下的那一
块归大黄。
现在女王想知道,这辆推土机如何移动,能够使得大黄领地中水稻种植总量
和小昊领地中小麦种植总量之和最大?

【输入】

输入文件名为 Divide.in。
输入第一行包含两个正整数 N 和 M,表示土地的行数与列数。
下接一个 N×M 的矩阵描述这块土地的信息,其中,每个格子的信息按照如
下方式表示:若该格子种的是水稻,则形式为“JX”,其中 X 为该格子中水稻的
种植量;若该格子种的是小麦,则形式为“KX”,其中 X 为该格子中小麦的种
植量。保证种植量均为小于等于 99 的非负整数,且每一行中相邻两个格子之间

有逗号隔开。

【输出】

输出文件名为 Divide.out。
输出第一行包含一个正整数,为可能的最大的两种作物种植量总和。

【输入输出样例】

Divide.in
4 3
K2 K3 K5
J3 K1 J1
J2 J4 K1
K1 K3 J3

Divide.out
17

【样例解释】

移动方法为向右下,向右下,向下。总和为(3+2+4)+(3+5)=17。【数据范围】
40%的数据保证 1<=N,M<=100。
100%的数据保证 1<=N,M<=1500。数据保证有梯度。

题解

DP+前缀和优化
设$f_{i,j}$为以(i,j)为起点时的答案

$f_{i,j}=max\{f_{i+1,j+1}+sum1+sum2,f_{i+1,j}+sum1,f_{i,j+1}+sum2\}$

sum1表示坐标(i,j)所在的那一行中在(i,j)右边的小麦种植总量,sum2表示坐标(i,j)所在的那一列中在(i,j)下面的水稻种植总量

sum1、sum2用前缀和就可以了

代码:

2. 扑克游戏

【题目描述】

著名的阳姐•查兰•伊丽莎白一世因为治理国家太有方了,最近国泰民安,阳
姐就只能和大黄或者小昊开始玩扑克游戏了。
这个扑克游戏的规则是这样的。首先,弄出 N(N 保证为偶数)张牌(当我
没说扑克吧),每张牌上都有一个分数 Wi,抽到这张牌的人将得到 Wi 的分数。
将这 N 张牌按照顺序叠成一叠。两个人轮流抽牌,每次都只能抽现存的最上面
的牌或者最下面的牌,并且不放回。当牌堆被抽光的时候,分数最高的人胜利。
因为女士优先,每次都是阳姐先抽。阳姐现在想知道,自己能不能赢,最多能得
到多少分,自己得到最高分的时候会抽到原牌堆中的哪些牌。(当两种抽法得到
的分数相等时,优先取最上面那张牌)这样说可能会有些不敬,不过由于阳姐出
色的(调)教(揉)练,小昊和大黄的智商可以视为极高,也就是说,双方都会
执行对自己最有利的抽法。

【输入】

输入文件名为 Poker.ni。
输入第一行一个正整数 N,代表牌堆中牌的个数。
第二行顺次包含 N 个数,代表牌堆中最上面的牌一直到最下面的牌的分数。

【输出】

输出文件名为 Joker.ans。
输出第一行为“WIN”或“LOSE”,代表赢或者输。
输出第二行代表阳姐最高的得分。
输出第三行 N/2 个正整数,代表阳姐得到最高得分的时候,按她抽到的先后
顺序,输出她抽到的牌在原来牌堆中的序号。

【输入输出样例】

Poker.in
10

Poker.out
8 4 1 6 3 1 9 7 6 6 WIN
28
1 10 8 6 4

【数据范围】

对于 60%的数据,1<=N<=100。
对于 100%的数据,1<=N<=1000,1<=Wi<=1000。

题解

。。。区间dp裸题
设$f1_{i,j}$为当前牌堆最上面的牌是第i张,最下面的牌是第j张时先手的最优解值,相应的f2表示后手的

当j-i为奇数,是后手抽牌,否则为先手抽牌

所以(伪代码):

至于输出路径,记录状态转移的前驱就行了

代码:

3. 罪人审判

【问题描述】

小昊是著名女帝,阳姐•查兰•伊丽莎白一世,的专属,宠物。
但是小昊人模人样,尤其是公正心,更是超乎正常人一等。所以阳姐委任他
担当最高法院最高大法官审判长一职。今天,大法官小昊审判了 N 个罪人,每
个人的罪恶度为 Di。按照惯例,这些罪人应该要背着跟他罪恶度相等重量的荆
棘游街示众。但是因为小昊的正义过头,导致这几天荆棘几乎卖完了,今天只有
M 个单位重量的荆棘了。万一某个罪人少背了 X 个单位的荆棘,那么民众对这
个罪人受到的处罚会产生 X 2 的不满值。现在小昊想知道,如何分配仅有的荆棘,
才能使民众对这 N 个犯人产生的不满值总和最小?对了,因为小昊的手无法抓
稳秤杆,所以每个罪人只能背整数单位的荆棘。

【输入】

输入第一行包含两个正整数 M 和 N,意义如上所述。
下接 N 行,每行一个正整数,为每个罪人的罪恶度 Di。

【输出】

输出一行包含一个正整数,代表最小的不满值总和。

【输入输出样例】

Output.txt(样例输入)
5 3
1
3
2

Input.txt(样例输出)
1

【数据范围】

40%的数据,M<=200000。
100%的数据,M,Di<=2.1*10 9 ,N<=10 5 ,保证答案大小在有符号 64 位整型变量
存储范围内。

题解

。。。被爆int只有40分了。。。
显然贪心
因为最后所有罪犯少背的重量是固定的,而且:
$a+b=c$时,$a^2+b^2<c^2$(因为$c^2=(a+b)^2=a^2+b^2+2ab$)
所以说白了就是要分配得最平均
O(n)的方法想了半天没想到,最后用平衡树(map)O(nlogn)搞的
思路是每次从平衡树中找出最大的(少背的最多的),再找出次大的,给最大的背上荆棘,让最大的少背的量和次大的相等,然后合并最大的和次大的节点,一直到用完荆棘或者全部为0(不满意度为0)
每个节点保存的是一种少背的量,可能有多个人对应了这个量,所以要保存这个量对应了多少人。

代码:

4. INDEX1

【问题描述】

INDEX 是谁?兄弟,这个问题你如果不知道我就只能怀疑你是从火星来的了。
但是,如果你真的不知道他是谁,那么,你可能和他拥有同一个故乡。
其实当年 INDEX 在火星上有 N 个基友和 M 个妹子,生活真是非常逍遥。他每天都把
基友和妹子排成一队,使得他能够站在最前面,领着他的基友后宫团游街(囧)。
但是,他的妹子们的嫉妒心是很强的,如果两个妹子站在一起,肯定会为 INDEX 吵得
不可开交。同时,INDEX 也是有老婆的人,他身后,也就是队伍的第一个人必须是他的基
友后宫团的团长——他老婆(也就是说,M 个妹子中有一个是他的老婆,为了使题目容易
理解,也就是第一个人已经确定是 M 个妹子中的一个了)。而且,他希望由一个基友来殿后。
现在 INDEX 想知道,他能够排成多少种不同的队伍,使得这个队伍满足他的要求?

【输入】

输入文件名为 Indexone.in。
输入一行包含两个整数 N 和 M。

【输出】

输出文件名为 Indexone.out。
输出一行,表示合法的队伍总数对 1000000007 的模值,如果不存在何方方案则输出 0。

【输入输出样例】

Indexone.in
1 1
Indexone.out
1

【数据范围】

对于 30%的数据,保证有 1≤N,M≤1000。
对于另外 30%的数据,保证有 1≤M≤10。
对于 100%的数据,保证有 1≤N,M≤1000000。

题解

组合数学。。。
第一个”老婆“是确定的一个人!没有M种选老婆的可能性!
可以把题目看成:n个男的组成n-1个盒子,再把m-1个女的丢到这n-1个盒子里

组成盒子的方案数是n!种,把m-1个女的丢进去的方案数时(n-1)×(n-2)×(n-3)×...×(n-m-1)
当然如果盒子数少于人数,答案为0

所以答案为:$n!×(n-1)×(n-2)×(n-3)×...×(n-m-1)$

代码:

4. INDEX2

【问题描述】

故事承接上文。
这事发生在博士还不那么内涵,现哥还不那么傻逼,姜嗲还没开始玩 dota,巨胖才 50Kg
的时候。有一天, INDEX 的老婆再也不能忍受 INDEX 那过分庞大超过一阿伏伽德罗常数的
后宫量,那天夜里,她将 INDEX 绑架到了飞船上,
“私奔”到了月球,在《Fly me to the moon》
的歌声中。好美啊!
这个时刻,INDEX 发现有一颗蓝色的星球一直在绕着一颗红色的星球转动。接着,他
又发现,他的故乡火星也一直在绕着这颗红色的星球转动!!!厉害爆了有木有!!!现在,他
的老婆将这颗蓝色星球命名为 A,他们的故乡火星命名为 B,并将他们的轨道平均分成 L
块,形成了 L 块扇形区域吗,并从 0 到 L-1 逆时针标号,A 星球和 B 星球都是沿逆时针绕
红色星球转动。一开始的时间计算为 0,在 0 时刻时,A 处在 Sa 块,B 处在 Sb 块。A 的移
动速度为 Va 块每 INDEX 小时,B 的移动速度为 Vb 块每 INDEX 小时。INDEX 向她老婆发
誓,
他们会在月球上度过一段美好的二人时光,
直到到某个 INDEX 小时整点的钟声敲响时,
若星球 A 和星球 B 所在块的编号相同,那么,他们启程返回火星。
思念自己庞大后宫团的 INDEX 想问你,他们启程返回火星的时刻。

【输入】

输入文件名为 Indextwo.in。
输入仅一行,包含五个正整数,分别为 L,Sa,Sb,Va,Vb。

【输出】

输出文件名为 Indextwo.out
输出仅一行,表示他们启程返回火星的时刻。若永远都不存在那个时刻,请输出
“Ohahahahahahaha”
,不包含双引号。

【输入输出样例】

Indextwo.in
3 1 1 2 2

Indextwo.out
0

【数据范围】

对于 30%的数据,保证有 1≤L≤100。
对于 100%的数据,保证有 1≤L≤1000000,而且 0≤Sa,Sb≤L-1,1≤Va,Vb≤L。

题解

首先令A的速度快于B的速度(如果B的速度较快就交换AB的速度与位置)
然后设v为va-vb(即速度差),d为(sb-sa+l) mod l(即A距离B多远)(l代表一圈的路程),然后巧设参考系,设B不动
那么大概是这个情况:

因为A第一次到达B的时候不一定是整数时间,所以可能A要再绕几圈,才能刚好在整点到达B。我们设还要绕x圈。
那么当前A的移动速度为v,初始距离为d,总路程为d+x×l,而且总路程一定能被v整除,即:
$(d+x\times l) mod v=0$
拆开:
$[d mod v+(x mod v)\times (l mod v)] mod v=0$
这里面d、v、l是定值,然后显然x小于v(因为如果x大于等于v取模后又小于v了,没有讨论的意义)。
那么我们从0到v-1枚举x的值,当$(d+x\times l) mod v=0$时就得到要转几圈了!
然后根据总路程可以算出总事件
显然如果不存在一个x能满足$(d+x\times l) mod v=0$,就无解了

代码:

附:能用扩展欧几里德算法在log的复杂度内求出答案