ThinkofBlank

分类

未归档(4) 论文(10) 题单(1) 题解(90)

/ 注册

TA的专栏 8篇文章 0人订阅

ThinkofBlank’s

8篇文章 1209人学习

全部文章（共18篇）

牛客练习赛65 D.最小公倍数题解

一.闲话哎，之前开C的时候，发现有点计算几何的味道，就打算放放，开D，结果发现D是数论，于是就决定搞出来了。然后一直Wa。。。debug了几个小错误后，实在没发现错了。。。结果后面rejudge就过了？？？/xk 二.题解首先，这题几个结论: 1.我们不会选两个相同的数（除了用1来补满和以外） ...

数论优化题解

2020-06-12

6 968

Steps to One 题解

挺简单的一道概率dp+简单数论+简单容斥题目。由于是编译器小白，枚举了n次编译器qwq。。。 c++的同学建议用clang++17那个编译器qwq 一.概率dp+简单数论部分比较容易想到的，我们设表示当前gcd为i，期望步后到达1 初始化然后，我们来推下转移方程: 明显的有，那么，我们只要...

数论题解动态规划研究

2020-06-08

4 945

C. Pinch Pinch Pinch 题解

贴一波谷歌翻译~ 注意，这题中每个方便面的分发是唯一的由于本人英语和语文辣鸡，所以完美将此题看错。。。出题人告诉我们：每次我们将一个大小为N的方便面分块时，我们要尽量使得所有的块小，而不是任意分成等差数列。由于我看错了题，所以我们先来讲讲分成任意等差数列怎么做。（大雾）我们设dp[i]表...

数论优化题解

2020-06-04

2 888

小AA的数列题解

又是求异或和的和的常见套路——按位计算，即计算二进制中每一位的贡献。需要注意的是，题目要求的不仅要区间长度在[L,R],而且区间长度必须是偶数（因为这个debug了好久qwq）我们先来简化下题目。我们假设只考虑一个二进制位x，并且区间长度也可以为奇数，那么这个怎么做呢？很简单，我们为了方便处...

数论题解

2020-05-22

1 1092

牛牛的最大公约数题解（强化版）

这道题，常规做法的突破点在于:（R-L<=1e5）这个条件那么，如果我们把这个条件去掉，询问数据为：1000000000 1 1 1000000000该怎么做呢？一开始，我们先按套路，将L-R取最大公约数为k，化成到取最大公约数为1 然后开始做题。首先，我们先来将答案表达式划出来： (...

数论题解研究

2020-05-08

3 1004

数列互质题解

该题之理论题解，代码打炸了(wa了)，就不放了qwq后来debug出来了，统计排序后第一个询问的答案时，我把1写成i了qwq 首先，我们明显的，我们需要使用莫队算法来维护每个颜色的出现次数，设c[i]表示区间中i出现了多少次，同时我们再维护一个数组d[i]表示出现次数为i的有几个颜色。这两个数组在莫...

数论研究题解

2020-05-06

3 1048

牛客算法周周练5 B. 求幂题解

这题比较难，于是就来写下题解吧公式警告题目意思非常简明，就是让你求成立的四元组的个数，考虑如何解决一开始，我的想法是两边同时取对化简，但是搞了很久，发现复杂度至少要n^2才可做，于是放弃了这个做法。我们现在来考虑下其他方法。。。首先，我们将a和c分解质因数那么一定有: 又因为,那么分别...

数论优化题解

2020-05-06

8 837

Symmetric Matrix 题解

太菜了，直接上OEIS 然后发现递推式: 于是。。。完了/x #include<bits/stdc++.h> using namespace std; const int N=1e5+1; int n,m; int a[N]; int main(){ while(~scanf(...

题解数论

2020-04-28

2 1053

子序列题解

update:新方法，树状数组优化dp，复杂度一道很简单的dp+数论题。。。我们设dp[i]表示以i结尾的子序列中成立的方案数那么，就有转移：答案就很显然了: 于是这题就基本做完了，不过，麻烦的是，你需要做这个式子如果我们直接算，最大的情况就可能搞出个,然后爆炸(当然，你要打个高精也没...

数论题解动态规划

2020-04-23

5 1149

牛客挑战赛39 E 牛牛与序列题解

一.闲谈这次比赛真惨，B题我的数据分块被卡了，只有75分qwq，C题打分块和线段树都被卡了，我好难啊。。。然后，看了下D题，emmm算了下一题，一看E题，哇数论题，于是操起草稿纸开干了。。。二.题解题目叫你求长度为n的序列，且数列元素为[1,k]的整数，且同时存在严格上升和严格下降的两个位置...

数论题解

2020-04-18

2 602