阿毛の次元

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

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;
}
  1. Stevhoom说道:

    Super Viagra To Buy Online cialis from canada Meilleur Pharmacie En Ligne Propecia

  2. ettazg60说道:

    Scandal porn galleries, daily updated lists
    http://footballpornman.xblognetwork.com/?virginia

    hardcore porn archives avatar the lat airbender porn winona ryder porn free paradise island porn model sankara amatuer porn studios

  3. mayla18说道:

    Teen Girls Pussy Pics. Hot galleries
    http://pornclipssexy.fetlifeblog.com/?yvonne

    bros and sisters porn undetectable porn site hot u porn big thick cock porn force tickled in bondage porn

  4. timrw18说道:

    New super hot photo galleries, daily updated collections
    http://gayscom.instakink.com/?joyce

    moondust porn nasty porn big tits save porn uk nairobi porn vintage pin up porn