夜间模式暗黑模式
字体
阴影
滤镜
圆角
主题色
NOIP2019模拟赛(二)03.10
T1 题意 题面 给定两个数$a$,$b$求出$b$个$a$相乘的结果。 数据范围 保证$a \leq 99.9999 ,b \leq 25$且$a$的有效数字不超过$6$位。 思路 对于20%的数据 你开$long\quad double$就好了呀。 对于100%的数据 你写高精度就好了呀。 说得很轻巧,但是打比赛的时候花了30分钟。。。 差不多…
10213. 「一本通 6.4 例 5」Strange Way to Express Integers
题意 给定 $2n$ 个正整数 $a_1,a_2,\cdots ,a_n$ 和 $m_1,m_2,\cdots ,m_n$,求一个最小的正整数 $x$,满足 $\forall i\in[1,n],x\equiv a_i\ (\bmod m_i\ )$,或者给出无解。 思路 其实题意就是求出: $x\equiv a[1] \bmod m[1]…
10181. 「一本通 5.5 练习 2」绿色通道
题意 高二数学《绿色通道》总共有 $n$ 道题目要抄,编号 $1\dots n$,抄第 $i$ 题要花 $a_i$ 分钟。小 Y 决定只用不超过 $t$ 分钟抄这个,因此必然有空着的题。每道题要么不写,要么抄完,不能写一半。下标连续的一些空题称为一个空题段,它的长度就是所包含的题目数。这样应付自然会引起马老师的愤怒,最长的空题段越长,马老师越生气。…
拓展欧几里得算法与应用
欧几里得算法 即:$gcd(a,b)=gcd(b,a$%$b)$ 欧几里得算法在oi里非常常用,几乎每个数学题都有欧几里得算法——$gcd$。 说白了就是求最大公约数。一行代码搞定: [crayon-5e89e4b443e22687570219/] 拓展欧几里得算法 定理 定理1:设$a$和$n$不全为$0$,则存在整数$x,y$,满足$ax+by…
Luogu 2019三月月赛 P5239 回忆京都 题解
题意 题目背景讲太多了吧。。。一句话题意: 有$Q$个询问,每个询问求出: $$\sum_{i=1}^n\sum_{j=1}^m C_j^i$$ 对于$60$%的数据,$q \leq 10, n\leq100,m\leq100$。 对于$100$%的数据,$q \leq 1000,n\leq1000,m\leq1000$。 思路 对于60%的数据 …
10182. 「一本通 5.5 练习 3」理想的正方形
题意 有一个 $a\times b$ 的整数组成的矩阵,现请你从中找出一个 $n\times n$ 的正方形区域,使得该区域所有数中的最大值和最小值的差最小。 思路 设$dp[i][j][k]$表示以$i,j$为左上角的正方形变成为$k$内的最大值,$dp2[i][j][k]$表示最小值。 可知,$dp[i][j][k]=max(dp[i+1][j…
zkw线段树 学习笔记
前置知识 C++位运算学过线段树(其实关系不大) 什么是zkw线段树 就是一种线段树。(废话) 与普通线段树相比,zkw线段树更快、更短小。 本篇博客讲一个例题:Luogu P3372 普通线段树 zkw线段树 zkw线段树的实现 首先来看一看变量的定义与BuildTree操作 这是一棵求和的线段树(废话) 然后我们发现它有16个叶子节点。 而$1…
2240. 「CQOI2014」数三角形
三倍经验 LOJ #2240. 「CQOI2014」数三角形 BZOJ 3505: [Cqoi2014]数三角形 Luogu P3166 [CQOI2014]数三角形 (Luogu要大一些。。。) 题意 给定一个$n \times m$的网格,请计算三点都在格点上的三角形共有多少个。下图为$4 \times 4$的网格上的一个三角形。注意三角形的三…
主席树(静态) 学习笔记
在学习主席树之前 你必须学习: 线段树。 前缀和。 sort函数、unique函数以及lower_bound函数的使用方法。 什么是主席树 主席树又叫函数式线段树,又名可持久化线段树。所以主席树的名称与他的功能一点关系都没有。 主席树的时空复杂度为$O(n logn)$。 主席树的模板 由于主席树比较难理解,所以结合代码理解一下: [crayon-…