问题索引问题1 寄存器的间接寻址在作业中有一个这样的指令： mov (%eax), %eax 其实我刚开始看的时候，也以为这一步只是内部的一些多余的操纵，但是深入了解后，发现并不是这样。 什么是寄存器？在解决这个问题前，我们应该知道什么是寄存器 给有特定功能的内存单元取一个别名，这个别名就是我们常说的寄存器。 寄存器的间接寻址与直接寻址1、寄存器寻址：是指操作数在寄存器中，由指令操作码中的rrr三位的值和PSW中RS1及RS0的状态，选中某个工作寄存器区的某个寄存器，然后进行相应的指令操作。 2、寄存器间接寻址：将指定的寄存器内容为地址，由该地址所指定的单元内容作为操作数。 也就是说这个指令，其实是以%eax中所存的数作为地址来寻址，并将这个寻到的数放到寄存器%eax中。 为什么要这样做呢？如果你真的深入了解了并思考了T2，你应该知道这个指令是为了后面的$x=a[i]$做准备，因此我们需要得到相对于$a$的首地址偏移量，得到了以后，才能够去以这个偏移后的地址去寻找$a[i]$。 movl -4(%ebp), %eax # 把 -4(%ebp)中的值也就是i 放到%eax ...

题目315. 计算右侧小于当前元素的个数 思路是一个树状数组的运用题，需要从后向前遍历，每次向树状数组中加入一个当前数即可，我们需要查询的是$x-1$. 在2020-04-04的每日一题中提到过，树状数组的下标其实就是数组中的数，但是由于这个题会有负数的存在，因此我们要保证树状数组的下标从1开始，需要把每个数加上一个10001即可。 代码class Solution {public: int len = 20001; vector<int> tree, ans; int lowbit(int x){ return x & (-x); } int query(int x){ int res = 0; for(int i = x; i; i -= lowbit(i)) res += tree[i]; return res; } void add(int idx){ for(int i = idx; i ...

题目307. 区域和检索 - 数组可修改 思路其实就是要我们动态维护一个前缀和数组，因为它涉及改变数组内的值，每次改变都需要重新计算一次前缀和，每次的复杂度是$O(n)$，如果有$n$个这种操作那么就会达到$O(n^2)$的复杂度，此时数据量如果是$1e5$​是过不掉的。 用差分的时候，修改数组内的数是$O(n)$。 鱼和熊掌不可兼得，此时树状数组这个高级数据结构为我们提供了一个折中的办法，让修改数组内的一个数与改变数组内某段数的总和的复杂度都是$O(logn)$。 它的主题思想是分块来实现，设定一个数组$tr[i]$表示区间右边界为$i$，长度为$i-lowbit(i)+1$区间内的所有数的总和，由于篇幅受限，不详细介绍树状数组的详细内容了。 class NumArray {public: vector<int> nums, tr; int len; int lowbit(int x){ return x & (-x); } void add(int idx, int x){ ...

CodeForces Div2 777 C本轮二维矩阵有两个题，都十分的有意思。 题目大意这个题就是按照所给矩阵来利用国际象棋的格子来填充这个棋盘，如果不能把这个棋盘渲染成所给样式返回$-1$，否则返回需要操作的次数以及每次需要改变的矩形的左上角坐标与右下角坐标。 思路需要注意的是这个题并没有让我们要找到最少的变换次数，因此我们可以采用赖皮的方法，因为我们发现如果只用两个格子的国际象棋棋盘来填充黑色格子的话，只要倒着来填充，就可以保证只维护当前的黑色格子，而不改变其他的格子，当$j=1$的时候，需要把$i-1,j$ 这两个格子填充好。 这种最终的操作次数最大也才是$m\times n$，所以基本不会$MLE$。 并且，如果当前棋盘最左上角的格子是黑色，那么一定不能够把该棋盘铺满。因为题目中说了在国际象棋中左上角的格子一定是一个白色格子；其余情况均可以铺满。 代码#include <bits/stdc++.h>using namespace std;const int N = 110;char g[N][N];void solve(){ int n, ...

题目954. 二倍数对数组 思路这个题目就是要求我们找到几个对，这个对满足其中一个数是另一个数的两倍。可以用哈希表来存储数，然后进行模拟判断就好了。 但是我们要注意$map$与$unordered_map$之间的区别，前者是一个严格的红黑树，因此我们如果没有插入某个数的话，是找不到对应的这个数的，并且它的查找复杂度书$O(logn)$，但是$unordered_map$中其实是一个哈希映射，这种映射的好处就是速度快，能够在$O(1)$的复杂度内找到数，在大数据的情况下占优明显。 代码class Solution {public: bool canReorderDoubled(vector<int>& arr) { sort(arr.begin(), arr.end()); unordered_map<int, int> m; for(auto x : arr) m[x] ++; int cnt = 0, len = arr.size(); for(int i ...

题目这个题的大意是给一个串，让我们从前向后找找到回文串或者是合法的括号串，然后删除并从该位置继续找，知道找达不到位置，返回操作的次数以及最后剩的串的长度 思路乍一看并不好下手，其实我们可以考虑分前缀来看，因为本题并没有要求最少的操作次数。 当开头是(的时候，直接向后跳两位，因为这必定是一个回文串或者是合法的括号串。当开头是)，它只能构成回文串，回文串要求以)结尾，可以发现一个惊奇的结果，如果找到最近的)，那么它们一定是一个回文串。 真的是一个绝佳的思路！！ 代码#include <bits/stdc++.h>using namespace std;void solve(){ int n; string s; cin >> n >> s; int l = 0, cnt = 0, r = 0; while (l + 1 < n) { if (s[l] == '(') { l += 2; //如果是左括号的话 那就一 ...

题目728. 自除数 思路简单模拟就行。 代码class Solution {public: bool check(int x){ vector<int> num; int tmp = x; while(tmp){ if(tmp % 10) num.emplace_back(tmp % 10); else return false; tmp /= 10; } for(int i : num){ if(x % i) return false; } return true; } vector<int> selfDividingNumbers(int left, int right) { vector<int> ans; ...

题意给定一个$x\times x$的网格，每个网格都有对应的分数$v_{i,j}$，并且它们都不一样。$G$与$M$一起来玩这个游戏，但每次都是从$M$开始，可以理解为它们的游戏就是取网格中的数，然后在经历了基数非常大的次数(题目中给的是$10^{100}$)后，谁的分数高谁就赢了。她们每次的决策都是最佳的情况，最后请按按网格输出每次赢的名字。 但是她们的游戏有一些限制，比如$M$刚开始放在$x_1$、$y_1$的网格上，$G$再后来放在$x_1’$、$y_1’$的位置上，这两个位置的坐标应该满足曼哈顿距离大于$k$。也就是：$$\lvert x_1 - x_1’\rvert+\lvert y_1 - y_1’\rvert > k$$ 思路这是一个思维力度很大的一个博弈论的题目。其实可以看一下在什么情况下$M$必赢。 因为这些分数都不一样，所以一定存在一个最大数与最小数，当$M$第一次放在的最大数的位置，那么后面都不用玩了，因为此时$M$一定会每次都放在这个位置，由于它最大，因此$G$的每次选择肯定都比它小，在非常大的游戏次数后，她们之间的分数一定越差越多，即$M$必赢。同理放在 ...

UTPC Contest 03-25-22 Div. 2 (Beginner)第一次用这种，感觉好高大上！ 前几题都很简单，封校后每天vp一次。D、E、F应该都很有意思。 D. Gold Coins Game就是给定两个数$n$、$m$，通过操作$-1$或者$\times3$来得到$m$，问最小的步数。这是一个很经典的最短路问题，需要使用$BFS$来解决，不过做的时候并没有写出来，还是不太熟练啊，还得多花点时间在算法竞赛上。这个题目的来源是4300. 两种操作。当时刚学习$BFS$，所以对这个题的印象很深刻。 最短路问题，一定有一个$dist$数组，并且要将它置为一个很大的值才能每次更新；然后就是每次更新的问题，要用当前出队的元素来更新其余的路径。$check$数组是$Dijkstra$特有的，其他最短路模型并没有这个东西。 #include <iostream>#include <cstring>#include <algorithm>#include <queue>using namespace std;const int N = 1 ...

CodeForces Div2 779 C题目大意给一个数$n$，然后给一个序列$C$，$C_i$表示的是第$i$次变换数组的前缀最大值中的数的个数。让我们判断所给出的$C$是否能对应一个正确的序列。 思路这是一个思维题，往往这种题目我们不能够直接的去想怎么构造这个序列，而应该从$C$中寻找规律。我们可以发现的是，每次变换后的$C_i$最多只会增加$1$​，甚至还会减少，但是减少多少我们并不确定，这种情况是某个较大的数被变换到了前面。 需要比较每两次变换之间的关系，其实往往都是从相邻的两次变换中找到关键点的。没有必要用C++中的$rotate$函数来把1放在前面，因为每次变换只满足这两种性质。 另外可以特判一下，每个$C$序列中$1$的个数只能有$1$个，因为最大值一定并且只会出现在序列头部一次。 代码C++方法： #include <bits/stdc++.h>using namespace std;int main(){ cin.tie(0); ios::sync_with_stdio(false); int T; cin >&g ...