Q779’s Blog

洛谷P1486 [NOI2004] 郁闷的出纳员 题解 题目链接：P1486 [NOI2004] 郁闷的出纳员 题意：维护一个数据结构，支持 插入一个大小为 \(k\) 的值，小于下界时不插入 所有元素加上 \(k\) 所有元素减去 \(k\) ，小于下界的删除 查询所有元素中的 \(k\) 大值 最后输出删除的元素个数（两元素相等算两个） 可以用平衡树来解决本题 听说正解是splay，不过我来讲一种替罪羊树的写法 我们可以维护一个 \(d\) ，表示每次加减的变化 这样每个元素就可以用 \(x+d\) 的形式表示了 在平衡树里放原来的数减去插入时的 \(d\) ，即 \(k-d\) 这样输出的时候就是正常的数了 那小于下界的怎么搞呢？ 根据替罪羊树的性质，我们可以直接把整课树重构 在Flatten操作时判断当前元素 \(x\) 加上 \(d\) 是否超过下界，且存在，否则就直接不管它了 \(k\) 大值直接查 \(num1-k+1\) 小值就好了 这个 \(num1\) 表示每次操作后的剩余结点数（两元素相等算两个） 因为它最后还有个询问删除的，再记录一下总插入结点数（...

ubuntu 卸载fcitx输入法 我又来水文章了 打开终端 输入 sudo apt-get remove fcitx sudo apt-get remove fcitx-module* sudo apt-get remove fcitx-frontend* sudo apt-get purge fcitx* 如果您原来使用的就是fcitx输入法，那再输入一句 sudo reboot 重启以后默认就是ibus输入法啦！ ibus大法好！

均值不等式及其证明 引理1 若 \(a\ge 0,b\ge 0\) ，则 \[ (a+b)^n\ge a^n+na^{n-1}b\qquad (n\in \mathbb{Z}^+) \] 证明直接二项式展开即可。 定理1 \[ \dfrac{\sum_{i=1}^{n}a_i}{n}\ge \left(\prod_{i=1}^na_i\right)^{\frac{1}{n}} \] 证明 考虑数学归纳法。 原命题等价于 \[ \left(\dfrac{\sum_{i=1}^{n}a_i}{n}\right)^n \ge \prod\limits_{i=1}^{n}a_i \] 设 \(n=k\) 时原不等式成立，规定 \(\forall i<j,a_i<a_j\) ，并记 \(S_n = \sum_{i=1}^{n}a_i\) 。 当 \(n=k+1\) 时，原不等式为 \[ \begin{aligned} \left(\dfrac{S_k+a_{k+1}}{k+1}\right)^{k+1} &\ge \prod\limits_{i=1}^{k+1}a...

浅谈分块 区间众数 前言 分块大法好（ 本文直接讲例题了 qwq P4168 [Violet]蒲公英 题目链接：P4168 [Violet]蒲公英 题意: 找到区间内编号最小的众数，强制在线 解法一 直接分块 设块长为 \(len\) ，块的总数为 \(t\) 个 我们先预处理出所有以块的端点为端点的区间众数和众数的出现次数 或者说就是把每个连续块组成的区间都算出编号最小众数和它的出现次数 别忘了离散化，不然MLE咯 总共有 \(t^2\) 个这样的区间，每次处理 \(O(n)\) ，则预处理时间复杂度为 \(O(nt^2)\) 暴力查询时可以在预处理过的数组基础上临时更新数组，以统计答案，再复原数组 总时间复杂度 \(O(nt^2+mn/t)\) 假设 \(m\) 和 \(n\) 数量级相同，解 \(nt^2=mn/t\)，\(t \approx \sqrt[3]{n}\) 则时间复杂度可以控制在 \(O(n^{5/3})\) 内 空间复杂度比较大，\(O(nt^2)\) （注：预处理所需） 代码如下 #include <bits/stdc++.h> using n...

LOJ10050 The XOR Largest Pair 题目链接：LOJ10050 The XOR Largest Pair 题意：给定 \(n\) 个非负整数，任取两个数，使得这两个数的异或结果最大，求这个最大值 肯定不是朴素枚举啊qwq 直接用Trie存每个数的二进制就可以了（注：把二进制看作字符串） 根据异或的定义，对于每个 \(a_j\) ，我们从最高位开始，尽可能取与 \(a_i\) 这一位相反的那一条路，一定可以得到最大值 至于最高位，我们只要不够的补 \(0\) 即可 因为它题目中说了每个数最大不大于 \(2^{31}-1\) ，那么我们直接保存为30位二进制即可 代码如下 #include <bits/stdc++.h> using namespace std; #define int long long #define MAXN (int)(1e5+5) #define INF 0x3f3f3f3f3f3f3f3f template<typename T>inline void read(T &k) { char ch=g...

洛谷P6186 [NOI Online #1 提高组] 冒泡排序 题解 题目链接：P6186 [NOI Online #1 提高组] 冒泡排序 题意：支持交换 \(a_x\) 和 \(a_{x+1}\) 和查询 \(k\) 轮冒泡排序后的逆序对个数， \(a\) 数组是长度为 \(n\) 的排列 首先逆序对这个东西可以用树状数组搞定 题目给的是排列，因此求逆序对的伪代码如下 for i=1~n: f[i]=i-sum(a[i])-1,add(a[i],1) 当然如果不是排列会稍微烦一点，可以看下我的这篇文章 设 \(f[i]\) 表示在 \(i\) 左侧比 \(i\) 大的数的个数，那么逆序对就是 \(\sum\limits_{i=1}^{n}{f[i]}\) （注：这里的 \(f[i]\) 就是上面伪代码中的 qwq） 我们看看冒泡排序了 \(k\) 次以后会发生什么事 首先每次冒泡排序所有的 \(f[i]\) 都会减少 \(1\) 当且仅当 \(f[i]>0\) 那么 \(k\) 次之后所有小于等于 \(k\) 的 \(f[i]\) 都会变成 \(0\) 因...

逆序对的三种求法 一、什么是逆序对？ 对于给定的一段正整数序列，逆序对就是序列中 \(a_i>a_j\) 且 \(i<j\) 的有序对 二、怎么求逆序对 1.归并排序解法 归并排序可以很好的解决逆序对问题 我们只需要计算跨越分界线的贡献，并保证分界线两端的答案已被统计，显然根据归并的性质是可以保证的 对于跨分界线的贡献计算很简单，只要在归并排序上加一句就行了 这个东西请您自己理解，没什么好讲的 qwq 代码如下 #include <bits/stdc++.h> using namespace std; #define int long long #define MAXN (int)(5e5+5) template<typename T>inline void read(T &k) { char ch=getchar();T x=0,f=1; while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<...

浅谈树状数组 区间修改&区间查询 一、区间修改，单点查询 首先我们可以先来想一下，树状数组的区间修改，单点查询怎么弄 我们可以维护一个关于原数组的差分数组 很容易知道 \(a_i=\sum\limits_{j=1}^{i}b_j\)，其中 \(b\) 为差分数组 那么区间修改时和差分的差不多，就是add(l,x),add(r+1,-x)表示 \([l,r]\) 加上 \(x\) 单点查询根据上面的结论，就是sum(i) 区间修改，单点查询的代码如下（注：这个不是LOJ132的代码 qwq） #include <bits/stdc++.h> using namespace std; #define int long long #define R register #define MAXN (int)(5e5+5) template<typename T>inline void read(R T &k) { R char ch=getchar(); R T x=0,f=1; while(!isdigit(ch)){if(ch=='-...

UVA11524 Values whose Sum is 0 题解 题目链接：UVA1152 4 Values whose Sum is 0 题意：给定四个数组，求 \(a_i+b_j+c_k+d_l = 0\) 的个数，多组数据+奇怪的输出格式 解法一 \(O(n^4)\) 枚举肯定过不去 想一想，我们有必要在枚举 \(i,j\) 的时候再去枚举 \(k,l\) 吗？ 没有，因为 \(k,l\) 的组合是有限的，只有这么多 我们可以先 \(O(n^2)\) 把所有 \(c_k+d_l\) 枚举出来，然后排个序，就可以二分找出所有的 \(-(a_i+b_j)\) 了 时间复杂度 \(O(n^2\log n)\) 代码如下 #include <bits/stdc++.h> using namespace std; #define int long long #define R register #define MAXN (int)(4e3+5) template<typename T>inline void read(R T &k) { R ch...

洛谷P1985 [USACO07OPEN] Fliptile S 题解 题目链接：P1985 [USACO07OPEN] Fliptile S 题意：二维的开关问题，一次改变该格和四连通格 注：原题是 \((m,n)\) ，但本人不习惯这种表示，所以就用 \((n,m)\) 替代（即 \(n\) 行 \(m\) 列）！ 首先看到题意马上想到搜索，发现状态数 \(2^{nm}\) ，直接起飞 显然我们可以发现对于一个位置，翻转次数至多 \(2\) 次，否则是没有意义的 且翻转的顺序不影响结果，这个性质类似于这题，题解 不同于链接中那题，本题的四连通会有一定影响，不可直接确定 如果您没做过那题没有关系 qwq 我们考虑 \((1,1)\) ，如果它要翻转，那么一定会影响到 \((1,2)\) 和 \((2,1)\) 这样我们又要考虑它右边的，又要考虑它下面的，很麻烦 于是提出设想，如果第一行已经确定了，那是不是可以推出第二行？ 答案是可以的 那么我们就可以枚举第一行的翻转状态，然后再逐行推结果 时间复杂度 \(O(nm2^m)\) 代码如下 #include <bits/s...

洛谷P2882 [USACO07MAR]Face The Right Way G 题解 题目链接：P2882 [USACO07MAR]Face The Right Way G 题意: 固定长度转向，求最小次数和相应的长度 （注：下文中的转向操作均以翻转一词替代 qwq） 首先可以想到搜索，状态数 \(2^n\) ，直接起飞 那么我们来分析一下，可以看出对于一个位置，如果它被翻转了大于 \(2\) 次，那这个一定不是必要的操作 也就是说，一个位置只可能被翻转至多 \(2\) 次 而且通过观察样例，我们可以发现其实翻转的顺序和答案无关 很容易想到我们要枚举 \(k\) （转向的区间长度），然后进行检查 怎么检查呢？我们要从左开始扫一遍，则至多翻转 \(n-k+1\) 次，而每次翻转要 \(k\) 个位置 时间复杂度\(O(n^3)\) ，显然 \(n\le 5000\) 是过不了的 考虑优化翻转操作 为了方便起见，我们可以把 B的位置记为 1，表示要翻转这个位置 记 \(f[i]\) 表示 \([i,i+k-1]\) 是否被翻转 那么如果从左往右扫到一个位置 \(i\) ，怎么判...

洛谷P4085 [USACO17DEC]Haybale Feast G 题解 题目链接：P4085 [USACO17DEC]Haybale Feast G 题意：给定 \(2\) 个由 \(N\) 个数字组成的数列 \(F,S\) ，需要找到使得 \(\sum_{k=i}^{j}F_k\ge M\) 的 \(i,j\) 并输出在所有满足条件的 \(i,j\) 中，\(\max(S_i,S_{i+1},...S_{j-1},S_{j}\))的最小值，数列里每个数非负 解法一 由非负这个条件我们可以得到一个重要结论 对于区间 \(A,B\) ，若 \(A \subsetneqq B\) ，则 \(A\) 的最大值小于等于 \(B\) 的最大值 因此具有单调性 那么我们可以二分答案解决此题 每次判断就 \(O(n)\) 扫一遍看看有没有满足条件的区间即可 时间复杂度 \(O(n\log \max \{S_i\})\) 代码如下 #include <bits/stdc++.h> using namespace std; #define int long long #define...