JURUO怎么写 qwertier's blog

Google Kickstart 2017 Round D

总结:做了一下Google Kickstart 2017 Round D,搞了两道题,最后Rank 18,感觉Google免费一日游应该有了?

废话:还剩30+45s的时候提交了第二题的小数据,还剩45s的时候提交了第二题的大数据\流汗。C连题都没看。。。

题解:以后再补吧。

Finger Search与启发式合并

n个元素(分别属于n个不相交的集合),使用二叉搜索树进行维护,进行n-1次合并,每次将两个集合合并。当使用的数据结构段为线段树时,整个过程的时间复杂度是的。然而,软萌教会了我使用Splay而不只是线段树(毕竟Splay支持的操作更多)来进行这n-1次启发式合并,且复杂度仍然保持为的方法。

首先,使用Splay启发式合并的复杂度为,其中为一个Splay中的每个元素插入到另一个Splay中的均摊复杂度。显然,。然而有一个小trick可以使

这个小trick即是:把树1(元素个数为n)合并到树2(元素个数为m),我们将树1中的元素按照树1中序遍历的顺序一一插入到树2中,且每次插入后都要Splay。

为啥能这样做呢?以后再补。因为我也不会

写在Braid通关之后

16年Steam圣诞节特惠的时候,看到一个口碑不错的游戏打折1,于是喜+1。然而下载下来之后试玩,并没有被吸引到。没有被吸引到的原因也很简单——画风。个人还是比较喜欢真实系的游戏,这种浓浓的油画风格的游戏,即使在画面里高高挂着太阳,也莫名让我有一种抑郁的感觉。另外主人公的设计也很怪异,见过穿着军装、牛仔裤或者不穿衣服(?)的,但从来没见过主角西装革履的横版过关游戏。穿着西服真的能蹦蹦跳跳吗。

于是游戏没玩多久就删了。

然而,跟叶忠豪讨(jiao)论(liu)项(you)目(xi)的时候,听到他Braid正玩得不亦乐乎。后来期末考完,Bioshock Infinite通关之后,没有游戏玩,想起叶神的安利,于是重新捡起了Braid。然后就一发不可收拾,没看攻略,断断续续用了十多个小时终于通关。

游戏的规则非常简单,主人公有若干技能:回退到某个时间点、产生影子做你做过的事以及产生一个放慢时间的力场。同时游戏里还有一些道具:钥匙、门、不受时间回退技能影响的道具、使主人公不受时间回退技能影响的道具以及“帮助”你通关的移动的怪物等等。然而,简单的规则,却被作者挖掘出了巧妙的用法,有时候让人不得不想很长时间、做很多尝试才能解开这些谜题。甚至有一个早晨,朦胧中想到了一关的解法,于是起床过了那一关之后回到床上继续睡觉。

回到某个时间点的技能

游戏的剧情非常混乱,快要玩完游戏时,我对故事的含义也一点头绪也没有。然而,当游戏玩到了最后一刻,看到了

Someone near him said: “It worked.”

Someone else said: “Now we are all sons of bitches.”

我才明白游戏的真正含义,主人公即是奥本海默2,而所谓的公主便是原子弹。主人公的时间回溯的能力不过是奥本海默在现实中的对自己所作所为的悔意在游戏中的映射。

如果不考虑游戏的剧情3,只考虑游戏的玩法4,Braid确实无法挑剔。但我对玩法包装了剧情还是剧情包装了玩法有点疑问。换句话说,作者到底是先想了大概的剧情,还是先做出了游戏的主体。产生这个疑问的原因是很难看出游戏剧情与游戏游玩的过程中的关系。游戏里的许多道具、角色和障碍很难找到象征的事物,十分让我费解,也许其中有更深刻的东西我还没感受到。但¥4花得很值倒是真的。

游戏最后一关,主人公历经万难“救”公主,整个过程倒放之后,俨然成了公主从主人公身边逃离,很耐人寻味。

  1. 当时只要¥4. 

  2. “曼哈顿计划”的实验室主任,被誉为“原子弹之父”,组织研制了原子弹。 

  3. 给玩家看的剧情和内涵的剧情。 

  4. 游戏的操作、游戏的规则和游戏的障碍或谜题。 

HDU 5828 Rikka with Sequence (2016 Multi-University Training Contest 8 1008)

题目大意是:给定一个序列,三种操作:

  1. 区间加
  2. 区间开方
  3. 区间和

首先,官方题解是有一点小问题的。虽然对于任意,但是不一定小于(有可能等于)。例如,。比赛时,估计至少有一半以上的程序没有考虑这个问题(std也没考虑)。(然而我啥都不会,关我什么事。)

按照官方题解的思路,我们可以用线段树维护区间和、区间加标记、区间最小值与最大值,当区间最小值等于区间最大值时(此时区间中的每个数都相同),将区间开方转化为区间加,当区间i最小值不等于最大值时,递归到左右子树,继续开方。

比赛时很多人都写了这样的算法,然而这样的解法可以被卡掉。序列为,然后区间和区间开方循环。。。

其实这种情况很好规避,正确的解法只需要加几个判断。如果而且或者,区间加;否则递归到左右子树,继续开方。

代码点此

Fast Walsh-Hadamard Transform

2016 Multi-University Training Contest 8 1003, color II

昨天多校打崩了,花了很长时间在第3题上。第三题题意大致是:给定一个无向图(),求出每个导出子图的色数。感觉的解法应该算是比较经典,(S’为S的子集,且S’是一个独立集)。然而tm数据防水,赛后才知道这样的复杂度已经能过了。。。

no_desire_to_live

不过话说回来,这题有比更优的做法。

Fast Walsh-Hadamard Transform

表示点集S是否为独立集,表示用i种颜色染点集是否可行,那么我们有,用加法来表示“或”,用乘法来表示“与”,我们有,是不是有点像卷积?所以我们可以用FWT来解决啦。

FWT(Fast Walsh-Hadamard Transform)的作用是加速这一类计算:

上式中,可以表示“与”、“或”、“异或”中的任意一类运算。

按照FFT的套路,我们希望能找到FWT与对应的IFWT,使得上述问题可在四步以内解决:

  1. 求出
  2. 求出
  3. 通过求出
  4. 通过,求出

对于一个,长度为。设表示表示。[.]

AND

通过某种构造,可以得到上式中表示“与”运算时的FWT为:

OR

“或”的FWT为:

XOR

代码:

namespace FWT {
template <typename T>
void or_fwt(T X[], int l, int r) {
if (l == r)
return;
int m = (l + r) >> 1;
or_fwt(X, l, m); or_fwt(X, m + 1, r);
for (int i = 0; i <= m - l; i++) {
X[m + 1 + i] += X[l + i];
}
}
template <typename T>
void or_ifwt(T X[], int l, int r) {
if (l == r)
return;
int m = (l + r) >> 1;
or_ifwt(X, l, m); or_ifwt(X, m + 1, r);
for (int i = 0; i <= m - l; i++) {
X[m + 1 + i] -= X[l + i];
}
}
template <typename T>
void and_fwt(T X[], int l, int r) {
if (l == r)
return;
int m = (l + r) >> 1;
and_fwt(X, l, m); and_fwt(X, m + 1, r);
for (int i = 0; i <= m - l; i++) {
X[l + i] += X[m + 1 + i];
}
}
template <typename T>
void and_ifwt(T X[], int l, int r) {
if (l == r)
return;
int m = (l + r) >> 1;
and_ifwt(X, l, m); and_ifwt(X, m + 1, r);
for (int i = 0; i <= m - l; i++) {
X[l + i] -= X[m + 1 + i];
}
}
template <typename T>
void xor_fwt(T X[], int l, int r) {
if (l == r)
return;
int m = (l + r) >> 1;
xor_fwt(X, l, m); xor_fwt(X, m + 1, r);
for (int i = 0; i <= m - l; i++) {
X[l + i] += X[m + 1 + i];
X[m + 1 + i] = X[l + i] - 2 * X[m + 1 + i];
}
}
template <typename T>
void xor_ifwt(T X[], int l, int r) {
if (l == r)
return;
int m = (l + r) >> 1;
for (int i = 0; i <= m - l; i++) {
X[l + i] += X[m + 1 + i];
X[m + 1 + i] = X[l + i] - 2 * X[m + 1 + i];
X[l+i] /= 2;
X[m + 1 + i] /= 2;
}
xor_ifwt(X, l, m); xor_ifwt(X, m + 1, r);
}
}
鲁ICP备16001914号