ThinkofBlank

分类

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

/ 注册

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

ThinkofBlank’s

8篇文章 1209人学习

全部文章（共21篇）

Steps to One 题解

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

数论题解动态规划研究

2020-06-08

4 945

基于字典树实现的O(n)排序来自专栏

我们用字典树，从高位到低位进行排序，使用中有类似于基排的思路。残留问题在于，空间方面，需要我们使用vector或类似的动态扩充的来做。不过，不想去想了，先给个代码： #include<bits/stdc++.h> using namespace std; const int N=1e5...

研究

2020-05-20

1 698

关于无向图缩点

把之前的补过来/xk 最近,做了好多图论,其中大部分都跟tarjan有关,而又有好多无向图。。。orz 我们都知道,tarjan会把能互达的若干点合并为一个点,然而,在无向图中,所有点都可互达(图联通),故,整个图就会缩成一个点...然鹅,我们把图画出来,又是另外的样子...明明就只有一个环,却把所...

理解图论研究

2020-05-19

0 1620

表达式计算4 题解

嗯。。。表达式计算的又一道类模板做这类题，其实就相当于在搞一个大模拟的题目。我们需要注意的是：因为有多余的括号出现，所以我们最好在一开始把多余的括号去掉，防止中途计算出现问题。其次，就是需要注意计算的顺序，对于此题，我们应该先算括号，再算乘方，然后按出现顺序算乘除，最后再按出现顺序算加减。我...

题解研究

2020-05-19

2 763

简单瞎搞题题解

一.闲话做题历程：点开题目->发现做过->点击提交->AC (/x) 二.题解明显的一道bitset的题目/x bitset是个高级的黑科技，支持各种操作，其中最有用处的，就是bitset支持位运算。我曾经尝试模拟了一下，貌似挺简单的，就是开个int数组，值就是当前状态状压后...

题解优化研究

2020-05-19

2 1256

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

这道题，常规做法的突破点在于:（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

边的染色题解

一.闲话今天这题着实有点难想啊。。。（也许我太菜了?qwq）字数警告二.题解首先，我们先考虑答案为0的情况——存在一个所以边的边权都确定的环，其中的边权异或和为1 考虑到做这个，边权未定的边并无任何影响，所以，我们先把这些边放到一边，先把边权确定的边全部连上，然后就开始做这道题了。首先，我...

图论题解研究

2020-04-22

8 1075

JOISC 2019 Day1 B 聚会题解

这道题莫名眼熟，于是马上猜到了结论：对于一棵树中，要求到三个点x,y,z总距离最小的点，那么，这个点一定是 lca(x,y),lca(x,z),lca(y,z)这三个点中的一个（一开始我还算了lca(x,y,z),后来发现好像不用。。。）所以，我们可以打个lca，每次再比较下到哪个点距离最小即可...

题解研究

2020-04-19

2 736

Rabbit的字符串题解

题目大意：给你一个串，问你这个串现在的顺序是不是不是最小表示法的串做法：一开始打算暴力，但是仔细想想，发现，暴力很可能卡成,导致凉凉。【比如给一个长度为n的串里面的每个字母都一样】一般来说，这道题应该属于字符串类型，需要使用字符串算法。但是！作为一个菜鸡，怎么会打字符串算法呢？/x所以，这里...

优化题解研究

2020-04-17

2 745