Q779’s Blog

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

Vijos1659 河蟹王国 题解 题目链接：Vijos1659 河蟹王国 题意：维护一个数据结构，支持区间最大值查询、区间加操作 一看就线段树水题 我们在建树时将最大值搞好查询就好了 那么区间加怎么办？ 显然区间加操作会将影响到的最大值增加同一个值，而改变后的最大值在上传时进行更新即可 等于就把线段树板子搬过来改一改就过了… 因为基本原理差不多 代码如下 #include <bits/stdc++.h> using namespace std; #define int long long #define R register #define INF 0x3f3f3f3f3f3f3f3f #define MAXN (int)(1e5+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=='-')f=-1;ch=getchar();} while(isdigi...

UVA1121 Subsequence 题解 题目链接：UVA1121 Subsequence 题意：给定数组，找最短连续子序列使其和大于 \(S\) ，多组数据 解法一 对于区间 \([l,r]\) ，若 \(\sum_{i=l}^{r}a[i]\ge S\) ，那么 \(\forall r'>r (r' \le n)\) 该条件均成立 那么我们只要枚举左端点，二分查找满足条件的最左的右端点，然后找个最小值就行了 区间和用前缀和优化即可 时间复杂度 \(O(n\log n)\) 代码如下 #include <bits/stdc++.h> using namespace std; #define int long long #define R register #define MAXN (int)(1e5+5) #define INF 0x3f3f3f3f3f3f3f3f int n,k; int sum[MAXN]; void proc() { R int mn=INF; for(R int l=1; sum[l]+k<=su...

ubuntu 无法连接至ibus 解决方法 在终端中输入以下指令 ibus-daemon -r -d -x 大概的意思就是把原来的进程杀掉然后启动ibus 然后ibus它就回来了 这篇文章好短啊（

洛谷P1006 [NOIP2008 提高组] 传纸条 题目链接：P1006 [NOIP2008 提高组] 传纸条 题意：网格图， \((1,1)\) 到 \((n,m)\) 找两条不重合的路径，最大价值 注：原题是 \((m,n)\) ，但我不习惯，所以就用 \((n,m)\) 替代（即 \(n\) 行 \(m\) 列）！ 解法一 最烂解法 ，但是能通过此题 设 \(dp[i][j][k][l]\) 表示第一条路径到 \((i,j)\) 的位置，第二条路径到 \((k,l)\) 的位置，能获得的最大价值 由于两条路径正着走反着走都一样，所以我们可以看作从 \((1,1)\) 到 \((n,m)\) 的两条不重合的路径 那么显然 \(dp[i][j][k][l] = \\ \max\{dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]\}+a[i][j]+a[k][l]\) 因为不重复，所以当 \(i=k,j=l\) 时要减去 \(a[i][j]\) 时间复杂度 \(O(n^4)...

UVA10006 Carmichael Numbers 题目链接：UVA10006 Carmichael Numbers 题意：若 \(\forall x (1<x<n) ,x^n\equiv x \mod n\) ，且 \(n\) 为合数，则称 \(n\) 为Carmichael Numbers，多组数据判断 \(n\) 是否是这种数 数据范围 \(2<n<65000\) 合数好处理，直接 \(O(\sqrt{n})\) 暴力判断即可 那么 \(x^n\) 怎么处理呢？ 如果我们去一个一个乘，时间复杂度 \(O(n^2)\) ，直接TLE 因此，我们要用到快速幂 对于 \(x^k\) ，根据整数的唯一分解定理和常识，\(k\) 可以写成唯一的二进制形式 则 \(x^k\) 可以被分解为它二进制位上每一个 \(1\) 的幂的乘积 例如： \(x^{(5)_{10}} = x^{(101)_2} = x^{(100)_2} \times x^{(1)_2} = x^{(4)_{10}} \times x^{(1)_{10}}\) 那么我们只需要把 \(k...