constexpr_ll

摘要： 拉格朗日插值法 拉格朗日插值法是一种简单经典的多项式插值法，它通过构造一个不超过 \(n-1\) 次的多项式来确定平面上的 \(n\) 个点 \((x_i,y_i)\) 即给定 \(n\) 个有序对 \((x_i,y_i)\)，求一个函数 \(f(x)\)，使得 \(f(x_i)=y_i\)。 怎么 阅读全文

摘要： 五年级 xxs 赛时被卡溢出了呜呜呜。 推式子 这个推式子推了我半小时，感觉推复杂了，不过也在赛后补题的时候过了。 什么文字的太多了，直接看形式化题意，让我们求 \[\sum_{1 \le l<r \le n} \sum_{l \le i<j \le r} [(j-1)k+a_j'-(i-1)k+a 阅读全文

摘要： 整除分块是什么 整除分块（又称数论分块）是数论中一种用于高效计算含有求和公式的技巧。当我们需要计算含有 \(\left \lfloor \dfrac ni \right \rfloor\) 的求和公式的技巧。 当我们需要计算 \[\sum_{i=1}^n f(i) \cdot g(\left \lf 阅读全文

摘要： 前言 欢迎收看五年级飞舞 xxs 撰写的不等式专题，大佬们不喜勿喷，觉得好的话可不可以留个点赞再走哦（有点无耻）。 本文主要讲述均值不等式的证明。 提醒 建议掌握高中数学的大佬观看。 均值不等式 正如本文标题，均值不等式的英文就是 AM-GM inequality。 均值不等式就是： 对于任意的非负 阅读全文

摘要： 省流：二维树状数组 题目传送门 对于一个二维前缀和： \[\sum_{i=1}^{x} \sum_{j=1}^{y} \sum_{u=1}^{i} \sum_{v=1}^{j} c[u][v] \]但是后面两个 \(\sum\) 其实可以变成 \[\sum_{i=1}^{x} \sum_{j=1}^ 阅读全文

摘要： 省流：带权并查集 题目传送门 带一个飞船与其所在列队头的距离就行了。 code #include <bits/stdc++.h> #define DEBUG #define Ofile(s) freopen(s".in", "r", stdin), freopen (s".out", "w", st 阅读全文

摘要： 省流：加个环至于绿吗？ 题目传送门 看到环——断环为链，即 for (int i = 1; i <= n; i++) a[n + i][n + i] = a[i][i]; 这题就是加了一个环和一个最大值，其他都没啥区别，参见 弱化版学习笔记 最后放一个 AC code code #include < 阅读全文

摘要： 省流：弱化版还是太弱化了。 题目传送门 为什么叫弱化版呢？因为他是一个链，不是环！ 这个区间 DP 还是比较经典的，先统计一下 AC 数量 前缀和 for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i]; 设 \(dp_{l,r}\) 表示合并 阅读全文

摘要： 省流：毒瘤字符串 题目传送门 没事中间加个转中缀干嘛？害的我当年调了一上午。 这个就是栈的经典板子后缀表达式的一个加强版，需要先中缀转后缀再求答案。 灵活变通，压两个栈不就行了。 中缀转后缀： string zhongzhui(string s){ mp['+'] = 1; mp['-'] = 2; 阅读全文

摘要： 省流：区间 DP 水题 题目传送门 顾名思义，“项链”说明这个题是一个环，我们可以使用类似 这题 的操作，断环为链，就是在原数组后面拼一截： for (int i = 1; i <= n; i++) a[i + n] = a[i]; 然后正常区间 DP 即可。 设 \(dp_{l,r}\) 表示合并 阅读全文