阿毛的笔记本

修合无人见,存心有天知

减肥计划

俺又开始减肥啦!

不得不说,因为某些原因的激励(当然是钱!),我准备在当前体重的基础上再减40斤。

熟悉笔者的人都知道,笔者已经在大体重基数上成功减掉了60斤大肥肉(并基本完整的保持到了现在)。因为有了之前成功经验,又有了让我无敌鸡血的动力,所以笔者对这次减肥很有信心。

直接上计划吧! 其实是直接写在手机备忘录里的,但感觉搬到博客上更有仪式感,嘿嘿嘿。 READ MORE →

真实玩者成长记ep1

我来里是了逃避现实,但我发现比自己更重要的西,我交到了多朋友,我找到了真爱。 ——《头号玩家》

 

打小我就是个喜欢游戏的孩子。与世呼吸了将近20年,很年轻,但我不知道这颗热爱游戏的心还是否能同我的生命,一直跳动下去。这些年来,遇到了很多精彩的好游戏,很多精彩的故事。我不想失去这些五颜六色的回忆,有感而发,随笔一些文字来记下从小到大我遇上的那些难忘、难言、感动的体验。

 

启蒙:PlayStation时光

我最早开始接触游戏应该是三四岁,那时候老叔有一台PS1。就是最早的,读碟、得插存档卡的那种。现在回忆起来真的感觉有些遥远。

图 1 最早的PlayStation开机画面

图 2  PlayStation

一回忆著一拈看,便似花前重见面。

  • 《古惑狼》

玩的最多的,是一头狼的冒险故事,有神庙,有机关。可以在水下驾驶潜艇,前往一个又一个的岛上去战斗。这是《古惑狼》(Crash Bandicoot)。但Bandicoot的汉译是袋狸,我可能就直接翻译成《碰碰狐》了(那估计玩的人就少了,毕竟碰碰狐这个名字太丑…)。

图 3  其实是袋狸的古惑狼

图 4  原版游戏画面

  • 《皇牌空战》

有一个开战斗机的游戏、发射导弹贼刺激。这是《皇牌空战3》(Ace Combat 3)。那会儿觉得代入感十足,就像真的在开战斗机,帅得很。也正是因为这款游戏,我变得特别钟爱于fps游戏中驾驶战斗机的部分。现在整天泡在新时代的画面下,再回头看,顿时觉得游戏技术的发展真的改变了很多。

图 5  《3》的封面

图 6  《3》的游戏画面

图 7  2019年出品的《7》代画面

 

  • 《合金弹头》

印象最深刻的,就是《合金弹头》(Metal Slug)。这个游戏我打的最多,晚上关了灯在床上疯狂搓手柄的场面还历历在目。现在回忆起来,我当时玩的应该是《X》,因为第二关是木乃伊关,但也有可能是《1》,因为《1》上有没有木乃伊关我不知道。后来在PSP上玩历代合集的时候也是,一直分不清楚哪代是哪代,总之突突突就完事了。

图 8  某代四人组 By: TakxxxYoxxxx

图 9  多代人物合照 By: Tonko

dfs练习题两道

#1 n皇后问题

检查一个如下的6 x 6的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行,每列,每条对角线(包括两条主对角线的所有对角线)上都至多有一个棋子。
1 2 3 4 5 6
1 O
2 O
3 O
4 O
5 O
6 O
上面的布局可以用序列2 4 6 1 3 5来描述,第i个数字表示在第i行的相应位置有一个棋子,如下:
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5

READ MORE →

常用背包模板

背包问题主要是背模板,这一段时间一直在学习背包相关的问题,记录几个dp模板吧。

一些复杂的背包问题(如泛化物品)未收录

01背包问题:

无优化

for(int i=1;i< =n;i++)
{
    for(int j=0;j<=m;c++)
    {
        f[i][j]=f[i-1][j];
        if(j>=w[i])
        f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i]);
    }
}

一维数组优化:

for(int i=1;i< =n;i++)
{
    for(int j=m;j>=0;j--)
    {
        if(j>=w[i])
        f[j]=max(f[j],f[j-w[i]]+v[i]);
    }
}

更进一步的常数优化:

for(int i=1;i< =n;i++)
{
    sumw+=w[i];
    bound=max(m-sumw,w[i]);
    for(int j=m;j>=bound;j--)
    {
        if(j>=w[i])
        f[j]=max(f[j],f[j-w[i]]+v[i]);
    }
}

READ MORE →

线性筛素数

日常突然更新的学习笔记。

最近做了一道在很大的范围里筛选出素数的神仙题,因为超时搞得很头疼,所以想来深入了解一下线性筛法,提高程序运行效率。

我们常说的线性筛是指在线性时间内把素数表筛出来的过程,这里介绍两种筛法.

一般筛法(埃拉托斯特尼筛法):

基本思想:素数的倍数一定不是素数

实现方法:用一个长度为N+1的数组保存信息(0表示素数,1表示非素数),先假设所有的数都是素数(初始化为0),从第一个素数2开始,把2的倍数都标记为非素数(置为1),一直到大于N;然后进行下一趟,找到2后面的下一个素数3,进行同样的处理,直到最后,数组中依然为0的数即为素数。

说明:整数1特殊处理即可。

举个例子

我们筛前20个数

首先初始为(0代表不是素数,1代表是素数)

0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

然后从2开始我们发现2被标记为素数,我们把2的倍数全部筛掉

变为:

0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

接着到3我们发现3仍然被标记,把3的倍数全部筛掉

变为:

0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0

接着一直重复下去就得到了最后的素数表:

0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0
2 3 5 7 11 13 17 19

 

const int MAXN = 1000000;  
void get_list()  
{  
    int i, j;  
    for (i=0; i<MAXN; i++) prime[i] = 1;  
    prime[0] = prime[1] = 0;  
    for (i=2; i<MAXN; i++)  
    {  
        if (!prime[i]) continue;  
        for (j=i*2; j<MAXN; j+=i) prime[ j ] = 0;  
    }  
}//调和级数证明可得复杂度为(nlglgn),所以不能称之为线性筛,但是它的实际运行速度也不是特别慢

下面我们来介绍一波真正的线性筛(欧拉筛法):

我们发现在上面的筛法中有的数字是多个素数的倍数,也就是说它可能会被重复计算多次,比如说6同时是2与3的倍数,它在计算时就被访问了两次,这样会导致效率低下,所以在下面的算法中我们考虑如何优化这种情况。

原理:

任何一个合数都可以表示成一个质数和一个数的乘积

假设A是一个合数,且A = x * y,这里x也是一个合数,那么有:

A = x * y; (假设y是质数,x合数)

x = a * b; (假设a是质数,且a < x——>>a A = a b y = a Z (Z = b y)

即一个合数(x)与一个质数(y)的乘积可以表示成一个更大的合数(Z)与一个更小的质数(a)的乘积,那样我们到每一个数,都处理一次,这样处理的次数是很少的,因此可以在线性时间内得到解。

仍然按上面的例子模拟(这里0为是素数,1为非素数,p为记录的素数表):

初始:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

p(empty)

然后到2的位置,把2放入素数表,做当前范围内可以筛掉的处理(具体是怎样的看代码叭):

1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

p 2 到3,把3放入素数表,继续处理

1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0

p 2 3 然后到了4,它不是个素数,也处理一下

1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0

p 2 3 …….

然后一直搞下去,最后也能得到完整的素数表,这样虽然看起来复杂一些,但是实际上我们发现对于每个数的处理几乎是O(1)的。

 void get_list(){
       for(int i=2;i<=maxn;i++){
             if(!is_not_pr[i]) prime[++tot]=i;
             for(int j=1;j<=tot&&i*prime[j]<=maxn;j++){
                   is_not_pr[i*prime[j]]=1;//合数标为1,同时,prime[j]是合数i*prime[j]的最小素因子
                   if(i%prime[j]==0) break;//即比一个合数大的质数和该合数的乘积可用一个更大的合数和比其小的质数相乘得到
             }
       }
}

所以说有了这两个东西后a掉那道题就很轻松了_(:зゝ∠)_