- 浏览: 118393 次
- 性别:
- 来自: 北京
最新评论
/* * Author: rush * Created Time: 2010年07月28日 星期三 09时29分05秒 * File Name: icpc/hdu3486.cpp */ #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <map> #include <set> #define out(v) cout << #v << ": " << (v) << endl using namespace std; typedef long long LL; const int maxn = 200000 + 5; int n, k, a[maxn]; int rmax[20][maxn]; void make() { for (int j = 0; j < n; ++j) rmax[0][j] = a[j]; for (int i = 0; i + 1 < 20; ++i) for (int j = 0; j + (1 << i) < n; ++j) rmax[i + 1][j] = max(rmax[i][j], rmax[i][j + (1 << i)]); } // [begin, end) int query(int begin, int end) { int k = 0; while ((1 << (k + 1)) < end - begin) ++k; return max(rmax[k][begin], rmax[k][end - (1 << k)]); } int main() { while (scanf("%d%d", &n, &k) != EOF) { if (n < 0 && k < 0) break; for (int i = 0; i < n; ++i) scanf("%d", &a[i]); make(); int m, L, prev = -1, sum, i, j; for (m = 1; m <= n; ++m) { L = n / m; if (L != prev) sum = 0, i = 0, j = 0; while (i + L <= n && j < m) { sum += query(i, i + L); i += L; ++j; } prev = L; if (sum > k) break; } printf("%d\n", m <= n ? m : -1); } return 0; }
update 20101230:
二维RMQ
/* * Author: rush * Created Time: 2010年12月30日 星期四 15时59分14秒 * File Name: icpc/pku2019_2.cpp */ #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <map> #include <set> #define out(v) cout << #v << ": " << (v) << endl #define FOR(i, n) for (int i = 0; i < n; ++i) #define two(x) (1 << x) #define min4(a, b, c, d) min(min(min(a, b), c), d) #define max4(a, b, c, d) max(max(max(a, b), c), d) using namespace std; typedef long long LL; int N, B, K; int mat[255][255]; int rmin[10][255][255], rmax[10][255][255]; void make() { FOR(i, N) FOR(j, N) rmin[0][i][j] = rmax[0][i][j] = mat[i][j]; for (int k = 0; k + 1 < 10; ++k) for (int i = 0; i + two(k) < N; ++i) for (int j = 0; j + two(k) < N; ++j) { rmin[k + 1][i][j] = min4(rmin[k][i][j], rmin[k][i][j + two(k)], rmin[k][i + two(k)][j], rmin[k][i + two(k)][j + two(k)]); rmax[k + 1][i][j] = max4(rmax[k][i][j], rmax[k][i][j + two(k)], rmax[k][i + two(k)][j], rmax[k][i + two(k)][j + two(k)]); } } int query(int x, int y) { int k = 0; while (two(k + 1) <= B) ++k; int tmin = min4(rmin[k][x][y], rmin[k][x][y + B - two(k)], rmin[k][x + B - two(k)][y], rmin[k][x + B - two(k)][y + B - two(k)]); int tmax = max4(rmax[k][x][y], rmax[k][x][y + B - two(k)], rmax[k][x + B - two(k)][y], rmax[k][x + B - two(k)][y + B - two(k)]); return tmax - tmin; } int main() { scanf("%d%d%d", &N, &B, &K); for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) scanf("%d", &mat[i][j]); make(); while (K--) { int x, y; scanf("%d%d", &x, &y); --x, --y; printf("%d\n", query(x, y)); } return 0; }
发表评论
-
lower_bound and upper_bound
2012-02-09 00:36 1151/** * @brief Finds the ... -
HDU 3954
2012-02-05 10:43 840线段树变种,也是在2logn段上面做文章 /* * ... -
HDU 4027
2012-02-04 22:09 849线段树变种 在2logn段上面做文章,swap(x, y)太阴 ... -
ICPC编码建议
2011-10-28 09:52 887写代码最重要的是清晰,包括思路的清晰和代码结构的清晰。我们无法 ... -
[转载]TopCoder插件
2011-09-08 22:13 971转载自:http://acm.cugb.edu.cn/blog ... -
UVALive 5112 - Sales Prediction
2011-01-06 10:19 1188封装了矩阵类 比赛做得很郁闷,为什么别人写得很长、很罗嗦的代码 ... -
hdu 3236
2010-12-12 14:10 797终于能过这道题了,算是背包必做题之一吧 /* * Au ... -
pku 1018
2010-12-11 15:18 602写了两三个版本,最后这个效率最高 #include < ... -
布斯(Booth)乘法
2010-10-07 19:59 1137源自http://watashi.ws/blog/1515/z ... -
高斯消元
2010-10-07 14:18 803import java.util.*; import j ... -
整数划分
2010-10-07 10:38 839#include <cstdio> #inc ... -
Treap
2010-09-18 22:19 980// Treap // Tested: bjtu1057 ... -
矩阵快速幂
2010-09-18 14:24 1050typedef LL matrix[55][55]; ... -
maximum clique 最大团
2010-09-02 18:12 1134最大团模板 #include <cstdio> ... -
计算Jacobi符号
2010-08-31 13:15 1291Quadratic reciprocity The Jacob ... -
Java 高效I/O
2010-08-19 16:54 775static BufferedReader cin = ... -
DLX pku 3076
2010-08-11 23:45 877标准数独,精确覆盖 // pku3076.cpp #in ... -
DLX hust 1017
2010-08-11 16:50 848“精确覆盖”问题 #include <cstdio& ... -
DLX hdu 3498
2010-08-11 16:48 1039“多重覆盖”或“重复覆盖”问题 #include < ... -
hdu 3509
2010-08-09 11:22 1004推导公式的题目,矩阵幂关键就在于构造系数矩阵 备忘: S(n, ...
相关推荐
该模板基于默认的RMQ模板。 实际上,它是相同的模板应用程序,但有以下更改: /controllers/main_controller.rb已经移动到/screens/main_screen.rb与推广惯例保持一致 使用ProMotion助手方法创建导航栏 安装及使用...
--RMQ --改点堆优化的dijkstra算法 --快速付利叶变换 --稳定婚姻问题 --SPFA(最短路快速算法) // thanks to love8909 几何相关 --初等几何学 --多边形几何 --几种凸包算法 --半平面交算法 --旋转卡壳算法 数据结构...
图论--LCA--在线RMQ ST 最小环: 图论--最小环--Floyd模板 树的直径: 图论--树的直径--DFS+树形DP模板 树的重心: 图论--树的重心(DFS) 模板 生成树: 图论--最小生成树--Kruscal 模板 ...
5.1.5 An(N), O(1)> algorithm for the restricted RMQ 60 5.1.6 An AC programme 61 5.2 最长公共子序列LCS 64 5.3 最长上升子序列/最长不下降子序列(LIS) 65 5.3.1 O(n^2) 65 5.3.2 O(nlogn) 66 5.4 Joseph问题 67...
5.1.5 An(N), O(1)> algorithm for the restricted RMQ 60 5.1.6 An AC programme 61 5.2 最长公共子序列LCS 64 5.3 最长上升子序列/最长不下降子序列(LIS) 65 5.3.1 O(n^2) 65 5.3.2 O(nlogn) 66 5.4 Joseph问题 67...
算法文档无代码RMQ&LCA问题提取方式是百度网盘分享地址
3.线段树模板(模板为区间加法) (线段树染色) (区间最小值) 4.线性基 (求异或第k大) 5.主席树(静态求区间第k小) (区间中小于k的数量和小于k的总和) (区间中第一个大于或等于k的值) 6.权值线段树 (求逆序对) 7.动态...
包括树剖,线段树,splay,Treap,网络流,RMQ,数论函数求值,主席树,树状数组,LCA,CRT,BSGS,树套树等模板。(注:其中的两个cdq模板都没用的,整体二分写错了,其余模板可以自行测试。 p.s.有些可能与一些已...
ACM 算法模板集 Contents 一. 常用函数与STL 二. 重要公式与定理 1. Fibonacci Number 2. Lucas Number 3. Catalan Number 4. Stirling Number(Second Kind) 5. Bell Number 6. Stirling's Approximation 7. Sum of ...
用PB实现组合查询,可作为模板,独立的pbl
8.6 LCA和RMQ 167 8.7 割和桥 171 8.8 最小生成树(kruskal) 172 8.9 最短路径 173 8.10 最大网络流 175 8.11 最小费用流 180 8.12 最大团问题 182 8.13 二分图匹配 184 8.14 带权的最优二分图匹配 184 9.搜索算法...
3.2 RMQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.2.1 一维 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.2.2 二维 . . . ...
用于打比赛的ACM算法模板 常用函数与STL 重要公式与定理 1. Fibonacci Number 2. Lucas Number 3. Catalan Number 4. Stirling Number(Second Kind) 5. Bell Number 6. Stirling's Approximation 7. Sum of ...
Ruby 动作模板用途:Promotion Promotion-menu RMQ Font Awesome
本科参加ACM竞赛的过程中积累下来的一部分算法模板,和自己在PKU上面做的一部分题目。 模板目录结构: 目录: 动态规划 O(n^2)的最长上升子序列 nlogn最长上升子序列 高精度 计算几何 Graham扫描法 两线段交点 凸...
基于RMQ(ST表) 26 Tarjan 28 二分图 31 相关总结 31 二分图最大匹配 32 二分图最大权匹配 35 网络流 38 最大流 && 最小割 38 费用流 46 一般数据结构 49 ST Table 49 树状数组 51 树链剖分 52 平衡二叉树 56 Splay...
5.1 RMQ问题…………………………………………………………(23) 6.1 trie字典树………………………………………………………...(24) 7.1 拓扑排序………………………………………………………….(26) 8.1 pick定理的...
ACM模版-->矩阵快速幂,搜索,树链剖分,线段树,动态规划,RMQ
ACM-ICPC团队参考 编程竞赛团队参考() 编译成pdf latex -output-format=pdf reference.tex 内容 杂项 立方体 约瑟夫斯 划分 随机 有用 比特面具 哈密顿步道的数量 ...最长共同祖先(rmq) 最长共同祖先(sqrt)
一大堆模版 自己可以下来参考 应该有200个以上吧 自己下来看看 其中一个目录 ... LCA/RMQ 有限状态自动机理论 排序 选择/冒泡 快速排序 堆排序 归并排序(OK) 基数排序 拓扑排序 排序网络