ThinkofBlank

题解

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

/ 注册

全部文章 / 题解（共12篇）

Steps to One 题解

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

数论题解动态规划研究

2020-06-08

4 947

表达式计算4 题解

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

题解研究

2020-05-19

2 769

简单瞎搞题题解

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

题解优化研究

2020-05-19

2 1258

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

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

数论题解研究

2020-05-08

3 1011

数列互质题解

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

数论研究题解

2020-05-06

3 1055

边的染色题解

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

图论题解研究

2020-04-22

8 1080

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 743

Rabbit的字符串题解

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

优化题解研究

2020-04-17

2 753

题解 P4980 【【模板】Polya定理】

【模板】Polya定理题解提供一个新算法。。。首先,我们来分析一下题目: 给一个有n个点的环图n种颜色，问本质不同的方案数那么，很明显的，这是一个polya定理（废话，题目名说明了一切）我们先来看看这道题的“操作”，很明显的操作就是只有一个——平移（有人说旋转，但我个人更喜欢看成平移。。。...

数论优化研究

2019-09-23

1 626

题解 P3871 【[TJOI2010]中位数】

看到此题，顿时兴奋了，因为，我以前yy出了一种排序，叫做二分链表插入排序。详细板子代码见博客结果因为vector的insert太慢而被我GG了跑【模板】快速排序然后，看到此题，找中位数嘛，肯定是要在排好序的数列里面选出嘛。。。支持添加数字，嘛，二分一下就好了啊...

题解研究排序

2019-01-13

0 630