阿毛的笔记本

修合无人见,存心有天知

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 →

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 →