四糸智乃

分类

算法(12) 题解(25)

/ 注册

TA的专栏 0篇文章 0人订阅

算法小入门

0篇文章 0人学习

全部文章（共35篇）

题解 | #智乃的数字积木(easy version)#

E、智乃的数字积木(easy version) 按照题意模拟，每次取色相同的一整段进行从大到小排序。这里萌新需要学习的两个小技巧数组切段每年看新生代码的时候尤其是有切字符串或者切数组这种需求的时候，发现新生切串一般都写的贼麻烦，其实这种只用写一个for+一个while语句就可以实现。 for ...

2022-01-28

2 557

题解 | #智乃的01串打乱#

D、智乃的01串打乱签到题，找到第一个0和第一个1的位置直接交换即可。时间复杂度O(N)O(N)O(N)，空间复杂度O(N)O(N)O(N)。 #include<bits/stdc++.h> using namespace std; const int MAXN=100005; ch...

2022-01-28

0 526

题解 | #智乃买瓜(another version)#

C、智乃买瓜(another version) 这道题属于是萌新也能做的多项式题（多项式除法）当然，解这道题不需要这么麻烦的理解啦。看到题目之后很自然的逆向思维，既然这道题是原题输入输出的倒置。不妨去想，怎么把放进背包的物品取出来。观察题目，说整只西瓜的质量都是偶数，那么最终答案为什么会出现质量...

2022-01-28

9 614

题解 | #智乃买瓜#

B、智乃买瓜简单背包，简单来讲，这道题的题解就写在题面里边了。 1.购买一整个重量为wiw_iwi的西瓜 2.把瓜劈开，购买半个重量为wi2\frac{w_i}{2}2wi的西瓜 3.不进行购买操作对应着DP转移的三个决策，不妨开一个dp[N][M]dp[N][M]dp[N][M]的数组，...

2022-01-28

1 467

题解 | #智乃的Hello XXXX#

A、智乃的Hello XXXX 输出hello world即可，当然，也可以随便输出其他符合要求的答案。大概是让萌新了解一下spj，毕竟本场有很多spj。时间复杂度O(1)O(1)O(1)，空间复杂度O(1)O(1)O(1) #include<bits/stdc++.h> using ...

2022-01-28

2 541

2021年儿童节J 智乃酱的配电箱谜题

这是一道线性代数经典题，问题来了，为什么儿童节要做线性代数呢。阿巴阿巴阿巴，我也不知道，可能我就是想出个数学题吧。（线性代数和数奥也差不多不是）首先肯定可以想到k很小，可以矩阵建图。考虑每一层网络之间的图都建成一个矩阵。例如第一层网络到第二层网络。如果第i个开关链接下层的第j...

矩阵线性代数

2021-06-01

5 764

CDQ分治（基于归并排序的分治）

CDQ分治预备知识分治与传统分治相同，CDQ分治的核心思想也是分而治之。对于一个数组序列上的问题，分治的思想是总是考虑中的这一部分，而对于这一求解函数则使用递归表示。式子中的加号并不一定是加法，只表示答案的合并。这个说法有点过于抽象了。 ...

分治 CDQ分治

2020-10-10

25 4418

上海大学校赛K迷宫

第一眼：bfs傻X题，然后发现它能跳。然后嘴巴BB了一句，起点bfs，终点bfs，单调栈+单调栈合并的傻X题。（...几小时后...） MD这个题怎么这么麻烦。好吧，这个题确实是没什么可以说的地方，没思路的话可能是不知道“单调队列处理固定划窗极值”这个套路。单调队列处理固定划窗...

2020-04-18

3 911

上海大学校赛G血压游戏

本题解需要掌握dsu on tree和长链剖的相关知识。具体可以见我的博客 dsu on tree：https://blog.nowcoder.net/n/a84c24c37daf450d8bf9db81607c8f98 长链剖分：https://blog.nowcoder.n...

2020-04-18

11 1230

长链剖分

长链剖分可以视作是dsu on tree算法的一个特例，在学习之前，需要掌握树链剖分以及dsu on tree。 dsu on tree:https://blog.nowcoder.net/n/a84c24c37daf450d8bf9db81607c8f98 dsu on tree用于解...

长链剖分 dsu 启发式合并

2020-04-15

4 2302