背包合集
数字组合题意给定 N个正整数，从中选出若干个数，使它们的和为 M，求有多少种选择方案。
思考01背包：n个物品，重量ai，背包容量为m，储存方案数。
123456789101112131415161718#include<bits/stdc++.h>using namespace std;int a[110],f[10010],n,m;int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; f[0]=1; for(int i=1;i<=n;i++){ for(int j=m;j>=a[i];j--){ f[j]+=f[j-a[i]]; } } cout<<f[m];}
自然数拆分题意给定一个自然数 N，要求把 N 拆分成若干个正整数相加的形式，参与加法运算的数可以重复。
注意:
拆分方案不考虑顺序；
...
线性dp合集
最长公共上升子序列 （LCIS）题意对于两个数列 A和 B，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列。
数列 A 和 B的长度均不超过 30003000。
思考状态表示：f[i][j]代表所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合；f[i][j]的值等于该集合的子序列中长度的最大值；
首先依据公共子序列中是否包含a[i]，将f[i][j]所代表的集合划分成两个不重不漏的子集：
不包含a[i]的子集，最大值是f[i - 1][j]；包含a[i]的子集，将这个子集继续划分，依据是子序列的倒数第二个元素在b[]中是哪个数：子序列只包含b[j]一个数，长度是1；子序列的倒数第二个数是b[1]的集合，最大长度是f[i - 1][1] + 1；…子序列的倒数第二个数是b[j - 1]的集合，最大长度是f[i - 1][j - 1] + 1；如果直接按上述思路实现，需要三重循环：
123456789101112131415for (int i = 1; i ...
深度学习基础——week3
[toc]
ResNet网络结构亮点
超深
residual模块
使用Batch Normalization加速训练，不需要使用dropout
残差结构有效解决了梯度消失/爆炸、退化问题
residual结构
重点：
1X1卷积层作用是改变通道数
右边的方法有效减少了参数
重点：
注意stride和通道数的变化
注意虚线部分的作用：改变深度和特征矩阵长宽
BN目的：使得一批（Batch）数据的特征矩阵每个维度满足均值为0,方差为1。(还有$\gamma \quad \beta$)
对象：一批数据，某一个通道的所有特征矩阵
注意：
训练时，traning:True 验证时：traning:False
Batch size 越大越好
bn层建议放在卷积层后，卷积不要使用bias (没用)
$\mu \quad \sigma^{2}$在正向传播过程中统计得到
$\gamma \quad \beta$在反向传播过程中训练得到
迁移学习好处：
快
数据集小也可以有好效果
注意：用别人的预处理方法
常见方式：
载入后训练所有参数，不固定
固定前面参数，只训练最后几 ...
简单数论
理论算数基本定理算术基本定理可表述为：任何一个大于1的自然数 $N$,如果 $N$ 不为质数, 那么N可以唯一分解成有限个质数的乘积 $\boldsymbol{N}=\mathrm{P}_{1}^{ \mathrm{a}_{1} }\mathrm{P}_{2}^{ \mathrm{a}_{2}} \ldots \ldots \mathrm{P}_{\mathrm{n}}^{ \mathrm{a}_{\mathrm{n}}}$, 这里 $\mathrm{P}_{1<} \mathrm{P}_{2<} \mathrm{P}_{3} \ldots \ldots<\mathrm{P}_{\mathrm{n}}$ 均为质数, 其中指数 $\mathrm{a}_{\mathrm{i}}$ 是正整数。这样的分解称为 $\boldsymbol{N}$ 的标准分解式。
约数个数如果 N = p1^c1 p2^c2 … pk^ck约数个数： (c1 + 1) (c2 + 1) … (ck + 1)约数之和： (p1^0 + p1^1 + … + p1^c1) … (pk^0 ...
最近公共祖先
LCA问题一颗有根树，每个点都有若干祖先（自己也是自己的祖先）。两个点最近的一个公共祖先称为它们的公共祖先。
方法：倍增先预处理:
f[i][j]表示i向上走 $2^j $步的祖先结点，递推公式f[i][j]=f[f[i][j-1]][j-1] (n log n)
depth[i]表示i的深度，规定根节点的深度是1，i的深度是到根节点的距离+1。
规定：f[i][j]跳过了，f[i][j]=0 depth[i]=0
求x和y的LCA，分两步来做。先将更深的点跳到浅点的那一层(log n)。然后假设同时往上跳k层，从大到小找k的二进制表示，跳到LCA为止（ log n）。
方法：tarjan (离线)在线做法：边读边做离线做法：先读完，再全部处理，最后全部输出。
Tarjon本质就是对向上标记法的一个优化，任取一个节点当成根节点进行dfs优先遍历，把所有节点分成三部分1）已经遍历并且回溯的标记成22）正在遍历的没有回溯的标记成13）未遍历的标记成0
注意：顺序一定不能乱。1）当这个点遍历子节点后的时候把子节点的祖宗更新成当前点2）只有当前点回溯的时候才可以用这个点来计算所 ...
最小生成树的应用
新的开始 题意：
有 n 口矿井，给他们供电，有两种方法。
在矿井 i 上建立一个发电站，费用为 vi（发电站的输出功率可以供给任意多个矿井）。
将这口矿井 i 与另外的已经有电力供应的矿井 j 之间建立电网，费用为 $p_{i,j}$。s
思考：首先看到这道题，发现条件2有点像最小生成树。直接想比较困难。我们可以虚拟一个超级结点，在i上建发电站的费用vi相当于从这个超级结点到vi连一条边的费用。这就把问题转换为了最小生成树问题。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include <iostream>#include <vector>#include <cstring>#include <algorithm>#include <queue>#include <deque>#include <map>using namespace std;typedef ...
图论中的负环
图论中的负环图中存在一个环，它所含边的权值和是负数。常用方法基于SPFA和抽屉原理
统计每个点入队的次数，如果某个点入队n次，说明存在负环
统计当前每个点中最短路所包含的边数，如果存在某个点的边数对于等于n，说明存在负环（常用，一般来说快一点）。
虫洞题意：比较裸的一道判断负环的题目
思考：直接SPFA
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include <iostream>#include <vector>#include <cstring>#include <algorithm>#include <queue>#include <deque>#include <cmath>#include <map>using namespace std;typedef long lon ...
大臣的旅费(树的直径，树形dp)
大臣的旅费 四届c++ A T10题意：给定一棵树，求直径
思考：方法一BFS。先任取一点，跑一遍bfs找到距离最大的点，再对距离最大的那个点作为起点，跑一遍bfs，就能找到直径了。
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include <iostream>#include <vector>#include <cstring>#include <algorithm>#include <queue>#include <deque>using namespace std;const int N=1e5+10;typedef pair<int,int> PII;typedef long long LL;vector<PII> mp[N];int n,p,q,d,dis[N];bool st[N];LL ans,idx;void bfs(int u)& ...
几种贪心技巧 2(蓝桥杯真题)
付账问题 九届Java A T10题意：现在有 n 个人出去吃饭，他们总共消费了 S 元。其中第 i 个人带了 ai 元。寻找一种付款方式使得标准差最小，输出这个标准差。
思考：带的钱ai小于平均值的话，必须付满ai元，剩下带的钱多余平均值的人，去除前面钱不够的人后，又有了新的平均值，再这样计算即可。
1234567891011121314151617181920212223242526272829#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>using namespace std;typedef long long LL;LL n,s,a[500010];int main(){ cin>>n>>s; for(int i=0;i<n;i++){ scanf("%lld",&a[i]); } sort(a,a+n); ...
股票买卖系列（贪心、dp、状态机）
股票买卖 II题意：给定股票每天的价格a[]，要求计算可以获得的最大利润（交易次数不限，只能买一股）
思考：贪心。若最优解有在第i天买，第j天卖，那么利润等同于连续在i...j 天买卖。所以只要a[i-1]<a[i]，就把它算到利润中去。
12345678910111213141516#include <iostream>#include <algorithm>using namespace std;typedef long long LL;int n,a[100010];LL ans;int main(){ cin>>n; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); if(i!=1&&a[i]>a[i-1]) ans+=a[i]-a[i-1]; } cout<<ans; return 0;}
股票买卖 III题意：在股票买卖 II上加限制： ...
最新文章
