Posts

“… so forward this to ten other people, to prove that you believe the emperor has 题意是说发短信,每个人只会给一个人发,问从哪个人开始发,能传到的人最多

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=83084#problem/I I - Fire Game **Time Limit:**1000MS **Memory Limit:**32768KB 64bit IO Format:%I64d & %I64u Submit Status Description Fat brother and Maze are playing a kind of special (hentai) game on an N*M board (N rows, M columns). At the beginning, each grid of this board is consisting of grass or just empty and then they start to fire all the grass. Firstly they choose two grids which are consisting of grass and set fire. As we all know, the fire can spread among the grass. If the grid (x, y) is firing at time t, the grid which is adjacent to this grid will fire at time t+1 which refers to the grid (x+1, y), (x-1, y), (x, y+1), (x, y-1). This process ends when no new grid get fire. If then all the grid which are consisting of grass is get fired, Fat brother and Maze will stand in the middle of the grid and playing a MORE special (hentai) game. (Maybe it’s the OOXX game which decrypted in the last problem, who knows.)

好爽,一遍ac 1 2 3 /************************************************************************* 4 > File Name: code/2015summer/searching/H.cpp 5 > Author: 111qqz 6 > Email: rkz2013@126.com 7 > Created Time: 2015年07月27日 星期一 09时11分28秒 8 ************************************************************************/ 9 10 #include<iostream> 11 #include<iomanip> 12 #include<cstdio> 13 #include<algorithm> 14 #include<cmath> 15 #include<cstring> 16 #include<string> 17 #include<map> 18 #include<set> 19 #include<queue> 20 #include<vector> 21 #include<stack> 22 #define y0 abc111qqz 23 #define y1 hust111qqz 24 #define yn hez111qqz 25 #define j1 cute111qqz 26 #define tm crazy111qqz 27 #define lr dying111qqz 28 using namespace std; 29 #define REP(i, n) for (int i=0;i<int(n);++i) 30 typedef long long LL; 31 typedef unsigned long long ULL; 32 const int N=1E2+5; 33 int A,B,C; 34 int d[N][N]; 35 bool flag; 36 struct node 37 { 38 int d,opt,par,prea,preb; 39 }q[N][N]; 40 41 void print(int x,int y) 42 { 43 // cout<<"x:"<<x<<"y:"<<y<<endl; 44 if (q[x][y].prea!=-1&&q[x][y].preb!=-1) 45 { 46 // cout<<"who is 111qqz"<<endl; 47 print(q[x][y].prea,q[x][y].preb); 48 if (q[x][y].opt==1){ 49 printf("FILL(%d)\n",q[x][y].par); 50 } 51 if (q[x][y].opt==2) 52 { 53 printf("DROP(%d)\n",q[x][y].par); 54 } 55 if (q[x][y].opt==3) 56 { 57 printf("POUR(%d,%d)\n",q[x][y].par,3-q[x][y].par); 58 } 59 } 60 61 } 62 void bfs() 63 { 64 memset(q,-1,sizeof(q)); 65 queue<int>a; 66 queue<int>b; 67 a.push(0); 68 b.push(0); 69 q[0][0].d=0; 70 while (!a.empty()&&!b.empty()) 71 { 72 int av = a.front();a.pop(); 73 int bv = b.front();b.pop(); 74 // cout<<"av:"<<av<<"bv:"<<bv<<endl; 75 if (av==C||bv==C) 76 { 77 flag = true; 78 //cout<<"yeah~~~~~~~~~~~~~~~"<<endl; 79 cout<<q[av][bv].d<<endl; 80 // cout<<"prea:"<<q[av][bv].prea<<"preb:"<<q[av][bv].preb<<endl; 81 print(av,bv); 82 return; 83 } 84 if (av<A&&q[A][bv].d==-1) 85 { 86 q[A][bv].d=q[av][bv].d+1; 87 q[A][bv].opt=1; 88 q[A][bv].par=1; 89 q[A][bv].prea=av; 90 q[A][bv].preb=bv; 91 a.push(A); 92 b.push(bv); 93 } 94 if (av>0&&q[0][bv].d==-1) 95 { 96 q[0][bv].d=q[av][bv].d+1; 97 q[0][bv].opt=2; 98 q[0][bv].par=1; 99 q[0][bv].prea=av; 100 q[0][bv].preb=bv; 101 a.push(0); 102 b.push(bv); 103 104 } 105 if (bv<B&&q[av][B].d==-1) 106 { 107 q[av][B].d=q[av][bv].d+1; 108 q[av][B].opt=1; 109 q[av][B].par=2; 110 q[av][B].prea = av; 111 q[av][B].preb = bv; 112 a.push(av); 113 b.push(B); 114 115 } 116 if (bv>0&&q[av][0].d==-1) 117 { 118 q[av][0].d=q[av][bv].d+1; 119 q[av][0].opt=2; 120 q[av][0].par=2; 121 q[av][0].prea=av; 122 q[av][0].preb=bv; 123 a.push(av); 124 b.push(0); 125 } 126 127 if (av+bv<=B&&q[0][av+bv].d==-1) 128 { 129 q[0][av+bv].d=q[av][bv].d+1; 130 q[0][av+bv].opt=3; 131 q[0][av+bv].par=1; 132 q[0][av+bv].prea=av; 133 q[0][av+bv].preb=bv; 134 a.push(0); 135 b.push(av+bv); 136 } 137 if (av+bv>B&&q[av-(B-bv)][B].d==-1) //把1往2里倒入的两种情况 138 { 139 140 int tmp = av-(B-bv); 141 q[tmp][B].d=q[av][bv].d+1; 142 q[tmp][B].opt=3; 143 q[tmp][B].par=1; 144 q[tmp][B].prea=av; 145 q[tmp][B].preb=bv; 146 a.push(tmp); 147 b.push(B); 148 } 149 150 if (bv+av<=A&&q[av+bv][0].d==-1) 151 { 152 q[av+bv][0].d=q[av][bv].d+1; 153 q[av+bv][0].opt=3; 154 q[av+bv][0].par=2; 155 q[av+bv][0].prea=av; 156 q[av+bv][0].preb=bv; 157 a.push(av+bv); 158 b.push(0); 159 } 160 if (bv+av>A&&q[A][bv-(A-av)].d==-1) 161 { 162 int tmp = bv-(A-av); 163 q[A][tmp].d=q[av][bv].d+1; 164 q[A][tmp].opt=3; 165 q[A][tmp].par=2; 166 q[A][tmp].prea=av; 167 q[A][tmp].preb=bv; 168 a.push(A); 169 b.push(tmp); 170 } 171 } 172 } 173 int main() 174 { 175 176 flag = false; 177 cin>>A>>B>>C; 178 bfs(); 179 if (!flag) 180 { 181 cout<<"impossible"<<endl; 182 } 183 184 185 return 0; 186 }

非常可乐 # **Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7194 Accepted Submission(s): 2865 **

Oil Deposits # **Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 17683 Accepted Submission(s): 10172 **

Find a way # ****Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6221 Accepted Submission(s): 2070 **

迷宫问题 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 }

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

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

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

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=83295#problem/I 最多18个点，选3个点，能够成的三角形不超过1000个，O(n2)暴力就可以。

http://poj.org/problem?id=2398 题意大概是说将一个盒子用n个board分成n+1 部分 然后往里面放toy,给定盒子,board,和toy的坐标

http://poj.org/problem?id=2251 简单bfs，只不过是三维的。。。 唯一的坑点在输出上…

http://codeforces.com/contest/558/problem/C 题目大意是说，给定N个数，可以对任意数进行任意次两种操作，×2，和/2（整除）

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

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82557#problem/A Zk的解法：拆点，把每一个点存成两份，r[i]和r[n+i]

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

最大连续区间和是一个经典的问题。给定一个长度为 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]最大。

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 }

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 }