GoPoux4 - 个人主页动态 - 牛客网

发布(38) 评论刷题

2020-10-21 07:38

已编辑

四川省绵阳中学 C++

<span>题解「Luogu1587 [NOI2016]循环之美」</span>

题意 求满足 \(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 \bot y][y \bot k] \] 首先要知道， \(k\) 进制下 \(\frac{x}{y}\) 小数点右移一位等于 \(\frac{x}{y} \times k\) 。 假设 \(\frac{x}{y}\) 小数部分的循环节长度为 \(l\) ，由于纯循环小数的特殊性质有： ...

0 点赞评论收藏

分享

2020-10-21 07:38

已编辑

四川省绵阳中学 C++

<span>题解「Luogu3327 [SDOI2015]约数个数和」</span>

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

0 点赞评论收藏

分享

2020-10-21 07:38

已编辑

四川省绵阳中学 C++

<span>题解「Luogu3209 [HNOI2010]平面图判定」</span>

首先需要了解平面图的定义： 如果图 \(G\) 能画在平面 \(S\) 上，即 除顶点处外无边相交 ，则称 \(G\) 可平面嵌入 \(S\) ， \(G\) 为可平面图或平面图。 设 \(G\) 是平面图，由 \(G\) 的边将 \(G\) 所在的平面划分成若干个区域，每个区域称为 \(G\) 的一个 面 ，其中面积无限的面称为无限面或外部面，面积有限的称为有限面或内部面。包围每个面的所有边组成的回路称为该面的 边界 ，边界的长度称为该面的 次数 。 为了强调平面图的面，用三元组表示一个平面图 \(G=(V,E,F)\) ，其中 \(F\) 表示平面图 \(G\) 中面的个数。 ...

0 点赞评论收藏

分享

2020-10-21 07:38

已编辑

四川省绵阳中学 C++

<span>题解「Luogu4782 【模板】2-SAT 问题」</span>

SAT 是适定性（Satisfiability）问题的简称。一般形式为 k - 适定性问题，简称 k-SAT。而当 \(k>2\) 时该问题为 NP 完全的。所以我们只研究 \(k=2\) 的情况。 ——摘自 OI-Wiki 2-SAT问题大多是固定的模型： 给定若干个均有两个元素的集合，为了方便，我们称集合 \(i\) 中一个元素为 \(A_i\) ，另一个元素为 \(A_i'\) 。现在给出若干限制条件，如选择 \(A_i\) 就不能选择 \(A_j\) ，选择 \(A_i\) 就必须选择 \(A_j\) 等（其中 \(i \not= j\) ）。询问是否存在一种方案，能...

0 点赞评论收藏

分享

2020-10-21 07:38

已编辑

四川省绵阳中学 C++

<span>总结「二项式反演」</span>

转载注明来源：https://www.cnblogs.com/syc233/p/13455373.html 二项式反演 ~ Inversion of the Binomial 前置知识 容斥原理 众所周知： \[\big | \bigcup_{i=1}^n A_i \big |=\sum_i \big|A_i \big|- \sum_{i<j}\big|A_i \cap A_j\big|+\sum_{i<j<k}\big|A_i\cap A_j \cap A_k\big|- \cdots+(-1)^{n-1} \sum_{a_i<a_{i+1}} \b...

0 点赞评论收藏

分享

2020-10-21 07:38

已编辑

四川省绵阳中学 C++

<span>题解「CF204E Little Elephant and Strings」</span>

后缀数组+ST表+分块。 合法的子串必须满足至少是k个串的字串。这个要求让我们自然而然想到一道相似的题 P5546 [POI2000]公共串 ，这道题用后缀数组很容易想到解法。 于是开始后缀数组乱搞。 先将所有字符串用分隔符隔开连接成一个串。注意，这里的分隔符必须两两不同，否则求出的 \(height\) 数组将会不正确。 在所得串上跑一遍后缀排序，得到 \(height\) 数组。 然后我们使用双指针在 \(height\) 数组上来枚举合法的区间，左右端点的扩展类似于莫队，当区间内出现了 \(K\) 个原串的字串时，此区间合法。 用ST表求出区间内 \(height\) 的...

0 点赞评论收藏

分享

2020-10-21 07:39

已编辑

四川省绵阳中学 C++

<span>题解「CF1000G Two-Paths」</span>

考试做到了类似的一道题 LOJ#6699，题解是换根DP。但是我不会换根，所以用倍增过了这道题qwq。 题意 给定一棵树，有点权和边权。询问从 \(u\) 到 \(v\)，每条边最多经过两次（即往返两次），经过的点权减边权（点权只算一次）的最大值。 题解 先考虑从点 \(u\) 开始，进入它的子树再返回所能得到的最大价值。不难想出如下转移方程： \[f(u)=a_u+\sum_{v \in son_u} {\rm{max}}\{0,f(v)-w(u,v)-w(v,u)\} \] 跑一遍树形DP将其计算出来。 然后考虑如何倍增。 记录 $ p(u,i) $ 表示从 \...

0 点赞评论收藏

分享

2020-10-21 07:39

已编辑

四川省绵阳中学 C++

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

校内测试考了这道题，当时按照题目背景瞎搞了搞，把样例水过了，结果爆零/kk 开始还以为正解要从题目背景中推出来，搞了一个多小时。考完发现背景和题目没什么关系啊！再也不看题目背景了 首先题面用粗体强调了：\(e_1\) 与 \(e_2\) 互素。也就是说,有整数 \(s,t\)，满足： \[s*e_1+t*e_2= {\rm{gcd}}(e_1,e_2)=1 \] 突破口一定是这个式子。 再看题目中 \(m\) 是以 \(m^{e_1},m^{e_2}\) 出现的，上面的那个式子可能要放到指数上。 这个 \("1"\) 就很巧妙啊，可以代换到很多地方，...

0 点赞评论收藏

分享

关注他的用户也关注了：

牛客网
牛客企业服务