基于python asyncio实现的简单反代

一直想用python实现一个简单的反代工具,最近终于着手做了一下,这篇文章主要是记录一下学习的东西。


参考资料

asycio实现TCP代理

asycio官方文档

解决StreamReader读取长数据一直阻塞

ngrok原理简单分析

设计思路

内网穿透

内网穿透的效果就是把只能在内网访问到的设备和服务暴露在公网上。例如内网的网站,俗称内网外入。

由于个人宽带不一定拥有公网IP,和有对称NAT的存在,所以在内网里可以访问公网的设备能向在公网的服务器请求TCP连接,但服务器却没有办法通过公网向在内网的PC请求连接。

于是可以先由内网设备与在公网的服务器建立一条TCP连接,然后其他设备访问公网服务器的某个端口,所有流量由服务器通过这条连接转发给内网设备。

TCP代理

首先是实现一个基础的TCP代理功能,因为无论是在服务器还是内网设备,都需要转发流量。

原理很简单,就是两个套接字,套接字A用来与服务连接,套接字B用来访问要代理的应用。然后不停地将A收到的发给B,将B收到的发给A。

最后我这里用了asyncio的套接字服务asyncio.start_server

监听套接字接收到新的请求以后会回调handle_proxy

async def join_pipe(reader, writer):
    try:
        while not reader.at_eof():
            writer.write(await reader.read(2048))
    finally:
        writer.close()

async def handle_proxy(local_reader, local_writer):
    try:
        remote_reader, remote_writer = await asyncio.open_connection(
            'jwzx.cqupt.edu.cn', 80
        )
        task_list = [
            asyncio.create_task(join_pipe(remote_reader, local_writer)),
            asyncio.create_task(join_pipe(local_reader, remote_writer)),
        ]
        print(f'New TCP connection link { local_writer.get_extra_info("peername") !r} to { remote_writer.get_extra_info("peername") !r}')
        done, pending = await asyncio.wait(task_list)
    finally:
        local_writer.close()

这个转发部分就是我的反代程序的核心部分了。

server与client

其实Client和Server就是两个几乎一模一样的代理服务器。但又右一点不一样。

考虑到例如http请求,浏览器请求一个页面的时候可能会发多次TCP连接和断开的请求,一旦server和client断开以后,server就没有办法主动连接client了,所以我参考ngrok的设计,也设计了一条Control tunnel的连接一直保持,用来管理用于proxy的通道。

当proxy断开以后,如果接到新的连接请求,就通过Control告诉client,让它与server建立一条新的proxy tunnel,并开始转发。

也就是说Server在监听到外部服务的时候会通知Client发一条新的连接Proxy,将Proxy连接的套接字B与外部的套接字A连在一起进行转发。

Client在监听到Control发来的新请求以后会按照信息向新的端口发连接,成功建立Proxy,得到套接字A以后,再开始与内网服务器建立链接,得到套接字B,然后链接这两个套接字开始转发。

然后就按照外部客户的要求,该发送就发送,该断开就断开。这样虽然每次会断开Server与Client的连接,但代码逻辑更简单了,写起来更方便。

代码实现

Demo

Read the rest

【树】2020ICPC小米网赛1G-Tree Projection

传送门

题意是说给一颗树的拓扑序列,再给它的dfs序列。两次根可能不同。

问你能不能构造出原树。

首先要分析两种序列的性质。

拓扑序和dfs序,排在后面的点肯定是前面的点的子孙。所以后面的点与前面的点连边不能超过1条。

那么有个很简单的想法:

使得两个序列都满足每个点与前面出现的点最多有一条边。

然而很遗憾这是不对的。下面给出一个反例

top:6 4 2 1 3 5

dfs:1 2 3 4 5 6

很显然这样一种构造只能满足拓扑序,不能满足dfs序。

要满足dfs序,还需要满足要满足一个条件:一个点要么是叶子(与后面不连边),要么是某个子树的根(必须与紧接着后面的一个点连边)。

所以需要构造一棵合法的树,每个序列的节点要满足两个两个条件:1. 每个点最多与前面一个点相连。 2. dfs序中的每个点还要满足要么后面挨着的一个点与他相连,要么后面没有点和他相连。

具体做的时候,两个指针i, j枚举dfs序,每次由B[j]向B[i]连边,保证 i < j 而且 i 在过程中单调不减,即可让dfs序列满足条件。同时让B[i]在A中的位置单调不增,即可让拓扑序满足第一个条件。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
const int N = 2e5 + 233;
int a[N], b[N], pos[N];
int main()
{
    // time_t startt = clock();

    // cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
    int n; 
Read the rest

【Splay】HDU20多校9-G Game

传送门

题意是说有一些方块堆积起来的积木。有两种操作。

1 x y 是把第x行从下数第y个方块往左推一个。这会导致有一些方块悬空,这些悬空的方块会受到重力的影响下落。如果可以移动输出移动的方块数量。

2 x 是输出第x列的方块数量。

根据样例分析。

  1. X往左走一格,可以看作XX+1之间插入了一个(y-1)的数。
  2. LX左边第一个小于y的数,假设L的是第rank个,那么R就是第rank+2个。LR之间那个数删掉即可。
  3. L会加上前面那个柱子里掉下来的一些方块。

具体来说,先找到排名x的点X,排名x+1的点XX,把X Splay到根,再把XX Splay到X下面,在XX的左儿子插入一个(y-1)

找到X以前的第一个小于y的点,根据size求出它的排名rank,顺便求出排名rank+1DR的排名rank+2,求出点R,把L Splay到根,R Splay到L下面,删掉… Read the rest

【状压DP】排列 – 阿里2020秋季校招

小强向你请教了一个奇妙的数学题:给定两个数n和m,小强可以通过对n里面的数位进行重新排列。

现在小强请你帮他计算出经过重新排列后所得到的数中满足不含有前导零并且能够整除m的数字有
多少个?

注意:相同的数只算一次

n < 1e15
m < 100

这题是SCOI2007魔改了条件

原题的方案里可以包含前导零。其实只需要判断一下如果当前状态是全0则表示有前导零的状态,不进行转移即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
const int N = 16, M = 110;
ll n, m;
ll f[1 << N][M];
vector<int> v;
bool vis[10];
int ze = 0;

int main()
{
    // time_t startt = clock();

    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
    int T; 
    T = 1;
    while(T--)  
    {
        cin >> n >> 
Read the rest

【贪心】CF448C – Painting Fence

传送门

题意说给n个高度为ai的板子,你可以用宽度为1的刷子横着涂色或者竖着涂色,当遇到空隙或者边缘的时候停止,不可以拐弯。问最少多少次能涂完。

做法是贪心,对于一个区间,如果我要横着涂,那些能一笔涂完的地方我一定要一笔涂完。

而对于一个矩形,很容易算出来到底横着还是竖着划算。

于是对于每个区间,我先把能横着涂的涂完(一个矩形),然后递归没涂的两个部分。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 233;
int a[N];
int solve(int l, int r, int u)
{
    if(l > r) return 0;
    int h = a[l], idx = l;
    for(int i = l; i <= r; i++) h = a[i] < h ? a[idx = i] : h;
    return min(r - l + 1, solve(l, idx - 1, h) + h - u + solve(idx + 1, r, h));
}
int 
Read the rest

【插头DP】Yajilin – 20HDU多校9Y

传送门

题意是说给一个网格,每个格子有一个权值,选择其中一些格子涂黑,要求黑色直接不能临边。然后还需要找到一条哈密顿回路。

问如何选择黑色的格子使得权值最大。

插头DP,0表示无插头,1、2表示对应联通分量的插头,3表示黑色格子的插头。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
const int N = 100007;
int n;
int a[16][16], state[2][N], dp[2][N], now;
int G(int k, int x) {return (k >> (x << 1)) & 3;} // 轮廓线k的第x位状态
int F(int k, int x) {return k << (x << 1);} // 编码第x位的状态k
// unordered_map<int, int> st;
int fst[N], pre[N], mk[N], mt, tot;
void init()
Read the rest

【KMP|DP】不含子串的最少删除次数

题目源于字节跳动2021秋招研发第二场第二题。

题意是说,给长度为n<10^5的字符串,里面包含十六进制数字(0~F),要求让这个字符串不能包含‘0010’这个子串,问最少要删除多少次。

其实这个子串很特殊,对于任意一个字符串,我总能找到一种方法使得我删除一个字符之后0010的个数减少一个。那么就是求一下出现了多少次0010即可。

但是如果给你的串不是0010而是一个随机的串呢?

又到了经典的“不包含子串”时间了。这种题一般是在KMP上dp。

先对模式串做一次KMP。

枚举原串的每一位,再枚举KMP的每个状态,若做匹配的时候没有匹配到结尾,说明不含模式串,此时可以直接对状态取最小,如果匹配到最后了则不能进行转移,因为此时表示含子串。

在原串i匹配到模式串j的情况下,如果我删除这一位,那么原串i+1则匹配模式串j,同时删除次数加一。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
int ne[10], f[100005][10];
char str[100005];
char p[10] = " 0010";
int T;
int main()
{
    // time_t startt = clock();
    int m = 4;
    for(int i = 2, j = 0; i <= m; i++)
    {
        while(j && p[i] != p[j 
Read the rest

【二分图匹配】Go Running – HDU20多校4G

传送门

题意是说,在一个无限长的坐标轴上,给n个报点。表示在t_i时间,在x_i这个位置出现了一个人。每个人会一直往左跑或一直往右跑。起点终点均未知。

问根据给你的信息推测,最少有多少人同时在跑步。


做法是,若出现则把平面坐标上(t_i,x_i)的点染黑。由于每个人只能朝一个方向跑,那么每个点会产生一条斜率为1和斜率为-1的直线。

问题转化为选择最少的直线覆盖这n个点。

具体写的时候,把坐标绕原点旋转45度,则所有直线平行于 x轴或 y 轴,每个点(x,y)xy连一条边。若选择x那么表示选择了平行于x的直线,若选择y则表示选择了平行与y的直线。

问题继续转化为,对于每条边,至少要有一个点被选择。即最小点覆盖问题。也就是二分图的最大匹配。

边数比较多,大概是四倍于点,点最多是10^5,所以做的时候用网络流dinic来匹配,可以到O(n\sqrt n).

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
const int N = 1e5 + 233;
unordered_map<int, int> ux, uy;
int nx[N], 
Read the rest

【kmp|线性基】Kidnapper’s Matching Problem-HDU20多校8K

传送门

题意是说给了n个数字am个数字bk个数字s

定义了一个集合S,它表示 s 的异或运算封闭群,就是说若干个s异或起来造出来的所有数都在这个集合S里。

定义了一个匹配,取与b数组长度相同的连续一段a数组,当且仅当对应位置异或起来的数字都在S里的时候,称为匹配成功。

问有多少个段能匹配成功。


首先可以用一个线性基来表示这k个s所表示的线性空间。

  1. a_ib_i均能用这个线性基表示出来,那么异或出来的数一定在群里。
  2. a_ib_i只有一个不能被线性基表示出来,那么异或出来的数肯定不在群里。

  3. 若两个数都不能被线性基表示出来,异或结果是可能在群里的。当且仅当把能用S表示出来的部分删掉后a’=b’。这个其实蛮明显的,比赛的时候没想到。

证明

然后就变成了B串为模式串,A串为原串,做KMP匹配。

温馨提示:本题卡cin,不知道是不是因为HDU编译器版本太旧,关同步也没用。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
int n, m, k;
const int mod = 1e9 + 7;
const 
Read the rest

【异或最小生成树】Graph – 20牛客多校5-B

传送门

题意说给一棵树,若在任意两点之间加边,权值为路径的异或和。

在保证图联通的情况下可以删边。

求如何操作使得最后这张图的边权和最小。

做法是先发现任意两点的边权其实可以看做给定,就是到根节点的异或和。

那么先预处理出来所有点的异或和当作点权,问题转化为:给定一些点,任意两点之间连边为其二的异或和,求最小生成树。

用到了Boruvka的思想,合并两个连接边权最小的连通块。

把所有点插入trie树上,考虑任意一层的任意一个点,最优的合并必然是要合并左右子树,因为更高位是相同的,异或得 0 。而合并所需要得代价就是其左子树所有点和右子树所有点的异或最小值。

分治来求每个节点的代价,左边的值都插入trie,枚举右边查询最小值。查完以后把trie清空。直接把所有idx的点标记为0即可。

#include<bits/stdc++.h>
using namespace std;
using namespace std;

const int N = 100010, M = 3000000;

int a[N], son[M][2], idx;

void insert(int x)
{
    int p = 0;
    for (int i = 30; i >= 0; i -- )
    {
        int &s = son[p][(x >> i) & 1];
        if (!s) s = ++ idx;
        p = s;
    }
}

int search(int x)
{
    int p = 0, res = 0;
    
Read the rest