题目链接https://www.luogu.org/problemnew/show/CF337D 分析这题觉得还是挺妙的 一个$naive$的做法,对于每个点为根做一遍搜索,对于距离小于等于$d$的点,计数器$+1$,最后再搜一遍统计计数器等于$m$的点就好了,但是这样做肯定超时 这时候我们就想办法减少搜索次数呗,如果某个点到相距最远的两个被亵渎的点距离都小于等于$d$,那么显然这点是合法的,于是
题目链接https://www.luogu.org/problemnew/show/CF337C 题意:有n个问题,回答对一个得一分,而且连续k个问题回答正确分数翻倍(之后连续的计数器重置为0计算),你回答对了m个,求你最小的可能得分 分析CF前几题常见套路,给你一个非常简单但有点烦人的问题,但总是有各种坑点让你$fst$ 我们肯定是尽量不让它连续回答对k个,于是分成$n/k$组(余下的那部分先不
题目链接https://cn.vjudge.net/problem/POJ-1845 分析$POJ$里的数学题总是这么妙啊 首先有一个结论就是$A=\prod{ \ {p_i}^{c_i} \ }$,那么$A$所有约数之和为$(1+p_1+p_1^2+..+p_1^{c_1}) * (1+p_2+p_2^2+…+p_2^{c_2}) … (1+p_n +p_n^2 +… + p_n^{c_n})$
题目链接https://www.luogu.org/problemnew/show/P1313 分析二项式定理$(a+b)^n=\sum_{k=0}^{n}{C^k_n a^k b^{n-k} }$ 于是我们要求的即是$C^k_n \times a^n \times b^m$,于是直接快速幂，然后按公式$C^k_n=\frac {n!}{(n-k)! \times k!}$,化成$\prod_{i
题目链接https://cn.vjudge.net/problem/POJ-2773 题意: 求第$k$个与$m$互质的数 分析因为$gcd(a,b)=gcd(a+t * b,b)$ 所以在$[1,m-1]$中与$m$互质的个数与在$[k \times m+1,(k+1) \times m-1]$的互质(把上一个式子的$b$看成$m$一下就明白了)的个数都等于$\phi (m)$ 然后直接暴力计算
题目链接https://www.luogu.org/problemnew/show/P4777 分析扩展$CRT$就是解决模数不互质的情况,说是扩展$CRT$,其实都是扩欧… 先来考虑两个方程的情况:$x \equiv a \mod b$和$x \equiv c \mod d$ 由方程1得$x=tb+a$,代入方程2中得$tb+a \equiv c \mod d$， 把它变得更像方程:$t \ti
题目链接https://www.luogu.org/problemnew/show/P2568 分析题目即求$\sum_{i=1}^N \sum_{j=1}^N [gcd(i,j)$ $is$ $a$ $prime$ $number$ $]$ 我们提出这个素数变成$\sum_p \sum_{i=1}^{\frac{N}{p} \ } \sum_{j=1}^{\frac{N}{p} \ } [gcd
题目链接https://www.luogu.org/problemnew/show/SP338 分析联想到不久前做过的一道题$Full$ $Tank$,感觉可以用优先队列做,于是写了$dijsktra$(非负权图不敢用$SPFA$了) 然后发现错了，想了挺久，发现它实际上是可以找$dis$更大的走以花费更少的钱,于是把$vis$数组和$dis$数组全去掉就A了 优先队列保证取出的距离是最短的,如果
题目链接https://www.luogu.org/problemnew/show/P1731 分析这题真[哔]恶心，加了一堆奇奇怪怪的优化 首先明确一点,半径和高都必须是正整数,意味着它们最小为$1$ 同时我们通过数学公式可以推得:当剩下体积$v$一定时，层数越少面积越小,也就是说, 越趋进一个圆柱面积越小. 于是我们可以预处理出搜索到每一层的最小剩余体积$miv[i]=miv[i-1]+i^3
题目链接https://www.luogu.org/problemnew/show/P1018 分析这道题套路跟山区建小学差不多,可以先去看看那篇题解 $f[i][j]$表示枚举到第$i$位数,放了$j$个乘号的最大结果,同样的我们枚举区间断点看看新加入的乘号(也就是最后一个乘号)放在哪最大 没写高精打了表(捂脸) 代码123456789101112131415161718192021222324