GoPoux4

分类

未归档(36) 题解(2)

/ 注册

全部文章（共23篇）

题解「P5451 [THUPC2018]密码学第三次小作业」

校内测试考了这道题，当时按照题目背景瞎搞了搞，把样例水过了，结果爆零/kk 开始还以为正解要从题目背景中推出来，搞了一个多小时。考完发现背景和题目没什么关系啊！再也不看题目背景了首先题面用粗体强调了：\(e_1\) 与 \(e_2\) 互素。也就是说,有整数 \(s,t\)，满足： ...

题解数学

2020-05-09

0 393

题解「CF1000G Two-Paths」

考试做到了类似的一道题 LOJ#6699，题解是换根DP。但是我不会换根，所以用倍增过了这道题qwq。题意给定一棵树，有点权和边权。询问从 \(u\) 到 \(v\)，每条边最多经过两次（即往返两次），经过的点权减边权（点权只算一次）的最大值。题解先考虑从点 \(u\) 开始，进...

树上问题题解动态规划

2020-08-01

0 422

题解「CF204E Little Elephant and Strings」

后缀数组+ST表+分块。合法的子串必须满足至少是k个串的字串。这个要求让我们自然而然想到一道相似的题 P5546 [POI2000]公共串，这道题用后缀数组很容易想到解法。于是开始后缀数组乱搞。先将所有字符串用分隔符隔开连接成一个串。注意，这里的分隔符必须两两不同，否则求出的 \(...

后缀数组字符串题解

2020-08-05

0 470

题解「Luogu4782 【模板】2-SAT 问题」

SAT 是适定性（Satisfiability）问题的简称。一般形式为 k - 适定性问题，简称 k-SAT。而当 \(k>2\) 时该问题为 NP 完全的。所以我们只研究 \(k=2\) 的情况。 ——摘自 OI-Wiki 2-SAT问题大多是固定的模型：给定若干个均有两个元素...

2-SAT 题解图论

2020-08-11

0 424

题解「Luogu3209 [HNOI2010]平面图判定」

首先需要了解平面图的定义：如果图 \(G\) 能画在平面 \(S\) 上，即除顶点处外无边相交，则称 \(G\) 可平面嵌入 \(S\) ， \(G\) 为可平面图或平面图。设 \(G\) 是平面图，由 \(G\) 的边将 \(G\) 所在的平面划分成若干个区域，每个区域称为 \(G\)...

题解 2-SAT 图论

2020-08-19

0 467

题解「Luogu3327 [SDOI2015]约数个数和」

首先有个东西是这题解题的关键： \[{\rm{d}}(ij)=\sum_{x|i}\sum_{y|i}[{\rm{gcd}}(x,y)=1] \] 有位dalao的题解证明了这个式子，可以去看看。然后就可以开始推式子了： \[\sum_{i=1}^n\sum_{j=1}^...

数学题解

2020-08-20

0 437

题解「Luogu1587 [NOI2016]循环之美」

题意求满足 \(1 \leq x \leq n,1 \leq y \leq m\) 的在 \(k\) 进制下能写成纯循环小数的最简分数 \(\frac{x}{y}\) 的个数。题解证明： \[\text{Ans}=\sum_{x=1}^{n}\sum_{y=1}^{m}[x ...

数学题解

2020-08-21

0 430

题解「Luogu6055 [RC-02] GCD」

题目要求： \[\text{Ans}=\sum_{i=1}^N\sum_{j=1}^N\sum_{p=1}^{\lfloor\frac{N}{j}\rfloor}\sum_{q=1}^{\lfloor\frac{N}{j}\rfloor}[{\rm{gcd}}(i,j)=1][{\rm{gc...

题解数学

2020-08-22

0 407

题解「Luogu2839 [国家集训队]middle」

题面给一个序列 \(s\) ，回答 \(Q\) 个这样的询问：\(s\) 的左端点在 \([a,b]\) 中，右端点在 \([c,d]\) 中的子区间的最大中位数。题解首先要知道中位数怎么求：二分出一个 \(mid\) ，判断中位数 \(m\) 与 \(mid\) 的大小关系。将询问...

题解数据结构二分

2020-08-25

0 387

题解「Luogu5221 Product」

题意求这个东西： \[\prod_{i=1}^N\prod_{j=1}^N\frac{{\rm{lcm}}(i,j)}{{\rm{gcd}}(i,j)} \ ({\rm{mod}} \ 104857601) \] 题解根据 \[{\rm{lcm}}(i,j)=\frac{...

题解数学

2020-08-25

0 398