这篇文章是由Lackey CCG的一篇关于CCG Design的文章渣翻过来的,原文链接点击:这里,需要翻墙。

最近有了自己的想法,对Game Design有了兴趣,就以此渣翻作为开始吧。

不知道作为一只不入流的程序有了这种想法会不会影响以后找工作啊……


随想

这一块在翻译的过程中就开始慢慢加了。

其实游戏本身是哪种形式的并没有太大的关系,本质上都是差不多的。

即便是差别很大的PVP和PVE,无非一个是与人打交道,一个是与物打交道。工作中不是也分为与人打交道的工作和与事物打交道的工作么,获取喜悦的方式不同,但是获得的快乐度对于没个体本身是没有什么差别的。就像有人喜欢FPS,有人偏好SLG,还有人热衷RPG一样。

画面党果然还是很有分量的。

游戏中的角色应当具有高辨识度。比如Dota2的英雄设计中有一条就是只通过剪影就能识别是哪一位英雄。

在翻译”A game should be fun whether you win or lose”这段的时候让我想起来Dota/LOL的一场完整的职业比赛(含BP),以及当前烫手的皇室战争。之前跟老大们闲聊的时候谈了皇室战争能否成为真正和炉石一样的竞技游戏,然后普遍结论是当前这个版本可能性不大……话说鹅厂要收购Supercell,是不是想借皇室磕炉石啊?

“Avoid mechanics that encourage tedious busywork or memorization”,比如需要不停刷怪升级和I Wanna那种的“背板”。

在程序设计之外看到了K.I.S.S.法则。

最大的两点感受:

  • 之前看英文资料绝大部分都是技术文档跟说明,术语使用都很精确且有对应中文词汇,即便是Paper也是差不多这样。这次换成与文化/亚文化相关的东西就比较见拙了,不少东西即便能读懂,想要达意地翻出来还是很难的。积累不够,还是要多学习。

  • 虽然是介绍CCG的设计,但是还是能够从中学习到一些基本的游戏设计原则的。以后在游戏设计的学习过程中应当将看到的东西与自己曾经玩过的游戏结合起来理解。


CCG Design 渣翻


A CCG with the best gameplay mechanics will fall flat if no one cares about playing it

一款CCG即便拥有最好的游戏机制,如果没有人对其感兴趣,那么它也只是一款失败之作。

设计一款CCG的工作就是在使它变得有趣和容易理解之间做出恰到好处的平衡,需要使得游戏足够新颖,易于上手并且有足够的策略空间。无论是选择什么样的题材(奇幻类、科幻类、政略类或者其他完全不同的类型),其本质都在于要使得玩家能够沉浸其中,也就是代入感——当一位法师玩家向他的敌人释放雷电术的时候,他并非只是想到自己在处理掉一个威胁,他可能会在想:“我召唤出了一道牛逼的闪电击中了那个傻样的混球。” 当然实际情况并非是指让人这样“呆瓜”般地去玩游戏,但是这种想象会使得游戏过程变得更有趣味。

肯定没人想去玩一款叫做“叠衣服”的卡牌游戏。(意指游戏设计比较乏味)

You need to establish a creative atmosphere, one players will care about and have fun in

应当去营造一种能够让玩家感受得到,并且能够在其中得到乐趣的充满创造力的氛围。

一个比较简单的方法是利用已有的IP来制作一款CCG,例如星球大战、指环王、魔兽、口袋妖怪、太空堡垒卡拉狄加(这是一部军事科幻电视剧)或者其他——当然这些IPs各自都已经至少拥有一款属于自己的CCG了。各种受欢迎的影视剧、动漫、游戏或者某个系列的书籍都可以拿来作为一款CCG的主题背景。如果采用这种方式制作一款CCG,那么无论是题材的吸引力、还是美术设计、甚至包括游戏本身的设计都可以跟随原型IP的主旨进行制作从而更快地完成游戏;但其缺憾在于需要得到这些IPs的授权,不然就得将游戏作为同人游戏发布了。

另外一个方式就是自己另开炉灶单干了——万智牌(Magic: the Gathering)就是这么做的。万智牌原创了一个世界观,为其添加了一系列故事并定义了相应的美术风格。但万智牌本身也属于奇幻题材,因此并非是重新制作了轮子。由于万智牌瞄准的是“当玩家们不玩龙与地下城(D&D,Dungeons & Dragons)的时候”,因此它所包含的奇幻类元素大量吸收了已有的经验。而D&D本身就在很大程度上继承了J.R.R Tolkien小说中的设定,因此也并不是白手起家。所以,如果打算采用这种方式来开始制作CCG,作者们也不需要从无到有自己搞一套出来——比如可以根据007系列电影来做一款关于特工的游戏。

另外可用的题材就是历史了,制作人们可以选择制作一款基于当前或者历史时间的CCG,比如做一些关于维京、埃及、罗马、日本幕府之类的CCG。但需要记住的是玩家希望能够有一些奇幻有趣的东西,因此当设计一款关于维京人的游戏时不要忘了加入一些北欧诸神、魔法元素以及其他一些属于“人外”的角色、时间和能力。

无论采用哪种方法,制作人都需要确保能够自己能够清晰地定义自己所创造的世界,确保人们愿意花上一段时间来了解它并喜欢上它。这可能是制作一个CCG最重要的事情了。

A very important part about making the game interesting is the artwork

使游戏有趣的一个十分重要的部分就是游戏的美术风格。

尽量将卡片上的图做的更大,尽量把卡片的模板做的更酷——毕竟一图胜千言。毕竟,玩家第一眼看到的是卡面,至少我自己对于卡面比较挫的游戏是兴趣缺缺。卡面是游戏留给玩家的第一印象,如果卡面不能吸引玩家,那就不能够指望太多。

卡面设计应当是形象化的,应当让玩家看到卡面之后能够立刻与卡牌代表的内容联系起来。(也就是说卡面应当具有辨识度)

卡面可以自己画,也可以使用一些免费的素材,甚至是用照片也行,当然也可以联系一些画师来帮忙。

A game should be fun whether you win or lose

无论输赢,游戏的过程必须是有趣的。

谨记不能让CCG在“布局”或者“中盘”中就能让玩家轻易推断出他最后是否能赢,除非游戏已经进行到了“终盘”或者游戏本来就设计为一个消耗碎片时间的短时间内就能打完。

(因为没有玩过Decipher的CCGs,因此后文对于Decipher的游戏的描述可能与原文有出入)

在Decipher的Lord of the Rings CCG中,玩家需要尽快到达目标点。如果一个玩家获得了得当的指引,那么其他玩家将会很难赶上他——这对于那些处于劣势的玩家是很无趣的。一个游戏不仅要建立起稳定良好的竞争机制,也需要一些卡牌来增加游戏的变数。但是这些用来增加变数的卡牌可能会使得玩家觉得这是个“靠人品”的游戏,因此在设计此类卡牌的时候必须非常小心。

Avoid mechanics that encourage tedious busywork or memorization

尽量避免需要玩家进行重动作和“背板”的设计。

Decipher的Star Wars和Wars采用了一个失败的设计:玩家需要将卡片从一个牌堆移动到另一个,然后再到第三个,然后再到第四个牌堆的堆底。这样就会有玩家来记忆牌堆中包含了哪些卡以及卡片在牌堆中的顺序。而除非你记忆力超群(Rain Man),不然你不会记得那些卡牌的。谨记不要去鼓励玩家为了取得一些优势而去做这些无趣的事情。

Don’t be different for the sake of being different

不要为了不同而不同。

如果一个设计已经被证明比另一个更好,那么请采用好的那个,即使是它已经被其他游戏采用过。如果几个设计不相伯仲,那么可以在他们中选择一个。CCGs已经出现了这么长时间,当前已经有不少的亮眼设计了,请不要去重复造轮子。研究其他CCGs可以帮助设计者理解它们的长处和弱点,从而帮助完成自己的设计。

由于缺乏设计上的前瞻性,一款已完成的CCG可能会存在一些“顽疾”:比如万智牌中的“卡地”(Mana Screw,指的是玩家当前桌面上卡牌的资源点数不够从而该回合什么都不能做)。而后面的World of Warcraft CCG则考虑到了这个问题在设计阶段就避免了“卡地”。

Use the lowest common demonator

数值设计尽量低一些。

有的游戏将卡牌数值翻倍,比如10、100甚至是1000,比如游戏王(YuGiOh)。游戏中的卡牌可能具有500点的攻击值,游戏中没有数值低于100的卡,因此他们可以尝试将数值除以100来简化——为了迎合用户而增大数值是一个不好的设计。Wizard的Star Wars也是这样,他们将卡牌的速度值扩大了10倍。

Card restrictions create variety

卡牌搭配带来多样性。

在游戏设计中一个很重要的就是限制卡牌之间的搭配。如果每一张卡牌都可以随意使用,那么玩家很快就会总结出来“最佳牌组”并一直使用它们。卡牌之间的搭配可以带来不同的牌组构建,从而带来不同的策略。为数众多的CCG已经采用了许多不同方式来将这一部分纳入它们的设计之中。

  • 使用资源来进行限制:万智牌通过不同的颜色来划分卡牌,每一种颜色的卡牌都有不同的特点。为了能够使用特定颜色的卡牌,玩家需要与其相对应的资源。通过这种手段可以组成不同的牌组,但是随着颜色种类的增多,对资源的适当管理就就变得越来越难了。

  • 使用分类来限制:WoW利用分类(参考炉石中的职业)来对卡组搭配做出限制。当玩家选择一个门类的时候,只有属于该门类的卡牌以及中立卡牌可以使用。WoW还通过派系来加强限制:在构建之前牌组之前,玩家可以选择加入联盟或者部落,并且只有中立阵营卡牌以及所选的阵营卡牌。通过这两种限制,玩家可以有部落德鲁伊卡组,联盟德鲁伊卡组,联盟游侠卡组等等不同的组合。

  • 通过效益来限制:Decipher的Lord of the Rings CCG允许玩家选择以不同的卡牌,但是同阵营的卡牌配组会有增益加成。

  • 通过处罚来限制:这与上面的方式类似,除非是有一些特使的惩罚方式。Warlords CCG允许玩家选择不同阵营的卡牌,但是不同阵营的卡牌在行动的时候需要额外耗费行动力。

(接下来这两段组织不好语言来翻了……)

不同分组的卡牌之间应当有明确的区分度。

为了使选择变得有意义,必须让玩家在得到一些东西的时候失去另一些。

Correlation of Mechanics to Flavor

说明与设计。

当设计师们为卡牌增加筹码,或者绘制卡牌,或者采用某一项设计的时候,都在告诉玩家这款游戏本身的背景。如果玩家真正沉浸在游戏中,他们会去推断在当前的设计下将会发生什么。也就是说,不必把一切都说明。

考虑下面三张卡牌:

010203

左边的卡牌试图将游戏文本混进卡牌的说明中,但这将会干扰玩家对游戏文本的理解。对于中间的那张卡片,它虽然没有花费那么多的文字来描述卡牌的内容,但玩家依旧可以得到足够了信息来了解这张牌,卡牌的内容被牌面设计以及玩家的想象力补充了——它很好地说明了设计与卡牌背景之间的关系。而右边的卡牌在上一张牌的基础上添加了一个用以说明该卡牌能力属性的的标签。虽然这使得卡牌变得复杂了一点,但一样可以使玩家很快明确牌的内容。建议在设计上尽量避免左边的设计,采用中间以及右边的设计。

Representing “Damage”

许多的CCGs包含角色卡用来代表人物、怪物、军队、载具甚至是建筑物。当这些角色受到伤害的时候,有三种常用的设计来对起进行表述。

(接下来就是完全的渣翻了……表示很多桌游术语都搞不清楚)

  • 筹码:这是最为直观的表示方式了:使用表示伤害的筹码并将其放置在牌面上。这种方式的好处在于它可以随着游戏一直进行下去并且对玩家很直观,同时还可以根据游戏的设计来很容易的移除伤害。但这个设计会使得桌面上的筹码越来越多从而影响到游戏的进行。同时,由于其他需要使用到筹码进行计数的机制的存在,如何管理筹码将会变得困难起来。

  • 每回合结束的时候进行伤害结算:万智牌没有使用基于筹码的伤害计算。如果一个角色在一个回合中受到了超量的伤害,那么该角色就会死亡,否则角色将会存活。角色可以在每个回合中受到治疗(三国杀的死亡结算机制)。从这个设计上来说,玩家可以很容易明确角色受到了多少伤害而不需要筹码的帮助。玩应该是有趣的,而不是一件需要记忆的苦差事。

  • 翻转卡牌:另外一种表示方式是转动卡牌,通过转动的角度来表示它收到的伤害(比如旋转卡牌90 180 270度等)。

  • 口袋妖怪采用的方法:将卡牌放置到不同的伤害区域或者取回手里。

最后需要说明的就是对于描述伤害的“短语”的选择。如果游戏中只有人物和怪物,那么可以考虑使用”wound”;但如果只有载具,那么采用“wound”就不合适了。同样,对于一个生物单位,“die”很不错,但对于建筑物或者僵尸来说“destroy”更好。如果游戏中只有一类单位,那么可以使用更加特定的词语,但如果不是这样,那么就需要考虑比较泛化的说法了。

Randomness

游戏中的随机性。

下面是过度随机导致的五五开——一张无意义的卡牌。

flip

对于CCGs来说随机是一个很重要的因素(Dota2中的河道神符、各种游戏的暴击、随机物品)。即便玩家正在输掉一场游戏,游戏的随机性可能会使得场面发生逆转。同样,对于优势玩家,随机性也可能使得他们输掉游戏。

随机性可以帮助不怎么熟练的玩家赢得胜利,,即便是高玩拿到了绝佳卡组也依旧有可能输掉游戏。对于一个新手玩家,如果他知道自己不太可能会赢得老玩家的话,那么他就很有可能放弃这个游戏。因此随机性确保了不同段位的玩家都可以赢的游戏。

但是当不确定性太多的时候,玩家就会抱怨这是一个“看脸”的游戏。如果一个拥有垃圾卡组的新手玩家可以和老手五五开,并且赢了,那么这场胜利也是没有意义的。

因此,设计CCG的时候应当引入适当的随机性,不要过量。

Methods of winning and losing

赢与输。

在CCGs中有多种方式来判定玩家在一场游戏中的输赢情况。这里建议选择一种作为主要的判定方式,辅以其他次级判定来防止出现判定死锁的情况。当然,多种判定方式也意味着玩家可以采用多种牌组。下面是几种典型的做法。

  • 增加或者减少某些特定的值。万智牌就是这么做的:玩家的20点生命值归零的时候被判定输掉游戏;而WoW则与其相反。需要注意的是,这些值是直接影响到游戏速度的。这里建议将其范围设定在10~30。这样数值的每一次变化都是有意义且不会使得游戏过程变得过于冗长。这个策略的一个变种是使用多个值:例如玩家必须获取10点能量和10点影响力才会获得胜利。

  • 刺杀。这指的是杀掉指定目标的方式(当然这个方目标常是玩家)。Warlords以及Lord of the Rings使用的就是这个方式。这种设计不仅要求玩家考虑到进攻,还需要考虑到防守,并且会带来非同一般的沉迷。它和前面提到的靠达到特定值的方式之间的不同之处是:这种设计能够给玩家一个明确的达到胜利的条件。

  • 确立足够的优势。在Wizard的Star Wars设计了三个星域。在每一个回合结束的时候,如果玩家被判定占领了其中的2个或2个以上,则玩家获得胜利。

  • 生存模式。杀掉所有的敌人(狼人杀?)。这种设计综合了特定值与压倒性优势两种方案。

  • 手牌。当手牌数量为0的时候判定玩家输掉游戏,这通常作为次级判定,特别是当玩家之间的胜负关系出现了死锁的情况。

  • 圣裁。卡牌中包含一些“如果…那么玩家就赢得此局”。这种牌应该谨慎设计,本质上说这是一种类似于随机事件影响过于强大的情况。

Resources, governing the power level of cards

资源。

利用资源的目的在于限制手牌中强力牌面同时被打出的次数。强力的卡牌会比那那些比较弱的卡牌消耗更大的资源。

详略。

Power creep, the death of your CCG

一个持续时间长久,不断推出新卡包的游戏会因为Power creep而快速死掉。

Power creep指的是新出的卡牌过于强力的情况。随着游戏不断更新,情况会变得越来越糟。较为贪婪以及短视的设计者通常会提高新卡的能力值来帮助新玩家更快地赶上老玩家,但这对游戏的长久发展并没有什么太大的好处。对老玩家来说,他们手中的牌都是花了很长时间与心血集起来的,如果新玩家很容易就能得到与之匹敌的卡组,那么这就意味着对老玩家说“你的努力一文不值”,并且对于卡组的搭配策略也会产生不利的影响。新加入的卡应当给基于原有的数值系统而非新的。而如果真的放出了此类卡牌,那么久必须对其作出足够的限制来减少它对游戏平衡性的影响。

Complexity:K.I.S.S.

复杂度。尽量简化游戏核心系统。

尽量不要往游戏里面塞进太多的东西。在Decipher的Star War中,玩家可以在太空中战斗,可以在陆地上战斗,可以占领控制点并且在它们之间移动,可以进行光剑搏击……等其他活动。好处是,这些东西确实还原了星战的氛围,而坏处是游戏变得过于复杂而难于上手。尽量不要把游戏设计得复杂,除非设计的是一款面向重度核心向玩家的游戏。在刚接触游戏时,每个人都是新人,不要让复杂的设计赶走宝贵的玩家。

谨记,设计游戏的时候首先考虑的是玩家,而不是设计师本人。“When you design a CCG, remember that you are creating it for other people and not for you. Make it easy to learn and challenging to master.”

同样,卡面设计也尽量简单,不要有太多复杂的东西。 A lot to read, a lot to forget, and a lot to keep track of。卡面简单并不意味着这张卡就无足轻重。新手设计们很容易就会看重那些繁琐的描述文字,从而将卡面设计的复杂难记。

(关于卡面字体的叙述不再详述)字体除了匹配游戏主题之外,应尽量易于识别。

Different Card Designs for different types of cards

这部分由于个人缺乏相关背景,虽然能够大致明白是在说什么东西,但是找不到合适的对应中文表达出来,还是直接看原文比较好一些。

Writing a tutorial for your game

新手引导。

一个好的新手引导是很重要的——如果玩家不知道整个游戏是在说什么,那就很难让他们继续下去。建议学习一下万智牌的做法(万智牌的教程可以在这里下载到)。当然视频教程更好,毕竟并不是人人都喜欢去看那些长篇大论的文字叙述。可以先展示卡牌,并指出它们之间的不同点。使用图表来说明游戏的目标、卡组的组牌规则。关键词索引是一个很重要的部分(就像字典那样)。

尽可能用图片说明代替文字。

(完)


Trapping Rain Water


Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

TRW

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

求当前位置的左右列中最小的那个,减去该列的值就得到该列可以积存的雨水量。

注释代码是一个O(n*m)的解法:计算每一行可以积存的雨水量。其中m是height数组中的最大值。

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
int trap(vector<int>& height) {
if (height.size() == 0)
return 0;
int sum = 0;
/* A TLE Solution
int MAX = 0;
for (int i = 0; i < height.size(); ++i) {
if (height[i] > MAX) MAX = height[i];
}

queue<int> q;
for (int i = 0; i < MAX; ++i) {
while(q.size()) q.pop();
for (int j = 0; j < height.size(); ++j) {
if (height[j] >= i) q.push(j);
if (q.size() == 2) {
int s = q.front();
int e = q.back();
sum += (e - s - 1);
q.pop();
}
}
}
*/


// AC Solution
vector<int> left(height.size(),0);
vector<int> right(height.size(), 0);
left[0] = height[0];
right[height.size() - 1] = height[height.size() - 1];

for (int i = 1; i < height.size(); ++i) {
if (height[i] < left[i - 1])
left[i] = left[i - 1];
else
left[i] = height[i];
}

for (int i = height.size() - 2; i >= 0; --i) {
if (height[i] < right[i + 1])
right[i] = right[i + 1];
else
right[i] = height[i];
}

for (int i = 0; i < height.size(); ++i) {
sum += ((left[i] > right[i] ? right[i] : left[i]) - height[i]);
}

return sum;
}
};


Red John is Back


Red John has committed another murder. But this time, he doesn’t leave a red smiley behind. What he leaves behind is a puzzle for Patrick Jane to solve. He also texts Teresa Lisbon that if Patrick is successful, he will turn himself in. The puzzle begins as follows.

There is a wall of size 4xN in the victim’s house. The victim also has an infinite supply of bricks of size 4x1 and 1x4 in her house. There is a hidden safe which can only be opened by a particular configuration of bricks in the wall. In every configuration, the wall has to be completely covered using the bricks. There is a phone number written on a note in the safe which is of utmost importance in the murder case. Gale Bertram wants to know the total number of ways in which the bricks can be arranged on the wall so that a new configuration arises every time. He calls it M. Since Red John is back after a long time, he has also gained a masters degree in Mathematics from a reputed university. So, he wants Patrick to calculate the number of prime numbers (say P) up to M (i.e. <= M). If Patrick calculates P, Teresa should call Red John on the phone number from the safe and he will surrender if Patrick tells him the correct answer. Otherwise, Teresa will get another murder call after a week.

You are required to help Patrick correctly solve the puzzle.

Input Format

The first line of input will contain an integer T followed by T lines each containing an integer N.

Output Format

Print exactly one line of output for each test case. The output should contain the number P.

Constraints:

1<=T<=20, 1<=N<=40

Sample Input

1
2
3
2
1
7

Sample Output

1
2
0
3

Explanation

For N = 1, the brick can be laid in 1 format only

The number of primes <= 1 is 0 and hence the answer.

For N = 7, one of the ways in which we can lay the bricks is

Red John

There are 5 ways of arranging the bricks for N = 7 and there are 3 primes <= 5 and hence the answer 3.

一个简单的铺砖问题。

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <cmath>
#include <cstdio>
#include <string.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int DP[41];

#define reset() memset(DP,0,sizeof(int)*41)

int solve(int N) {
if (N == 4) return 2;
if (N <= 0) return 0;
if (N < 4) return 1;
if (DP[N]) return DP[N];
return DP[N] = solve(N-1)+solve(N-4);
}

bool isPrime(int n) {
if (n % 2 == 0) return false;
for (int i = 2; i*i <= n; ++i) {
if (n % i == 0)
return false;
}
return true;
}

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int T;

cin >> T;

for (int i = 0; i < T; ++i) {
int N = 0;
cin >> N;
if (N == 4) {
cout << "1" << endl;
continue;
}
else if (N < 4) {
cout << "0" << endl;
continue;
}
reset();
int r = solve(N);
int c = 1;
while(r>2) {
if (isPrime(r))
++c;
r--;
}
cout << c << endl;
}

return 0;
}


Stock Maximize


Your algorithms have become so good at predicting the market that you now know what the share price of Wooden Orange Toothpicks Inc. (WOT) will be for the next N days.

Each day, you can either buy one share of WOT, sell any number of shares of WOT that you own, or not make any transaction at all. What is the maximum profit you can obtain with an optimum trading strategy?

Input

The first line contains the number of test cases T. T test cases follow:

The first line of each test case contains a number N. The next line contains N integers, denoting the predicted price of WOT shares for the next N days.

Output

Output T lines, containing the maximum profit which can be obtained for the corresponding test case.

Constraints

1 <= T <= 10

1 <= N <= 50000

All share prices are between 1 and 100000

Sample Input

1
2
3
4
5
6
7
3
3
5 3 2
3
1 2 100
4
1 3 1 2

Sample Output

1
2
3
0
197
3

Explanation

For the first case, you cannot obtain any profit because the share price never rises.
For the second case, you can buy one share on the first two days, and sell both of them on the third day.
For the third case, you can buy one share on day 1, sell one on day 2, buy one share on day 3, and sell one share on day 4.

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int M = 0,N = 0;
scanf("%d",&M);
int stocks[50001];
for (int i = 0 ; i < M; ++i) {
scanf("%d",&N);
if (1 == N) {
printf("0\n");
continue;
}
for (int k = 0; k < N; ++k) {
scanf("%d",&stocks[k]);
}
long long MAX = 0;
int flag = N - 1;
for (int j = N - 1; j >= 0; --j) {
if (j > 0) {
if (stocks[j] <= stocks[j - 1])
continue;
else {
flag = j;
while(j >= 0 && stocks[j] <= stocks[flag]) {
MAX += stocks[flag] - stocks[j];
--j;
}
++j;
}
}

}
printf("%lld\n",MAX);
}
return 0;
}


Candy


这个题目在HackerRank上面也有,链接在 这里

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> candies(ratings.size(), 0);
candies[0] = 1;
int flag = 0;
bool less = false;
for (int i = 1; i < ratings.size(); ++i)
{
if (ratings[i] > ratings[i - 1])
{
candies[i] = candies[i - 1] + 1;
}
else if (ratings[i] < ratings[i - 1])
{
flag = i - 1;
while (i < ratings.size() && ratings[i] < ratings[i - 1])
++i;
--i;
int diff = i - flag; // 判断后面有多少个比flag位置小的数
if (diff >= candies[flag])
{
// 重新调整分配的糖果
for (int k = flag; k <= i; ++k)
{
candies[k] = diff+1;
--diff;
}
}
else
{
for (int k = flag + 1; k <= i; ++k)
{
candies[k] = diff;
--diff;
}
}
}
else
{
candies[i] = 1;
}
}

int sum = 0;
for (int i = 0; i < ratings.size(); ++i)
{
sum += candies[i];
}

return sum;
}
};


Font Size


From: HiHoCoder MS April 2016: Font Size

描述

Steven loves reading book on his phone. The book he reads now consists of N paragraphs and the i-th paragraph contains ai characters.

Steven wants to make the characters easier to read, so he decides to increase the font size of characters. But the size of Steven’s phone screen is limited. Its width is W and height is H. As a result, if the font size of characters is S then it can only show ⌊W / S⌋ characters in a line and ⌊H / S⌋ lines in a page. (⌊x⌋ is the largest integer no more than x)

So here’s the question, if Steven wants to control the number of pages no more than P, what’s the maximum font size he can set? Note that paragraphs must start in a new line and there is no empty line between paragraphs.

输入

Input may contain multiple test cases.

The first line is an integer TASKS, representing the number of test cases.

For each test case, the first line contains four integers N, P, W and H, as described above.

The second line contains N integers a1, a2, … aN, indicating the number of characters in each paragraph.

For all test cases,

1 <= N <= 103,

1 <= W, H, ai <= 103,

1 <= P <= 106,

There is always a way to control the number of pages no more than P.

输出

For each testcase, output a line with an integer Ans, indicating the maximum font size Steven can set.

样例输入

1
2
3
4
5
2
1 10 4 3
10
2 10 4 3
10 10

样例输出

1
2
3
2

二分答案。

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;


int N, P, W, H;
int CharNum[1001];

int solve(int fs)
{

if (fs > W || fs > H)
{
return 1000001;
}
// fs 是字体大小
int cols = W / fs; //计算每一行有多少字
int totalLines = 0;

for (int i = 0; i < N; ++i) //计算每一段有多少行
{
int paragLines = CharNum[i] / cols;
if (CharNum[i] - paragLines * cols > 0)
paragLines += 1; // 多的那几个字另算一行
totalLines += paragLines;
}

int LinesPerPage = H / fs; // 一页有几行
int pages = totalLines / LinesPerPage;
if (totalLines - LinesPerPage * pages > 0)
pages += 1; // 多的几行算作一页
return pages;
}

int main(int argc, char** argv)
{

// 二分答案?
int TASKS = 0;
cin >> TASKS;

for (int i = 0; i < TASKS; ++i)
{
// input
cin >> N >> P >> W >> H;
for (int k = 0; k < 1001; ++k)
{
CharNum[k] = -1;
}
for (int j = 0; j < N; ++j)
{
cin >> CharNum[j];
}

int PS = 0;
int S = 1;
int mid = 0;
while (PS < S && mid != P)
{
mid = solve(S);
if (mid < P)
{
PS = S;
S *= 2;
}
else if (mid > P)
{
S = (S + PS) / 2;
}
}
cout << S << endl;
}

return 0;
}

Nim Game


You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

重要的是找出必胜状态与必败状态。

此类问题的正确描述在于注释内的代码,通过递推关系求出结果。

非注释代码只是根据题目取了巧,递推求结果会导致超时。

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:

bool canWinNim(int n) {
/*
if ( n == 0 ) return false;
if ( n <= 3 ) return true;
vector<bool> stones(n,false);
stones[0] = stones[1] = stones[2] = true;
for (int i = 3; i < n ; ++i)
{
if (stones[i-1] && stones[i-2] && stones[i-3])
{
stones[i] = false;
}
else
{
stones[i] = true;
}
}
return stones[n-1];
*/

return !(n % 4 == 0);
}
};


Nim Sum


From: HiHoCoder #1163 博弈游戏·Nim游戏

Nim Sum的应用。

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <vector>
using namespace std;

int main(int argc, char** argv)
{

int N = 0;
cin >> N;
if (N == 1)
{
cout << "Alice" << endl;
return 0;
}
int M = 0;
cin >> M;
int r = M;
for (int i = 1; i < N; ++i)
{
cin >> M;
r ^= M;
}
(r == 0) ? (cout << "Bob" << endl) : (cout << "Alice" << endl);

return 0;
}

Word Break


Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given

s = “leetcode”,

dict = [“leet”, “code”].

Return true because “leetcode” can be segmented as “leet code”.

呃……DP?

感觉代码写的挺不好的……

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
public:
vector<vector<int>> DP;
bool solve(int begin, int end, string& s, unordered_set<string>& wordDict)
{

if (begin > end) return false;
if (DP[begin][end] == 1) return true;
else if (DP[begin][end] == 2) return false;
if (begin == end)
{
string str;
str.push_back(s[begin]);
if (wordDict.find(str) != wordDict.end())
{
DP[begin][end] = 1; return true;
}
else
{
DP[begin][end] = 2; return false;
}
}
else if (begin > end)
{
DP[begin][end] = 2;
return false;
}
else
{
string str;
for (int i = begin; i <= end; ++i)
{
str.push_back(s[i]);
}
if (wordDict.find(str) != wordDict.end())
{
DP[begin][end] = 1; return true;
}

for (int i = begin; i <= end; ++i)
{
bool l = solve(begin, i, s, wordDict);
bool r = solve(i+1, end, s, wordDict);
if (l && r)
{
DP[begin][end] = 1; return true;
}
else
{
if (0 == DP[begin][end])
{ DP[begin][end] = 2; }
}
}
}
DP[begin][end] = 2;
return false;
}

bool wordBreak(string s, unordered_set<string>& wordDict) {
DP = vector<vector<int>>(s.length(),vector<int>(s.length(),0));
return solve(0, s.length()-1, s, wordDict);
}
};

正文


最近在写开题报告,基本就是把弄一个Material Editor需要做的事情捋一遍。

结果这一遍捋过之后发现这货其实跟CG本身并没有太大关联,倒是跟Visual Programming关系挺好的。

这样要做的基本上大半个属于编译领域的事情了。前端就是一个UI系统,中间代码就是HLSL/GLSL/CG代码,至于后端……把生成的代码直接交付给Shader编译器也可以,想自己优化一遍也可以(因为中间代码肯定是有冗余的,我想试着做做看)。

大致脉络有了,方法也有了,就看码力了。

勉!

Dijkstra最短路径


借用HiHo的一个题,来讨论一下单源最短路径问题。

From: HiHoCoder HiHo一下第23周

万圣节的早上,小Hi和小Ho在经历了一个小时的争论后,终于决定了如何度过这样有意义的一天——他们决定去闯鬼屋!

在鬼屋门口排上了若干小时的队伍之后,刚刚进入鬼屋的小Hi和小Ho都颇饥饿,于是他们决定利用进门前领到的地图,找到一条通往终点的最短路径。

鬼屋中一共有N个地点,分别编号为1..N,这N个地点之间互相有一些道路连通,两个地点之间可能有多条道路连通,但是并不存在一条两端都是同一个地点的道路。那么小Hi和小Ho至少要走多少路程才能够走出鬼屋去吃东西呢?

输入

每个测试点(输入文件)有且仅有一组测试数据。

在一组测试数据中:

第1行为4个整数N、M、S、T,分别表示鬼屋中地点的个数和道路的条数,入口(也是一个地点)的编号,出口(同样也是一个地点)的编号。

接下来的M行,每行描述一条道路:其中的第i行为三个整数u_i, v_i, length_i,表明在编号为u_i的地点和编号为v_i的地点之间有一条长度为length_i的道路。

对于100%的数据,满足N<=10^3,M<=10^4, 1 <= length_i <= 10^3, 1 <= S, T <= N, 且S不等于T。

对于100%的数据,满足小Hi和小Ho总是有办法从入口通过地图上标注出来的道路到达出口。

输出

对于每组测试数据,输出一个整数Ans,表示那么小Hi和小Ho为了走出鬼屋至少要走的路程。

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
5 23 5 4
1 2 708
2 3 112
3 4 721
4 5 339
5 4 960
1 5 849
2 5 98
1 4 99
2 4 25
2 1 200
3 1 146
3 2 106
1 4 860
4 1 795
5 4 479
5 4 280
3 4 341
1 4 622
4 2 362
2 3 415
4 1 904
2 1 716
2 5 575

样例输出

1
123

这里先给出AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX-1)

int N, M, S, T;

vector<vector<int>> graph;

int ans = 0;

vector<int> curs;

vector<int> vis;

vector<int> costs;

int findNext()
{

int MIN = INT_MAX;
int next = 0;
for (int i = 1; i < N + 1; ++i)
{
if (costs[i] < MIN && vis[i] == 0)
{
MIN = costs[i];
next = i;
}
}
return next; // <------------------------ 注意这里的next
}

void solve()
{

while (true)
{
int next = findNext();
if (next == 0) break;

// <------------------------- 注意这里的松弛操作
for (int i = 1; i <= N; ++i)
{
if (graph[next][i])
{
int len = costs[next] + graph[next][i];
if (len < costs[i])
costs[i] = len;
}
}

curs.push_back(next);
vis[next] = 1;
}

ans = costs[T];
}

int main(int argc, char** argv)
{

cin >> N >> M >> S >> T;

graph = vector<vector<int>>(N + 1, vector<int>(N + 1, 0));
vis = vector<int>(N + 1, 0);
costs = vector<int>(N + 1, INT_MAX);

for (int i = 0; i < M; ++i)
{
int a, b, c;
cin >> a >> b >> c;
if (graph[a][b] == 0)
{
graph[a][b] = c;
graph[b][a] = c;
}
else
{
if (graph[a][b] > c)
{
graph[a][b] = c;
graph[b][a] = c;
}
}
}
costs[S] = 0;

solve();

cout << ans << endl;

return 0;
}

讲解Dijkstra算法的文章有很多,算法本身的思想也不难,这里不再多说,主要说明一下关于为何会想到用 “队列” 来加速Dijkstra算法。

请注意上面代码中,findNext 函数中的 返回值 next,以及松弛操作的过程。结合图例说明一下,就很明了了。

原始图状态:

Graph

下面规定:在图中,未访问的节点标记为绿色,已访问的节点标记为红色,得到的next节点标记为黄色,经过松弛操作但未访问的节点为青色。源点为 5 号节点。

第一次得到的next:

N1

第一次松弛操作之后:

S1

第二次得到的next:

N2

第二次松弛操作之后:

S2

第三次得到的next:

N3

第三次松弛操作之后:

S3

第四次得到的next:

N4

第四次松弛操作之后:

S4

第五次得到的next:

N5

第五次松弛操作之后:

S5

这样就结束了,得到了源点 5 到途图中所有可达节点的最短路径值。

注意上面步骤的青色节点的变化,优化就是在这个上面做文章了:使用一个队列来维护青色节点,初始状态下,队列只包含起点可达节点,当队列为空的时候,算法结束。

由于next的节点要选取到源点最近的节点,因此应当使用一个优先队列,每次松弛操作之后应当把新增的候选节点加入到该队列中。

下面是AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <fstream>
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;

#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX-1)

int N, M, S, T;

vector<vector<int>> graph;

struct Node
{
int index;
int cost;
friend bool operator<(const Node& l, const Node& r);
};

bool operator<(const Node& l, const Node& r)
{
return l.cost > r.cost;
}

int ans = 0;

vector<int> curs;

vector<int> vis;

vector<int> costs;

vector<Node> q;

void solve()
{

while (q.size())
{
make_heap(q.begin(), q.end());
int next = q[0].index;
pop_heap(q.begin(), q.end());
q.pop_back();

for (int i = 1; i <= N; ++i)
{
if (graph[next][i] && 0 == vis[i])
{
int len = costs[next] + graph[next][i];
if (len < costs[i])
{
costs[i] = len;
bool exist = false;
// 修改值
for (auto it = q.begin(); it != q.end(); ++it)
{
if (it->index == i)
{
it->cost = len;
exist = true;
}
}
if (false == exist)
{
Node n;
n.cost = len;
n.index = i;
q.push_back(n);
}
}
}
}

curs.push_back(next);
vis[next] = 1;
}

ans = costs[T];
}

int main(int argc, char** argv)
{

cin >> N >> M >> S >> T;

graph = vector<vector<int>>(N + 1, vector<int>(N + 1, 0));
vis = vector<int>(N + 1, 0);
costs = vector<int>(N + 1, INT_MAX);

for (int i = 0; i < M; ++i)
{
int a, b, c;
cin >> a >> b >> c;
if (graph[a][b] == 0)
{
graph[a][b] = c;
graph[b][a] = c;
}
else
{
if (graph[a][b] > c)
{
graph[a][b] = c;
graph[b][a] = c;
}
}
}

curs.push_back(S);
costs[S] = 0;

Node n;
n.cost = 0;
n.index = S;
q.push_back(n);

solve();

cout << ans << endl;

return 0;
}

A*算法


A*算法是一种启发式算法。

在某种程度上,可以将Dijkstra算法视为是一种BFS。BFS的特点就是首先确定搜索边界,并对这个边界上的每一个点进行处理。

如果在处理搜索边界上的点时,能够估计一下它们距离目标结点的开销,并且将其考虑进去,那么就可以提高算法的执行效率。

如果算法使用的启发因子给出的是从任何节点到目标节点的实际开销的下限,那么A*可以保证给出最优解。

最直接的就是计算节点之间的直线距离(笛卡尔坐标系下)。

A*算法的估价函数可以表示为:f’(n) = g’(n) + h’(n)。其中f’(n)是估价函数,g’(n)是起点到终点的最短路径值,h’(n)是节点N到到目标节点的路径的启发值。

以上来源于:Mat Buckland 《游戏人工智编程案例精粹》 以及 王敬东 《游戏地图寻径及地图编辑器的研究》

这里先放上两篇对A*讲解很不错的文章。

两篇文章对A*的工作方式介绍的很清楚,这里就不再多说。只说一下需要注意的一些地方:

  • A*所谓的 OPEN(开启) 与 CLOSE(关闭) 表,实际上与前述Dijkstra算法中的红色节点与青色节点一致。
  • A*算法的next节点判定实际上是由两个量来决定的:源点到当前结点的最短路 以及 当前节点到目标节点的启发值(例如笛卡尔坐标系下的直线距离)。
  • 建议先弄清楚Dijkstra算法,然后看第二篇文章,搞清白三个值是怎么起作用的,后面再去看那个英文的专讲。