隊列 手算到機算 入門 隊列 循環隊列
總目錄：從手算到機算 算法競賽入門篇
隊列：先進先出
1.洛谷 P1996 約瑟夫問題
隊列寫法如下
手算過程如下：
輸入:
10 3
輸出：
3 6 9 2 7 1 8 5 10 4
h代表隊首，t代表隊尾
隊列如下：h=1,t=11
位置1 2 3 4 5 6 7 8 9 10
數值1 2 3 4 5 6 7 8 9 10
報數1:h=2,t=12
位置2 3 4 5 6 7 8 9 10 11
數值2 3 4 5 6 7 8 9 10 1
報數2:h=3,t=13
位置3 4 5 6 7 8 9 10 11 12
數值3 4 5 6 7 8 9 10 1 2
報數3.h=4,t=13
3出列
位置4 5 6 7 8 9 10 11 12
數值4 5 6 7 8 9 10 1 2
報數1:h=5,t=14
位置5 6 7 8 9 10 11 12 13
數值5 6 7 8 9 10 1 2 4
報數2:h=6,t=15
位置6 7 8 9 10 11 12 13 14
數值6 7 8 9 10 1 2 4 5
報數3.
6出列:h=7,t=15
位置7 8 9 10 11 12 13 14
數值7 8 9 10 1 2 4 5
以此類推......
AC代碼如下：
#include <bits/stdc++.h>
int q[10010];
int main(){
int n,m,i,h,t,cnt;
scanf("%d%d",&n,&m);
h=1;
for(i=1;i<=n;i++)q[i]=i;
t=n+1,cnt=0;
while(h<t){
cnt++;
if(cnt==m){
printf("%d ",q[h]);
cnt=0,h++;
}else{
q[t]=q[h];
h++,t++;
}
}
return 0;
}
循環隊列寫法如下
手算過程如下：
輸入:
10 3
輸出：
3 6 9 2 7 1 8 5 10 4
循環隊列如下：h=0,t=10
位置0 1 2 3 4 5 6 7 8 9 10
數值1 2 3 4 5 6 7 8 9 10
報數1:h=1,t=0
位置0 1 2 3 4 5 6 7 8 9 10
數值1 2 3 4 5 6 7 8 9 10 1
報數2:h=2,t=1
位置0 1 2 3 4 5 6 7 8 9 10
數值2 2 3 4 5 6 7 8 9 10 1
報數3:h=3,t=1,3出列
位置0 1 2 3 4 5 6 7 8 9 10
數值2 2 3 4 5 6 7 8 9 10 1
報數1:h=4,t=2
位置0 1 2 3 4 5 6 7 8 9 10
數值2 4 3 4 5 6 7 8 9 10 1
報數2:h=5,t=3
位置0 1 2 3 4 5 6 7 8 9 10
數值2 4 5 4 5 6 7 8 9 10 1
依次類推
......
AC代碼如下：
#include <stdio.h>
int q[110],h,t;
int main(){
int n,m,i,cnt;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)q[i]=i+1;
h=0,t=n,cnt=0;
while(h!=t){
cnt++;
if(cnt==m)cnt=0,printf("%d ",q[h]);
else{
q[t]=q[h];
t=(t+1)%(n+1);
}
h=(h+1)%(n+1);
}
return 0;
}
2.洛谷 P1540 機器翻譯
隊列寫法如下
手算過程如下：
整個查字典過程如下：每行表示一個單詞的翻譯，冒号前為本次翻譯後的記憶體狀況：
1：查找單詞 1 并調入記憶體。
1 2：查找單詞 2 并調入記憶體。
1 2：在記憶體中找到單詞 1。
1 2 5：查找單詞 5 并調入記憶體。
2 5 4：查找單詞 4 并調入記憶體替代單詞 1。
2 5 4：在記憶體中找到單詞 4。
5 4 1：查找單詞 1 并調入記憶體替代單詞 2。
AC代碼如下：
#include <stdio.h>
int m,n;
int q[1010],h,t;
int main(){
int i,x,j,cnt;
scanf("%d%d",&m,&n);
h=t=1,cnt=0;
for(i=1;i<=n;i++){
scanf("%d",&x);
for(j=h;j<t;j++)//隊列中查找
if(q[j]==x)break;
if(j==t){//記憶體中未找到
cnt++;
if(t-h==m)h++,q[t]=x,t++;//記憶體已滿
else q[t]=x,t++;//記憶體未滿
}
}
printf("%d\n",cnt);
return 0;
}
3.洛谷 P1162 填塗顔色
樣例模拟如下：
6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
遇到外圍的0，變成-1
-1 -1 -1 -1 -1 -1
-1 -1 1 1 1 1
-1 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1
列印時，
遇到-1，列印0.
遇到1,列印1.
遇到0,列印2.
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1
AC代碼如下：
#include <bits/stdc++.h>
#define maxn 35
int a[maxn][maxn],n;
int h,t;
struct node{
int r,c;
}q[maxn*maxn];
int next[][2]={{-1,0},{1,0},{0,-1},{0,1}};
void bfs(int r,int c){
int nr,nc,rr,cc,i;
h=t=1;
q[t].r=r,q[t].c=c,t++;
while(h<t){
rr=q[h].r,cc=q[h].c;
for(i=0;i<4;i++){
nr=rr+next[i][0],nc=cc+next[i][1];
if(1<=nr&&nr<=n&&1<=nc&&nc<=n&&!a[nr][nc])
a[nr][nc]=-1,q[t].r=nr,q[t].c=nc,t++;
}
h++;
}
}
int main(){
int i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(j=1;j<=n;j++)
if(!a[1][j])bfs(1,j);
for(j=1;j<=n;j++)
if(!a[n][j])bfs(n,j);
for(i=1;i<=n;i++)
if(!a[i][1])bfs(i,1);
for(i=1;i<=n;i++)
if(!a[i][n])bfs(i,n);
for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
if(a[i][j]==-1)printf("0 ");
else if(!a[i][j])printf("2 ");
else printf("1 ");
printf("\n");
}
return 0;
}