金晖のBlog

线段树 普通线段树 区间合并 单点修改和查询区间内最大的连续子段和（有负数） 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182int n, m;int a[MAXN];struct segmentnode { int l, r; ll sum, lmx, rmx, mx; //mx表示最大区间和，lsum表示最大前缀和，rsum表示最大后缀和} tree[MAXN << 2];void pushup(int rt) { int suml = tree[rt << 1].mx; int sum = tree[rt << 1].rmx + tree[rt << 1 | 1].lmx; int sumr = tree[rt ...

状态机模型 对于状态机而言，如果上一个状态合法，而且可以转移到当前状态，那么这个转移合法。状态机的转移，就类似于图中两个点连边。主要是判断这个转移是否合法， 如果合法，就添加边。 以没有上司的舞会这题为例，当前上司不参加对应两种状态：其下属参加和下属不参加都是合法的。当前上次参加对应两种状态：其下属参加和下属不参加，那么第一种状态就是非法的。 题目： 街道上有 nnn 家店铺，第 iii 家店铺的财产是 a[i]a[i]a[i] 。小偷不能连续偷两个相邻的店铺。求小偷能获得的最大财产。 如果要偷第 iii 家店铺，那么第 i−1i-1i−1 个店铺不能被偷，因为这是非法的，此时 dp[1][i]=max(dp[1][i−2],dp[0])+a[i]dp[1][i] = max(dp[1][i - 2], dp[0]) + a[i]dp[1][i]=max(dp[1][i−2],dp[0])+a[i] 否则的话 dp[0][i]=max(dp[1][i−1],dp[0][i−1])dp[0][i] = max(dp[1][i - 1], dp[0][i - 1])dp[0][i]=ma ...

旅行计划 （拓扑+DP板子）传送 小明要去一个国家旅游。这个国家有 NNN 个城市，编号为 111 至 NNN ，并且有 MMM 条道路连接着，小明准备从其中一个城市出发，并只往东走到城市 iii 停止。 所以他就需要选择最先到达的城市，并制定一条路线以城市 iii 为终点，使得线路上除了第一个城市，每个城市都在路线前一个城市东面，并且满足这个前提下还希望游览的城市尽量多。 现在，你只知道每一条道路所连接的两个城市的相对位置关系，但并不知道所有城市具体的位置。现在对于所有的iii ，都需要你为小明制定一条路线，并求出以城市 iii 为终点最多能够游览多少个城市。 分析： 状态转移和那道最长路有点像，而且权值还是1，反而更简单了 这居然是个绿题 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include<bits/stdc++.h& ...

简介 Attack Lab 的内容针对的是 CS-APP 中第三章中关于程序安全性描述中的栈溢出攻击。在这个 Lab 中，我们需要针对不同的目的编写攻击字符串来填充一个有漏洞的程序的栈来达到执行攻击代码的目的，攻击方式分为代码注入攻击与返回导向编程攻击。 实验目的 官方文档https://csapp.cs.cmu.edu/3e/attacklab.pdf 这次实验的文件有点多，一一介绍下。具体东西还得参考cmu给出的实验文档，本实验没有该文档几乎都不知道自己该干什么。 讲义中首先给我们展示了导致程序漏洞的关键：getbuf 函数。 123456unsigned getbuf(){ char buf[BUFFER_SIZE]; Gets(buf); return 1;} getbuf 函数在栈中申请了一块 BUFFER_SIZE 大小的空间，然后利用这块空间首地址作为 Gets 函数的参数来从标准输入流中读取字符。由于没有对读入字符数量的检查，我们可以通过提供一个超过 BUFFER_SIZE 的字符串来向 getbuf 的栈帧之外写入数据。 在代 ...

首先翻译成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&# ...