↓ 跳过正文
111qqz的小窝
111qqz的小窝

Posts

2015

poj 3984 迷宫问题

·1 分钟
ACM Bfs 路径记录
迷宫问题 1 2 3 4 /************************************************************************* 5 > File Name: code/2015summer/searching/KK.cpp 6 > Author: 111qqz 7 > Email: rkz2013@126.com 8 > Created Time: 2015年07月25日 星期六 13时33分00秒 9 ************************************************************************/ 10 11 #include<iostream> 12 #include<iomanip> 13 #include<cstdio> 14 #include<algorithm> 15 #include<cmath> 16 #include<cstring> 17 #include<string> 18 #include<map> 19 #include<set> 20 #include<queue> 21 #include<vector> 22 #include<stack> 23 #define y0 abc111qqz 24 #define y1 hust111qqz 25 #define yn hez111qqz 26 #define j1 cute111qqz 27 #define tm crazy111qqz 28 #define lr dying111qqz 29 using namespace std; 30 #define REP(i, n) for (int i=0;i<int(n);++i) 31 typedef long long LL; 32 typedef unsigned long long ULL; 33 int a[10][10]; 34 int head = 0; 35 int tail = 1; 36 int dirx[2]={1,0}; 37 int diry[2]={0,1}; 38 struct node 39 { 40 int x,y,pre; 41 }q[10]; 42 43 void print(int x) 44 { 45 if (q[x].pre!=-1) 46 { 47 print(q[x].pre); 48 printf("(%d, %d)\n",q[x].x,q[x].y); 49 } 50 } 51 void bfs() 52 { 53 q[head].x=0; 54 q[head].y=0; 55 q[head].pre=-1; 56 while (head<tail) 57 { 58 if (q[head].x==4&&q[head].y==4) 59 { 60 print(head); 61 return; 62 } 63 for (int i = 0 ; i < 2 ; i++ ) 64 { 65 int newx=dirx[i]+q[head].x; 66 int newy=diry[i]+q[head].y; 67 if (newx>=0&&newx<5&&newy>=0&&newy<5&&a[newx][newy]==0) 68 { 69 q[tail].x=newx; 70 q[tail].y=newy; 71 q[tail].pre=head; 72 tail++; 73 } 74 } 75 head++; 76 } 77 78 } 79 int main() 80 { 81 for ( int i = 0 ; i < 5 ; i++ ) 82 { 83 for ( int j = 0 ; j < 5; j++) 84 { 85 cin>>a[i][j]; 86 } 87 } 88 printf("(0, 0)\n"); 89 bfs(); 90 91 return 0; 92 }

poj 3087 Shuffle'm Up (bfs)

·1 分钟
ACM Bfs
http://poj.org/problem?id=3087 用bfs写的，但是其实就是个模拟啊喂！ 只有一种操作，何谈最短？　一直往下写就行了．

poj 3126 Prime Path (bfs)

·2 分钟
ACM Bfs
http://poj.org/problem?id=3126 题意是说,给定两个四位素数a b 问从a变换到b,最少需要变换几次. 变换的要求是,每次只能改变一个数字,而且中间过程得到的四位数也必须为素数. 因为提到最少变换几次,容易想到bfs,bfs第一次搜到的一定是最短步数.

poj 3279 Fliptile (搜索..暴力？)

·2 分钟
ACM Brute Force
http://poj.org/problem?id=3279 反转类问题. 有N*M个方格,每个上面有数字0或者1 操作一个方格,这个方格即其相邻的四个方格(有公共边)会改变状态(由0变1或者由1变0)

POJ 1564 Sum It Up (DFS+剪枝）

·2 分钟
ACM Dfs
http://poj.org/problem?id=1564 dfs 三个参数 x,sum,k, x表示开始的坐标,sum表示当前的和,k表示这是一组答案中的第几个数,是用来记录路径的…

cf 556C Case of Matryoshkas

·1 分钟
ACM 算法竞赛
http://codeforces.com/contest/556/problem/C 果然一晚上不睡觉会导致读错题么… 需要注意的是 如果有一个是 1 2 4 6 那么 1,2是不必拆开的….

最大连续区间和的算法总结

·2 分钟
ACM 算法竞赛
最大连续区间和是一个经典的问题。给定一个长度为 n 的序列 a[1],a[2]…a[n-1],a[n]，求一个连续的子序列 a[i],a[i+1]…a[j-1],a[j]，使得 a[i]+a[i+1]…a[j-1]+a[j]最大。

poj 3278 catch that cow

·1 分钟
ACM Bfs
http://poj.org/problem?id=3278 bfs,用到了stl的queue 1 2 3 /* *********************************************** 4 Author :111qqz 5 Created Time :2016年02月19日 星期五 15时45分05秒 6 File Name :3278.cpp 7 ************************************************ */ 8 9 #include <algorithm> 10 #include <cstdio> 11 #include <iostream> 12 #include <cstring> 13 #include <string> 14 #include <cmath> 15 #include <map> 16 #include <stack> 17 #include <queue> 18 19 using namespace std; 20 typedef long long LL; 21 const int inf = 8E8; 22 const int N=2E5+7; 23 int d[N]; 24 int n,k; 25 void bfs() 26 { 27 queue<int> q; 28 memset(d,-1,sizeof(d)); 29 q.push(n); 30 d[n]=0; 31 while (!q.empty()) 32 { 33 int x = q.front(); 34 q.pop(); 35 if ( x==k ) 36 { 37 break; 38 } 39 int next[10]; 40 next[1]=x-1; 41 next[2]=x+1; 42 next[3]=2*x; 43 for ( int i = 1; i <= 3 ; i++ ) 44 { 45 if (next[i]>=0&&next[i]<=100000&&d[next[i]]==-1) 46 { 47 d[next[i]]=d[x]+1; 48 q.push(next[i]); 49 } 50 } 51 } 52 53 54 } 55 int main() 56 { 57 while (scanf("%d %d",&n,&k)!=EOF) 58 { 59 bfs(); 60 cout<<d[k]<<endl; 61 } 62 return 0; 63 }

POJ 1028 Web Navigation

·1 分钟
ACM Stl
http://poj.org/problem?id=1028 1 2 3 4 /* *********************************************** 5 Author :111qqz 6 Created Time :2016年02月19日 星期五 15时45分01秒 7 File Name :1028.cpp 8 ************************************************ */ 9 10 #include <algorithm> 11 #include <cstdio> 12 #include <iostream> 13 #include <cstring> 14 #include <string> 15 #include <cmath> 16 #include <map> 17 #include <stack> 18 #include <queue> 19 20 using namespace std; 21 typedef long long LL; 22 const int inf = 8E8; 23 stack<string> backstack; 24 stack<string> forwardstack; 25 string cur; 26 string cmd; 27 int main() 28 { 29 cur ="http://www.acm.org/"; 30 31 while (cin>>cmd) 32 { 33 if (cmd=="QUIT") 34 { 35 break; 36 } 37 if (cmd=="BACK") 38 { 39 if (backstack.empty()) 40 { 41 cout<<"Ignored"<<endl; 42 continue; 43 } 44 forwardstack.push(cur); 45 cur=backstack.top(); 46 backstack.pop(); 47 cout<<cur<<endl; 48 } 49 if (cmd=="FORWARD") 50 { 51 if (forwardstack.empty()) 52 { 53 cout<<"Ignored"<<endl; 54 continue; 55 } 56 backstack.push(cur); 57 cur=forwardstack.top(); 58 forwardstack.pop(); 59 cout<<cur<<endl; 60 } 61 if (cmd=="VISIT") 62 { 63 backstack.push(cur); 64 65 cin>>cur; 66 while (!forwardstack.empty()) forwardstack.pop(); 67 cout<<cur<<endl; 68 69 } 70 } 71 72 73 return 0; 74 }

poj 1833 排列

·1 分钟
ACM Stl
http://poj.org/problem?id=1833 还是next_permutation. 这次是Int类型的 需要注意的是next_permutation是先判断时候有后继，返回一个bool值，如果为true，就转化到后继。

poj 1256 Anagram

·1 分钟
ACM Stl
http://poj.org/problem?id=1256 题意是说求出一个字符串的全排列，按字典序 需要注意的是字典序和传统意义上的字典序不同

codeforces 548B Mike and Fun

·1 分钟
ACM Brute Force
http://codeforces.com/problemset/problem/548/B 比赛的时候不懂为什么就没做出来…. 其实很容易想到一个o(q*(n+m))的做法… 就是每次更新，要同时更新当前更新行的最大连续和….O（m）可以完成…然后在O（n）扫一遍，找到所有行中的最大值。 然后需要注意的是，在第一次更改之前就要把每个行的最大值处理出来l.. 然后cf机器真是够快，O(nmq)的1.2S过。。。。