四糸智乃

题解

算法(12)

/ 注册

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

题解 | #智乃的数字积木(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

上海大学校赛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

CodeForces 600E Lomsat gelral

树上启发式合并(dsu on tree)，也叫静态树链分治模板题,预处理dfn可以节省一个dfs，改写成for循环，常数更小。 #include<bits/stdc++.h> using namespace std; const int MAXN=100005; int n; int ...

静态树链分治 dsu 启发式合并

2019-07-30

0 895

2019CEOI D1T2 Dynamic Diameter

题目大意：给一颗无根带边权树。支持两种操作： 1、修改某条边的边权。 2、查询当前直径。点分树模板题，全局开一个multiset维护直径，对于每个重心开一颗线段树和一个局部multiset，用欧拉序线段树维护每一个子树中的最值，然后将其放入局部multiset。接下来取局部mul...

线段树点分树树分治树的直径 stl

2019-07-28

0 1122