「BJOI2019」光线

题目链接: https://oj.woshiluo.site/problem/2055 / https://www.luogu.org/problemnew/show/P5323

我看到题目的一瞬间

我是在学 oi 还是在学物理?

然后我仔细思考了一下,这两个镜子来回反射,您这是要求极限?

然后我仔细思考了一下

设 $f_i$ 为从 $1$ 到 $i$ 的透光率,$g_i$ 为从 $i$ 到 $1$ 的反光率

继续阅读“「BJOI2019」光线”

Luogu P3174 [HAOI2009]毛毛虫

题目链接: https://www.luogu.org/problemnew/show/P3174

这应该是我第一次没看 sol 做紫题吧……

虽然个人感觉比大多数紫题简单许多

题目本质是要求最长链的,但是要求是带每个点周围点的

我们设每个点的点权是这个点的连接点个数减 1

然后求最长链

得出来的链的长度 +2 即为答案

可以理解为因为大多数点都有一条边要连出去防止重复计算而减一

但是这样链头链尾会没算上,所以加二

继续阅读“Luogu P3174 [HAOI2009]毛毛虫”

Luogu P1829 [国家集训队]Crash的数字表格

题目链接: https://www.luogu.org/problemnew/show/P1829

显然,题目所求为以下式子

以下均默认$n \leq m$

$$
\sum_{i = 1}^n \sum_{j = 1}^m lcm(i,j)
$$

先来一些比较显然的东西
$$
\begin{aligned}
\sum_{i = 1}^n \sum_{j = 1}^m lcm(i,j) & =
\sum_{i = 1}^n \sum_{j = 1}^n \frac{i \cdot j}{\gcd(i,j)}\\
& = \sum_{d = 1}^n d \sum_{i = 1}^{\frac{n}{d}} \sum_{j = 1}^{\frac{m}{d}} i \cdot j \cdot [\gcd(i,j) = 1]\\
\end{aligned}
$$
后面一段看起来还可以再加优化

继续阅读“Luogu P1829 [国家集训队]Crash的数字表格”

基于 WebDAV 的 安卓 与 Linux 之间的写作同步

并不是多新奇或是巧妙的做法,仅仅是利用纯纯写作的 WebDAV 同步特性和 WebDAV 在 Linux 下的可挂载性

这种方法刚好满足我个人的需求,特此写于此处,望能给予有类似需求的人一点帮助

0 准备工作

  • 安卓端: 纯纯写作
  • Linux 端: Typora
  • Linux 端需要安装davfs2
  • 一台具有读写访问的 WebDAV 服务器
  • 我们希望您具有使用 Markdown 的能力,来避免过于复杂的鼠标或者快捷键操作
继续阅读“基于 WebDAV 的 安卓 与 Linux 之间的写作同步”

狄利克雷卷积 && 杜教筛 入门 — P4213 【模板】杜教筛(Sum)

狄利克雷卷积

数论函数

数论函数是指一类函数,其定义域是正整数,值域是一个数集

积性函数都是数论函数

常见的数论函数有

  • $id(n) = n$ 单位函数,完全积性函数
  • $\epsilon(n) = [n = 1]$ 元函数,完全积性函数
  • $d(n)$ 约数个数,积性函数
  • $\sigma(n)$ 约数和函数,积性函数
  • $\mu(n)$ 莫比乌斯函数,积性函数
  • $\varphi(n)$ 欧拉函数,积性函数
继续阅读“狄利克雷卷积 && 杜教筛 入门 — P4213 【模板】杜教筛(Sum)”

莫比乌斯反演入门 – [SDOI2015]约数个数和

道理我都懂,考试时这东西能推?

本人菜鸡,有问题请指出

鉴于不同博客对于整除符号$|$的定义不同, 特此表明本博客的整除定义

$a | b$ 表明 $b$ 是 $a$ 的倍数

0x01 什么是反演

对于一个数列${f_n}​$,如果有另外一个数列${g_n}​$满足如下条件
$$
g_n = \sum_{i = 1}^n a_if_i
$$
反演的过程是用$ g_n$来表示 $f_n$
$$
f_n = \sum_{i = 0}^n b_ig_i
$$

继续阅读“莫比乌斯反演入门 – [SDOI2015]约数个数和”

Luogu P1403 [AHOI2005]约数研究

题目

实际上一开始看到题目我是打算写筛法的,后来发先是个除法分块秒切题目

显然

$$
\sum_{i = 1}^{n} f(i) = \sum_{i = 1}^{n} \lfloor \frac{i}{n} \rfloor
$$

除法分块即可

代码

#include <cstdio>

int n;
long long ans;

int main(){
    scanf("%d", &n);
    for(int left = 1, rig; left <= n; left = rig + 1){
        rig  = n / (n / left);
        ans += 1LL * (n / left) * (rig - left + 1);
    }
    printf("%lld", ans);
}


[CQOI2007]余数求和

题目

一开始老是把思路和做​ 和​ 弄混……

然后陷入思维死角,感谢题解把我拉了出来​

$$
\sum_{i = 1}^{n} k \mod i \
= \sum_{i=1}^{n} k – i \times \lfloor \frac{k}{i} \rfloor \
= n \times k – \sum_{i=1}^{n} i \times \lfloor \frac{k}{i} \rfloor​
$$

然后就是除法分块,这个转化是真的要命QAQ

代码

#include <cstdio>

long long n,k,ans=0;

inline long long Min(long long a,long long b){return a<b?a:b;}

int main(){
   scanf("%lld%lld",&n,&k);
   ans=n*k;
   for(long long l=1,r;l<=n;l=r+1){
       if(k/l!=0) r=Min(k/(k/l),n);
       else r=n;
       ans-=(k/l)*(r-l+1)*(l+r)/2;
  }
   printf("%lld",ans);
}

Luogu 1248 加工生产调度

题目

题目链接: https://www.luogu.org/problemnew/show/P1248

这道题目暴力显然不可取$ 1000!$ , DP 的状态不太容易定义,只能贪心大法

分析贪心

我们可以先假设只有两个物品$ A $ 和$ B $,则存在以下两种情况($ x $代表物品在 A 工厂加工所需时间,$ y $ 代表 B 工厂,以下同理)

  1. 先加工$ A $后加工$ B $,则时间为$ A.x + B.y + \max(A.y, B.x) $
  2. 先加工$ B $后加工$ A $,则时间为$ A.y + B.x + \max(A.x, B.y) $

则若先加工 A 比先加工 B 优,应满足
$$
A.x + B.y + \max(A.y, B.x) < A.y + B.x + \max(A.x, B.y) \\
\begin{align}
&= \max(A.y, B.x) – A.y – B.x < \max(A.x, B.y) – A.y – B.x \\
&= -\min(A.y, B.x) < -\min(A.x, B.y) \\
&= \min(A.x, B.y) < \min(A.y, B.x)
\end{align}
$$
然后放到cmp里,A 了?

等一下,这个方法……是错误的

继续阅读“Luogu 1248 加工生产调度”