overfit
L2正则化
目的:从高维降到低维,以降低overfittingoverfittingoverfitting的可能。
方法:从所有 ∑q=0Qwq2≤C\sum_{q=0}^Q w_q^2\leq C∑q=0Qwq2≤C即∣∣w∣∣2≤c||w||^{2}\leq{c}∣∣w∣∣2≤c的www中选ErrorErrorError最小者。
L2正则化后的www 可能为0的项个数较少,但总的长度固定。
即满足www 在半径为c\sqrt{c}c 的球内。由于要使www 最终达到wlinw_{lin}wlin ,wlinw_{lin}wlin常常在某凸多边形的中心。
类似如图情况:
即所求极值点常在球面上,故可将条件 ∣∣w∣∣2≤c||w||^{2}\leq{c}∣∣w∣∣2≤c变为∣∣w∣∣2=c||w||^{2}={c}∣∣w∣∣2=c
拉格朗日乘数法
问题转化为求f(w)=Einf(w)=E_{in}f(w)=Ein在g(w)=w2−C=0g(w)=w^2-C=0g(w)=w2−C=0 的条件下的条件极值。
拉格朗日乘数法将求 f(w)f(w)f(w)在www 满足一 ...
2018ICPC横滨区域赛
A. Digits Are Not Just Characters
模拟
直接把所有字母处理成数字,相邻数字都合并成一个数字,再逐位比较。
注意数字优先级始终比字母大,所以字母都加上INF
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include<bits/stdc++.h>using namespace std;#define ll long longtypedef pair<int, int> pii;const int maxn = 1e4 + 5;int n;vector<string>a;vector<ll>vc[1010];string s;bool cmp(int x, int y) {//x<y true int i = 0, j = 0; while (i < vc[x].size() && j < vc[y] ...
杜教筛学习笔记
用途&复杂度
杜教筛可用于计算一些积性函数的前缀和:∑i=1nf(i)\sum_{i=1}^nf(i)∑i=1nf(i)。
时间复杂度 n2/3n^{2/3}n2/3,需要预处理出 n2/3n^{2/3}n2/3 数据量的前缀和。
原理
令 S(n)=∑i=1nf(i)S(n)=\sum_{i=1}^nf(i)S(n)=∑i=1nf(i)。
∑i=1ng(i)S(⌊ni⌋)=∑i=1n(f∗g)(i)\sum_{i=1}^n g(i)S(\lfloor\frac{n}{i}\rfloor)=\sum_{i=1}^n (f*g)(i)
i=1∑ng(i)S(⌊in⌋)=i=1∑n(f∗g)(i)
以上就是杜教筛最关键的点。
证明:
∑i=1n(f∗g)(i)=∑i=1n∑d∣ig(d)f(⌊id⌋)=∑d=1ng(d)(∑i=1⌊nd⌋f(i))=∑d=1ng(d)S(⌊nd⌋)\begin{align}
\sum_{i=1}^n(f*g)(i) &= \sum_{i=1}^n\sum_{d|i}g(d)f(\lfloor\frac{i}{d}\rfloor ...
私人云盘与Emby搭建踩坑记录
这两天实在不想复习 : ) 就整了个服务器.趁着还没忘,记一下踩过的坑.
云盘和Emby两个合在一起写了.
私人云盘
先说一下租的阿里云服务器配置
1核 CPU | 2GB 内存 | 40GB SSD | 5Mbps 限制峰值带宽 | 1000GB 每月流量
由于服务器的空间实在太少了,就又租了个阿里云的OSS.
外挂的对象存储OSS
100G | 标准存储包 | 中国大陆通用
由于自己比较菜,我还配置了宝塔的可视化界面,这个在B站也能找到教程视频.ftp工具用的是MobaXterm.
我主要是跟着大佬博客做的.以下只是过程中自己遇到的问题.
大佬视频里讲了三个私有云,我用的是Cloudreve,这一个可能对插件要求更多,所以视频里也讲了,配置的过程比其他两个多一些,之前我没看视频,折腾了半天,就是经不去,真的吐了…
大佬博客里说可能会有权限问题,但我实践过程中755权限也是可以的,如果实在有问题,在宝塔的"文件"界面,找到解压下来的cloudreve文件夹可以直接改权限.
原博客里是php7.2版本,我买的是php7.3,下载扩展的时候也要注意修改.
把 ...
数论专题
牛牛与LCM
题意:问能否从 n 个数中选出一些数,使得lcm=x。
把所有 x 的因子都选出来,看lcm如果不等于x,则不行,否则行。
123456789101112131415161718192021222324252627282930#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3f3f;const int N = 2e6 + 10;const ll mod = 998244353;int n; ll x;ll a[N], lcm = -1;int gcd(int a, int b) { if (a < b)swap(a, b); return b == 0 ? a : gcd(b, a%b);}int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) ...
数字逻辑基础
组合电路
译码器
功能:nnn 个输入变量转化为 2n2^n2n 个输出变量。2进制转10进制。输出外部取反。
例:3-8译码器
把函数转化为析取式,(析取式与合取式互补),再取极小项对应的下标即可。
连接时使能端要全连通,极小项的从高位向低位,连接译码器的高向低。
注意若输出端取反了,则实际输出是极小项的反,不能直接用。
数据选择器
功能:从 2n2^n2n 个输入选择一个输出。最多接受 n+1n+1n+1 个变量。
例:4选1数据选择器
同样把函数化为积之和。
选定一个变量作为数据端,若规定了不能取反,则只能选择在函数中只以原变量的形式出现的变量。
把函数以其它 nnn 个变量二进制递增的形式排好序。
按照二进制由低位向高位分别由上到下连接数据选择端,(与译码器相反)。另一个变量与1,0,按照二进制位对应连接数据端。
数据选择器与译码器的数据端连接顺序不同,译码器直接从左到右连接从上到下,数据选择器按照二进制位对应连接。
优先编码器
功能:10进制转2进制。输入和输出外部都取反。
例:8-3编码器
仅当控制端选通,且输入存在1,即选通且正在编码,YsY_sYs为 ...
并查集/生成树专题
https://vjudge.net/article/2169
Genghis Khan the Conqueror
题意:求出一棵生成树后要增加原图某条边的边权,有多种可能,问新的生成树的期望值。
树形dp
如果增加的边不是生成树上的边,答案显然还是生成树。
而如果是生成树上的边那就要找到一个新边连接原边两个点所在的集合。
可以树形dp对求出的生成树处理出不在生成树上的,连接两个点的不同集合的边最小值。
枚举每个点,作为生成树的根,转化为有根树。
在固定根的情况下,用一个点的子树所有点的最小返祖边(特定是直接连接到根的边)更新这个点与它父亲的dp值。
枚举完所有根之后的dp值就是完整的dp值。
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182#include<bits/stdc++.h>using namesp ...
大物
电容器储存的能量 W=12Q2CW=\frac{1}{2}\frac{Q^2}{C}W=21CQ2
磁导率 μ=BH\mu=\frac{B}{H}μ=HB,相对磁导率 μr\mu_rμr
有气隙时H不同,B相同。H=Bμ0μrH=\frac{B}{\mu_0 \mu_r}H=μ0μrB , H′=Bμ0H'=\frac{B}{\mu_0}H′=μ0B,H的线积分等于两个H的线积分和。
动生电动势 ξ动=∫abV→×B→⋅dl→\xi_动=\int_a^b \overrightarrow{V}\times \overrightarrow{B} \cdot {\rm d}\overrightarrow{l}ξ动=∫abV×B⋅dl
感应电动势 ξ\xiξ 先根据不同的位置 x 求出B,x 为 t 的函数,再求出Ψ\PsiΨ,Ψ\PsiΨ 对 t 求导。
由静电平衡,极板内电场强度为 0. 故相对两极板面的面电荷密度为相反数。两极板中板内一点收到四个面的电场强度和为 0. 则最上面的面电荷密度与其他三个面的和为相反数。
多项式生成函数组合数学专题
快速傅立叶之二
题意:求 ck=∑i=kn−1ai∗bi−kc_k=\sum\limits_{i=k}^{n-1}a_i*b_{i-k}ck=i=k∑n−1ai∗bi−k
FFT
把 aaa 数组翻过来。
ck=∑i=kn−1an−1−i∗bi−k=∑i=0n−1−kan−1−k−ibic_k=\sum\limits_{i=k}^{n-1}a_{n-1-i}*b_{i-k}=\sum\limits_{i=0}^{n-1-k}a_{n-1-k-i}b_ick=i=k∑n−1an−1−i∗bi−k=i=0∑n−1−kan−1−k−ibi。
则 ci=(a∗b)n−i−1c_i=(a*b)_{n-i-1}ci=(a∗b)n−i−1
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283#include &l ...
博弈专题
https://vjudge.net/contest/26587#overview
A - Calendar Game
题意:给定从 1900/1/1 到 2001/11/4 的任意一个日期,每次操作可以跳到明天或者下个月相同日期,先到 2001/11/4 的赢。
判断月份和日期之和的奇偶。
两种操作都会使得奇偶性改变,由于 11/3 是必胜态,所以如果和为偶数,则也是必胜。
有两个特殊的时间,9/30 和 11/30,这两个日期可以从奇数变到奇数,也就使得处于这两个日期可以使对面变为必败态。
123456789101112131415161718#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3f3f;const int N = 2e6 + 10;const ll mod = 1e9 + 7;int T;int main() { scanf("%d", ...