金晖のBlog

首先翻译成Clike 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495def phase_6: r13 = rsp rsi = rsp read_six_numbers r14 = rsp r12 = 0 .401114: rbp = r13 eax = *(r13) eax = eax - 1 if eax <= 5: goto 401128 explode_bomb .401128: r12 = r12 + 1; if r12 == 6: goto 401153 ebx = ...

第一题 开胃小菜，直接翻译成C代码吧。 123456esi = *(0x402400);eax = strings_not_equal(rdi, rsi);if (eax) return;else explode_bomb; 其中strings_not_equal是接受两个字符串并进行比较，如果不同则输出0. 因此，这个函数是与预设字符串比较，如不同则炸弹爆炸。 利用gdb调试工具，输入命令x/s 0x2400得到内存中存放的字符串输入即可拆解第一个炸弹。 第二题 先翻译成Clike 1234567891011121314151617181920212223242526rsi = rsp;read_six_numbers;if (*rsp == 1) { goto 400f30;}explode_bomb;goto 400f30;.400f17: eax = *(rbx - 4); eax = eax + eax; if (*rbx == eax) { goto 400f25; } explode_bomb;.400f25: rbx = r ...

CSAPP著名实验：DATALAB 内容是关于计算机信息的表示，主要是位操作、整数题和浮点数相关的题。 实验满分截图 bitXor 只用~和&运算符实现异或操作。 123int bitXor(int x, int y) { return ~(~(x & ~y) & ~(~x & y));} tmin 返回INT_MIN 123int tmin(void) { return 1 << 31;} isTmax 不使用移位运算符，计算是否是补码最大值。 123456int isTmax(int x) { int i = x + 1; //0x10000000 int j = i + x; //0x11111111 i = !i; //0x7fffffff = 0,0xFFFFFFFF = 1 return !(~j) & !(i);} 思路是假设当前x为Tmax，然后将其往0x0转化。但是需要注意，对于-1此时值也为0.0xFFFFF ...

这是一个几乎用纯js文件写的拳皇小游戏。目前并不支持联机作战，且没有人机AI，且只有草薙京一名角色，且没有任何技能只有拳击。 特点： 背景音乐播放。分三种状态，战斗、结束战斗、结算挂机 较为流畅的操作体验（得益于HTML5的Canvas标签） 比较神奇的碰撞检测 血条的渐变显示 玩法： 玩家1： W：上跳 D：向右走 A：向后走 SPACE：出拳攻击 玩家2： 方向键上：上跳 方向键左：向左走 方向键右：向右走 ENTER：出圈攻击 源码仓库： 请自己解决跨域问题。 github地址

原题链接 翻译： 给出一个长度为n的数组，对每个元素a[i],可以执行 a[i] = a[i] + a[i] mod 10 无限次。问可不可以构造出一个所有元素相等的数组。 思路： 找规律即可。手算模拟几次发现，除了末尾为5或0的数字需要特判。其他数字在模20后可以统统分成两组，两个集合是对立的，根据这个去check即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980#include<bits/stdc++.h>using namespace std;#define ll long long#define MAXN 200005#define MAXM 200005typedef pair<int, int> pii;#define INF 0x3f3f3f3f#define rep(i, x, y) fo ...

主席树另一模板 在某个历史版本上修改某一个位置上的值 访问某个历史版本上的某一位置的值 每进行一次操作，生成一个新的版本。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071#include<bits/stdc++.h>using namespace std;#define ll long long#define MAXN 1000005int read() { int x=0,f=1;char ch; do{ch=getchar();if(ch=='-') f=-1;} while(ch<'0'||ch>'9'); do{x=x*10+ch-48;ch=getchar();} while(ch>='0&# ...

拓扑排序例题： 模板题1：P4017 传送 题意： 给你一个食物网，你要求出这个食物网中最大食物链的数量。 （这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。） Delia 非常急，所以你只有 111 秒的时间。 由于这个结果可能过大，你只需要输出总数模上 801120028011200280112002 的结果。 输入： 第一行，两个正整数 n,mn,mn,m，表示生物种类 nnn 和吃与被吃的关系数 mmm 。 接下来 mmm 行，每行两个正整数，表示被吃的生物A和吃A的生物B。 输出： 一行一个整数，为最大食物链数量模上 801120028011200280112002 的结果。 思路： 记录下所有入度数为0的节点，将他们的初始状态 dp[i]dp[i]dp[i] 定义为1.之后对于 xxx 的所有后继节点 yyy 定义出度数为0的节点个数为m。 状态转移方程为：dp[y]=max(dp[x]+1,dp[y])dp[y]=max(dp[x]+1,dp[y])dp[y]=max(dp[x]+1,dp[y] ...

带权并查集的一些拙见 路径压缩 这是一个普通的并查集。如果我们对 CCC 执行find操作，最终会得到 AAA ，但是过程中会经过B。如果C的父亲特别多，这步就会消耗相当的时间，我们可以让 CCC 直接指向 AAA ，省去中间的操作进行优化，下图就是希望得到的结果 操作方法就是 将每个节点直接与其find操作最终得到的节点连接一条边 。在 findfindfind 方法中实现 12345678int findx(int x){ if(x!=f[x]) { f[x]=findx(f[x]); } return f[x];} 带权并查集 这就是基于路径压缩的带权并查集的样子。可以看到，在普通并查集的基础上，带权并查集在边中添加了一些额外的信息可以更好的处理问题。在 边上记录额外的信息 的并查集就是 带权并查集 每一条边都记录了节点到根节点的一个权值。基于路径压缩就会产生两个问题： 我们希望得到的是 节点与根节点 的权值。但是在路径压缩之前，每个节点都是与 父节点 连接的，这个权值自然也是和其 父节点 ...

玄学优化&其他算法 个人用到的一些优化/调试技巧，和一些杂七杂八的算法 玄学启发 指数级别, dfs+剪枝，状态压缩dp n≤100→O(n3)n≤100 \rightarrow O(n^3)n≤100→O(n3)，floyd，dp，高斯消元 n≤1000→O(n2),O(n2logn)n≤1000 \rightarrow O(n^2), O(n^2logn)n≤1000→O(n2),O(n2logn)，dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford n≤10000→O(n×n)n\leq 10000 \rightarrow O(n\times \sqrt{n})n≤10000→O(n×n​) ，块状链表、分块、莫队 n≤100000→O(nlogn)n\leq 100000 \rightarrow O(nlogn)n≤100000→O(nlogn)，各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap， prim+heap、spfa、求凸包 ...

图论模板 包括了一些简单的图论内容,不含网络流 树与图的存储 邻接矩阵：mp[a][b]mp[a][b]mp[a][b] 存储边 a→ba \rightarrow ba→b 邻接表： 123456789101112int head[MAXN];//表头int tot;//边的总数struct EDGE { int to, next, val;}edge[MAXM];void add_edge(int from,int to,int val) { //添加一条边 edge[++tot].to = to; edge[tot].val = val; edge[tot].next = head[from]; head[from] = tot;} //初始化tot = 0;memset(head, 0, sizeof head); 树与图的遍历 时间复杂度 O(n+m)O(n+m)O(n+m) nnn 表示点数 ，mmm 表示边数 深度优先遍历： 12345678int vis[MAXN];//标记某个点有没有被遍历过void ...