Cur1ed

题解

ac自动机(12) cf(1) KMP&拓展KMP(22) 后缀数组(21) 回文串(2) 图论(9) 字典树(6) 字符串(2) 未归档(87) 计算几何(1) 计算机网络实验(1)

/ 注册

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

画个圈圈诅咒你

有被诅咒到....... 题意主要是画线的这两个条件。题解这个题的关键在于，还记得高中的正弦定理和三角函数的运算。博主早就将知识还给老师了，幸好有学霸旁友指点。推导过程看图本来题解就写到了这里，但是我敲代码的过程中发现我的三角函数也白学了...

2020-08-05

6 688

Game SET

题意一套牌有四种属性，每种属性都有三种特征，shapes (one, two, or three), shape (diamond, squiggle, or oval), shading (solid, striped, or open), color (red, green,...

2020-08-03

1 566

Interesting Computer Game

题意给出n对数，你可以操作n次，每次操作只能在下面三种中选择一种，问最多可以选多少个不同的数字。什么都不做如果a[i]以前没选过，那么可以选择a[i] 如果b[i]以前没选过，那么可以选择b[i] 题解想法...

2020-08-03

4 539

Kabaleo Lite

题意有n道菜，1≤n≤105，a[i]是每道菜可以赚的钱，−109≤ ai ≤109，b[i]是这道菜的个数，1≤bi≤105，你每次只能选从1开始连续的菜，然后问最多有多少顾客，并且顾客最多的前提下赚的钱最多是多少。题解这个题的重点在于会用__int128，我都没...

2020-08-03

8 735

2020牛客暑期多校训练营（第七场）

BDH B. Mask Allocation 题意题目读了半天才读懂.... 有n*m个口罩，把他们装到盒子里，然后必须满足既可以把这些口罩分成n组，一组m个；也可以将它们分成m组，一组n个。要求分的组数最少，并且字典序最大。题解比赛的时候没敢写，没造出来样...

2020-08-02

0 579

Easygoing Single Tune Circulation（后缀自动机+字典树）

题意给定n个字符串 s[i]，再给出m个查询的字符串 t[i]，问 t[i] 是否为某个 s[i] 循环无限次的子串。题解分成两种情况 ① t[i] 比 s[j] 短，这个时候可以用后缀自动机，把每个 s[j] 重复一次，然后放到SAM中，这样直接每次直接查询就好了。...

2020-08-01

1 695

carpet

题意有一个n*m的地毯，aij表示地毯每格的元素，bij表示地毯每格的价格，要求选取一块价格最大值最小的地毯，并且这块地毯无限铺开之后，原地毯是其子矩阵。题解先找到这个矩阵的最小循环节子矩阵，求一下每行的循环节长度用map记录，取出现次数为m并且循环节长度最小的；每列也求一下...

2020-07-29

8 623

2020牛客暑期多校训练营（第六场）

BCEGK B. Binary Vector 题意大概是说有一个A={0,1}，每天可以在An (n维空间) 中生成一个新的二进制向量，n天中生成的向量线性无关的概率是，求。题解由于这N个向量线性无关,则这N个向量张成的空间秩为N,考虑将每次随机的向量加...

2020-07-27

0 625

2020牛客暑期多校训练营（第五场）

DEFI D. Drop Voicing 题意：给你一个数列，你可以进行两种操作。 Drop-2: 将n-1位置的数移到第一个位置，变成 pn−1, p1, p2, …, pn−3, pn−2, p...

2020-07-25

0 565

我不爱她

前几天打牛客的多校，今天写这个题发现是基本一样的题，改成多组输入，map改成unordered_map（不然会t），最后的乘平方改成乘一次就好了，不要取模。先对所有的字符串后缀hash，用unordered_map记录每个hash值（后缀）有多少个一样的。这个地方后缀的 hash 值可以将字...

2020-07-23

2 602