regularization

[洛谷传送门](https://www.luogu.com.cn/problem/AT_arc146_c "洛谷传送门") [AtCoder 传送门](https://atcoder.jp/contests/arc146/tasks/arc146_c "AtCoder 传送门") 好可爱的题啊。 没 ......

[洛谷传送门](https://www.luogu.com.cn/problem/AT_arc139_d "洛谷传送门") [AtCoder 传送门](https://atcoder.jp/contests/arc139/tasks/arc139_d "AtCoder 传送门") 看成方案数想了 1 ......

[洛谷传送门](https://www.luogu.com.cn/problem/AT_arc132_e "洛谷传送门") [AtCoder 传送门](https://atcoder.jp/contests/arc132/tasks/arc132_e "AtCoder 传送门") 感觉挺 educa ......

[洛谷传送门](https://www.luogu.com.cn/problem/AT_arc132_f "洛谷传送门") [AtCoder 传送门](https://atcoder.jp/contests/arc132/tasks/arc132_f "AtCoder 传送门") 没见过这种在新运算 ......

[洛谷传送门](http://https://www.luogu.com.cn/problem/AT_arc139_c "洛谷传送门") [AtCoder 传送门](https://atcoder.jp/contests/arc139/tasks/arc139_c "AtCoder 传送门") ~~ ......

[洛谷传送门](https://www.luogu.com.cn/problem/AT_arc132_d "洛谷传送门") [AtCoder 传送门](https://atcoder.jp/contests/arc132/tasks/arc132_d "AtCoder 传送门") 提供一个 dp 思 ......

这题太神仙了吧！感觉还不是很懂，但是尽力理一下思路。 设 $t_x$ 为最大的 $j$ 使得 $i_j = x$，不存在则 $t_x = 0$。 设 $1 \sim n$ 的数按照 $t$ 从小到大排序后是 $p_1, p_2, ..., p_n$，设 $q_i$ 为 $i$ 在 $p$ 中的排名， ......

[洛谷传送门](https://www.luogu.com.cn/problem/AT_arc130_c "洛谷传送门") [AtCoder 传送门](https://atcoder.jp/contests/arc130/tasks/arc130_c "AtCoder 传送门") 分类讨论，但是写起 ......

[洛谷传送门](https://www.luogu.com.cn/problem/AT_arc133_e "洛谷传送门") [AtCoder 传送门](https://atcoder.jp/contests/arc133/tasks/arc133_e "AtCoder 传送门") 其实是套路题，但是 ......

洛谷传送门 AtCoder 传送门 技巧性比较强的题（？ 设 $a$ 为最优解的 $A$，则 $a$ 可以贪心构造，就是每一位都取到下界。 考虑设 $b_i = \frac{a_i}{i}$，因为 $i \times b_i < (i + 1) \times b_{i+1}$，则 $b_{i+1} ......

AtCoder Regular Contest 159 传送门 A - Copy and Paste Graph 图的邻接矩阵为 $$ \left( \begin{matrix} A & A & \cdots & A \ A & A & \cdots & A \ \cdots & \cdots & ......

洛谷传送门 AtCoder 传送门 It's all MAGIC 这种题目一般先考虑局面要满足什么条件能必胜，然后根据这个性质来计数。 如果把黑板上的数写成一个集合 $S$，那么： $\varnothing$ 为必胜态，${1}, {2}$ 显然为必败态，打表发现其他单元素集合都为必胜态； 如果 $ ......

洛谷传送门 AtCoder 传送门 不难猜想有解充要条件为 $n \ge 5$ 且 $\frac{n(n-1)}{2} \bmod 3 = 0$。 发现如果钦定一个点的出边都为同一种颜色，那么条件 $2$ 一定满足。 那么题目等价于把 ${0,1,...,n-1}$ 分成 $3$ 组使得每组的和相等 ......

洛谷传送门 AtCoder 传送门 观察可以发现： 使每支箭的距离都为 $D$ 一定不劣； 每支箭坐标一定为整数； 设最左边的箭坐标为 $x$，那么 $x$ 太小时可以把最左边的箭移到最右边，$x$ 太大时可以把最右边的箭移到最左边。计算可得 $x$ 的最优取值范围为 $x \in [-\left\ ......

Regularization 正则化 课件翻译 Modeling Nonlinear Relation 非线性关系建模 上节课学了线性模型但是非线性模型也很重要 考虑一个由基函数的线性组合定义的模型 在数学中，基函数是函数空间中特定基底的元素。 函数空间中的每个连续函数可以表示为基函数的线性组合，就 ......

洛谷传送门 AtCoder 传送门 考虑判断有无解。把序列分成 $c = \left\lceil\frac{len}{k}\right\rceil$ 段，则 $\forall a_i \le c$ 且 $\sum\limits_{i=1}^n [a_i = c] \le ((len - 1) \bm ......

洛谷传送门 AtCoder 传送门 我一年前甚至不会做/qd 发现 $a_{x_1}$ 为 $k = \min\limits_{i=1}^n a_i$ 时最优。然后开始分类讨论： 如果 $\min\limits_{a_i = k} a_{i+n} \le k$，答案为 $(k, \min\limit ......

洛谷传送门 AtCoder 传送门 很典但是并不会做…… 设 $s_i = \oplus_{i=0}^n i$，所求即为： $$\sum\limits_{l=L-1}^R \sum\limits_{r=l+1}^R [s_l \oplus s_r = V]$$ 考虑把它化成下界相同的形式，即求： $ ......

洛谷传送门 AtCoder 传送门 考虑把所有 $a_i = a_{i+1}$ 的位置断开，分别计算然后把方案数乘起来。接下来的讨论假设 $a_i \ne a_{i+1}$。 考虑一个 dp，设 $f_i$ 为 $[1,i]$ 最后剩下的集合的方案数。转移需要从之前所有可以被删的区间转移过来。 现在 ......

洛谷传送门 AtCoder 传送门 首先将度数 $-1$。 设 $f_i$ 为体积为 $i$ 至多能用几个物品凑出来，$g_i$ 为至少。 我们现在要证明一个东西：$x \in [g_i, f_i]$，$(i, x)$ 合法。 首先若 $(s, x)$ 合法，那么必须满足 $s - x \in [- ......

洛谷传送门 AtCoder 传送门 很厉害的题！ 考虑所有车站已确定，如何求 $0$ 到 $n+1$ 的最短路。设 $g_{i,0}$ 为只考虑 $0 \sim i$ 的点，到 $i$ 和它左边第一个 $\text{A}$ 的最短路，$g_{i,1}$ 同理。有转移： 若 $s_{i-1} = \t ......

洛谷传送门 AtCoder 传送门 对每个红格的行和列连边，建出二分图。对于二分图中的每个连通块分别考虑。 大胆猜测对于每个连通块，我们都能够进行适当的操作，使得只有一行/一列没被操作（显然不能使所有行和列都被操作）。对应的方案就是随便取一棵生成树，把不被染白的那一行/列拎出来当根，然后自底向上，每 ......

洛谷传送门 AtCoder 传送门 **差分约束算法：**给出 $m$ 个不等式形如 $x_{a_i} \le x_{b_i} + y_i$，求是否有解。 考虑把不等式看成图上的三角不等式 $dis_v \le dis_u + d$，连边 $(b_i, a_i, y_i)$，以 $x_i$ 最大的位 ......

洛谷传送门 AtCoder 传送门 很神奇但是经典的构造，学习一下。 注意到题目给的操作很像斐波那契。但是难点是如何将 $O(\log n)$ 个斐波那契数相加。 考虑一个操作序列 $4,3,4,3,...$（共 $m$ 个）。发现在第 $i$ 个操作之前给 $x$ 或 $y$ 加 $1$，等价于最 ......

Real Scenario(现实场景) Here's the scenario: you're given the job of checking the pages on a web server for doubled words (such as "this this"), a common ......

洛谷传送门 AtCoder 传送门 从高到低按位考虑。 设当前位有 $k$ 个 $1$。 如果 $k \bmod 2 = 0$，这意味着 Alice 如果选了一个数，Bob 可以选相同的数。发现可以分成 $(0,0),(1,1)$ 两组，递归下去即可。 如果 $k \bmod 2 = 1$，意味着答 ......

洛谷传送门 AtCoder 传送门 感觉挺典的，~~为啥有 2500 啊（~~ 观察发现，反转序列对 $\sum\limits_{i=1}^{n-1} |a'i - a'{i+1}|$ 影响不大。具体而言，设反转了 $a_l \sim a_r$，记 $s = \sum\limits_{i=1}^{n ......

洛谷传送门 AtCoder 传送门 第一步就没想到 可以考虑化简限制。设所有点按 $E_i$ 从小到大排序后顺序是 $p_1,p_2,...,p_n$。发现只需满足 $E_{p_{i+1}} - E_{p_i} \ge \operatorname{dis}(p_i, p_{i+1})$。证明是对于任 ......

洛谷传送门 AtCoder 传送门 很强的博弈 + 性质题。下文令 A 为 Takahashi，B 为 Aoki。 发现单独考虑一个序列 $a_1,a_2,...,a_n$： 若 $n \bmod 2 = 0$： 若 A 为先手，答案为 $\max(a_{\frac{n}{2}}, a_{\frac ......

洛谷传送门 AtCoder 传送门 不妨假设 $B_X \le B_Y$。设 $f(x) = A_X + \frac{x}{B_X}, g(x) = A_Y + \frac{x}{B_Y}, F(x) = \left\lfloor{f(x)}\right\rfloor, G(x) = \left\l ......