Kur1su

题解

paper(8) 机器学习(2) 生活记录(6) 读书笔记(1)

/ 注册

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

牛客IOI周赛28-普及组 ABC题解

A. String Game Solution 签到题，做次，将的第一个字符放在的后面，并将第一个字符删除。注意，但是每做次后字符串会变成初始的样子，所以对字符串长度取模随后用双端队列模拟即可。 Code https://ac.nowcoder.com/acm/contest/vi...

2021-08-29

1 787

2021牛客暑期多校训练营1 H. Hash Function（数论，FFT/NTT卷积）来自专栏

Description 给出一个序列，找到最小的正整数，使得能够让序列在函数的作用后互不相同。 Solution 不妨思考什么时候会存在两个数字满足：设，由同余的性质，得到，即，因此满足于是我们知道，的取值不能够是的因子。那么只需要找到序列中所有的即可，显而易见的就是借...

2021-08-23

4 624

2021CCPC华为云挑战赛 CDN流量调度问题（数论分块，dp）来自专栏

Desciption 给出个任务，每个任务需要花费，一开始有个资源，可以最多为它分配个，总共可以多分配个，最后总的花费是。 Solution 补题的时候发现网上没人写题解，还是写一写希望能帮到和我一样的小白。显然是经典的数论分块，对于每个最多有种取值，这个可以预处理出...

2021-08-22

2 1022

2021牛客暑期多校训练营10 F. Train Wreck(思维题) 来自专栏

Description 给出一个出入栈顺序和一堆数字，构造一个序列满足任意时刻入栈时序列都是唯一的。 Solution Code https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48581485

2021-08-16

6 803

2021牛客暑期多校训练营9 E. Eyjafjalla (划分树，树上倍增) 来自专栏

Description 给出一棵树，个查询，每次查询给出代表病毒在点爆发，在的温度可以传播根节点为，保证离根节点越近，温度越高，根节点温度最高。 Solution 我们知道，对于一个初始节点，它的子树必定温度小于它本身，所以设当前温度为 , 中的这一部分可以直接查询子树里有多少...

2021-08-15

6 661

2021牛客暑期多校训练营7 F.xay loves trees(线段树、树上滑窗) 来自专栏

Description 给两棵树，选取一系列编号的节点，需要满足在树1中节点联通，且互为祖先关系在树2中节点互不为祖先关系 Solution 看了题解，不会他讲的主席树做法，还是感觉树上滑窗的思路好理解。但是很多人说树上滑窗可能会被卡，不是很懂。。。不过仔细一想，如果树上滑窗能被卡，这题应该...

2021-08-13

3 830

HDU多校8 1004 Counting Stars（线段树）来自专栏

Description 数据结构区间减去区间加上区间求和 Solution 难度比较适中的一道题，注意到操作1最多减去次，个数字需要的操作次数数量级为，考虑用线段树维护区间，可以完成操作1，最终用一个代表这个区别是不是全为，因为就不需要再操作了。对于操作2，每次只是对...

2021-08-12

2 538

2021牛客暑期多校训练营6 H. Hopping Rabbit(扫描线) 来自专栏

Description 一只兔子在草原上跳来跳去,草原上有猎人布下的n个陷阱.现在将草原看作一个二维直角坐标系,兔子看作一个点,陷阱看作一个矩阵(且它的边必定与x轴或y轴平行),兔子每次会沿x轴或y轴方向移动距离d(即如果兔子在,它跳一次后在四个点中的一个.问在坐标系中是否存在一个点,使兔子无论怎么...

2021-08-10

5 945

2021牛客暑期多校训练营4 B.Sample Game(期望dp) 来自专栏

Description 给出一个随机生成器，每次生成，当且仅当生成的为不小于前面生成的所有值才能继续生成，否则结束。求生成数字的个数平方的期望值。 Solution Code https://ac.nowcoder.com/acm/contest/view-submission?submi...

2021-08-08

5 546

sosdp题集

1. 165E - Compatible Numbers Compatible Numbers 由于 , 那么显然找的子集必然满足条件。不妨令表示的子集里存在于所给序列中的某一个，枚举子集即可。 /* * @Author: Kurisu */ #include<bits/std...

2021-08-06

2 763