• 等级
  • 4656 访问
  • 129 原创
  • 2 转发
  • 45980 排名
  • 2 评论
  • 0 获赞

POJ - 1321 - 棋盘问题 【DFS】

在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。 Input 输入含有多组测试数据。  每组数据的第一行是两个正整数,n k,用一个空格隔开,表示了将在一个n*n的矩阵内描述棋盘,以及摆放棋子的数目。 n <= 8 , k <= n...

2018-08-10 15:05:48

POJ - 3126 - Prime Path 【BFS + 素数打表】

题意:给你两个四位数的素数,让你从第一个素数变成第二个,每次操作只能改动一位数字,且需要保证改动后的数字任为为素数;输出需要操作多少次;  题解:先素数打表,BFS处理时将满足条件的数字放入队列中(未被访问过且为素数,与队列front()的元数只有一位数字不同); #include<iostream> #include<cstdio> #include<cstr...

2018-08-08 10:24:22

POJ-3278 - Catch That Cow【BFS】

题意: John要去抓奶牛,奶牛不会移动,John移动的方式有三种: 向前移动一步,耗时一分钟; 向后移动一步,耗时一分钟; 向前移动当前所处的位置的2倍,耗时一分钟; 题解:1. if(N >= k),当John所处的位置大于奶牛的, John 只能向后一步一步移动,即耗时N - K ;      2. if(N < K),用BFS去解决;  #include<io...

2018-08-06 11:56:36

搜索剪枝

what's 剪枝? 常用的搜索有Dfs和Bfs。 Bfs的剪枝通常就是判重,因为一般Bfs寻找的是步数最少,重复的话必定不会在之前的情况前产生最优解。 深搜,它的进程近似一颗树(通常叫Dfs树)。 而剪枝就是一种生动的比喻:把不会产生答案的,或不必要的枝条“剪掉”。 剪枝的关键就在于剪枝的判断:什么枝该剪,什么枝不该剪,在什么地方减。 剪枝的原则? 正确性,准确性,高效性。 常用...

2018-08-06 10:59:16

HDU - 2612 - Find a way 【BFS】

题意: 输出Y和M 到图中 ‘@’的最小步数之和 题解: 用三维数组分别储存Y 和 M 到 图中的每一点的步数,输出最小的步数和; #include<iostream> #include<cstdio> #include<cstring> #include<queue> #define INF 0x7ffffff using namespace...

2018-08-06 09:53:58

POJ - 3984 -迷宫问题【BFS + 打印路径】

题解:  用一个结构体二维数组来存每个点的上一个点的坐标,通过递归到达起点,在回溯时打印路径 #include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; int mp[5][5]; bool vis[5][5]; int di...

2018-08-04 15:14:16

POJ - 2251 - Dungeon Master 【BFS】

题意:  从S到E需要多少分钟(只能上下左右前后移动一格,每移动一个耗费1分钟); #include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int maxn = 35; struct node{ int...

2018-08-04 14:34:14

Codeforces - 617E - XOR and Favorite Number【莫队】

#include<bits/stdc++.h> using namespace std; const int maxn = 1<<20; struct node { int l, r, id; }Q[maxn]; int pos[maxn], a[maxn]; long long ans[maxn], flag[maxn]; bool cmp(node a, ...

2018-08-04 10:38:45

POJ - 2230 - Watchcow【欧拉回路】/补

#include<iostream> #include<cstdio> #include<vector> using namespace std; const int maxn = 1e4+10; const int maxm = 4e4+10; int n, m; struct Edge{ int to,flag; }e; vector<Edg...

2018-08-01 15:44:48

UVA - 10129 -Play on Words【欧拉路】/补

(来自:《算法竞赛入门经典》)题意:输入n(n≤100000)个单词,是否可以把所有这些单词排成一个序列,使得每个单词的第一个字母和上一个单词的最后一个字母和上一个单词的第一个字母相同(例如acm,malform,mouse)。每个单词最多包含1000个小写字母。输入中可以有重复的单词。 【分析】 把字母看作结点,单词看成有向边,则问题有解,当且仅当图中有欧拉路径。前面讲过,有向图存在欧拉道路...

2018-08-01 10:48:50

HDU - 1285 -确定比赛名次【拓扑排序】

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1285 #include<bits/stdc++.h> using namespace std; const int maxn = 515; int mp[maxn][maxn]; int _in[maxn]; int ans[maxn]; int N, M; void init() {...

2018-07-30 11:11:01

LOJ - #6284. 数列分块入门 8

题目链接:https://ajax.loj.ac/problem/6284 #include<bits/stdc++.h> using namespace std; const int maxn = 1e5+5; int a[maxn], pos[maxn], blo, n, tag[maxn], l, r, c; void reset(int x) { if(tag[x]...

2018-07-30 10:05:15

LOJ - #6283. 数列分块入门 7

题目链接: https://ajax.loj.ac/problem/6283 #include<bits/stdc++.h> #define ll long long #define mod 10007 using namespace std; const int maxn = 1e5 + 5; int blo, opt, l, r, c, n, m; int pos[maxn],...

2018-07-26 15:52:37

LOJ - #6282. 数列分块入门 6

题目链接:https://ajax.loj.ac/problem/6282 #include<bits/stdc++.h> #define ll long long using namespace std; const int maxn = 1e5 + 5; int blo, opt, l, r, c, n, m; int pos[maxn], a[maxn], st[maxn*2...

2018-07-26 10:36:42

LOJ-#6281. 数列分块入门 5

题目链接:https://ajax.loj.ac/problem/6281 #include<bits/stdc++.h> #define ll long long using namespace std; const int maxn = 5e4 + 5; int blo, opt, l, r, c, a[maxn], flag[maxn], pos[maxn], n, sum[...

2018-07-26 09:10:19

LOJ - #6280. 数列分块入门 4

题目链接:https://loj.ac/problem/6280 #include<bits/stdc++.h> #define ll long long using namespace std; const int maxn = 5e4 + 5; int blo, n, opt, l, r, c, pos[maxn]; ll atag[maxn], sum[maxn], a[ma...

2018-07-25 17:41:21

LOJ - #6279. 数列分块入门 3

题目链接:#6279. 数列分块入门 3 #include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; int blo, n, opt, l, r, c, a[maxn], pos[maxn], atag[maxn]; set<int>st[maxn]; int add(int l, int...

2018-07-25 17:12:37

LOJ - #6278. 数列分块入门 2

输出格式 对于每次询问,输出一行一个数字表示答案。 样例 样例输入 4 1 2 2 3 0 1 3 1 1 1 3 2 1 1 4 1 1 2 3 2 样例输出 3 0 2 #include<bits/stdc++.h> using namespace std; const int maxn = 5e4 + 5; int blo, n, opt, l, r,...

2018-07-25 11:02:14

LOJ - #6277数列分块入门 1

输出格式 对于每次询问,输出一行一个数字表示答案。 样例 样例输入 4 1 2 2 3 0 1 3 1 1 0 1 0 0 1 2 2 1 0 2 0 样例输出 2 5 #include<bits/stdc++.h> using namespace std; const int maxn = 5e4 + 5; int blo, n, opt, l, r, c...

2018-07-25 10:11:31

牛客小白月赛5 - G - 异或(xor)【找规律】

链接:https://www.nowcoder.com/acm/contest/135/G   从前,Apojacsleam家的水族箱里,养了一群热带鱼。     在这几条热带鱼里,Apojacsleam特别喜欢一条叫做TbGx(请勿人肉)的热带鱼,所以每次都让她第一个吃食物。对于每一条鱼,Apojacsleam都有一个顺序,鱼会按照这个顺序排序,越靠前的地位越高。    吃饱喝足是要睡觉的...

2018-07-24 16:39:45

北里五井

关注
  • 中国