Superb_day

原创 零碎知识的备忘录

1）next_permutation()【#include <algorithm>】作用：求一个排序的下一个排列的函数，可以遍历全排列。参考案例：Noip普及组2004 火星人#include<bits/stdc++.h>using namespace std;int a[10005],n,m;int main(){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++)scanf("%d",&am

原创 YOLOv1-3代的个人理解笔记

本文的资料来自于多方面网络内容，包含个人见解和资料整理。Yolov1：一.预测阶段（1）前阶段上面为yolov1 标准，下面为yolov1快速版本。1.输入必须缩放调整为正方形，像素为448*448，3代表3通道RGB。2.Conv.Layer7*7*64-s-2的意思是卷积框为7*7，卷积核filter为64，s代表stride参数。Maxpool.Layer的意思是池化层。原图式：n x n卷积核： f x fpadding（边框补充）：pstride ..

原创 机器学习（3）Optimizer优化

import torchimport torch.utils.data as Dataimport torch.nn.functional as Fimport matplotlib.pyplot as plt# torch.manual_seed(1) # reproducible#超参数：提前定义的参数LR = 0.01BATCH_SIZE = 32EPOCH = 12# fake datasetx = torch.unsqueeze(torch.linspace(-1,.

原创 机器学习（2）快速搭建、saveAndLoad、批训练

一、快速搭建这是上一篇博客中所用的搭建方法，看起来确实复杂。主要思路：我们用 class 继承了一个 torch 中的神经网络结构, 然后对其进行了修改。#-----建立神经网络-----class Net(torch.nn.Module): #继承torch的组件 #class(类)是面向对象编程的基本概念，是一种自定义数据结构类型 命名为Net #init搭建这个信息层所需要的信息 def __init__(self, n_feature, n_hidd

原创 机器学习（1）关系拟合（回归）与区分类型（分类）

开了个新坑，这波学习遭老罪了，啥都看不明白，一个一个查。注释1：

原创 子序列问题

（一）一个序列中的最长上升子序列（LIS）例题 ：导弹拦截（求不上升序列长度和上升序列长度）#include <iostream>#include <algorithm>using namespace std;const int N = 100010;int a[N], d1[N], d2[N], n;int main() { while (cin >> a[++n]); n--; //输入 int len1 = 1, len2 = 1; //

原创 I. Command Sequence CCPC2021网络赛

Problem I. Command Sequence Input fifile: standard input Output fifile: standard output Time limit: 1 second Memory limit: 256 megabytes There is a robot that can move by receiving a sequence of commands. There are four types of command in.

原创 Prim堆优化

#include<bits/stdc++.h>#define R register int//优化,可忽略#define P pair <int,int>using namespace std;int k,n,m;int cnt,sum,dis[10005],vis[10005];vector <int> E[200005];//存点vector <int> W[200005];//存边inline void add(int u,int v,.

原创 tarjan强连通分量

原创 贪心 Day9

一、活动安排问题

原创 图论 Day8

一、拓扑有向无环图才有拓扑排序拓扑排序是图的所有顶点的一个排列（所有点出现且仅出现一次）如果图中有点A->B 那么在拓扑排序中点A的位置一定在点B前面时间复杂度O(N)拓扑排序的应用：1. 有向图找环 （能找到拓扑排序说明没有环）2. 解决依赖问题 （用A->B表示B依赖A，以此建图，找到的拓扑排序里A一定在B之前完成）二、最短路1.Bellman-Ford、SPFABellman-Ford思想： 对于一条最短路，最多经过n-1条边 每轮我们遍历所有的边对最.

原创 DP Day7

一、背包1.01背包设f（i，j）为只考虑前i个物品的前提下，每个物品只能拿一次，最多用j容量能获得的最大价值。显然，f（0,0），f（0,1），f（0,2）...f（0，m）的值为0。假设已知f（i-1,0），f（i-1,1）...f（i-1,V），考虑如何求出f(i,j)（0≤j≤V）。 f（i,j）和f（i-1，j）的区别是f（i，j）还可以考虑第i个物品。 也就是说，f（i，j）只会根据取与不取第i个物品从之前的状态转移过来： ①不拿第i个物品最优：f（i-1，j） ②拿第i个物品.

原创 数据结构 DAY 6

一、栈int a[maxn],tot;#define top() (a[tot])#define pop() (tot--)#define push(x) (a[++tot]=(x))//注意tot是否大于0STL stack二、队列STL queue三、并查集四、二叉树1.二叉树二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的...

原创 STL Day2

STL 是⼀个 C++ 软件库，⾥⾯包含算法（algorithms）、容 器（containers）、函数（functions）、迭代器（iterators）一、string1.创建string类型变量string s(int n,char c); 创建一个string，由n个c组成，注意c是字符型要用单括号''2.读入stringcin>>s; 读入s，遇到空格或回车停止，无论原先s是什么内容都会被新读入的数据替代 getline(cin,s); 读入s，空格也同样会读入，

原创 kmp周期性循环节（Cyclic Nacklace HDU - 3746）

知识点：考察对next数组的理解：周期性字符串循环节长度 ans 是 n−next[n] ，也可以理解为 n-next 的前缀是最小覆盖子串 ，而当前提为n% ans==0&&next[n] !=0时，循环次数是 n/ans 。题意:给你一串字符串。可以在这个字符串左右加上任意字符，使最后求得的字符串可以构成循环。思路：用前缀数组可以求得初始字符串的最小循环节。最小循环节=（原字符串长度-末尾前缀数组值）然后进行讨论：如果最小循环节=原子符串长度.说明末尾前缀数组值为

原创 KMP算法

一、概述KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同发现的，故简称KMP，是用来处理字符串匹配问题的，它的时间效率可以达到O（n）。对于平常的字符串比较，时间效率为O（mn），线性扫一遍*字符串本身长度，孰高孰低一眼便知，所以掌握KMP算法还是很有必要的。二、模型展示假设有字符串A和B：A：ababaabab...B：abac开始匹配。...

原创 基础计算几何（叉积）

图来源于网络。基本思路① 快速排斥实验（不涉及计算几何）：如果两条边所在矩形不相交则一定不相交，即满足（min(x1,x2)<=max(x3,x4) &&min(x3,x4)<=max(x1,x2) &&min(y1,y2)<=max(y3,y4) &&min(y3,y4)<=max(y1,y2)） 才可能相交②跨立实验：即以其中一条线段为直线，判断另一线段的两端点是否在它两边，但是可能出现以下情况...

原创 数论整理笔记

一、质数问题1、欧拉函数在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目）​int phi[1000010]; void Euler_excel(int n)//n是打表打到多少{ phi[1]=0; for(int i=2;i<=n;i++) phi[i]=0; for(int i=2;i<=n;i++) if(!phi[i]){ for(int j=i;j<=n;j+=i){

原创 唯一分解定理与lcm，gcd的关系（LightOJ1236-Pairs Forming LCM）

题目大意：给一个n，求1到n里有多少对a,b满足a,b的最小公倍数是n。网上找了个证明，写的比较清楚明白。#include <iostream>#include <algorithm>#include <cmath>#include <stdio.h>using namespace std;const int maxn = 1e7+10;typedef long long ll;ll T,N;ll P[1000010],tail

原创 求n^k的前三位和后三位

求后三位很简单，就是在快速幂的过程中模1000即可。求前三位比较复杂：b对应下方代码的y。#include <iostream>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;ll a,b;int T;ll ksm(ll a,ll b){ ll res = 1; while(b){ if(b&1.

原创 算术基本定理 唯一分解定理 （Aladdin and the Flying Carpet LightOJ - 1341 ）

It's said that Aladdin had to solve seven mysteries before getting the Magical Lamp which summons a powerful Genie. Here we are concerned about the first mystery.Aladdin was about to enter to a magical cave, led by the evil sorcerer who disguised himself

原创 lower_bound( )和upper_bound( ) Cf Round #725 (Div. 3) C

C. Number of Pairstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an arrayaaofnnintegers. Find the number of pairs(i,j)(i,j)(1≤i<j≤n1≤i<j≤n) where the sum of...

原创 并查集之链表搜索的O(1)时间复杂度

POJ 1456 Supermarket题目大意：给你 N 件不同的商品，每件商品最多可以买一次。每件物品对应两个值 pi dipi 表示物品的价值，di 表示可以买的最迟时间（也就是第一天到第 di 天都可以买这件物品）每天最多可以买一件物品，问你可以得到的最大价值。https://vjudge.net/problem/POJ-1456#include <stdio.h>#include <string.h>#include <iostream>

原创 利用typedef定义新类型

在结构体使用中，一直打struct会很麻烦，比如下面求两点之间的连线距离：struct Point {double x,y;};double dist(struct Point a,struct Point b){ return (a.x-b.x,a.y-b.y);}在c语言中，定义结构体的方法为“struct 结构体名词{域定义}；”注意花括号后面还有一个分号。所有用到Point的地方都需要写一个struct。用以下方法可以避开struct，让结构体用起来和int，double.

转载 优化火车头

听说可以优化速度，代码来自于网络。#pragma GCC optimize(3)#pragma GCC optimize("Ofast")#pragma GCC optimize("inline")#pragma GCC optimize("-fgcse")#pragma GCC optimize("-fgcse-lm")#pragma GCC optimize("-fipa-sra")#pragma GCC optimize("-ftree-pre")#pragma GCC opti.

原创 c++常用STL大总结

想了半天感觉写一些单个的stl专题过于麻烦，和网上的也差不多，不如写一篇总结，盘点一下主流的stl以及它们的作用，什么时候使用哪个比较好。理想状态下，这篇文章看完之后你就能比葫芦画瓢去用。一、当你需要（对数据进行一对一映射）/（用数据A找数据B）的时候 ------使用map1、介绍Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的处理能力。Map是一类关联式容器。它的特点是增加和删除节点对迭代器的影响很

原创 矩阵乘法快速幂

今天员工小c写题的时候遇到了在第四黑厂时期就没填的坑，今日再次见面，自然是无奈，但是他请教了他的好朋友枫系，原来需要矩阵乘法快速幂的知识。Number Sequence时间限制: 1 Sec 内存限制: 256 MB题目描述此题HDUOJ数据过水，网上题解中直接将n%49的做法是错误的。A number sequence is defined as follows:f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7

原创 2021-01-28 求n的n次方的最高位

今天写了个题很有意思，求n的n次方的最高位，需要一定的数学思维（其实高中数学足以）#include<bits/stdc++.h>using namespace std;int main(){ long long i,k,t;scanf("%lld",&t);//t组数据 double n,a; while(t--) { cin>>n;//输入这个n k=n*log10(n); a=p

原创 游戏制作日记（1）blender与ue4的模型初步导入

怕什么真理无穷，进一寸有进一寸的欢喜。虽然我对胡适无感，但是这句话还是不错的。近来决定真正的开始制作游戏，同期在csdn上记录日记，写这个的目的有几点吧。第一点就是激励我推进项目的进度。第二点就是能对走过的路加以记录，做个知识的笔记。第三点就是能够让大家见证我的成长吧。最近解决的问题就是blender 和 ue4的模型导入。blender不像3dmax，maya等建模软件有虚幻商城自带的插件，blender得需要额外的操作。这一手操作我是混迹ue4和blender的交流qq群学来的，

原创 指针浅谈

我在中学的时候，指针学的就不太好（黑厂老板没咋讲，出来背黑锅！ /狗头保命），上了大学发现还不熟悉，临近期末考试，再不会不行了，所以认真的再研究一下子。（这是黑厂的最后一个故事，该换世界观了，突然觉得时间过得好快）我用一个比较形象的方法来解释吧。int sum=16909060; 有个叫作sum的房子，里面有四个房间（int 为4个字节，char为1个，short为2个......），住着一个叫 16909060的家庭 ，这个家庭有 0x01 02 03 04 四个人（16进制），01 02..

原创 归并排序求逆序对

今天是2018.11.9，明天就是NOIP，感觉自己基本数据结构已经差不多掌握了，但是在与学长luo y b对拍板子的时候突然发现逆序对和归并排序这个盲区，花了1小时差不多补上了。为了NOIP RP ++ ，特此水一篇，供以后的OIER借鉴。（PS.也许是人生最后一篇呢...）下面贴代码：void msort(int s,int t){ if(s==t) return; int m...

原创 dijkstra堆优化

再求单源最短路径时，算法有优劣之分，个人认为在时间方面 朴素dijkstra&gt;bellmanford&gt;SPFA&gt;dijkstra+heap，所以掌握dijkstra堆优化对于OIER是必要的。本文主要解说迪杰斯特拉堆优化的板子以及它所用到的知识；dijkstra算法、快读、stl以及链式前向星请自行百度或者看我的其他文章。代码如下，注释个人觉得已经很清楚了。#inc...

原创 动态规划的个人感想

半停课状态的这几天，我猛肝了一波动态规划，突然有了以下一些思路和感想。1. 大多题目都可以使用动态规划来做，只是时间和空间是否允许的问题。  1.1 使用f数组描述状态，如果描述不清，加一维；还描述不清，再加一维。直到算法的时间或空间gg为止。n个[ ]可能大多数情况无法实现，但是我认为客观存在这种算法。  1.2 当[ ]与[ ]之间存在直接联系（比如横纵坐标的某些关系）或与其他[ ...

原创 无限读入的两种方式

有时候我们会遇到无限读入的题目，需要按ctrl+z+enter结束输入，所以掌握无限读入的方法以应对毒瘤。scanf() 返回的是已经成功读入元素的个数。int n=0；方法一：while(scanf("%d",&amp;a[++n])!=EOF)；EOF是一个计算机术语，为End Of File的缩写，在操作系统中表示资料源无更多的资料可读取。ps.    EOF=-1...

原创 哈希开链法详解c++

一、概述这是哈希的一种算法，算是冲突比较少的，但是也难免会有。这是我们需要探究的问题，开链法就是好方法之一。开链法原理比较简单，代码比较玄学，大家要在学习的过程之中动手模拟，才能完全掌握它。int hash(string h){ int seed=37,p=10007; int ans=0; int len=h.length(); for(int i=0;i&lt;n;...

原创 动态规划之背包01

一、概述动态规划可能是信息学中比较棘手的一块内容了，个人认为本质和搜索比较相似。背包问题01：有N件物品和一个容量为V的背包。第i件物品的价格（即体积，下同）是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。如果我们定义一个二维数组dp[i][j]，dp[ i ][ j ] 表示 在面对第 i 件物品，且背包容量为  j 时所能获得...

原创 分治算法

一、概述分治算法说白了就是把一个大型问题转化为小问题逐个解决。个人感觉和分治算法含有递归的意味。一般步骤：（1）分解，将要解决的问题划分成若干规模较小的同类问题；（2）求解，当子问题划分得足够小时，用较简单的方法解决；（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。总之，分治可以产生贪心，二分，线段树等问题。说实话，分治算法是一种思想，没有什么特定的...

原创 多方法求素数（定义法、埃氏法、欧氏法）

一、概述素数,又称质数，一个你小学到现在都十分苦恼的老朋友。我上小学的时候，老师告诉我说把这个数用已经知道的素数从小到大一点一点试，假如说如果都不能除尽，那它就是个素数。前两天偶然辅导一个小学生的数学作业，发现几乎都使用素数表这个东西。（确实这种东西也比较玄学）那程序如何实现的呢？主要分为三个方法：定义筛法、埃氏筛法、欧氏筛法。各有用途，大家自行理解和使用。二、定义筛法定义法是...

原创 最小生成树（kruskal算法）

一、概述最小生成树问题顾名思义，概括来说就是路修的最短。接下来引入几个一看就明白的定义：最小生成树相关概念：带权图：边赋以权值的图称为网或带权图，带权图的生成树也是带权的，生成树T各边的权值总和称为该树的权。最小生成树（MST）：权值最小的生成树。最小生成树的性质：假设G＝(V,E)是一个连通网，U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U，v∈...

原创 超级简单并查集详解

一、概述并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。其实说白了大部分还是用于寻找两个点是否联通，求最小生成树。二、分析1、背景阐明首先我们需要先阐明一个简单的道理，假如从A城能到B城，从B城能到C城，那么自然A城和C城联通。并查集便是基于这个理论。...