阿毛的笔记本

修合无人见,存心有天知

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
这只是跳棋放置的一个解。请遍一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。

特别注意: 对于更大的N(棋盘大小N x N)你的程序应当改进得更有效。不要事先计算出所有解然后只输出,这是作弊。如果你坚持作弊,那么你登陆USACO Training的帐号将被无警告删除

输入

一个数字N  (6  < =  N  < =  13)  表示棋盘是N  x  N大小的。

输出

前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。

样例输入

6

样例输出

2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 4
#include <bits/stdc++.h>
using namespace std;
int a[100];
bool b[100],c[100],d[100];
int sum=0;
int n;
void prints()
{
    if(sum<3){
        for(int i=1;i<=n;i++)
        {
            cout<<a[i];
            if(i!=n)cout<<" ";
        }  
   
        cout<<endl; } sum++; } void queen(int i){ if(i>n) {
        prints();
        return;
    }
    else{
        for (int j=1;j<=n;j++) { if((!b[j])&&(!c[i+j])&&(!d[i-j+n])) { a[i]=j; b[j]=true; c[i+j]=true; d[i+n-j]=true; queen(i+1); b[j]=false; c[i+j]=false; d[i+n-j]=false; } } } } int main() { cin>>n;
    queen(1);
    cout<<sum;
    return 0;
}

#2 单词接龙

单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如 beastastonish,如果接成一条龙则变为beastonish,另外相邻的两部分不能存在包含关系,例如at 和 atide 间不能相连。

 

输入

输入的第一行为一个单独的整数n (n \le 20)表示单词数,以下n 行每行有一个单词,输入的最后一行为一个单个字符,表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

输出

只需输出以此字母开头的最长的“龙”的长度

样例输入

5
at
touch
cheat
choose
tact
a

样例输出

23

说明

(连成的“龙”为atoucheatactactouchoose)

NOIp2000提高组第三题

 

#include <bits/stdc++.h>
using namespace std;
string ss[20];
int use[20],length=0,n;
int canlink(string str1,string str2)
{
    for(int i=1;i<min(str1.length(),str2.length());i++)
    {
        int flag=1;
        for(int j=0;j<i;j++)
            if(str1[str1.length()-i+j]!=str2[j])flag=0;
        if(flag) return i;
    }
    return 0;
}
void solve(string strnow,int lengthnow)
{
    length=max(length,lengthnow);
    for(int i=0;i<n;i++)
    {
        if(use[i]>=2)continue;
        int c = canlink(strnow,ss[i]);
        if(c>0)
        {
            use[i]++;
            solve(ss[i],lengthnow+ss[i].length()-c);
            use[i]--;
        }
    }
}
int main()
{
    memset(use,0,sizeof(use));
    cin>>n;
    for(int i=0;i<=n;i++) cin>>ss[i];
    solve(' '+ss[n],1);
    cout<<length;
    return 0;
}

常用背包模板

背包问题主要是背模板,这一段时间一直在学习背包相关的问题,记录几个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掉那道题就很轻松了_(:зゝ∠)_

GCD的几种实现方法

最简单的gcd算法:

int gcd(int x, int y)
{
     if(y == 0) return x;    
     if(x < y)      return gcd(y,x);    
     else        return gcd(y, x%y);
}

ACM中常用的gcd算法:

int gcd(int a, int b){ return a == 0 ? b : gcd(b % a, a); }

经过优化的gcd算法(分成奇偶两种情况):

int gcd(int x,int y )
{
    if(x < y) return gcd(y,x);  // x>y
    if( y == 0) return x;  // if y=0, x is GCD
    else
    {
         if( !(x%2) )
         {                
           if( !(y%2) )  //x,y both even
               return 2*gcd(x >> 1, y >> 1);    
          else      // x is even, y is odd
               return gcd(x >> 1, y );  
         }
          else
         {
           if( !(y%2) )  // x is  odd,  y is even
               return gcd(x, y >> 1);
           else       // x, y both odd
               return gcd(y,x-y);
         }
    }
}

LG P1308 统计单词数

这本来是一道自动机的水题。但是可以用一个很巧妙的结构化解法,这样能大大缩减代码长度,并且降低了这道题的难度(让它更水)。

在这里贴一下代码,如下:

//定义头文件
#include <iostream>
#include <string>
//命名空间
using namespace std;
int main(){
    //定义两个字符串
    string a;
    string b;
    //用string库,调用getline, 直接读入一整行
    getline(cin,a);
    getline(cin,b);
    //转换大小写,可以都转换为大写,或者小写
    for (int i=0;i<a.length();++i){
        a[i]=tolower(a[i]);
    }
    for (int i=0;i<b.length();++i){
        b[i]=tolower(b[i]);
    }
    //因为连起来的不算,所以要在前后加几个空格,一定要是同样多的,同量减同量,等于同量
    a=' '+a+' ';
    b=' '+b+' ';
    //先看看会不会找不到,用a.find()和string::npos
    if (b.find(a)==string::npos){
        cout<<-1<<endl;
    }
    //如果找得到
    else {
        int alpha=b.find(a);
        int beta=b.find(a),s=0;//计数器初始化为0
        while (beta!=string::npos){
            ++s;//计数器
            beta=b.find(a,beta+1);
        }
        cout<<s<<" "<<alpha<<endl;//输出第一个和总共有几个
    }
    //函数返回值为0,结束整个程序
    return 0;
}

 

ACM-ICPC Asia Qingdao Regional Contest, Online

前言:
昨天参加了一波青岛赛区的ACM网络赛,很快乐的水了一下午,感觉自己一直不在状态。

只做出来五道题,C题思路有问题,WA了几次,超时了几次,罚时罚到爆炸。

简单记录一下五道题的思路和代码。

READ MORE →

sshd连接修复笔记

前言:阿毛这个博客服务器的sshd从几个月前就出现问题,命令只能通过管理控制台自带的SVN去执行,并且是osx自带的ssh和windows的xshell都连不上。这就让人很难受了。

查了很多资料,但是鄙人实在是太菜了,一直没找到是哪里出的问题,重启也重启了,补包也补包了,重装也重装了,甚至还自己写了几个脚本想强行启动,但始终是不行。

所以阿毛就需要找一个解决方案,因为本身就是一个linux小白,加上懒,所以一开始是想通过提交工单解决这个问题的,但是体验很一般(手动掰掰),搁置了很长时间,直到今天才修复。


READ MORE →

大桥施工笔记

鉴于某些不可描述的原因,科学上网的路越来越窄,笔者不得不自己搭桥。

为了以防记忆丧失,无法正确使用大桥,便写下这篇笔记。


 

已于2019年8月23日更新
SSR部署脚本(CentOS6/Debian6/Ubuntu14 ):

yum -y install wget
wget –no-check-certificate https://freed.ga/github/shadowsocksR.sh; bash shadowsocksR.sh

SSR管理界面命令:

bash ssr.sh

锐速安装

(只支持 CentOS6 x64 及 CentOS7 x64 系统,不支持任何 Debian & Ubuntu 系统)

用Xshell连接服务器后,执行下面命令。

uname  -r

回车后输出当前系统内核版本。主要分三种情况:

1、结果以 2 开头,例如 2.6.32-696.18.7.el6.x86_64。

这种输出结果说明我们的服务器为 CentOS6 x64 系统,大家直接查看第三步进行锐速安装即可。

2、结果以 3 开头,例如 3.10.0-693.11.6.el7.x86_64。

这种输出结果说明我们的服务器为 CentOS7 x64 系统,大家直接查看第四步进行锐速安装即可。

3、结果以 4 开头,例如 4.12.10-1.el7.elrepo.x86_64。

这种输出结果说明我们的服务器已经安装 Google BBR 拥塞控制算法,此时已经无法继续安装锐速。

CentOS6 x64 系统安装锐速

若确定服务器为 CentOS6 x64 系统则看这一步。

按照下图提示,我们继续复制下列命令:

wget --no-check-certificate -O appex.sh
https://raw.githubusercontent.com/hombo125/doubi/master/appex.sh
&& bash appex.sh install '2.6.32-642.el6.x86_64'

 

CentOS7 x64 系统安装锐速

若确定服务器为 CentOS7 x64 系统则看这一步。

按照下图提示,我们继续复制下列命令:

wget --no-check-certificate -O rskernel.sh
https://raw.githubusercontent.com/hombo125/doubi/master/rskernel.sh
&& bash rskernel.sh

等待内核更换完毕后系统会自动重启并断开连接。然后重新连接,执行下面命令。

 yum  install net-tools -y &amp;&amp; wget -- no-check-certificate -O appex.sh
https://raw.githubusercontent.com/0oVicero0/serverSpeeder_Install/master/appex.sh
&& bash appex.sh install

若系统选择是CentOS6 x64,不需要更换内核,直接执行下列安装命令

wget  -- no-check-certificate -O appex.sh https://raw.githubusercontent.com/0oVicero0/serverSpeeder_Install/master/appex.sh
&& bash appex.sh install '2.6.32-642.el6.x86_64'

安装步骤一路回车就行了。

开发计划

手头的开发计划(坑)有两个,简单做一下记录。

READ MORE →

网站折腾记

从保定回来以后,就马不停蹄的做这个网站。

本来准备复活已经积灰的妹Blog,结果我的新浪云早就因为拖欠续费凉凉了。翻箱倒柜之前的数据备份也找不到了,很是心累,于是才有了推翻重做的打算。

在Hostker和Aliyun两家服务商之间犹豫了很久,最终选择了性价比较高的Hostker,其实最主要的是这家的UI做的太萌了。

服务器各方面都很满意,就是官方限制SSR有点难受。当然了,政策优先,毕竟不能跟官方对着干。

多年来一直使用WindowsServer,这是第一次实际上手Linux的服务器。不得不说,Linux的确是运行效率高,少了很多杂七杂八的进程,更适合做服务器。

我从16年信竞退役以后就没怎么培养过自己的前端技术,很明显感觉到现在手生了不少。技术要慢慢练,争取4年后能在圈内分得一点小小位置。

15年之前有一个ihtml.org的域名,我把所有的作品都放在里面了。当时的服务器是童老板提供的一台香港的VPS,配置很高,用着也很满意。但自己手残给整个网站上了个加密应用,只有随机生成的一把秘钥。果不其然,我找不到秘钥了,所有的作品也都凉凉了。当时有一些我现在觉得还能惊艳到自己的作品,我准备尽量的搜集。所以从今天开始,我会把我能找到的完整或者接近完整的作品逐一放在实验室里,不接受对当时作品的任何批评,请诸君静言慢赏。

接触互联网开发已经快5年了,回头看看过去,还是挺感慨的。一路高歌,无人相伴,但风雨无阻。

这次的博客折腾好以后就不再大动了,计划19.6前写一个完全独立开发的WP模版出来。

不知道是不是错觉,总感觉身边建站的人少了。这究竟是单纯的错觉还是事实呢?如果是事实,是因为市场饱和度的日益增长还是因为多家互联网平台的完善化呢?

我的博客主要当作开发日记用,当然里面也会发一发日常,po一手照片,多愁善感个一两句什么的。应该会发表一些系列的小说或者杂文什么的,也会发表一些个人的观点。综上所述:这就是个普通的博客。

没什么对访问量的需求,甚至不希望有访客。感觉写的很多东西是偏向私密的,而且访客越少对服务器的需求就越小,这毕竟不是一个商业化的网络应用。

如果你恰巧来到了我这里,对某些文字或者图像产生了兴趣,如果你需要转载,请评论告诉我一声;如果嫌麻烦,转载后请留原文链接。

修合无人见,存心有天知。