- 博客(100)
- 收藏
- 关注
RSS订阅原创 Marp + Vscode添加幻灯片Logo
实验室要定期汇报工作，我自己因为写笔记的时候都是用Markdown，每次需要在PPT里修改格式手打公示特别麻烦，于是就想重新用Marp来做演示，但是实验室的Logo总不能在最中间看着很违和（可能因为我们实验室的Logo有点emmm）希望可以把它放在演示左上角，但是找了一圈没有教程，文档里也没有讲到这种用法。于是乎想到可以在Marp里加HTML语法来实现这个功能，就自行查找了一下，其实有一篇教程讲了但是这部分的操作没有给演示。
2023-01-17 23:32:21
362
原创 MPEG音频编码实验
MPEG标准主要有以下五个，MPEG-1、MPEG-2、MPEG-4、MPEG-7及MPEG-21等。该专家组建于1988年，专门负责为CD建立视频和音频标准，而成员都是为视频、音频及系统领域的技术专家。及后，他们成功将声音和影像的记录脱离了传统的模拟方式，建立了`ISO/IEC11172`压缩编码标准，并制定出MPEG-格式，令视听传播方面进入了数码化时代。因此，大家现时泛指的MPEG-X版本，就是由ISO `(InternationalOrganization for Standardization)
2022-05-29 21:42:54
356
1
原创 JPEG原理分析及JPEG解码器的调试
JPEG图像压缩算法能够在提供良好的压缩性能的同时，具有比较好的重建质量，被广泛应用于图像、视频处理领域，网站上80%的图像都采用了JPEG压缩标准。
2022-05-22 17:39:49
1153
原创 LZW算法原理及实现
LZW属于第二类词典编码，其基本思想是：企图从输入的数据中创建一个“短语词典”，这种短语词典可以是任意字符的组合。编码数据过程中，当遇到已经在字典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。
2022-04-17 18:11:37
1754
原创 PNG文件转YUV格式并实现播放
文章目录PNG文件转YUVPNG文件格式YUV文件格式什么是YUV格式文件？YUV采样YUV 4:2:0RGB转YUV实验过程获取PNG文件信息获取IHDR信息获取PLTE调色板信息获取IDAT信息对IDAT数据块进行解压缩将解压缩的IDAT数据进行转换多个YUV合成PNG文件转YUV前言：本次实验选用了PNG转YUV，做的过程十分煎熬…主要原因是PNG的IDAT数据块的解码部分没有自己手写轮子，直接调用的Python的zlib库，所以每个像素解压缩出来的数据分布完全没有概念，而且第一次选的图片还是带α
2022-04-08 21:13:52
1473
原创 RGB文件三通道分量的熵的计算
RGB文件三通道分量的熵的计算所给的RGB文件是按照b,r,g的顺序排列，文件分辨率256×256256\times256256×256代码实现了以下功能：计算RGB三通道分量的熵将结果导出到.cvs文件中为了方便理解，用Excel进行了数据可视化。#include <iostream>#include <cstring>#include <cmath>#include <algorithm>#include <vector>
2022-03-15 10:07:01
276
原创 WAV格式文件分析
WAV是最常见的声音文件格式之一，是微软公司专门为Windows开发的一种标准数字音频文件，该文件能记录各种单声道或立体声的声音信息，并能保证声音不失真。它符合资源互换文件格式（RIFF）规范，用于保存Windows平台的音频信息资源，被Windows平台及其应用程序所广泛支持。Wave格式支持MSADPCM、CCITT A律、CCITT μ律和其他压缩算法，支持多种音频位数、采样频率和声道，是PC机上最为流行的声音文件格式；但其文件尺寸较大，多用于存储简短的声音片段。
2022-03-12 18:27:27
1051
原创 PNG格式文件的分析
便携式网络图形（`Portable Network Graphics`，PNG）是一种采用无损压缩算法的位图格式，其设计目的是试图替代GIF和TIFF文件格式，同时增加一些GIF文件格式所不具备的特性。PNG使用从LZ77派生的无损数据压缩算法，一般应用于JAVA程序、网页或S60程序中，原因是它压缩比高，生成文件体积小。
2022-03-09 13:52:30
1411
原创 Plants vs. Zombies 解题报告
临比赛前最后一次模拟给打吐了…这道二分的细节是真的多。题解：首先肯定想到的是我们二分答案，然后我们自然就得到了每一个花最小浇水的次数d[i]d[i]d[i]，然后我们贪心一下，当我们给d[i]d[i]d[i]浇水的时候，顺便去把d[i+1]d[i + 1]d[i+1]也浇了，这样我们就可以得到对于每一个d[i]d[i]d[i]，使他满足最小浇水次数的最少移动次数ste[i]ste[i]ste[i]，最后我们只需要累计一下ste[i]ste[i]ste[i]，然后和mmm比较即可。但是有坑！首先s
2021-11-11 21:30:52
1314
原创 Monopoly 解题报告
网络赛的时候没有搞出来，前几天做Atcoder的时候做到了一场STL场的比赛，就回来一起把这个题也补了。题解：首先肯定的是，如果当前的xxx合法，一定可以在序列中找到一个a[i]a[i]a[i]，满足：x≡a[i]moddx \equiv a[i] \enspace mod \enspace dx≡a[i]modd，其中ddd为a[i]a[i]a[i]的总和。并且我们发现，当d<0d < 0d<0时，我们可以把a[i]a[i]a[i]和xxx全部取反，这样再讨论其实和正数的情况是
2021-11-11 21:22:09
254
原创 2021-10-16
HDU-4811这个题绝对是近期做的最傻逼的一次…我是SB…题意：首先这个题目的题意我就没怎么看懂…后知后觉发现这个是说得放进去球之后的空间前后而不是时间前后…每次往一个队中放入某种颜色的球，积分规则是：第一个放入的球不得分后面放入的球如果在这个队伍的一端，得分为此时队伍中不同颜色的球的数目。或者也可以放在某两个球的中间，得分为新加入球的位置的左右两边的不同颜色球的数目和。最后输出可能的得分的最大值。题解：其实挺好做一题，直接可以分情况讨论：如果三种颜色的球都大于222，那就构造
2021-10-16 10:34:55
112
原创 线段树整理
文章目录线段树整理题解部分HDU-1394HDU-2795POJ-2828POJ-2886HDU-1698POJ-2528线段树整理最近搞线段树上瘾。总结一下这一次遇到的一些题型：纯板子题目（区间操作）线段树求逆序对数线段树带遍历优先级线段树 + 反素数 + 约瑟夫环线段树 + 离散化插队问题线段树的染色问题（Lazy标记的理解）这里把做题过程中遇到的一些经典题目和对应思路解法记录一下。题解部分HDU-1394题意：给定一个序列ai{a_i}ai为一排列，现在按照某种方式
2021-09-12 10:17:57
109
原创 LuoGu P1197 星球大战
并查集 + 逆向思维题解：直接看题的话其实没有什么很好的思路，直接正向删除节点维护的话，时间复杂度必然爆炸…所以这个题目可以逆向考虑：我们假设现在有kkk个点是坏的，我们去修这kkk个点，每修一个点就统计一次整张图的联通块数目。所以先假设每一个点都是独立的，也就是total=n−ktotal = n - ktotal=n−k。之后每加入一个点都统计一次连通块的数目，解决两个点之间的联通性问题我们可以用并查集维护。#include <bits/stdc++.h>#define ill
2021-08-08 21:53:01
67
原创 BZOJ4195 程序自动分析
离散化 + 并查集题解：首先因为不等式并不具有传递关系，或者说冲突的情况只能是不等式和等式的冲突。我们先把所有的等式归于一类，然后逐个判断不等关系是否可以存在即可。这里需要注意，数据范围达到了1e91e91e9，一般的数组是开不下的，同时如果用mapmapmap肯定会超时，那就需要考虑离散化，把1→1e91\to 1e91→1e9的数据映射到1→2e51\to 2e51→2e5上，结合并查集即可。#include <bits/stdc++.h>#define ill __int128
2021-08-08 14:05:02
89
原创 AcWing 165 小猫爬山
题解：复习一下DFSDFSDFS，考虑到后面的图论和数据结构好多都是需要搜索的，所以这里再巩固一下，毕竟自己的搜索实在是一言难尽QAQ。带有回溯（还原现场）类型的题目，其实关键就是确定搜索边界+搜索的方法，这个题目的边界肯定是全部的猫都被放到了车上，然后我们的搜索方法是：当前对于编号为nownownow的猫：尝试把他放在第iii个车上，1≤i≤cnt1 \leq i \leq cnt1≤i≤cnt，cntcntcnt为当前我们租的车数目。如果放的下，我们就递归dfs(now+1,cnt)dfs(no
2021-08-04 21:01:53
74
原创 AcWing 164可达性统计
拓扑排序+STL(bitset)STL(bitset)STL(bitset)题解：我们假设从节点iii出发，可以达到的点集为S=s1,......snS = {s_1,......s_n}S=s1,......sn，那么我们要求节点iii可达的点数，其实就是SSS中所有点可达的点数之和，表示为：f(i)=∑i=1nf(si)f(i) = \sum_{i = 1} ^ nf(s_i)f(i)=∑i=1nf(si)其中f(i)f(i)f(i)为从iii出发可以到达的总点数。既然设计到到达顺序的问题
2021-08-04 20:08:13
109
原创 AcWing 160T
题解：就离谱的很的KMPKMPKMP之前写的159使用了KMPKMPKMP一个小拓展，直接对字符串数组进行模式匹配。这个更考验理解能力QAQ为啥这么说呢，就是整个KMPKMPKMP模式匹配从求解NextNextNext数组到求解FFF数组进行匹配，整个过程要求你必须了如指掌而且清楚每一步的操作原理。所以我就没了TAT这里我们首先对BBB字符串进行自我匹配求出NextNextNext数组，然后让他和AAA字符串进行匹配，我们发现求解过程中的这一步：for (int i = 1, j = 0;i
2021-07-30 11:01:18
69
原创 AcWing159T
好久没看的KMPKMPKMP题解：这个题一开始的思路是想看每一行的最短不整除循环节然后求一个lcmlcmlcm，但是最后被自己的数据Hack了…后来看了一下题解发现还可以直接对字符串数组进行KMPKMPKMP，原理其实是一样的，不过可以更快得确定完全覆盖需要得最小行数和最小列数。很妙的思路#include <bits/stdc++.h>#define ill __int128#define ll long long#define PII pair <ll,ll>#
2021-07-29 20:29:41
81
原创 AcWing 157 & 158
两个题目分别是考察的树的最小表示（157）和字符串的最小表示（158）。字符串的最小表示对于一个字符串SSS，有众多的循环同构串，所谓最小表示就是这些循环同构串中字典序最小的那个串。我们可以采用一个O(n)O(n)O(n)的算法求解出长度为nnn的字符串的最小表示。int n = strlen(s);int k = 0,j = 1,i = 0;while (i < n && j < n && k < n) { if (s[(i + k) % n]
2021-07-28 15:54:06
85
原创 Nowcoder 多校联合第四场题解
Nowcoder 多校联合第四场C.LCS题解：题意为，我们给出三个等长字符串s1s_1s1,s2s_2s2,s3s_3s3，定义a=LCS(s1,s2)a = LCS(s_1,s_2)a=LCS(s1,s2)，b=LCS(s2,s3)b = LCS(s_2,s_3)b=LCS(s2,s3)，c=LCS(s1,s3)c = LCS(s_1,s_3)c=LCS(s1,s3)。要求构造出满足条件的三个字符串，如果不存在输出NONONO。先构造公共前缀，取aaa,bbb,ccc中最小的，
2021-07-27 21:29:53
48
原创 Ac.wing 149. 荷马史诗
追逐影子的人，自己就是影子。 ——荷马写在前面纯粹是因为自己喜欢哈哈哈哈题解：我们需要让这个替换后的字符串总长度最小，同时要求在保持最小字符串长度的前提下，我们尽可能让最长的字符串最短。所以我们贪心一下很容易想到：如果要总的字符串长度最短，我们就让数量最大的单词长度最短就可以了，我们就把这个数量理解为Huffman的权值，把长度理解为Huffman中节点距离根的深度，这样就转换成了一个Huffman问题，同时我们把节点据根的深度表现在根到节点的路径上，这样就是使用了Trie树的原理。如何让最长的字
2021-03-07 23:48:16
138
原创 2021牛客寒假算法基础集训营1题解
F.对答案一时爽题解：签到题，直接去看两个人的成绩是否相同，相同+2不同则+1AC代码：#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<stack>#include<queue>#
2021-02-12 22:29:44
308
原创 Educational Codeforces Round 101 (Rated for Div. 2) A-D
A.Regular Bracket Sequence题解：这个题目一开始WA了两发的原因很玄学：没有看出来他的()只有一对…那么在()有且仅有一对的情况下，我们首先判断当前字符串的长度是不是偶数，也就是判断lenmod 2==0len\mod 2 == 0lenmod2==0，如果当前字符串的长度非偶，那么就可以直接say no了，否则我们就让前一半的?变成(，后一半变成)然后用一个stack就可以了AC代码#include<iostream>#include<cstring
2021-01-27 10:13:45
82
原创 Ac.Wing 142.前缀统计
题解：问加入的字符串中有多少是当前给出的字符串的前缀子串，那么我们就可以对每一个加入的字符串建立Trie树，然后只需要把最后的End数组改一下意义就可以，因为统计的是前缀数目，那我们就把每一个作为结尾的节点数目记录一下，然后当我们发现这个节点是作为结尾的时候，让ans进行一次累加即可AC代码：#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<
2021-01-21 16:45:59
76
原创 Educational Codeforces Round 102 (Rated for Div. 2) A-D题解
A.Replacing Elements题解：如果需要替换就使用整个序列中最小的两个元素去做替换，如果替换后仍不满足直接Say NOAC代码：#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<stack&
2021-01-20 10:39:35
101
原创 Ac.wing 140 后缀数组
题解：理论上后缀数组的求解要使用倍增orDC3算法来求解，但是这显然超出了我的水平范围不符合题目的要求。所以我们就正大光明得使用Hash + Sort来做。题目比较难处理的点在于，我们对于两个后缀字符串的比较，因为比较的最坏时间复杂度为O(n)O(n)O(n)，但是我们快排就已经有了O(nlogN)O(nlog{N})O(nlogN)的复杂度，显然对于3e5的数据肯定会超时，那我们应该怎么去处理呢？其实和之前的题目相似，我们使用二分答案的方法做，我们二分得出两个后缀字符串重合的最大长度，然后去找下一位比
2021-01-18 17:46:19
76
原创 Ac.Wing 139. 回文子串的最大长度
题解：这个题目如果单独拿出来就是一道裸的Manacher算法，但是这里希望我们强化一下Hash算法，所以我就写了两个版本的。Manacher：#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<vector>#include<map>#include<stack&g
2021-01-18 11:27:33
115
原创 Ac.Wing 137 雪花雪花雪花
题解:这个题目应该说是一个比较常规的Hash但是自己太菜了写的好乱QAQ理一下Hash的思路叭：首先需要定义一个Hash函数，用来对数据进行离散化操作，然后结合链表去储存数据，一般使用邻接表比较多。理想的一个Hash表可以把算法时间复杂度优化到O(1)O(1)O(1)，建立Hash函数后我们随即建表，邻接表的表头储存的就是数据的“特征值”，每一个特征值下存着对应的数据链表，这样子我们在查找的时候就可以直接通过特征值找元素了。那么对于这个题目，我们首先确定Hash函数：对于两个相同的六元组，他们的元素
2021-01-14 17:19:01
75
原创 Ac.Wing 106 动态中位数（Offline）
题解：这个题目和之前的邻值查找问题很相似，这个题关键就是在于弄清楚链表中中位数到底是如何变化的。我们简单分析一下这个题目：动态取值，动态取出中位数，Online做法是使用大小堆，但是这里因为刚学了链表其实是不会大小堆orz我们就用Offline的方法写了。首先我们把所有的数据加入链表并排序，记录一下他们在原链表中的位置和现在的位置，我们仍然是和136题一样采用从后取值的方式，对于第n个数据，答案肯定是a[(n+1)/2]a[(n + 1 ) / 2]a[(n+1)/2]，我们知道它只有在链表长度为奇
2021-01-14 11:43:32
167
原创 Codeforces Round #693 (Div. 3) 题解(ABCDE)
A.Cards for Friends题解：分开来讨论长和宽就可以，分别对长和宽一直除以二并做一个累乘，得到的结果直接再乘起来就可以AC代码：#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<set>#include<bitset>#include<queue&
2021-01-14 11:09:22
176
原创 Ac.Wing 136 邻值查找
题解：这个题目是有两种写法的，y总在视频里只讲了list的写法，这里我们也用STL set写了一个。先说一下两种写法的思路：链表写法（OffLine）其实不管是使用链表存储还是set存储，算法的核心就是找到每一个点的前驱和后继节点，然后通过比较这两个节点和选定值差的大小关系决定使用哪一个作为最后的答案。我们假设把所有数据存入链表后进行排序，同时用一个数组记录排序后的元素在原链表中的位置是多少，我们从n开始，找每一个节点的前后驱节点，比较后存入一个记录答案集合中，然后把这个节点删除，继续找下一个节点
2021-01-13 09:35:43
120
原创 Ac.Wing 135最大子序和 + 131最大子矩阵
关于单调队列/栈的总结其实之前看过蓝书上的单调队列/栈的解释，但是还是感觉懵懵懂懂得，今天趁着做这个题目把单调队列和栈写个小总结。首先单调队列和单调栈都是为了实现在决策队列中及时排除一定不是最优解的情况，以达到节省时间，提高效率的目的。不管是单调栈还是单调队列，其核心思想都是单调二字，也就是说，我们需要维护的永远都是队头or栈头的那个最小or最大的元素，对于单调队列而言，基本的思路就是：维护队首，如果队首超出范围那就要删除维护单调去除冗杂，像本题中，遇到队伍中比当前值还大，并且排名还靠前的元素我们
2021-01-12 11:12:53
120
原创 Ac.Wing 133蚯蚓 进阶指南P56 题解
写在前面的话：这道题久违了个人感觉这个题目的质量还是相当不错的，结合了队列和数学，难度上在Ac.Wing属于橙题范围，做这个题的时候发现的主要问题在于：一些数学公式的推导思路和理解还要去训练对于整体偏移和通过偏移量求值的问题的理解下面给题解：题解：这个题目可以去用最朴素的方法解决：就是说我们定义一个偏移量，每一次从队列中取出一个最大值，然后把他分得的floor(px)floor(px)floor(px)和x−floor(px)x - floor(px)x−floor(px)全部减去q后加入
2021-01-11 10:37:34
87
原创 数据结构——图(Graph)
数据结构——图(Graph)目录1.图的基本概念2.图的基本代码操作3.图的进阶操作和应用1.1 图的定义任何一个图都是由顶点和边构成的。我们采用集合的思想，可以把任何一个图用两个集合表示出来：记作G=(V,E)G = (V,E)G=(V,E)，其中V是表示顶点的有限集合，E为边的有限集合。允许E为空集，此时表示的含义是：图G只有顶点但是不存在边。1.2 图的相关术语1. 有向图和无向图我们举一个例子来理解：题目描述：某省政府进行"畅通工程"，现在给出每两个城市之间的道路和道路
2020-11-30 09:49:13
2896
原创 数据结构整理 —— 顺序表
线性表——顺序表2.1 线性表的基本概念2.1.1 线性表的基本定义线性表是一个由N个相同元素组成的有序序列。一般来说，线性表主要分为顺序表、单链表、循环单链表、双链表和循环双链表。线性表主要可以解决一系列数据的线性存储，而它的存储方式又分为顺序储存和链式储存，以此可以实现数据的输入输出、插入、查找等操作。2.1.2 线性表的基础操作初始化 ~~ InitList()销毁单链表 ~~ Dest
2020-10-24 10:33:46
2954
原创 蓝桥杯练习 Basic-12 16进制转8
题解：这个题目算是发现了我在位运算上的知识缺陷。先说一下涉及到位运算进制转换上的一些知识点：八进制和二进制：八进制数通过除2取余法，得到二进制数，对每个八进制为3个二进制，不足时在最左边补零。3位二进制数按权展开相加得到1位八进制数。（注意事项，3位二进制转成八进制是从右到左开始转换，不足时补0）。十六进制和二进制：十六进制数通过除2取余法，得到二进制数，对每个十六进制为4个二进制，不足时在最左边补零八进制是取三合一，十六进制是取四合一。（注意事项，4位二进制转成十六进制是从右到左开始转换
2020-09-06 09:24:12
117
原创 Educational Codeforces Round 93 (Rated for Div. 2)
Educational Codeforces Round 93 (Rated for Div. 2)A. Bad Triangle题解：其实这个题很水的…之前做过一个给出你四个数让你组三角形，这一次就是要求不一样。我们已知a序列是一个非递减序列，那么如果a种存在题目所说的BT的话，那么一定包括a[1]和a[2]，因为不管i,j取何值，相加后的结果一定是：a[i] + a[j] <= a[1] + a[2]，所以用a[1]和a[2]凑出这个BT三角就完了。AC代码:#include<i
2020-08-28 23:16:09
89
原创 AcWing 110 防晒
题解：emmm这个题目是一个贪心的问题，但是一开始理的不是很清楚…首先这个题目提供两种方法，一种是一般贪心，还有一种就是使用了一下优先队列，其实原理都是一样的。法一：我们把奶牛的minSPF从大到小排序，然后再对防晒霜按照SPF降序排序，这样我们对于每个奶牛都去选择SPF最大的那个防晒霜。可以证明的是：对于前面的奶牛，如果这个防晒霜的SPF大于minSPF，那么之后的奶牛一定也满足这个条件。也就是说，当前奶牛可用的任意两瓶防晒霜x,y，如果SPF(x) > SPF(y)，那么对后面的奶牛就一定
2020-08-28 15:22:52
128
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人