APTX博客

  • ACGN
  • Coding
  • DevOps
  • Daily
  • Share
  • Bangumi
logn
OI

HDU 1806 Frequent values(区间RMQ问题)题解

洛谷:https://www.luogu.org/problemnew/show/U50167 Description 给定一个非降序的由 n 个整数构成的序列以及 q 个由整数i 和 j 构成的询问。对于每一个询问,输出在 a[i],a[i+1], ... ,a[j-1],a[j]里面出现次数最多的那个(些)整数出现的次数。 Input 第一行包含两个整数, n 和 q。第二行包括 n 个整数 a[1],a[2], ... ,a[n],由空格分开。以下 q 行每一行包括一个询问,一个询问由两个整数 i 和 j 构…

2018年11月3日 0条评论 1309点热度 0人点赞 神楽坂 みずき 阅读全文
OI

POJ 3233 Matrix Power Series(矩阵快速幂+二分)题解

洛谷:https://www.luogu.org/problemnew/show/U50124 Description 给定一个 n*n 的矩阵 A 以及一个正整数 k,计算\(S = A^1 + A^2 + A^3+...+A^k\) Input 输入只有一组测试数据。输入的第一行包括三个正整数 n, k, m。接下来的 n 行每行包括 n 个非负整数,按照行优先的顺序输入矩阵 A 的元素。 Output 输出 S 中每一个元素 mod(%)m 以后的值 Sample Input 2 2 4 0 1 1 1 Sa…

2018年11月3日 0条评论 1220点热度 0人点赞 神楽坂 みずき 阅读全文
OI

#C/C++#数据结构:ST表模板

简介 ST表用于区间RMQ问题,它可以做到O(nlogn)预处理,O(1)查询最值。相比线段树,更加有利于静态数据的最值问题。主要是利用倍增的思想。 洛谷:P3865 模板 #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <iostream> #include <vector>…

2018年9月8日 0条评论 1607点热度 0人点赞 神楽坂 みずき 阅读全文
OI

C/C++ 最短路算法Dijkstra算法 + 堆优化模板

简介 Dijkstra算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。 无优化复杂度:O(n ^ 2) 那么有O(km)的Spfa算法我们为什么需要Dijkstra算法呢? 因为某些毒瘤出题人会专门设计网格图来卡Spfa算法,使其变为O(m ^ 2)如下方提到的落谷题目。 洛谷:P3371(弱化版) Spfa能过    P4779(标准版)卡S…

2018年8月3日 0条评论 2943点热度 0人点赞 神楽坂 みずき 阅读全文
OI

#C/C++#树状数组模板

问题模型 现在有一个这样的问题:有一个数组a,,现在给你w次修改,q次查询,修改的话是修改数组中某一个元素的值;查询的话是查询数组中任意一个区间的和。 这个问题很常见,首先分析下朴素做法的时间复杂度,修改是O(1)的时间复杂度,而查询的话是O(n)的复杂度,总体时间复杂度为O(qn) 可能你会想到前缀和来优化这个查询,我们也来分析下,查询的话是O(1)的复杂度,而修改的时候修改一个点,那么在之后的所有前缀和都要更新,所以修改的时间复杂度是O(n),总体时间复杂度还是O(qn)。 可以发现,两种做法中,要么查询是O(…

2018年6月29日 0条评论 1775点热度 0人点赞 神楽坂 みずき 阅读全文

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
站点域名变更通知 私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话 从《AMRITA》到《HELLO WORLD》── 野﨑まど世界观下的个体与世界的真实感 几种云端 VSCode/类 VSCode 方案对比与部署 Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版
中国银行莫奈卡万事达借记卡网申与评测 Linux下使用Sublime Text3 破解汉化并配置C++编程环境 C++快读快写模板 《从零》第二季&《春物》第三季制作决定 #C/C++#二分图匹配匈牙利算法模板(邻接表/邻接矩阵) HDU 1806 Frequent values(区间RMQ问题)题解
标签聚合
ST C/C++ 洛谷 动漫 OI C++ HTML 日常
分类
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share

COPYRIGHT © 2017-2022 APTX博客. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang