电影网站虚拟主机和vps,网站免费注册会员怎么做,泉州seo-泉州网站建设公司,网上购物商城首页一、双指针
1.AcWing 1238.日志统计
分析思路 前一区间和后一区间有大部分是存在重复的 我们要做的就是利用这部分 来缩短我们查询的时间 并且在使用双指针时要注意对所有的博客记录按时间从小到大先排好顺序 因为在有序的区间内才能使用双指针记录两个区间相差 相当于把一个…一、双指针
1.AcWing 1238.日志统计
分析思路 前一区间和后一区间有大部分是存在重复的 我们要做的就是利用这部分 来缩短我们查询的时间 并且在使用双指针时要注意对所有的博客记录按时间从小到大先排好顺序 因为在有序的区间内才能使用双指针记录两个区间相差 相当于把一个有序的时间序列进行每次递增1的划分 代码实现
#includeiostream
#includealgorithm#define x first
#define y second
using namespace std;
const int N100010;
typedef pairint,intPII;
PII logs[N];
bool st[N];
int cnt[N];
int main()
{int n,d,k;cinndk;for(int i0;in;i) cinlogs[i].xlogs[i].y;sort(logs,logsn);for(int i0,j0;in;i){int tlogs[i].y;cnt[t];while(logs[i].x-logs[j].xd){cnt[logs[j].y]--;j;}if(cnt[t]k) st[t]true;}for(int i0;i100000;i){if(st[i]) coutiendl;}return 0;
}
2.AcWing 1240.完全二叉树的权值
分析思路 双指针 从第一层根节点i1开始每一层开头都是2i,而每一层的长度就为pow(2,d-1)d为层数 前缀和 因为是完全二叉树所以算到最后要考虑是否越界。 代码实现
双指针
#includebits/stdc.husing namespace std;
typedef long long LL;
const int N100010;
int q[N];
LL sum[N];
int n,t;int main()
{scanf(%d,n);for(int i1;in;i) scanf(%d,q[i]);LL m-1e18;for(int i1,d1;in;i*2,d){LL s0;for(int ji;jipow(2,d-1)jn;j) sq[j];if(sm){ms;td;}}couttendl;return 0;
}前缀和
#includebits/stdc.husing namespace std;
typedef long long LL;
const int N100010;
int q[N];
LL sum[N];
int n,t;int main()
{scanf(%d,n);for(int i1;in;i) scanf(%d,q[i]);for(int i1;in;i) sum[i]sum[i-1]q[i];LL m-1e18;for(int i1,d1;in;i*2,d){LL s0;LL ripow(2,d-1)-1;if(rn) ssum[r]-sum[i-1];else ssum[n]-sum[i-1];if(sm){ms;td;}}couttendl;return 0;
}二、BFS
1.AcWing 1101.献给阿尔吉侬的花束
分析思路 BFS广度优先遍历就是队首出队然后与队首相关的入队。上图为模拟过程 代码实现
#include cstdio
#include cstring
#include iostream
#include algorithm
#include queue#define x first
#define y secondusing namespace std;typedef pairint,int PII;const int N210;int n,m;
char g[N][N];
int dist[N][N];int bfs(PII start,PII end)
{//队列queuePIIq;memset(dist,-1,sizeof dist);//初始化距离为-1;dist[start.x][start.y]0;q.push(start);int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1};while(q.size())//队列不为空{auto tq.front();//队首q.pop();//枚举四种方向上的情况for (int i 0; i 4; i ){int x t.x dx[i], y t.y dy[i];if (x 0 || x n || y 0 || y m) continue; // 出界if (g[x][y] #) continue; // 障碍物if (dist[x][y] ! -1) continue; // 之前已经遍历过dist[x][y] dist[t.x][t.y] 1;if (end make_pair(x, y)) return dist[x][y];q.push({x, y});}}return -1;
}int main()
{int t;cint;while(t--){cinnm;for(int i0;in;i) scanf(%s,g[i]);//读入的是字符串,不需要加PII start,end;//起点与终点for(int i0;in;i){for(int j0;jm;j){if(g[i][j]S) start{i,j};else if(g[i][j]E) end{i,j};}}int distance bfs(start, end);if (distance -1) puts(oop!);else printf(%d\n, distance);}return 0;
}2.AcWing 1096.地牢大师
分析思路 二维上多加了一维就有六个方向读入用二维读入。 代码实现
#includeiostream
#includealgorithm
#includecstdio
#includecstringusing namespace std;struct Point
{int x,y,z;
};const int N100;
char g[N][N][N];
int dist[N][N][N];
int l,r,c;
Point q[N * N * N];
int dx[6] {1, -1, 0, 0, 0, 0};
int dy[6] {0, 0, 1, -1, 0, 0};
int dz[6] {0, 0, 0, 0, 1, -1};int bfs(Point start,Point end)
{int hh0,tt0;q[0]start;memset(dist,-1,sizeof dist);dist[start.x][start.y][start.z]0;while(hhtt){auto tq[hh];for(int i0;i6;i){int xt.xdx[i],yt.ydy[i],zt.zdz[i];if(x0||y0||z0||xl||yr||zc) continue;if(g[x][y][z]#||dist[x][y][z]!-1) continue;dist[x][y][z]dist[t.x][t.y][t.z]1;if(g[x][y][z]E) return dist[x][y][z];q[tt]{x,y,z};}}return -1;}int main()
{while(cinlrc,l||r||c){Point start,end;for(int i0;il;i){for(int j0;jr;j){scanf(%s,g[i][j]);//三维用两维来存for(int k0;kc;k){if(g[i][j][k]S) start{i,j,k};else if(g[i][j][k]E) end{i,j,k};}}}int distancebfs(start,end);if(distance-1) puts(Trapped!);else printf(Escaped in %d minute(s).\n,distance);}return 0;
}
用队列的方式
#includeiostream
#includealgorithm
#includecstdio
#includecstring
#includequeueusing namespace std;struct Point
{int x,y,z;
};const int N100;
char g[N][N][N];
int dist[N][N][N];
int l,r,c;int dx[6] {1, -1, 0, 0, 0, 0};
int dy[6] {0, 0, 1, -1, 0, 0};
int dz[6] {0, 0, 0, 0, 1, -1};int bfs(Point start,Point end)
{queuePoint q;int hh0;q.push(start);memset(dist,-1,sizeof dist);dist[start.x][start.y][start.z]0;while(q.size()){auto tq.front();for(int i0;i6;i){int xt.xdx[i],yt.ydy[i],zt.zdz[i];if(x0||y0||z0||xl||yr||zc) continue;if(g[x][y][z]#||dist[x][y][z]!-1) continue;dist[x][y][z]dist[t.x][t.y][t.z]1;if(g[x][y][z]E) return dist[x][y][z];q.push({x,y,z});}q.pop();}return -1;}int main()
{while(cinlrc,l||r||c){Point start,end;for(int i0;il;i){for(int j0;jr;j){scanf(%s,g[i][j]);//三维用两维来存for(int k0;kc;k){if(g[i][j][k]S) start{i,j,k};else if(g[i][j][k]E) end{i,j,k};}}}int distancebfs(start,end);if(distance-1) puts(Trapped!);else printf(Escaped in %d minute(s).\n,distance);}return 0;
}
