WORIA

数学   大整数    加减乘除，取模，逻辑运算符，输入，输出，绝对值，幂   1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891 ...

https://codeforces.com/contest/1659 D. Reverse Sort Sum   题意：有一个长为 nnn 的数组 AAA，共操作 nnn 轮，第 iii 轮操作对 AAA 中前 iii 个元素排序，把这 nnn 轮得到的 nnn 个数组对应位置相加，得到数组 CCC，先给定数组 CCC，要求还原出数组 AAA。 双指针 目的是找出 AAA 中所有 000 的位置。 一个指针指向当前轮的第一个 111，另一个指针指向当前知道的最后一个 000。 现在移动指向 000 的那个指针，若下一个位置是 111，则得到的数组和上一轮相同，那么指向第一个 111 的指针所在位置上的元素和+1（因为它这一轮还是 111）；若下一个位置是 000，则指向第一个 111 的指针所在位置上的元素和从此以后不再增加（因为它以后将始终是 000），所以只要看指向第一个 111 的指针相比于初始状态增加了几，就能知道指向 000 的指针移动了几次后找到了下一个 000​。 为了比较指向第一个 111 的指针相比于初始状态增加了几，就要把所有历史轮次操作组成的矩阵填充成右上部分全 ...

https://codeforces.com/contest/1654 D. Potion Brewing Class   题意：有长为 nnn 的正整数数组 aaa，给定 n−1n-1n−1 个条件，每个条件要求 ai/aj=x/ya_i/a_j=x/yai​/aj​=x/y，问数组所有元素的和，mod 998244353。 dfs nnn 个点，n−1n-1n−1 个条件，刚好建成一棵树，每条边为儿子与父亲的比值，根为 a1a_1a1​，则 ai=a1a_i=a_1ai​=a1​乘 iii 到根的路径上边权的的积。aia_iai​ 是正整数说明 a1a_1a1​ 是所有分母的lcm。求出 a1a_1a1​ 后再遍历求和即可。 但是要取模，无法求lcm。所以质因数分解，记录每个质数的最大出现次数，乘起来就是lcm。 分子要用来约分，所以同样要一路记下来。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626 ...

https://codeforces.com/contest/1647 E. Madoka and the Sixth-graders   题意：房间里有 nnn 个座位，第 iii 个座位上的人的编号为 bi∈{1,2,⋯ ,n}b_i\in\{1,2,\cdots,n\}bi​∈{1,2,⋯,n}，每一轮座位 iii 上的人移动到座位 pi∈{1,2,⋯ ,n}p_i\in \{1, 2,\cdots,n\}pi​∈{1,2,⋯,n}，若多个人移到同一个座位，则编号最小的人留下，其他人永远离开游戏。房间外有无限多的人，编号为 n+1,n+2,⋯n+1,n+2,\cdotsn+1,n+2,⋯，每一轮移动后必定空出座位，房间外的人按编号顺序坐到空座位上。经过若干轮后，最终座位 iii 上的人的编号为 aia_iai​。给定 ai,pia_i,p_iai​,pi​，问初始排列 bib_ibi​，保证有解，输出字典序最小的解。 倍增 把 ppp 建成图，入度为 000 的就是空座位，且每轮都一样。通过空座位上的人的编号可以知道游戏进行了几轮，记为 CCC。 倍增得到 CCC 轮后初始每个座 ...

https://codeforces.com/contest/1658 B. Marin and Anti-coprime Permutation   题意：给定 nnn，问有几种 nnn 的排列 ppp，使得 gcd⁡(1⋅p1, 2⋅p2, …, n⋅pn)>1\gcd (1 \cdot p_1, \, 2 \cdot p_2, \, \dots, \, n \cdot p_n) > 1gcd(1⋅p1​,2⋅p2​,…,n⋅pn​)>1. 数论 gcd只可能是1或2. 假设 gcd=k，则 111 到 nnn 中所有非 kkk 的倍数都必须与 kkk 的倍数相乘。而总共有 ⌊nk⌋\lfloor\frac{n}{k}\rfloor⌊kn​⌋ 个 kkk 倍数，所以必须要 2⋅⌊nk⌋≥n2\cdot\lfloor\frac{n}{k}\rfloor \geq n2⋅⌊kn​⌋≥n，则 k≤2k\le 2k≤2。 1234567891011121314151617181920212223242526272829303132333435363738394041424 ...

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 ...

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∫L​f(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=∫ba​f(ϕ(t),φ(t))ϕ(t)2+φ(t)2​dt 非参数方程： 将x作为参数，同理。 第二型曲线积分∫LP(x,y)dx+Q(x,y)dy\int_L P(x,y){\rm d}x+Q(x,y){\rm d}y∫L​P(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 ...