Backl1ght

分类

题解(9)

/ 注册

全部文章（共8篇）

题解 | #进击的图灵机#

进击的图灵机假设执行完内的指令之后位于。然后问题转换一下就是内和点相同的点有多少个。然后由于只有个操作，所以不同的点数至多有个，所以对于每个点可以哈希一下，然后离散化映射成一个数，不同的数至多也只有个。对于数维护一个vector记录所有数的下标，然后再二分就可以求区间内出现了多少次。 #in...

C++ 二分查找

2021-09-20

1 508

题解 | #一个经典概率问题#

一个经典概率问题解法其实已经写在题目里了，分别实现两种方法，然后根据两者不同的特征判断是哪一个方法生成的。 B的生成方法就不说了，L的生成方法由于每条半径生成方法是相同的，所以选哪一条半径其实都一样，不如直接固定选一个半径。然后考虑使用均值判断，由于算出来两者相差还蛮大的，就直接用就行了。 #i...

C++ 概率与统计随机化

2021-09-20

1 524

题解 | #漂亮数#

H. 漂亮数线性筛加打表. 如果处理出以内,每个数是否是漂亮数,然后做个前缀和,就可以回答询问了. 怎么处理呢? 线性筛的过程中标记一下就可以了. #include <bits/stdc++.h> using namespace std; #ifdef BACKLIGHT #inclu...

2021-08-28

1 550

题解 | #加减#

I. 加减可以借助二分做. 易得:经过操作之后,出现次数最多的数一定是原来数组中的数. 数的顺序对于答案没有影响,不妨先排序. 然后就可以枚举原来数组中的数,使用给定操作去取得最优解,然后所有可能中的最大值即为答案. 假设当前枚举到的数为. 贪心地优先取和的差的绝对值小的数是最优解之一. 然后就可...

2021-08-28

7 608

题解 | #零一奇迹#

G. 零一奇迹其实就是个模拟题,怎么过的人这么少啊? 首先可以将整数看成60位2进制数,然后一个位置至多被个长度小于等于60的区间包含. 由此,一次更新顶多修改360个数,直接暴力枚举所有的区间修改就完事了. 初始化类似直接暴力. 一开始为了统计区间内的数的个数还写了平衡树,然后喜提TLE. ...

2021-08-28

2 456

题解 | #数学家的迷题#

数学家的迷题对于操作2，其答案为区间内元素不同质因数的个数。注意到，而内的素数个数约有个。如果使用bitset存储每个元素的质因数，再用线段树维护区间内bitset或和，即可求得区间内元素不同质因数，进一步就可以获取其质因数个数。对于一个数，可以求出其所有质因数，所以建线段树的复杂度为，单点更...

2021-06-26

0 433

题解 | #哲学家的沉思#

哲学家的沉思做法1 考虑离线处理，将所有询问挂到区间左端点上。逆序跑单调栈(递减)，假设现在栈顶元素为。此时，对于询问，答案为单调栈内值属于的元素个数。由于栈顶为，答案为单调栈的某一个后缀。通过二分后缀的起点，就可以以的时间复杂度求解。单调栈部分共，每一个询问，总的时间复杂度为。做法2 （...

2021-06-26

0 564

题解 | #音乐家的曲调#

音乐家的曲调 DP。首先通过双指针可以找到对于每一个，满足条件的左边界。然后令表示将前个元素划分成个不相较的区间，区间长度和的最大值。时间复杂度为。

2021-06-26

0 710