上海市大学生程序设计竞赛 - EOJ Monthly 2021.12
https://acm.ecnu.edu.cn/contest/497/
C. Paint
题意：一个长为 nnn 的数组，初始全为0，mmm 次操作，两种：1. 把最后 xxx 个元素全部变为 yyy；2. 查询当前有几个不同的数。
栈
用栈模拟，同时记录每种颜色的出现次数。
1234567891011121314151617181920212223242526272829303132333435363738#include <bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e6 + 10;const int INF = 0x3f3f3f3f;typedef pair<int, int> pii;int n, m;int cnt[N];int ans = 1;stack<pii>st;int main() { scanf("%d%d", &n, &m); st.push({1, 0 ...
EOJ Monthly 2021.10
https://acm.ecnu.edu.cn/contest/463/
D. 赌怪
题意：A，B两人轮流从 [1,1018][1, 10^{18}][1,1018] 各抽取 nnn 张牌，可能重复。抽完后，A 先打出一张牌，B 必须打出一张比 A 大的牌。打出就丢掉。若 B 无法出牌则 A 赢，否则 B 赢。问 A 赢的概率。
卡特兰数
数字范围很大，可以近似认为不会抽到重复的牌。
把 A，B 抽到的牌放一起从小到大排序，必须满足在任意位置 p，从开始位置到位置 p 这个区间中，A 牌的个数大于等于 B 牌的个数。也可以说 A 的最小的牌小于 B 的最小的牌，A 的次小牌小于 B 的次小牌。这两种说法等价。
这其实就和括号序列的合法性是一样的。A 视为左括号，B 为右括号。
所以牌的排列方式个数就是 n 对括号的合法序列数，也就是卡特兰数。
ans=1n+1(2nn)(2nn)=1n+1ans=\frac{\frac 1{n+1}\binom {2n}n}{\binom {2n}n}=\frac{1}{n+1}
ans=(n2n)n+11(n2n)=n+11
12345 ...
高数
仅为考试复习，非笔记！
曲线积分
第一型曲线积分∫Lf(x,y)ds\int_L f(x,y){\rm d}s∫Lf(x,y)ds：
解法：
参数方程：x=ϕ(t)\phi(t)ϕ(t) , y=φ(t)\varphi(t)φ(t).
=∫baf(ϕ(t),φ(t))ϕ(t)2+φ(t)2dt=\int ^a_b f(\phi(t),\varphi(t))\sqrt{\phi(t)^2+\varphi(t)^2}{\rm d}t=∫baf(ϕ(t),φ(t))ϕ(t)2+φ(t)2dt
非参数方程：
将x作为参数，同理。
第二型曲线积分∫LP(x,y)dx+Q(x,y)dy\int_L P(x,y){\rm d}x+Q(x,y){\rm d}y∫LP(x,y)dx+Q(x,y)dy：
解法：
参数方程：x=ϕ(t)\phi(t)ϕ(t) , y=φ(t)\varphi(t)φ(t).
=∫ba[P[ϕ(t),φ(t)]ϕ′(t)+Q[ϕ(t),φ(t)]φ′(t)]dt=\int ^a_b [P[\phi(t),\varphi(t)]\phi&#x ...
单链表找环
数据结构考试题
上课没听导致做不出来。。
快慢指针
设指针 slow，fast 的步长分别为 111 和 222，且都从头节点出发。
结论1：最终两个指针会在环中相遇，且此时慢指针 slow 还未走完环一圈。
证明：
设整个链表的线性部分长度为 xxx，环的长度为 nnn，相遇时 slow 指针在环中走了 SSS 步。
假设 S≥nS\geq nS≥n
则 slow 指针总共走了 x+Sx+Sx+S 步，由于 fast 指针速度为 slow 指针2倍，所以 fast 指针走了2x+2S2x+2S2x+2S 步。
则 slow 指针在环中走了 L(slow)=SL(slow)=SL(slow)=S 步，fast 指针在环中走了 L(fast)=x+2SL(fast)=x+2SL(fast)=x+2S 步。
L(fast)−L(slow)=(x+2S)−S=x+S>SL(fast)-L(slow)=(x+2S)-S=x+S>S
L(fast)−L(slow)=(x+2S)−S=x+S>S
若 S≥nS\geq nS≥n，则 L(fast)−L(slow)>n ...
逻辑回归康复笔记
逻辑回归是分类!!
理论证明及交叉熵误差见https://blog.csdn.net/weixin_39445556/article/details/83930186
对于输入x，输出 $ h_{\theta}(x) = g(\theta^{T}x)$
其中 $ g(z)=\frac{1}{1+e^{−z}} $，即Sigmoid函数。
123#定义sigmoid函数def sigmoid(z): return(1 / (1 + np.exp(-z)))
损失函数
假设输入X为m维向量
$$ J(\theta) = \frac{1}{m}\sum_{i=1}^{m}\big[-y^{(i)}, log,( h_\theta,(x^{(i)}))-(1-y^{(i)}),log,(1-h_\theta(x^{(i)}))\big]$$
向量化的损失函数(矩阵形式)
$$ J(\theta) = \frac{1}{m}\big((,log,(g(X\theta))^Ty+(,log,(1-g(X\theta))^T(1-y)\big)$$
12345678910#定义损失函数def ...
莫比乌斯函数/反演
前置
数论函数：定义域为正整数的函数。
积性函数：∀(a,b)=1,f(a⋅b)=f(a)⋅f(b),f\forall (a,b)=1,f(a\cdot b)=f(a)\cdot f(b),f∀(a,b)=1,f(a⋅b)=f(a)⋅f(b),f为数论函数。
莫比乌斯函数与欧拉函数都为积性函数。
迪利克雷卷积：
(f∗g)(x)=∑d∣xf(d)⋅g(xd)(f*g)(x)=\sum_{d|x}f(d)\cdot g(\frac{x}{d})
(f∗g)(x)=d∣x∑f(d)⋅g(dx)
迪利克雷卷积的单位元：
e(n)=[n=1]={1,n=10,n≠1e(n)= [n=1]=\begin{cases}
1, & \text {$n=1$} \\
0, & \text{$n\neq 1$}
\end{cases}
e(n)=[n=1]={1,0,n=1n=1
对于任意 fff 有：
e∗f=∑d∣xe(d)f(xd)=fe*f=\sum_{d|x}e(d)f(\frac{x}{d})=f
e∗f=d∣x∑e(d)f(dx)=f
莫比乌斯函 ...
网络流24题
2019/11/27 洛谷开坑
2019/12/6 完结
飞行员配对方案问题
https://www.luogu.com.cn/problem/P2756
简单二分图匹配，匈牙利算法即可。
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include<bits/stdc++.h>using namespace std;#define ll long longtypedef pair<int, int> pii;const int INF = 0x3f3f3f3f;const int maxn = 1e3 + 10;int V;vector<int>G[maxn];int match[maxn];bool used[maxn];void add_edge(int u, int v) { G[u].push_back(v); G[v].push_back(u); ...
线性回归康复笔记
损失函数
线性回归与逻辑回归的损失函数是不一样的！！
线性回归是回归算法，所以是连续的，而逻辑回归是分类算法。
x⃗=(x1,x2,x3…xn)\vec x = (x_1,x_2,x_3 \dots x_n)
x=(x1,x2,x3…xn)
f(x)=w1x1+w2x2+w3x3+⋯+wnxn+bf(x) = w_1x_1+w_2x_2+w_3x_3+ \dots + w_nx_n + b
f(x)=w1x1+w2x2+w3x3+⋯+wnxn+b
minS=12n∑i=1n(f(xi)−yi)2minS = \frac {1} {2n} \sum_{i=1}^{n} {(f(x_i)-y_i)^2}
minS=2n1i=1∑n(f(xi)−yi)2
其中的 1n\frac1 nn1 只是将代价函数值归一化的系数。
表示每一个训练点 (xi,yi)(x_i,y_i)(xi,yi) 到拟合直线 yiˆ=θ⋅xiy_iˆ=θ⋅x_iyiˆ=θ⋅xi 的竖直距离的平方和，通过最小化上面的损失函数可以求得拟合直线的最佳参数 θθθ 。
这里的损失函数之所 ...
线代
仅为考试复习，非笔记！
同型的两矩阵的秩相同 ⇔\Leftrightarrow⇔ 矩阵等价。
两向量组等价 ⇒\Rightarrow⇒ 秩相等。
r(AB)<=r(A)
合同则正负惯性系数相等。
相似则特征值相等。
牛客网提高组模拟赛第七场 T3 洞穴
题意：有向图，问是否存在从 aaa 到 bbb 长度为 LLL 的路径。
状压dp+bitset+倍增优化
取中间点 kkk，若存在 iii 到 kkk 长度为 ppp ，从 kkk 到 jjj 长度为 qqq ，则状态转移得到存在 iii 到 jjj 长度为 p+qp+qp+q 的路径。
所以 dp[i][j][k]∈{0,1}dp[i][j][k]\in \{0,1\}dp[i][j][k]∈{0,1} 表示从 iii 到 kkk 是否存在长度为 jjj 的路径。但是显然这是存不下的，所以把 jjj 变为存在长度为 2j2^j2j 的路径倍增。之所以能这样优化与本题边长都为 111 有关。由于每个 lll 都能被拆为几个二进制的和，所以最终查询时对 lll 再处理。
状态转移方程为
dp[i][j+1]∣=dp[k][j],(dp[i][j][k]=1)dp[i][j+1]|=dp[k][j],(dp[i][j][k]=1)
dp[i][j+1]∣=dp[k][j],(dp[i][j][k]=1)
查询时由低到高遍历 lll，设当前能到点集为 SSS，当前距离为 L1L_1L ...
