H：日志统计
题目描述
小明维护着一个程序员论坛。现在他收集了一份"点赞"日志，日志共有 N 行。其中每一行的格式是：
ts id
表示在 ts 时刻编号 id 的帖子收到一个"赞"。
现在小明想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为 DD 的时间段内收到不少于 KK 个赞，小明就认为这个帖子曾是"热帖"。
具体来说，如果存在某个时刻 T 满足该帖在 T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞，该帖就曾是"热帖"。
给定日志，请你帮助小明统计出所有曾是"热帖"的帖子编号。
输入描述
输入格式：
第一行包含三个整数N,D,K。
以下 N 行每行一条日志，包含两个整数 ts 和 id。
其中，1≤K≤N≤105,0≤ts≤105,0≤id≤105。
输出描述
按从小到大的顺序输出热帖 id。每个 id 一行。
输入输出样例
示例
输入
7 10 2 0 1 0 10 10 10 10 1 9 1 100 3 100 3
输出
1 3
运行限制
最大运行时间：1s
最大运行内存: 256M
#include <iostream> #include <vector> #include <cmath> #include <algorithm> using namespace std; vector<int> a[100005]; int n,d,k; //d时间有k个赞 int ans[100005]; bool check(vector<int> x){ sort(x.begin(),x.end()); int y=x.size(); int l=0,r=1; int cnt=0; while(l<=r && r<y){ if(x[r]-x[l]<d){ cnt=max(cnt,r-l+1); r++; }else{ l++; } if(cnt>=k){ return true; } if(l==r){ r++; } } return false; } int main(){ cin>>n>>d>>k; int mm=0; for(int i=0;i<n;i++){ int ts,id; cin>>ts>>id; mm=max(mm,id); a[id].push_back(ts); } int c=0; for(int i=0;i<=mm;i++){ if(a[i].size()>=k){ if(check(a[i])){ cout<<i<<endl; } } } return 0; }
找了半天都没找出问题来。啊啊啊啊
I:全球变暖
题目描述
你有一张某海域 NxNNxN 像素的照片，"."表示海洋、"#"表示陆地，如下所示：
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
.......
.......
.......
.......
....#..
.......
.......
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
输入描述
第一行包含一个整数 (1≤N≤1000)。
以下 N 行 N 列代表一张海域照片。
照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。、
输出一个整数表示答案。
输入输出样例
示例
输入
7 ....... .##.... .##.... ....##. ..####. ...###. .......
输出
1
运行限制
最大运行时间：1s
最大运行内存: 256M
dfs深搜，立一个flag，没有淹没为ture
#include <iostream> using namespace std; int n; char a[1005][1005]; bool flag; int dao1; int dao2; bool b[1005][1005]; bool v[1005][1005]; int c[4][2]={{-1,0},{0,-1},{1,0},{0,1}}; void dfs(int x,int y){ if(x<0 || x>=n || y<0 || y>=n || a[x][y]!='#' || b[x][y]){ return; } b[x][y]=1; if(a[x-1][y]=='.' || a[x][y-1]=='.' || a[x+1][y]=='.' ||a[x][y+1]=='.'){ a[x][y]='T'; }else{ flag=true; } dfs(x-1,y); dfs(x,y-1); dfs(x+1,y); dfs(x,y+1); } int main(){ cin>>n; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cin>>a[i][j]; } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(a[i][j]=='#'&&!b[i][j]){ flag=false; dfs(i,j); dao1++; if(flag){ dao2++; } } } } cout<<dao1-dao2; return 0; }
J:乘积最大
题目描述
给定 NN 个整数 A1,A2,⋯AN。请你从中选出 K 个数，使其乘积最大。
请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 10^9+9109+9 的余数。
注意，如果 X<0，我们定义 X 除以 09+9 的余数是负(−X)除以 10^9+9109+9 的余数。
即：0−((0−x)%109+9)。
输入描述
输入格式：
第一行包含两个整数N,K。
以下 NN 行每行一个整数Ai。
其中，1≤K≤N≤105，−105≤Ai≤105。
输出描述
输出一个整数，表示答案。
输入输出样例
示例
输入
5 3 -100000 -10000 2 100000 10000
输出
999100009
运行限制
最大运行时间：1s
最大运行内存: 256M
分类讨论，排序后考虑都是正数，都是负数，和正负数都有
#include <iostream> #include <algorithm> using namespace std; #define m 1000000009 int n,k; int a[100005]; long long sum; int main(){ sum=1; cin>>n>>k; for(int i=0;i<n;i++){ cin>>a[i]; } sort(a,a+n); if(k==n){ for(int i=0;i<n;i++){ sum=(sum%m*a[i]%m)%m; } cout<<sum%m; return 0; } if(a[0]>=0){ for(int i=n-1;i>n-1-k;i--){ sum=(sum%m*a[i]%m)%m; } }else if(a[n-1]<=0 && k%2==0){ for(int i=0;i<k;i++){ sum=(sum%m*a[i]%m)%m; } }else if(a[n-1]<=0 && k%2!=0){ for(int i=n-1;i>n-1-k;i--){ sum=(sum%m*a[i]%m)%m; } }else if(a[0]<0 && a[n-1]>0 && k%2==0){ int l=0,r=n-1; while(k){ long long b1=(long long)a[l]*a[l+1]; long long b2=(long long)a[r]*a[r-1]; if(b1>b2){ sum=(sum%m*b1%m)%m; l+=2; }else{ sum=(sum%m*b2%m)%m; r-=2; } k-=2; } }else if(a[0]<0&&a[n-1]>0&&k%2!=0){ sum=a[n-1]; k--; int l=0,r=n-2; while(k){ long long b1=(long long)a[l]*a[l+1]; long long b2=(long long)a[r]*a[r-1]; if(b1>b2){ sum=(sum%m*b1%m)%m; l+=2; }else{ sum=(sum%m*b2%m)%m; r-=2; } k-=2; } } cout<<sum%m; return 0; }
#include <bits/stdc++.h> using namespace std; const int N=1e6+10,mod=1000000009; typedef long long ll; ll a[N]; int main(){ int n,k; cin>>n>>k; for(int i=0;i<n;i++)cin>>a[i]; sort(a,a+n); int f=1; int l=0,r=n-1; ll res=1; if(k%2){ res=a[r--]; k--; if(res<0) f=-1; } while(k){ ll x=a[l]*a[l+1]; ll y=a[r]*a[r-1]; if(x*f>y*f){ res=x%mod*res%mod; l+=2; } else { res=y%mod*res%mod; r-=2; } k-=2; // cout<<res<<endl; } cout<<res; return 0; }
