月份:2019年3月

篇文章

NOIP2019模拟赛(五)03.31 解题报告
Link NOIP2019模拟赛(五)03.31 A. 「NOIP模拟赛」电阻 题意 询问要得出一个电阻值为$\frac{a}{b}$的元件至少需要多少个电阻值为$1$的电阻。 元件由$3$种方式组成: 一个电阻 一个元件与一个电阻串联 一个元件与一个电阻并联 思路 并联电阻阻值计算 总电阻值为:$总R_总=\frac{1}{\frac{1}{R_…
Codeforces Gym 101002 H. Jewel Thief 题解
题意 类似于一个背包,空间为$M$,有$N$个物品,第$i$个物品体积为$w_i$,价值为$c_i$,求价值之和的最大值。 其中,$1 \leq n \leq 100000$,$1\leq m \leq 300000$,$1\leq w_i \leq 3$,$1\leq c_i \leq {10}^9$ 思路 首先注意到$n,m$非常大,所以普通的…
10238. 「一本通 6.6 练习 9」网格
题意 某城市的街道呈网格状,左下角坐标为 $A(0, 0)$,右上角坐标为 $B(n, m)$,其中 $n \ge m$。现在从 $A(0, 0)$ 点出发,只能沿着街道向正右方或者正上方行走,且不能经过图示中直线左上方的点,即任何途径的点 $(x, y)$ 都要满足 $x\ge y$,请问在这些前提下,到达 $B(n, m)$ 有多少种走法。 思…
「NOIP模拟赛」欧拉口算 题解
题目描述 令 $C(n)$ 表示 把 $n$ 拆分成 $a\times b=n(a\leq b)$ 且 $a,b$ 的因子个数相同的方案数 给定一个整数$n$,$(1 \leq n \leq 100)$。 求出$C(n!)$。 思路 先把$n!$拆成若干个质数的乘积。 即:$n!={p_1}^{c_1} \times {p_2}^{c_2} \ti…
10166. 「一本通 5.3 练习 1」数字游戏
题意 给定多组数据,每组数据给定三个数:$a,b,n$表示求在区间$[a,b]$内各位数之和模$n=0$的数的个数。 思路 这是一道数位$DP$的模板题。 设$f[i][S]$表示处理到第$i$位,$S$为和。 $f[i][S]=f[i-1][(S+i)%N](0<=k<=Dim[i] or 9)$ 其中$k$的取值范围根据上一位的状态…
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-5db08230ebcd4322087987/] 拓展欧几里得算法 定理 定理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%的数据 …