主页

背景 家里的服务器上跑了一些Web服务，而家宽的80/443被ISP ban掉了，很长一段时间内都使用frp类似的工具作内网穿透。 但frp这类工具都存在着一个问题：服务无法在不做改动的情况下，正确获取到用户的IP地址。因为内网穿透的原理可理解为是在VPS上跑一个listener，然后将所有在指定端口收到的请求内容转发到家里服务器上的receiver，这个receiver再在本地向对应服务发送请求内容，而此时包的source ip则变成了本地的IP，因此服务就只能读取到这个本地的source ip了。 要解决这个问题，对于Web服务来说，还可以在VPS上跑一个HTTP反向代理的服务，将真实的IP通过X-Forwarded-IP Header传到家里服务器，服务再从Header中读...

这里列一点东西，以后继续补充。 更换枚举顺序，让一些不在dp式子左边的变量出现在最内层，方便接下来优化。 （感觉非常常用）预处理后缀/前缀和，省去一些连续的枚举 删掉无用状态 树链剖分 CF1249F Maximum Weight Subset 题意 给你一棵树，有 $n$ 个节点，每个节点有点权 $a_i$。你需要选出若干个节点，满足任意两个之间距离（即简单路径上的边数）$\gt k$，求点权和的最大值。 思路 首先不难想到，我们可以设计一个状态 $f_{u,i}$ 表示 $u$ 子树中，$u$ 到最近一个选中的节点距离为 $i$，且子树中选中的节点距离 $\gt k$ 时，最大的权值和。 那么就直接按照这个思路来写一个转移。 int f[220]...

题意 给你一个串 $s$，和 $m$ 个串 $t_i$，要求你回答 $q$ 个询问，每个询问有四个参数 $l,r,pl,pr$，要求你在 $t_{[l,r]}$ 中找出 $s_{[pl,pr]}$ 的出现次数。 题解 类似于这种需要查询出现次数的，都应该联想到SAM。而我们学习SAM时，有一道类似的题，不过 $t$ 串只有一个。那道题我们是将 $t$ 串插入SAM，并将 $s_{[pl,pr]}$ 在SAM上找到，通过 $topo$ + 跳 $fail$ 来算出出现次数。 这道题的区别在于 $t$ 串有多个，且询问时需要在指定范围内查找。我们先解决一个简单版问题——假设 $l=1,r=m$。 那么就和那个简单题是一样的，不过我们要将所有串插入SAM。这里既可以拼成一个整串，然...

题面 给出一个大小为 $n$ 的无向图，求使得任意两点间只有1～2条简单路径的加边方案数。（$n \leq 20$）。 题解 首先可以知道最终这个图要么是个树，要么是一个树多了一条边（也就是基环树）。 那么我就不会了。。。 后面了解到了 Prufer序列 这个神奇的东西，大致是一个可以 Serialize/Deserialize 一棵树的东西。利用这个东西呢，可以推出在 $n$ 个点的图中，使所有 $k$ 个联通块加 $k-1$ 条边联通的方案数恰好是$n^{k-2}\cdot\prod\limits_{i=1}^k siz_i$ 然后呢，就比较好做了。 Case 1. 原本就有个环 数一下联通块，直接上Prufer联通求方案数即可。 Case 2. 原本没有环 首...

题意 有无限个质量为 $4$ 的幂的砝码，给定正整数 $n$，在使用的砝码数量尽可能少的情况下，求称量重量为 $n$ 的金子的方案数。($1 \leq n \leq 10^{1000}$) 题解 想想可以怎么凑出最后的 $n$，首先你可以全放在右盘；或者，也可以放更大的在右盘，再放些小的在左盘。 可以倒着考虑每位，因为显然想要凑出$(33)_4$，你不会选择放$15 \times 4^0$，而只会直接在当前位放需要的砝码数量（$3 \times 4^0$），或是放一个大一点的，再减去若干个小的（$1 \times 4^1 - 1 \times 4^0$）每位的影响最多只会在 $1$ 的幅度内影响到上一位（也就是在上一位借 $1$）。 那么就可以开始写转移啦。这里用顺推，设翻转...

题意 给你一个图，需要给每个点分配一个信息中心，在点上建立信息中心需要花费 $k$；此外，传输代价为d[点到其中心的距离]。求最小总代价及分配方案。 题解 开始发现dp状态不是很好设计，所以可以考虑dp的性质——无后效性，即无需考虑当前会对未来造成什么影响。 而当前状态是由之前的状态（叶节点的状态转移而来），所以可以设 $f_{u,i}$ 表示 $u$ 子树被分配到 $i$ 的代价。 转移的时候就讨论一下叶节点是否也分配到了 $i$ 即可。 初始状态？ 在叶节点时 $f_{u,i}=k+d[dis_{u,i}]$ 向上推，如果和某一个儿子使用一样的中心，那么就减去重复的k即可；如果不用一样的中心，那么就选儿子最小代价的方案转移过来。 所以 $f_{u,i}=k+d[d...

解决的问题 已知 $n$ 次函数上的 $n$ 个不同点，求解析式/某个 $f(x)$ 的值。 方法 我们可以用一个通用的方法构造一个满足条件的函数： \[\begin{aligned} f(x) =&\{y_1 \cdot \frac{(x-x_2)(x-x_3)...(x-x_n)}{(x_1-x_2)(x_1-x_3)...(x_1-x_n)}\}\\ +&\{y_2 \cdot \frac{(x-x_1)(x-x_3)...(x-x_n)}{(x_2-x_1)(x_2-x_3)...(x_2-x_n)}\}\\ +&\{y_3 \cdot \frac{(x-x_1)(x-x_2)...(x-x_n)}{(x_3-x_1)(x_3-x_2)...(x...

题意 有⼀排阶梯，每列的⾼度不减，且是 $1$ 到 $7$ 的整数，⾼度为 $i$ 的阶梯有 $w_i$ 个，现在你需要给阶梯的某些边缘上⾊，要求边缘必须上⾊，且不能框出 $1∗1$ 的⼩正⽅形。求⽅案数对 $10^9+7$ 取模。 题解 每列的高度只能是1-7，这个数字很小，那么可以将每列上色情况用二进制表示。只记录中间的横边及右侧的竖边即可开始转移。 假如记有颜色的为0，没颜色的为1，记左侧（上一列右侧）为 $i$，右侧为 $j$，中间的为 $k$，那么可发现如果 $i j k k«1 == 全1$，则成立。 把 $i,j$ 作为矩阵行列，个数放入转移矩阵，ksm一下就可以啦。 代码 ...