做服装到哪个网站拿货品质好,做玄幻封面素材网站,有口碑的中山网站建设,wordpress模版位置深度优先搜索#xff08;DFS#xff09;#xff0c;即按照深度优先的顺序搜索的算法。
深度优先搜索一般使用栈来实现。
[USACO1.5] 八皇后 Checker Challenge
题目描述
一个如下的 6 6 6 \times 6 66 的跳棋棋盘#xff0c;有六个棋子被放置在棋盘上#xff0c;使得…深度优先搜索DFS即按照深度优先的顺序搜索的算法。
深度优先搜索一般使用栈来实现。
[USACO1.5] 八皇后 Checker Challenge
题目描述
一个如下的 6 × 6 6 \times 6 6×6 的跳棋棋盘有六个棋子被放置在棋盘上使得每行、每列有且只有一个每条对角线包括两条主对角线的所有平行线上至多有一个棋子。 上面的布局可以用序列 2 4 6 1 3 5 2\ 4\ 6\ 1\ 3\ 5 2 4 6 1 3 5 来描述第 i i i 个数字表示在第 i i i 行的相应位置有一个棋子如下
行号 1 2 3 4 5 6 1\ 2\ 3\ 4\ 5\ 6 1 2 3 4 5 6
列号 2 4 6 1 3 5 2\ 4\ 6\ 1\ 3\ 5 2 4 6 1 3 5
这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。 并把它们以上面的序列方法输出解按字典顺序排列。 请输出前 3 3 3 个解。最后一行是解的总个数。
输入格式
一行一个正整数 n n n表示棋盘是 n × n n \times n n×n 大小的。
输出格式
前三行为前三个解每个解的两个数字之间用一个空格隔开。第四行只有一个数字表示解的总数。
样例 #1
样例输入 #1
6样例输出 #1
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4提示
【数据范围】 对于 100 % 100\% 100% 的数据 6 ≤ n ≤ 13 6 \le n \le 13 6≤n≤13。
题目翻译来自NOCOW。
USACO Training Section 1.5
代码实现
#includeiostream
using namespace std;
#define MAX_N 13
int ans[MAX_N5];
int vis_col[MAX_N5]{0},vis_dui1[MAX_N*25]{0},vis_dui2[MAX_N*25];
int n,cnt0;
void dfs(int row)
{if(rown1){cnt;if(cnt3){for(int i1;in;i){if(i!1)cout ;coutans[i];}coutendl;}return ;}for(int i1;in;i){if(vis_col[i])continue;if(vis_dui1[i-rown])continue;if(vis_dui2[irow-1])continue;vis_col[i]1;vis_dui1[i-rown]1;vis_dui2[irow-1]1;ans[row]i;dfs(row1);vis_col[i]0;vis_dui1[i-rown]0;vis_dui2[irow-1]0;}
}
int main()
{cinn;dfs(1);coutcnt;return 0;} [NOIP2000 提高组] 单词接龙
题目背景
注意本题为上古 NOIP 原题不保证存在靠谱的做法能通过该数据范围下的所有数据。
本题为搜索题本题不接受 hack 数据。关于此类题目的详细内容
NOIP2000 提高组 T3
题目描述
单词接龙是一个与我们经常玩的成语接龙相类似的游戏现在我们已知一组单词且给定一个开头的字母要求出以这个字母开头的最长的“龙”每个单词都最多在“龙”中出现两次在两个单词相连时其重合部分合为一部分例如 beast 和 astonish如果接成一条龙则变为 beastonish另外相邻的两部分不能存在包含关系例如 at 和 atide 间不能相连。
输入格式
输入的第一行为一个单独的整数 n n n 表示单词数以下 n n n 行每行有一个单词输入的最后一行为一个单个字符表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。
输出格式
只需输出以此字母开头的最长的“龙”的长度。
样例 #1
样例输入 #1
5
at
touch
cheat
choose
tact
a样例输出 #1
23提示
样例解释连成的“龙”为 atoucheatactactouchoose。 n ≤ 20 n \le 20 n≤20。
代码实现
#includeiostream
#includevector
using namespace std;
#define MAX_N 20
string arr[MAX_N5];
int to[MAX_N5][MAX_N5];
int cnt[MAX_N5]{0};
vectorintstart;
int n;
int final_ans0;
void dfs(int k,int ans)
{final_ansmax(final_ans,ans);for(int i1;in;i){if(to[k][i]cnt[i]!2){cnt[i]; dfs(i,ansarr[i].size()-to[k][i]);cnt[i]--;}}return ;
}
int main()
{cinn;char st;for(int i1;in;i)cinarr[i];cinst;for(int i1;in;i){if(arr[i][0]st)start.push_back(i);for(int j1;jn;j){int max_lenmin(arr[i].size(),arr[j].size());for(int len1;lenmax_len;len){int j_poslen-1;int flag1;int szarr[i].size();for(int ksz-1;k(sz-len);k--){if(arr[i][k]arr[j][j_pos--])continue;flag0;break;}if(flag){if(lenmax_len)break;to[i][j]len;break;}}}}for(auto fir:start){cnt[fir]1;dfs(fir,arr[fir].size());cnt[fir]-1;}coutfinal_ans;return 0;
}
[USACO05DEC] Scales S
题目描述
约翰有一架用来称牛的体重的天平。与之配套的是 $ N \ ( 1 \leq N \leq 1000 ) $ 个已知质量的砝码所有砝码质量的数值都在 32 32 32 位带符号整数范围内。
每次称牛时他都把某头奶牛安置在天平的某一边然后往天平另一边加砝码直到天平平衡于是此时砝码的总质量就是牛的质量约翰不能把砝码放到奶牛的那边因为奶牛不喜欢称体重每当约翰把砝码放到她的蹄子底下她就会尝试把砝码踢到约翰脸上。
天平能承受的物体的质量不是无限的当天平某一边物体的质量大于 $ C \ ( 1 \leq C \leq 2^{30} ) $ 时天平就会被损坏。砝码按照它们质量的大小被排成一行。并且这一行中从第 3 3 3 个砝码开始每个砝码的质量至少等于前面两个砝码也就是质量比它小的砝码中质量最大的两个的质量的和。
约翰想知道用他所拥有的这些砝码以及这架天平能称出的质量最大是多少。由于天平的最大承重能力为 C C C他不能把所有砝码都放到天平上。
现在约翰告诉你每个砝码的质量以及天平能承受的最大质量你的任务是选出一些砝码使它们的质量和在不压坏天平的前提下是所有组合中最大的。
输入格式
第 1 1 1 行输入两个用空格隔开的正整数 $ N $ 和 $ C $。
第 2 2 2 到 $ N1 $ 行每一行仅包含一个正整数即某个砝码的质量。保证这些砝码的质量是一个不下降序列。
输出格式
输出一个正整数表示用所给的砝码能称出的不压坏天平的最大质量。
样例 #1
样例输入 #1
3 15
1
10
20样例输出 #1
11代码实现
#includeiostream
#includealgorithm
using namespace std;
#define MAX_N 1000
int fama[MAX_N5];
int final_ans0;
int n,c;
bool cmp(int a,int b)
{return ab;
}
void dfs(int i,int ans)
{if(in){final_ansmax(final_ans,ans);return ;}if(ansfama[i1]c)dfs(i1,ansfama[i1]);if(ansfama[i1]fama[i2]c)dfs(i1,ans);return ;
}
int main()
{cinnc;for(int i1;in;i)cinfama[i];sort(fama1,fama1n,cmp);dfs(0,0);coutfinal_ans;return 0;}
【XR-2】奇迹
题目背景 相信奇迹的人本身就和奇迹一样了不起。——笛亚 《星游记》 题目描述
我们称一个日期为一个八位数第 1~4 位构成年第 5~6 位构成月第 7~8 位构成日不足位数用 0 补足。同时要求日期所代表的这一天真实存在且年的范围为 1~9999。
出现奇迹的日期都存在相同的特点由“日”组成的两位数由“月日”组成的四位数由“年月日”组成的八位数均为质数。但并不是所有存在这样特点的日期都一定会出现奇迹。
现在你得到了一个可能会出现奇迹的日期然而不幸的是这个日期却是残缺的八位中可能有若干位无法确定。你需要知道这个日期有多少种可能这样你才能做好充足的准备去迎接奇迹的到来。
输入格式
本题有多组数据。
第一行一个正整数 T T T表示数据组数。
接下来的 T T T 行每行一个八位字符串。其中第 i i i 位如果为 -则表示日期的第 i i i 位无法确定否则表示日期的第 i i i 位为字符串中第 i i i 位上的数字。
输出格式
对每组数据一行一个整数表示答案。
样例 #1
样例输入 #1
2
53-7-3-7
20190629样例输出 #1
6
0提示
【样例 1 1 1 说明】
53-7-3-7 的 6 6 6 种可能的日期如下
53070307
53070317
53170307
53370307
53570317
53770307【数据规模与约定】
一共 10 10 10 个测试点记 c c c 为八位字符串中 - 的个数。
对前 9 9 9 个测试点在第 i i i 个测试点中保证 c i − 1 c i - 1 ci−1。
对 100 % 100\% 100% 的数据保证 1 ≤ T ≤ 10 1 \le T \le 10 1≤T≤10。
代码实现
#includeiostream
#includemath.h
using namespace std;
#define MAXSIZE 10000005
int prim[10005],zhishu[10005],vis[10005],runnian[10005];
int m_to_d[13]{0,31,28,31,30,31,30,31,31,30,31,30,31};
int ans0;
int cnt0;
int s[9];
void Init()
{for(int i2;i10005;i){if(!vis[i]){prim[cnt]i;zhishu[i]1;vis[i]1;}for(int j1;jcnt;j){if(i*prim[j]10005)break;vis[prim[j]*i]1;if(i%prim[j]0)break;}}for(int i1;i9999;i){if(i%40)if(i%100!0)runnian[i]1;else if(i%4000)runnian[i]1;}return ;
}
bool pdzs(int x)
{if(x 2) return 0;for(int i 1; i cnt; i)if(x % prim[i] 0) return x prim[i];return 1;
}
void dfs(int pos,int num,int rn,int dy)
{if(pos0){if(num1231)return ;if(rn1!runnian[num/10000])return ;if(pdzs(num))ans;return ;}if(pos4){if(num31||num1231)return ;if(dy1m_to_d[num/100]!31)return ;if(!pdzs(num))return ;if(num%10029num/1002)rn1;}if(pos6){if(num0||num31)return ;if(!pdzs(num)) return ;if(num31)dy1;}if(s[pos]-1)for(int i0;i9;i)dfs(pos-1,numi*pow(10,8-pos),rn,dy); else dfs(pos-1,nums[pos]*pow(10,8-pos),rn,dy);
}
int main()
{int t;cint;Init();while(t--){ans0;char c;for(int i1;i8;i){cinc;s[i](c-?-1:c-0);}dfs(8,0,0,0);coutansendl;}return 0;} 油滴扩展
题目描述
在一个长方形框子里最多有 N N N 个相异的点在其中任何一个点上放一个很小的油滴那么这个油滴会一直扩展直到接触到其他油滴或者框子的边界。必须等一个油滴扩展完毕才能放置下一个油滴。那么应该按照怎样的顺序在这 N N N 个点上放置油滴才能使放置完毕后所有油滴占据的总面积最大呢不同的油滴不会相互融合
注圆的面积公式 S π r 2 S \pi r^2 Sπr2其中 r r r 为圆的半径。
输入格式
第一行一个整数 N N N。
第二行四个整数 x , y , x ′ , y ′ x, y, x, y x,y,x′,y′表示长方形边框一个顶点及其对角顶点的坐标。
接下来 N N N 行第 i i i 行两个整数 x i , y i x_i, y_i xi,yi表示盒子内第 i i i 个点的坐标。
输出格式
一行一个整数长方形盒子剩余的最小空间结果四舍五入输出。
样例 #1
样例输入 #1
2
20 0 10 10
13 3
17 7样例输出 #1
50提示
代码实现
对于 100 % 100\% 100% 的数据 1 ≤ N ≤ 6 1 \le N \le 6 1≤N≤6坐标范围在 [ − 1000 , 1000 ] [-1000, 1000] [−1000,1000] 内。
#includeiostream
#includemath.h
using namespace std;
#define PI 3.1415926535
double x[10],y[10],r[10];
double xa,xb,ya,yb;
double s;
double yd0;
int vis[10],w[10];
int n;
double dis(int a,int b)
{return sqrt(pow(x[a]-x[b],2)pow(y[a]-y[b],2));
}
void dfs(int id,double num)
{if(idn1){ ydmax(yd,num);return ;}for(int i1;in;i){if(vis[i])continue;vis[i]1;w[id]i;r[id]1000000;r[id]min(r[id],fabs(xa-x[i]));r[id]min(r[id],fabs(xb-x[i]));r[id]min(r[id],fabs(ya-y[i]));r[id]min(r[id],fabs(yb-y[i]));for(int j1;jid;j){double dddis(w[id],w[j]);if(ddr[j]){r[id]0;break;}r[id]min(r[id],dd-r[j]);}dfs(id1,numPI*r[id]*r[id]);vis[i]0;}return ;
}
int main()
{cinn;cinxayaxbyb;sfabs(xa-xb)*fabs(ya-yb);for(int i1;in;i)r[i]1000000;for(int i1;in;i)cinx[i]y[i];dfs(1,0);s-yd;printf(%.0lf,s);//自带四舍五入 return 0;
}
