海港在NOIP2016竞赛中扮演了怎样的角色？

本文共计833个文字，预计阅读时间需要4分钟。

题目链接：海峡+这一题怎么样呢？还不错吧，也不是太难，没有用到什么特殊的算法，但写法还是很值得学习的。

思路讲解：我们维护三个队列（这里我们用手动模拟队列的操作）：

1. 队列A：用于存储初始的待处理节点。

2.队列B：用于存储从队列A中取出节点后，其相邻节点（即下一个节点）的索引。

3.队列C：用于存储当前处理的节点及其相邻节点的索引。

具体步骤如下：

1. 初始化队列A，将起始节点加入队列A。

2.当队列A不为空时，执行以下操作：

a. 从队列A中取出一个节点，加入队列C。 b. 将该节点的所有相邻节点索引加入队列B。 c. 当队列B不为空时，执行以下操作： i. 从队列B中取出一个索引，加入队列A。 ii. 将该索引对应的节点加入队列C。

3.遍历队列C，将队列C中的节点按顺序输出。

这样，我们就能按照题目要求，得到每个节点的顺序输出。

题目链接：​​海港​​​
这一题怎么样呢？还好吧，也不是太难，没有用到什么特殊的算法，但写法还是很值得学习的。下面讲一下思路：
我们维护三个队列（这里我们采用自己手写的队列，因为这比STL的要快，不过这一题，STL也够了），分别存储时间，人数，国籍。
然后模拟就行了，先看代码，我在细说：

#include<cstdio>
#include<queue>
#define H 86400
using namespace std;
struct que{ //1
int num[300005];
int first=0,tail=0;
void push(int x){
num[tail]=x;
tail++;
}
int front(){
return num[first];
}
void pop(){
first++;
}
};
int n,ans,vis[100005]; //n船数，ans当前答案，vis记录每种国籍人数
que num; //每只船的人数
que t; //每只船的到达时间
que nat; //每个人的国籍
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int m,c;
scanf("%d%d",&c,&m);
num.push(m);
t.push(c);
for(int j=1;j<=m;j++)
{
int peo;
scanf("%d",&peo);
nat.push(peo);
if(vis[peo]==0) ans++; //2
vis[peo]++; //3
}
while(c-H>=t.front()) //4
{
int p=num.front();
t.pop();
num.pop();
for(int k=1;k<=p;k++)
{
vis[nat.front()]--;
if(vis[nat.front()]==0) ans--;//5
nat.pop();
}
}
printf("%d\n",ans);
}
return 0;
}

讲5点：
1处：手写队列，非常简单，只要实现三个函数就够了，因为我们也只能用到这三个，在本题中。
2处：如果这个国籍人数从0变成1了，就说明又多了一种国籍，所以答案+1
3处：把vis对应的国籍人数加1
4处：循环判断是否有超过24小时的，有就不断让它们出队列
5处：如果一个国籍的人数从1变成0，那么就说明国籍数减少一，所以答案减一。