目录
P8661 [蓝桥杯 2018 省 B] 日志统计
题目描述
小明维护着一个程序员论坛。现在他收集了一份“点赞”日志,日志共有 N 行。其中每一行的格式是 ts id
,表示在 ts 时刻编号 id 的帖子收到一个“赞”。
现在小明想统计有哪些帖子曾经是“热帖”。如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞,小明就认为这个帖子曾是“热帖”。
具体来说,如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞,该帖就曾是“热帖”。
给定日志,请你帮助小明统计出所有曾是“热帖”的帖子编号。
输入格式
第一行包含三个整数 N、D 和 K。
以下 N 行每行一条日志,包含两个整数 ts 和 id。
输出格式
按从小到大的顺序输出热帖id。每个 id 一行。
输入输出样例
输入 #1复制
7 10 2 0 1 0 10 10 10 10 1 9 1 100 3 100 3
输出 #1复制
1 3
说明/提示
对于 50%50% 的数据,1≤K≤N≤1000。
对于 100%100% 的数据,1≤K≤N≤105,0≤id,ts≤105。
时限 1 秒, 256M。蓝桥杯 2018 年第九届省赛
题目分析
1,我们不清楚编号最大会是多少,所以我们每输入一次就记录最大值
2,因为要从小到大输出,所以我们对数据按时间排序,定义一个单调队列数组(n个帖子,n个队列)每一个帖子存一个队列,此时,有效赞的个数就是队列的大小,数据依次判断入队
3,如果准备入队的数据不在区间,则出队
4,答案数组存放满足题目要求的编号
代码示例
#include<bits/stdc++.h>
using namespace std;
struct node
{
int ts;
int id;
} a[100005];
bool f[100005];
int n,k,d,maxn;
bool cmp(node x,node y)//函数控制排序要求
{
if(x.ts!=y.ts)return x.ts<y.ts;
else return x.id<y.id;
}
deque<int>p[100005];
int main()
{
cin>>n>>d>>k;
for(int i=1; i<=n; i++)//输入
{cin>>a[i].ts>>a[i].id;
maxn=max(a[i].id,maxn);}
sort(a+1,a+1+n,cmp);//排序
for(int i=1;i<=n;i++)
{p[a[i].id].push_back(a[i].ts);//先入队,等下判断是否需要出队
while(!p[a[i].id].empty()&&a[i].ts-p[a[i].id].front()>=d)p[a[i].id].pop_front();//过时了,所以出队
if(p[a[i].id].size()>=k)f[a[i].id]=1;//标记哪个编号符合要求
}
for(int i=0;i<=maxn;i++)//一直输出到编号最大值
if(f[i])cout<<i<<endl;
}
P8662 [蓝桥杯 2018 省 AB] 全球变暖
题目描述
你有一张某海域 N×N 像素的照片,.
表示海洋、 #
表示陆地,如下所示:
.......
.##....
.##....
....##.
..####.
...###.
.......
其中 "上下左右" 四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 22 座岛屿。
由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。
例如上图中的海域未来会变成如下样子:
.......
.......
.......
.......
....#..
.......
.......
请你计算:依照科学家的预测,照片中有多少岛屿会被完全淹没。
输入格式
第一行包含一个整数 N。(1≤N≤1000)。
以下 N 行 N 列代表一张海域照片。
照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。
输出格式
一个整数表示答案。
输入输出样例
输入 #1复制
7 ....... .##.... .##.... ....##. ..####. ...###. .......
输出 #1复制
1
说明/提示
时限 1 秒, 256M。蓝桥杯 2018 年第九届省赛
题目分析
1,题目总体思路,所有岛屿减去不可能被完全淹没的岛屿等于被淹没的岛屿
2,不可能被淹没的岛屿满足四个方向都是陆地的条件,所以此时不可能被淹没的岛屿加一
3,我们从遇到陆地后从他开始判断岛屿并判断岛屿的各个方向,如果为海洋则返回
4,每一个点走过后标记为另一个字符(除题目给的字符外自己定义一个)
5,最后输出所有岛屿减去未被完全淹没的岛屿的值
代码示例
#include<bits/stdc++.h>
using namespace std;
int dx[]= {0,1,0,-1},dy[]= {1,0,-1,0},sum,ans,n,k,t;
char f[1010][1010];
void dfs(int x,int y)
{
if(f[x][y]=='.')return;//为海洋则返回
if(!t)
{ k=0;
for(int i=0; i<4; i++)
if(f[x+dx[i]][y+dy[i]]!='.')k++;//判断四个方向是否是海洋
if(k==4)ans++,t=1;//如果四个方向都是陆地,则不可能被淹没,此岛屿标记为1
}
f[x][y]='*';//标记走过的
for(int i=0; i<4; i++)
{
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<0||ny<0||nx>=n||ny>=n||f[nx][ny]!='#')continue;//如果不为陆地或已经走过的话找另一个方向
dfs(nx,ny);
}
}
int main()
{
cin>>n;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
cin>>f[i][j];
for(int i=1; i<n-1; i++)
for(int j=1; j<n-1; j++)
if(f[i][j]=='#')//遇到陆地开始判断岛屿和搜索岛屿的各个方向
{
sum++;
t=0;
dfs(i,j);
}
cout<<sum-ans;
}
如以上有任何说得不清晰的,还望各位大佬指出