• 等级
  • 9135 访问
  • 130 原创
  • 2 转发
  • 50828 排名
  • 5 评论
  • 1 获赞

排序模板

1.冒泡排序(O(n²))最好情况下O(n)for(inti=0;i<n-1;i++)//升序 { for(intj=0;j<n-1-i;j++) { if(a[j]>a[j+1]) { inttemp=a[j]; a[j]=a[j+1]; a[j+1]=temp;...

2019-04-08 16:03:46

POJ - 1321 - 棋盘问题 【DFS】

在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。Input输入含有多组测试数据。 每组数据的第一行是两个正整数,nk,用一个空格隔开,表示了将在一个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>#defineINF0x7ffffffusingnamespace...

2018-08-06 09:53:58

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

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

2018-08-04 15:14:16

POJ - 2251 - Dungeon Master 【BFS】

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

2018-08-04 14:34:14

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

#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1<<20;structnode{intl,r,id;}Q[maxn];intpos[maxn],a[maxn];longlongans[maxn],flag[maxn];boolcmp(nodea,...

2018-08-04 10:38:45

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

#include<iostream>#include<cstdio>#include<vector>usingnamespacestd;constintmaxn=1e4+10;constintmaxm=4e4+10;intn,m;structEdge{intto,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>usingnamespacestd;constintmaxn=515;intmp[maxn][maxn];int_in[maxn];intans[maxn];intN,M;voidinit(){...

2018-07-30 11:11:01

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

题目链接:https://ajax.loj.ac/problem/6284#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e5+5;inta[maxn],pos[maxn],blo,n,tag[maxn],l,r,c;voidreset(intx){if(tag[x]...

2018-07-30 10:05:15

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

题目链接: https://ajax.loj.ac/problem/6283#include<bits/stdc++.h>#definelllonglong#definemod10007usingnamespacestd;constintmaxn=1e5+5;intblo,opt,l,r,c,n,m;intpos[maxn],...

2018-07-26 15:52:37

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

题目链接:https://ajax.loj.ac/problem/6282#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintmaxn=1e5+5;intblo,opt,l,r,c,n,m;intpos[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>#definelllonglongusingnamespacestd;constintmaxn=5e4+5;intblo,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>#definelllonglongusingnamespacestd;constintmaxn=5e4+5;intblo,n,opt,l,r,c,pos[maxn];llatag[maxn],sum[maxn],a[ma...

2018-07-25 17:41:21

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

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

2018-07-25 17:12:37

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

输出格式对于每次询问,输出一行一个数字表示答案。样例样例输入412230131113211411232样例输出302#include<bits/stdc++.h>usingnamespacestd;constintmaxn=5e4+5;intblo,n,opt,l,r,...

2018-07-25 11:02:14

LOJ - #6277数列分块入门 1

输出格式对于每次询问,输出一行一个数字表示答案。样例样例输入412230131101001221020样例输出25#include<bits/stdc++.h>usingnamespacestd;constintmaxn=5e4+5;intblo,n,opt,l,r,c...

2018-07-25 10:11:31

北里五井

关注
  • 中国