Kur1su

题解

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

/ 注册

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

2021牛客寒假算法基础集训营6 E 网格(dp)

Description 一句话题意：每个网格点可以选择上下里面选一个方向，左右里面选一个方向，相邻的位于所选方向上的网格有的贡献。 Solution 比赛时一眼就看出是 , 但是没有仔细思考细节。今天重新思考后发现其实不难。对于网格点，其实行列的贡献是相互独立的，即行与列的答案hubuy并且每一...

2021-03-01

2 661

2021牛客寒假算法基础集训营5 石子游戏（差分、思维）

Description Solution 前置知识: 差分不懂差分的同学可以百度先进行学习。学会差分能够实现题目中的相邻个石子堆数目加，有助于我们进一步处理。首先思考，对于每一个石子数量，如果当前的数量不是堆石头里面最大值，那么它一定要进行差分操作，差分到变成但是考虑到这样后...

2021-02-23

3 679

2021牛客寒假算法基础集训营5 比武招亲（上）（组合数学）

Description Solution 本人不擅长组合数学，因此只能打表找规律 map<vector<int>, int> mp; void dfs(int now, vector<int> v) { if (now == m) { sort(v...

2021-02-23

8 752

2021牛客寒假算法基础集训营4 G. 九峰与蛇形填数(线段树)

Description Solution 显然对于每个方格上的数字都可能被多次覆盖，但是真正起作用的是最后一次覆盖的时候。考虑一个问题：如果我知道某个点最后一次覆盖是第几次操作，那么意味着我知道最后一次覆盖的方阵初始点与边长，能不能推算当前点的值呢?显然是可以的——这个自己手推一下吧, 应该几分...

2021-02-20

5 709

2021牛客寒假算法基础集训营4 J. 邬澄瑶的公约数(数学)

Description 一句话题意：给定个数字 (), 个数字 ()求 Solution 我们先考虑下子问题：求 , 无非就是质因数分解，然后找到大家都有的因子, 以及这个因子出现的最小次数。举个例子： , 共同出现的质因子是 , 分别出现了次，那么最小次数就是 , 因此回到本...

2021-02-20

3 639

2021牛客寒假算法基础集训营3 E. 买礼物(线段树、链表思想)

Description Solution 一开始的思路是用把2的查询是否有相同转换成查询里有多少个不同的数字，用带修莫队/树套树等奇奇怪怪的做法。然而，的数据范围支撑不了上述和的做法。于是考虑能否用的复杂度完成本题。注意到我们可以用链表记录每一个数字上次出现和下次出现的下...

2021-02-05

14 692

2021牛客寒假算法基础集训营2 F. 牛牛与交换排序(思维题、deque)

Description Solution 数据强度可能不够大，不能保证我的写法是完全正确，不过主要是学会用模拟实现翻转。对于本题，我们需要找到一个符合条件的，随后利用实现的翻转。找到合适的，由限制条件得到启发，最小的不在自己位置的数字一定是最先处理的。不妨找到第一个不在自...

2021-02-04

5 624

2021牛客寒假算法基础集训营2 I 牛牛的“质因数”(数学) 来自专栏

Description 牛牛定义了一个函数F(x)，它表示将x做质因数分解后得到的数字从小到大升序排列，然后将其“拼接”成一个大整数。例如1500=22355*5,F(1500)=223555。牛牛现在想要知道的值。 Solution , 考虑朴素做法：筛出的素数，对于的每一个数字进行质因...

2021-02-03

13 928

2021牛客寒假算法基础集训营1 A. 串(数位dp)

Description 求长度不超过，且包含子序列""的、只由小写字母构成的字符串有多少个？ Solution 不妨令表示枚举到第个位置的时候状态为其中，状态是当前是否已满足条件——已出现""的子序列而状态是当前是否已经出现了字母发现总共的状态只有个，记忆化搜索一...

2021-02-01

10 788

【每日一题】New Year Tree 题解(树链剖分线段树状压) 来自专栏

Description 给一棵树，根为1，每个节点有一种颜色，有两种操作：将该节点x及其子树的颜色都变为y 查询节点x及其子树有多少种颜色 Solution 颜色的范围为 (), 不妨用二进制上的每一位去代表每一种颜色是否存在那么检查有多少种颜色只需要统计二进制的1个数，用函数即可由于是树...

2021-01-17

3 752