企业官网建设流程全解析

咸阳市网站建设公司,python做的网站,百度广告买下的订单在哪里找,网站建设教程pdf百度云st表一般的适用范围 a b区间可能有重叠部分 但是并不影响ab区间的答案 能通过a区间的答案 b区间的答案 加工出来 那么这种问题就是一个可重复贡献问题 例如区间最最值#xff08;RMQ) 区间公约数 但是 区间求和 显然是不可以的 再例如 区间按位与 区间按位或…st表一般的适用范围a b区间可能有重叠部分但是并不影响ab区间的答案能通过a区间的答案 b区间的答案 加工出来 那么这种问题就是一个可重复贡献问题例如区间最最值RMQ) 区间公约数但是 区间求和 显然是不可以的再例如区间按位与 区间按位或ST表都能高效解决优劣RMQ问题可以用st表维护 也可以用线段树优势时间复杂度 nlogn 单次查询o(1代码量好写劣势: 所需要的空间比较大维护的信息有限不支持修改操作P4155 [SCOI2015] 国旗计划时间限制: 1.50s 内存限制: 250.00MB复制 Markdown 退出 IDE 模式题目描述A 国正在开展一项伟大的计划 —— 国旗计划。这项计划的内容是边防战士手举国旗环绕边境线奔袭一圈。这项计划需要多名边防战士以接力的形式共同完成为此国土安全局已经挑选了 N 名优秀的边防战士作为这项计划的候选人。A 国幅员辽阔边境线上设有 M 个边防站顺时针编号 1 至 M。每名边防战士常驻两个边防站并且善于在这两个边防站之间长途奔袭我们称这两个边防站之间的路程是这个边防战士的奔袭区间。N 名边防战士都是精心挑选的身体素质极佳所以每名边防战士的奔袭区间都不会被其他边防战士的奔袭区间所包含。现在国土安全局局长希望知道至少需要多少名边防战士才能使得他们的奔袭区间覆盖全部的边境线从而顺利地完成国旗计划。不仅如此安全局局长还希望知道更详细的信息对于每一名边防战士在他必须参加国旗计划的前提下至少需要多少名边防战士才能覆盖全部边境线从而顺利地完成国旗计划。输入格式第一行包含两个正整数 N,M分别表示边防战士数量和边防站数量。随后 N 行每行包含两个正整数。其中第 i 行包含的两个正整数 Ci​、Di​ 分别表示 i 号边防战士常驻的两个边防站编号Ci​ 号边防站沿顺时针方向至 Di​ 号边防站为他的奔袭区间。数据保证整个边境线都是可被覆盖的。输出格式输出数据仅 1 行需要包含 N 个正整数。其中第 j 个正整数表示 j 号边防战士必须参加的前提下至少需要多少名边防战士才能顺利地完成国旗计划。输入输出样例输入 #1复制运行4 8 2 5 4 7 6 1 7 3输出 #1复制运行3 3 4 3说明/提示N≤2×105,M109,1≤Ci​,Di​≤M。我们要选出第i条线段参与的情况下 覆盖一个环形的最少的线段数目我们输入每条线段的编号和起点终点 然后按照起点排序首先破环成链 后面复制一份 并且将每条线段在后侧都复制一份设st表的定义为st[i][j]表示从编号为i的线段开始跳1j步最远能到达 的线段的编号然后初始化st表 即每个编号跳一步能到哪也就是st[i][0]dp的思想根据跳一步的数据 推导出2.....等二进制步数然后最后开始跳 也就是模拟一遍过程 找到最少的线段数 跳的过程中 先设定一个目标 也就是总覆盖长度m当前起点 然后优先跳大步子 逐渐减小 (倍增的思想 因为每一步都是一个二进制某一位 从大到小跳一定可以表示所有的步数 每次枚举一个大步数 如果跳到的这个点小于终点 那么就跳转到这个点 并且答案加上这个步数 最后输出答案即可#include bits/stdc.h using namespace std; const int N2e55; struct node{ int l,r,id; }line[2*N]; int n,m; int st[2*N][30]; int ans[N]; //输入 排序 复制 dp推导st 查询 bool cmp(node a,node b){ return a.lb.l; } int jump(int i){ int aimline[i].lm,curi,nxt,ans1; for(int p20;p0;p--){ nxtst[cur][p]; if(nxt!0line[nxt].laim){ ans(1p); curnxt; } } return ans; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cinnm; for(int i1;in;i){ cinline[i].lline[i].r; line[i].idi; if(line[i].lline[i].r){ line[i].rm; } }sort(line1,line1n,cmp); for(int i1;in;i){ line[in]line[i]; line[in].lm;line[in].rm; } for(int i1,arrive1;i2*n;i){//初始化每个点一步最远跳到哪个边的编号的起点 while(arrive12*nline[arrive1].lline[i].r){//某编号的边起点自己的终点 arrive; } st[i][0]arrive; } for(int p1;p20;p){ for(int i1;i2*n;i){ st[i][p]st[st[i][p-1]][p-1]; } } for(int i1;in;i){ ans[line[i].id]jump(i); } for(int i1;in;i)coutans[i] ; return 0; }RMQ区间最值问题P2880 [USACO07JAN] Balanced Lineup G时间限制: 1.00s 内存限制: 512.00MB复制 Markdown中文退出 IDE 模式题目描述每天农夫 John 的 n (1≤n≤5×104) 头牛总是按同一序列排队。有一天John 决定让一些牛们玩一场飞盘比赛。他准备找一群在队列中位置连续的牛来进行比赛。但是为了避免水平悬殊牛的身高不应该相差太大。John 准备了 q (1≤q≤1.8×105) 个可能的牛的选择和所有牛的身高 hi​ (1≤hi​≤106,1≤i≤n)。他想知道每一组里面最高和最低的牛的身高差。输入格式第一行两个数 n,q。接下来 n 行每行一个数 hi​。再接下来 q 行每行两个整数 a 和 b表示询问第 a 头牛到第 b 头牛里的最高和最低的牛的身高差。输出格式输出共 q 行对于每一组询问输出每一组中最高和最低的牛的身高差。输入输出样例输入 #1复制运行6 3 1 7 3 4 2 5 1 5 4 6 2 2输出 #1复制运行6 3 0st表分别维护最大值最小值 做差即可#include bits/stdc.h using namespace std; const int N5e45; int st1[N][30]; int st2[N][30]; int n,q; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cinnq; int powerlog(n)/log(2)1; for(int i1;in;i){ cinst1[i][0]; st2[i][0]st1[i][0]; } for(int p1;ppower;p){ for(int i1;in-(1p)1;i){ st1[i][p]max(st1[i][p-1],st1[i(1(p-1))][p-1]); st2[i][p]min(st2[i][p-1],st2[i(1(p-1))][p-1]); } } while(q--){ int l,r;cinlr; int klog(r-l1)/log(2); int num1max(st1[l][k],st1[r-(1k)1][k]); int num2min(st2[l][k],st2[r-(1k)1][k]); coutnum1-num2\n; } return 0; }区间GCDP1890 gcd 区间时间限制: 1.00s 内存限制: 125.00MB复制 Markdown中文退出 IDE 模式题目描述给定 n 个正整数 a1​,a2​,…,an​。m 次询问每次询问给定一个区间 [l,r]输出 al​,al1​,…,ar​ 的最大公因数。输入格式第一行两个整数 n,m。第二行 n 个整数表示 a1​,a2​,…,an​。以下 m 行每行两个整数 l,r 表示询问区间的左右端点。输出格式共 m 行每行表示一个询问的答案。输入输出样例输入 #1复制运行5 3 4 12 3 6 7 1 3 2 3 5 5输出 #1复制运行1 3 7说明/提示对于 30% 的数据1≤n≤1001≤m≤10对于 60% 的数据1≤m≤1000对于 100% 的数据1≤l≤r≤n≤10001≤m≤1061≤ai​≤109。#include bits/stdc.h using namespace std; const int N1e35; int st[N][30]; int n,m; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cinnm; for(int i1;in;i)cinst[i][0]; int tlog(n)/log(2)1; for(int p1;pt;p){ for(int i1;in-(1p)1;i){ st[i][p]__gcd(st[i][p-1],st[i(1(p-1))][p-1]); } } while(m--){ int l,r;cinlr; int klog(r-l1)/log(2); cout__gcd(st[l][k],st[r-(1(k))1][k])\n; } return 0; }区间众数问题题目描述 给出一个非降序排列的整数数组a1,a2,…,an,你的任务是对于一系列询问i,j,回答ai,ai1,…aj中出现次数最多的值所出现的次数输入数据 输入包含多组数据。每组数据第一行为两个整数n和q1≤nq≤100000。第二行包含n个非降序排列的整数a1,a2,…,an-100000≤ai≤100000。以下q行每行包含两个整数i和j1≤i≤j≤n输入结束标志为n0输出格式 对于每个查询ij输出查询结果也就是i~j中出现次数最多的数的个数之间用换行隔开注朴素算法可能会超时这个注释原本题目里面就有不是我自己加的。。由 hicc0305 提供翻译思路 题目是升序排列的 那么我们可以对每一个数字建立一个桶 统计每个数字的次数然后每次查询的时候 判断区间首末的元素类型是否相等 相等直接输出 不相等就特判以下首末元素的个数 然后将首末元素之间的元素的众数 用st表维护桶的区间最大值就可以 然后比较即可所有相同的数都是连在一起的所以我们可以把原序列分段比如样例-1 -1 1 1 1 1 3 10 10 10我们可以这样记录我们把所有相同的数归成一段。用num[p]来记录p这个位置在第几段里比如num[1]1,num[2]1,num[3]2。然后用l[i]来记录第i段的左边界的序号r[i]来记录第i段的右边界的序号比如l[2]3,r[2]6。然后我们对于每个询问l,r只需要把l,r分成三个部分求像这样