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

发布(38) 刷题

2020-10-24 23:30

C++

用平衡树模拟这个过程，每个点维护它代表的小球的颜色和个数。 操作一新建一个颜色为 x，个数为 y 的结点。 操作二是基本的平衡树删除操作。 操作三，把第 u 个桶的平衡树打上翻转标记，再合并到第 v 个桶的平衡树上。 Code： #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #define Rint register int #define INF 0x3f3f3f3f using names...

0 点赞评论收藏

转发

2020-10-21 11:38

已编辑

C++

bitset大法吼啊 不难发现，如果询问的数的某一位为1，那么要找的数中的这一位也必须为1。所以要找的数中，每一个询问数中这一位为1的位都为1。 每一位开一个bitset，存有哪些数这一位为1。举个例子，对于样例 3 7 ，每一位的bitset应该长这样（最低位是第0位）： bit[0]:11 bit[1]:11 bit[2]:01 bit[3]:00 询问时，将询问数中为1的位的bitset与起来，得到的bitset中存的数，满足这些位上均为1。那么只需要判断得到的bitset中是否为空即可。 例如，询问 4 ，4 的二进制表达是 100 ，取第2位的bitset，这个bitset的第2位...

0 点赞评论收藏

转发

2020-10-21 07:32

已编辑

C++

<span>测试「20201020测试总结」</span>

分没了，rating也没留着。 T1 只需要开方5次，所以可以找到一个分界点，使得它恰好只能开方5次。通过二分，可以算出这个分界点是 \(2^{32}\) 。 考试时前1h看错了题，以为是开6次，结果找出了一个很大的数做分界点。最后30min发现题读错了，慌慌张张地重新找了分界点，结果找成了 \(2^{32}-1\) …… \(\text{Code}:\) #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include &l...

0 点赞评论收藏

转发

2020-10-21 07:32

已编辑

C++

<span>记录「十月做题记录」</span>

转载注明地址：https://www.cnblogs.com/syc233/p/13771723.html 前言 没有前言 其实是咕咕咕了 。 P6835 [Cnoi2020]线形生物 题面 题解 月赛时没做出来的题，下来看了题解才会。 令从 \(x\) 走到 \(y\) 的期望步数为 \(E_{x\to y}\) ，\(x\) 的返祖边集合为 \(S_x\) ，\(S_x\) 的大小为 \(deg_x\) ，则： \[\begin{aligned} E_{x\to x+1}&=\frac{1}{deg_x+1}\times 1+\frac{1}{deg_...

0 点赞评论收藏

转发

2020-10-21 07:32

已编辑

C++

<span>测试「20201019测试总结」</span>

题蛮正常的，拿了个rk3，感觉还行。 T1 令所有数位上的数的和为 \(sum\) ，不难发现要求的就是 \(sum\times \frac{10^n-1}{9}\)，最小的质因数要么在 \(sum\) 中，要么在 \(\frac{10^n-1}{9}\) 中。在 \(sum\) 中的最小质因数很好求出来，而 \(\frac{10^n-1}{9}\) 的质因数不好求出，但是由于它可能成为答案的质因数只能比 \(sum\) 的最小质因数小，所以可以枚举质数 \(p\) ，判断 \(\frac{10^n-1}{9} \ {\rm mod} \ p\) 是否等于零即可。 判断的时候转换一下...

0 点赞评论收藏

转发

2020-10-21 07:33

已编辑

C++

<span>测试「20201015测试总结」</span>

关于这套题： 那么***题是怎么回事呢，小编也不知道。 那么现在就来看看这套题有多***。 T1 这道题是本次考试中最正常的一道。 转换一下思路，将位置 \(i\) 的一个在 \(t\) 时刻出现的物品看做是在 \(t-i\) 时刻在位置 \(0\) 出现。 按在位置 \(0\) 的出现时刻依次考虑所有物品，选出当前已花费时间最少的小车去运送这个物品。 用一个数据结构支持查询最小元素，插入删除元素。 然而这道题题面写的数据范围是： 也就是说读入量完全可以达到 \(10^9\) 的级别。然而出题人为了使标程通过，数据最大只有1e7…… \(\text{Code...

0 点赞评论收藏

转发

2020-10-21 07:33

已编辑

C++

<span>测试「20201013测试总结」</span>

连着两次考试小于机房平均分了/kk，不努点力看来是不行了。 T1 将图分成一个团和一个独立集的方案数，正解是爆搜/fad。 然而把图建出来反而不好搜，于是不建图，只枚举每个点在团中还是在独立集中。这样看起来是 \(O(2^N)\) ，但实际上可以剪枝剪掉大部分不合法方案。 考场上时间没分配好，打了2h暴力无果。 考后bitset爆艹标算 \(\text{Code}:\) #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #i...

0 点赞评论收藏

转发

2020-10-21 07:33

已编辑

C++

<span>题解「LOJ2348 「JOI 2018 Final」美术展览」</span>

转载注明来源：https://www.cnblogs.com/syc233/p/13803903.html 题面 题意 有 \(n\) 个物品，物品 \(i\) 有尺寸 \(A_i\) 和价值 \(B_i\) 。选择若干个物品，使得选择的物品的总价值 \(S\) 减尺寸的极差 \(A_{max}-A_{min}\) 最大。 题解 发现若固定 \(A_{min}\) 和 \(A_{max}\) ，那么一定将尺寸在 \([A_{min},A_{max}]\) 中的物品选完，那么 \(S\) 的值就很好求得。将物品按 \(A\) 升序排序，那么选择的物品一定是一段区间。 同时固定两个...

0 点赞评论收藏

转发

2020-10-21 07:33

已编辑

C++

<span>测试「20201012测试总结」</span>

T1T2分往脸上送，T3直接劝退。 T1 数三角形。 先固定一条直线，求它能与其他直线组成多少个三角形。这个很好求。 令 \(S\) 为所有直线的集合，\(k_i\) 表示直线 \(i\) 的斜率，\(c_k\) 表示斜率为 \(k\) 的直线条数，则直线 \(l\) 能与其他直线组成的三角形个数即为： \[\begin{aligned} \frac{1}{2}\sum_{i\in S,k_i\not =k_l}c_{k_i}\times (n-c_{k_l}-c_{k_i})&=\frac{1}{2}\sum_{i\in S,k_i\not =k_l}(c_{k_...

0 点赞评论收藏

转发

2020-10-21 07:33

已编辑

C++

<span>游记「CSP-S2020游记」</span>

Day -1 上午打了两道题，然后一直看初赛看了一天。 Day 1 考前 上午9:00进了考场。 发现考场是小学教室，桌子很矮，腿伸不开，很难受/kk。 考试 结果考室里没有钟，监考员又不让戴手表，于是只能估摸着时间做题。被迫成为时间管理带师 题感觉比去年要简单。 单选题很快做完了，没有什么特别恶心的题。 阅读程序T1和T2难度一般，就是T2的分析时间复杂度需要花一点时间分析清楚，最后15min重新分析了一遍挽救了5分/fad 。 然后阅读程序T3是什么毒瘤，只有第5小题找出规律选了个比较正确的答案，其他连蒙带猜选了几个答案跑路。 补全程序T1没什么问题，T2只要理解了...

0 点赞评论收藏

转发

2020-10-21 07:33

已编辑

C++

<span>题解「SPOJ8093 JZPGYZ - Sevenk Love Oimaster」</span>

转载注明来源：https://www.cnblogs.com/syc233/p/13784426.html 广义SAM+区间数颜色。 几篇写广义SAM的题解似乎都没写对啊/fad，都是插入新串时直接将 \(las\) 设为 \(1\) 的，在这篇博客中提到这样建出来的广义SAM是有问题的。 所以这里再写一篇题解来讲一下如何正确使用广义SAM解决这道题（当然也不能保证完全正确，毕竟我也才学广义SAM）。 对所有模板串建立一个广义SAM，每个结点记录它存储的串的信息的编号。因为在广义SAM中，一个结点可能保存了多个模式串的状态，所以需要每个点开一个vector来记录，而不是单纯的使...

0 点赞评论收藏

转发

2020-10-21 07:33

已编辑

C++

<span>总结「二次剩余」</span>

转载注明来源：https://www.cnblogs.com/syc233/p/13741831.html 二次剩余，之前从数竞同学那听到过这个东西，觉得在OI中没啥用。直到今天T1考了二次剩余，我才流下了没有数理基础的眼泪。 二次剩余，其实就是模意义下开根。 给定常数 \(n\) ，解同余方程： \[x^2 \equiv n \ ({\rm{mod}} \ p) \] 当存在 \(x\) 满足上式时，则 \(n\) 是模 \(p\) 的二次剩余。 否则 \(n\) 是模 \(p\) 的二次非剩余。 为了方便，下面的同余式均省略 \(({\rm{mod}} \ p...

0 点赞评论收藏

转发

2020-10-21 07:34

已编辑

C++

<span>总结「李超线段树」</span>

转载注明来源：https://www.cnblogs.com/syc233/p/13722356.html 最近复习了李超线段树，发现网上不同人的写法有较大不同，所以写这篇博客总结一下自己的写法。 李超线段树是线段树的一个变种，支持在平面直角坐标系中动态插入线段，查询一条竖线与所有线段的交点纵坐标的最大值或最小值。 引入 P4097 [HEOI2013]Segment 题面 题意 要求在平面直角坐标系下维护两个操作： 在平面上加入一条线段。记第 \(i\) 条被插入的线段的标号为 \(i\)。 给定一个数 \(k\)，询问与直线 \(l:x=k\) 相交的线段...

0 点赞评论收藏

转发

2020-10-21 07:34

已编辑

C++

<span>题解「Luogu3970 [TJOI2014]上升子序列」</span>

转载注明来源：https://www.cnblogs.com/syc233/p/13693730.html 先不考虑序列长度至少为 \(2\) 的限制和去重，那么这道题就是一个简单的DP： 令 \(f_i\) 表示以 \(a_i\) 结尾的上升子序列个数，那么很容易写出转移方程： \[f_i=\sum_{j=1}^{i-1}f_j[a_j<a_i] \] 直接转移 \(O(n^2)\) ，可以用树状数组优化到 \(O(n \ {\rm{\log}} \ n)\) 。 考虑如何去重。发现若对于当前数 \(a_i\) ，存在 \(a_j=a_i,1\leq j<i...

0 点赞评论收藏

转发

2020-10-21 07:34

已编辑

C++

<span>题解「Luogu1099 树网的核」</span>

转载注明来源：https://www.cnblogs.com/syc233/p/13693027.html 树的直径+尺取法。 题意 给定一棵带边权无根树，在其直径上求出一段长度不超过 \(s\) 的路径 \(F\) ，使得离路径距离最远的点到路径的距离最短。 题解 首先，在 \(s\) 的限制下，\(F\) 应尽量长。这个画下图就不难明白。 先求出直径，令直径的两端点分别为 \(x,y\) 。 定义一个关于直径上点 \(u\) 的函数 \(dis(u)\) ，表示除直径上的点到 \(u\) 的最远距离。那么就有一个结论： 对于任意一个直径上的点 \(u\) ，有 ...

0 点赞评论收藏

转发

工具箱

TA的圈子

TA的笔记

牛客网
牛客企业服务