牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共10篇）

模拟11 题解

A. string 类似 HEOI2016排序。排序这道题因为只询问单点最终答案，二分答案，将小于和大于等于答案的数分别设为0 1，用线段树维护0 1的排序即可。算法一：本题中的1～n变成了0～25（即a～z），单点询问变成了全体询问。仿照排序那道题的做法，线段树优...

线段树 dp trie树组合计数

2019-08-02

0 442

模拟31 题解

A. math 考试时打的错解，取每个$a_i$与k的gcd，分别做背包由0直到k。但是复杂度有点问题，于是做了个筛。 $O(k sqrt(k))$一定没有问题，在不构造特殊数据下很优秀。考后突然被自己一个简单的数据hack掉了。 2 6...

dp trie树单调栈

2019-08-25

0 360

模拟46 题解

A. Set 原序列中，一定存在一段连续的区间，保证区间和整除n。不妨将区间和表示为前缀和的形式，如果存在任意两个相同的取值，那么该区间合法。而前缀和总共有n+1个，不同的取值最多有n个，固一定存在至少一个合法区间。 B. Read 题意其实是问序列中是否存在大于...

trie树

2019-09-19

0 450

模拟68 题解

考试过程大概是：上来看T1，看懂了题但是丝毫没有思路，甚至没有想到第一步贪心，心态稍崩。接着看T2，发现似乎可以直接上主席树上树，然后想了想复杂度，直接找前趋后继，复杂度似乎很正确。 T3只会暴力。然后就回去把T2切了，一遍过大样例自信不对拍。结果忘了在线这回事，一个小时之后才发现...

trie树主席树贪心位运算二分答案

2019-10-11

0 401

省选模拟18 题解

A. 编码一眼原题，是一道数据结构（？）优化2-SAT建图的题。 2-SAT还是比较容易看出来的，每一个串只有$0/1$两种取值，一个串对另一个串起到了限制的作用。于是暴力的做法就是先将所有的串按照长度排序，由小到大分别将两个副本插入字典树。对字典树上每个节点维护一个vector，表示...

单调指针 Hash dp 高斯消元二分答案折半搜索 2sat trie树

2020-02-05

0 387

省选模拟32 题解

A. 送你一道签到题这个函数显然是个积性函数。刚开始的想法是可以直接考虑分开每个质因子，然后乘一块的贡献显然是正确的。后来一想这个玩意实际上就是 $id^k$ 点积上 $d(x)$ 的 $m$ 次卷积，所以肯定是积性的。然后看这个数据范围，显然要搞个 min25筛。然后一想，这...

容斥 trie树 min25筛 dp 数学

2020-02-26

0 295

省选模拟45 题解

A. matrix 当然考虑左端点为 $l$的所有矩形的贡献。通过一个 trie，对 trie 上每个节点开一个 set，来找到每个串 $s$ 存在的位置。那么可以把当前答案的形式化成 $ans=\sum \limits_{s} val_s$ ，其中 $val_s$ 表示这个串出现的区间数...

多项式 trie树 set dp 启发式合并扫描线线段树

2020-03-14

0 467

省选模拟71 题解

A. 王子这个数据范围加上很奇怪的限制，其实就应该是网络流了。可以首先钦定选择了 $A$ 类，然后将其中的一些替换为 $B$ 类。其实与志愿者招募那个题挺像的，只不过原来是对于每个点选择 $[l,r]$ 个区间。但是现在的问题是要求每个区间选择 $[l,r]$ 个数点。其实并不难...

网络流分块 trie树 AC自动机线段树 set

2020-04-15

0 477

省选模拟96 题解

A. 多边形因为本题保证了 \(n\) 不为偶数，所以 \(n\) 没有 \(\frac{n}{2}\) 这个循环节。然后考虑 \(\frac{n}{3}\) 这个循环节，如果能形成锐角一定有 \(m=3\)。如果存在更小的循环节，那么一定不存在锐角了。所以尽量特殊处理一下 \(m=3\) ...

多项式 trie树

2020-05-14

0 372

noi前第十二场题解

A. string 对于这类字符串匹配题，有个套路是直接用 \(FFT\) 优化。然后发现这题字符集很小，所以枚举一个字符，将匹配串中的这个字符设为 \(1\)，模式串中的非这个字符设为 \(1\)。然后用一些技巧优化一下，就可以用 \(|\sum|+1\) 次长度为 \(n\) 的 \(DF...

平衡树多项式 trie树 dp 字符串

2020-07-25

0 553