python算法复习笔记4(树状数组,线段树,矩阵乘法,st表)
题目来源:https://www.acwing.com/activity/content/2869/
楼兰图腾题意https://www.acwing.com/problem/content/243/
思路按照中间的点将答案划分为不重不漏的N个集合,依次计算每个集合中的个数,使用树状数组优化
树状数组注意下标从1开始
代码1234567891011121314151617181920212223242526272829303132333435363738n = int(input())tr = [0 for i in range(n+2)]big = [0 for i in range(n+2)] # 下标为i的数左边比它大的个数sm = [0 for i in range(n+2)]def lowbit(x): return x&(-x)def add(i,c): while i<=n: tr[i]+=c i += lowbit(i)def sum(idx): res = 0 while idx: res ...
python算法复习笔记3(拓扑序,Dijkstra,SPFA,最小生成树,LCA,二分图)
题目来源:https://www.acwing.com/activity/content/2869/
有向图的拓扑序列题意1234给定一个n个点m条边的有向图,点的编号是 1到n,图中可能存在重边和自环。请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出 −1。若一个由图中所有点构成的序列 A 满足:对于图中的每条边 (x,y),x在A中都出现在y之前,则称A是该图的一个拓扑序列。
思路拓扑序列模板,属于bfs的应用
首先记录各个点的入度
然后将入度为 0 的点放入队列
将队列里的点依次出队列,然后找出所有出队列这个点发出的边,删除边,同事边的另一侧的点的入度 -1。
如果所有点都进过队列,则可以拓扑排序,输出所有顶点。否则输出-1,代表不可以进行拓扑排序。
代码12345678910111213141516171819202122232425262728293031from sys import stdinfrom collections import deque(n,m) = map(int,stdin.readline().strip().split( ...
杂谈101B:回顾与展望
2022.12.15 — 2023.2.20期末考试延期带来了很多麻烦。原本我计划寒假尽量把第二篇论文弄出来,并尽早地套磁。但因为期末考试延期等因素,这两条任务直到近期才开始…
假期前期,因为离期末考试很远+担心新冠,一直都在玩
后面开始写简历+套磁+复习,但又由于过年各种串亲戚,效率很低
花时间套了个老师,还认真准备了自我介绍,读了十来篇论文,结果发现是在养鱼o(╥﹏╥)o
挺内疚,两个月的假期真正用来学习的时间只有十几天,把要考的5科简单过了一遍。其他的竞赛科研也都没碰。
然后就是美赛了。。。因为两个队友没有相关知识储备,全程都是我一个人建模+代码,还得兼顾写作的一些技术细节。所幸C题用的基本都能用深度学习的方法,建模和代码还算顺利,质量肯定能达到M奖的水平。
可是万万没想到最后排版出了问题!!有一段话和公式重复了两次(大概1/3页的篇幅),我们发现这个问题时已经是比赛结束后了。真的乌鱼子😅
总之,2022.12.15 — 2023.2.20这段时间,不管是运气,还是自己的学习状态,都是远没达到预期的。
2023.2.21 — 现在先说今天考的CSP,混了个1%
这还真得归功 ...
python算法复习笔记2(并查集、哈希、单调队列、bfs、dfs)
题目来源:https://www.acwing.com/activity/content/2869/
亲戚题意并查集裸题
题解/坑点用python的input会TLE
from sys import stdin
stdin.readline().strip().split()
代码123456789101112131415161718192021222324252627from sys import stdinN,M = (int(_) for _ in stdin.readline().split(" "))fa = [i for i in range(N+1)]def find(x): if x!=fa[x]: fa[x] = find(fa[x]) return fa[x]for i in range(M): x,y = (int(_) for _ in stdin.readline().split(" ")) fx = find(x) fy = find(y) fa[fa[x]] = f ...
简单算法题——复习笔记1(模拟,二分,双指针,递推)
题目来源:https://www.acwing.com/activity/content/2869/
截断数组题意给定一个长度为 n 的数组
现在,要将该数组从中间截断,得到三个非空子数组。要求,三个子数组内各元素之和都相等。请问,共有多少种不同的截断方法?
题解/坑点简单题,前缀和。我最开始的想法是先统计出前缀1/3 和 后缀 2/3 两个下标数组。再双指针遍历两个数组,做乘法运算,求和。
但其实有简洁的做法,如代码所示。注意要先算ans+=cnt,再ans++
代码1234567891011121314151617181920212223using namespace std;typedef long long LL;LL a[100010],s[100010];LL n,ans,cnt;int main(){ scanf("%lld",&n); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); s[i]=s[i-1]+a ...
杂谈100B:动画安利(个人向)
本篇文章使用ChatGPT进行辅助写作
众所周知,博主作为二次元爱好者,动画当然没少看。最近有个「动画生涯个人喜好表」挺火的(https://lab.magiconch.com)
我也跟风做了一个,不说废话直接上图
入坑作 — 罪恶王冠狭义上的二次元是指日本acg文化,我是从初一/初二的时候开始接触的,而我的入门之作,就是这部罪恶王冠。
罪恶王冠中的末世的背景设定,女主和她的歌曲,男主的「王之力」等等,对于当时的我来说,都是非常震撼和新奇的。也启蒙了我很多中二的幻想。印象最深的还是楪祈和她的歌曲,EGOIST的作品至今仍然在我的音乐播放列表中。
时间来到三年后,我上高中时看了动画区某up主的吐槽(他的观点也是网上关于这部动漫的主流),回忆后发现「最2王冠」一说倒也不无道理hh。
总结:这是一部制作精良,但剧情浅薄的原创作品,设定符合「中二少年」的一切幻想,作为我初中二年级时的动漫入坑之作,罪恶王冠确实是一部不错的作品。
最喜欢 — 无职转生我高中的时候接触了无职转生的原作。与其他国产爽文/异世界厕纸不同,无职中的主角的实力并不是顶尖的。小说描绘了卢迪乌斯的一生,虽然是发生在一个虚 ...
SAR图像变化检测深度学习研究方法
概述一般方法
第一步,在进行变化检测之前需要对两幅图像进行几何校正、辐射校正以及去噪等预处理操作。
几何校正是指SAR成像过程中,由于传感器姿态、地球旋转等条件的影响会使原始图像上地物的特征与其对应的地面地物的特征发生几何畸变, 所以在变化检测之前需要对图像执行几何校正操作。
辐射校正是指图像在获取、传输过程中会发生辐射失真的现象,因此在图像预处理的过程中有必要进行辐射校正。
图像去噪是指SAR传感器在成像过程中会被相干斑噪声干扰,导致获取的图像不能准 确而真实的反映出地物信息,故在SAR图像变化检测之前有必要对相干斑噪声进行滤除。
第二步,生成差异图是指对两幅SAR图像进行某种操作从而生成为一幅图像 的过程。值得注意的是生成差异图这一步骤在SAR图像变化检测中并不是不可或缺的(该步骤表示为虚线框),经过近年来的研究可知,变化信息可以通过直接对预处理后的图像进行操作来获得。
第三步,采用变化检测算法对差异图或预处理之后的图像以有监督或无监督的方式进行分类,进而得到变化检测结果图
评价指标假设,在变化检测结果图中,实际发生变化但检测为未变化的像素点数为Cu, 实际未发生变化但检测为变 ...
6D姿态估计-笔记1
ICCV2021 SO-Pose: Exploiting Self-Occlusion for Direct 6D Pose Estimation自遮挡下的6dof位姿估计。 从单个RGB图像直接回归杂乱环境中对象姿势(即3D旋转和平移)的所有6个自由度(6DoF)是一个具有挑战性的问题。而端到端的方法最近有所改进。在高效率下显示了有希望的结果,但在姿态精度方面,与基于PnP/RANSACP的精细方法相比,它们仍然较差。在这项工作中,我们通过一种新的关于自遮挡的推理来解决这一缺点,以便为三维对象建立一个两层表示,这大大提高了端到端6D姿势估计的准确性。我们的框架,命名为SO Pose,以单个RGB图像作为输入,并分别生成2D-3D对应作为自遮挡信息利用共享编码器和两个独立解码器。然后将两个输出融合,以直接回归6DOF姿态参数。结合对齐对应、自遮挡和6D姿势的跨层一致性,我们可以进一步提高准确性和鲁棒性,在各种具有挑战性的数据集上性能sota.
CVPR2021 StablePose: Learning 6D Object Poses from Geometrically Stabl ...
目标检测相关摘录
RetinaNet针对现有单阶段法(one-stage)目标检测模型中前景(positive)和背景(negatives)类别的不平衡问题,提出了一种叫做Focal Loss的损失函数,用来降低大量easy negatives在标准交叉熵中所占权重(提高hard negatives所占权重)
pvtv2pvthttps://zhuanlan.zhihu.com/p/360563672
自从ViT在图像分类中取得效果之后,关于vision transformer的研究呈井喷式爆发,PVT将ViT应用在其它图像任务中(如分割和检测),PVT相比ViT引入了和CNN类似的金字塔结构,使得PVT像CNN那样作为backbone应用在dense prediction任务。
CNN结构常用的是一种金字塔架构。这主要有两个方面的考虑,一是采用stride=2的卷积或者池化层对特征降维可以增大感受野,另外也可以减少计算量,但同时空间上的损失用channel维度的增加来弥补。
但是ViT本身就是全局感受野,所以ViT就比较简单直接了,直接将输入图像tokens化后就不断堆积相同的transformer ...
自监督——MAE
自监督
对比学习
生成式
SimMIM
随机mask
Prediction haeds只需要一层全连接即可
Prediction targets 最朴素的 L1
MAE概述MAE 的做法可以用一句话概述:以一定比例随机 mask 掉图片中的一些图像块(patch)然后重建这些部分的像素值。
主要特点有两个:
非对称的编、解码器设计
使用较高(如 75%)的掩码率(mask 比例)
Encoder 通常是多层堆叠的 Transformer,而 Decoder 仅需较少层甚至1层
MAE 的方法属于 掩码自编码(Masked Autoencoding) 范畴,这种这玩法在 NLP 尤为火热,大名鼎鼎的 BERT 在预训练中就是这么玩的:以一定比例 mask 掉输入文本中的一些部分,让模型去预测这批被 mask 掉的内容。
Mask 策略首先,沿袭 ViT 的做法,将图像分成一块块(ViT 中是 16x16 大小)不重叠的 patch,然后使用服从均匀分布(uniform distribution)的采样策略对这些 patches 随机采样一部分,同时 mask 掉余下的另一 ...