——Light!
0%

发表于 更新于 Valine：

不会太长，因为之前是发微博上的。记性比较差，一般如果看完当天没有马上评论可能就过去了。。。

命运石之门0

真的觉得很神啊！！因为要描述世界大战，所以不能像正篇那样表面看上去那么“纯洁”，显露的bug也会更多。然而，有一个评论说得很好，0的美，是“壮丽”的美，是即使跳跃三千次也要改变未来的决心，是为了到达sg线必须经历的。

比较不满的是，阿万音由季的烟雾弹实在是太刻意了一点……黑衣人来袭击之前正好说要去打工，打工第二天正好伤到相同的地方，而且下一次还是伤到相同的地方 = =

2021-01-02

工作细胞

脑洞非常大！科普也很到位，看片还能学习基础知识233333 中间有一集好甜啊[二哈]最后两集很燃！总之很棒棒~

2018-10-11

龙与虎

一些疑问：
北村和大河再怎么熟也没熟到可以随便咬她可丽饼的程度吧？？反正北村对大河还有很多很奇怪的地方，比如文化祭夜里竟然约她跳舞，你喜欢的会长tmd还在旁边看着你好吗？？
第16话，会长都说了”如果我说喜欢他的话他就会跟着我去了”，这不是明摆着两情相悦吗？北村竟然还会被叫做最大可怜虫。。。
以及，没有刻意的推进的话，一整个学期的亲密接触就是只能多了解那么一点点呢。。。

阅读全文 »

发表于 更新于 Valine：

今天发现一篇好文章，转载收藏一下。
以下全文转载自关于不同版本 glibc 更换的一些问题

关于不同版本 glibc 更换的一些问题

在做 pwn 题时，更换 ELF 文件的 libc 版本一直让人头疼，所以写文记录关于 glibc 的下载，替换，调试的一些问题。

如何获取不同版本的 glibc

手动下载

通过镜像源可以下载到常见版本的 glibc 及其符号表。

通过 Ubuntu 的 old-releases 镜像站 或者 清华的镜像站 可以下载到不同版本的 glibc。然后通过 dpkg -x *.deb 来解压 deb 包得到 libc。

当然也可以通过 Debian 等发行版的镜像源来下载 glibc。

自动化工具

有两个项目可以实现自动下载 libc：https://github.com/niklasb/libc-database 和https://github.com/matrix1001/glibc-all-in-one ，前者不会下载符号表，而后者会将符号表存入对应 libc 的 “.debug” 文件夹中。

阅读全文 »

发表于 更新于 Valine：

写写题解和吐槽。

初赛第1场题解

树木规划

比较简单的贪心算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int treePlanning(vector<int> &trees, int d) {
        int pre=-1e9;
        int res=0;
        for (const auto &x : trees) {
            if (x-pre>=d) {
                pre=x;
            } else {
                res++;
            }
        }
        return res;
    }
};

正三角形拼接

有点麻烦的分类讨论，讨论过的类就不再存在（本题中不需要考虑不能实现）。

  1. 如果某长度至少三次，0刀
  2. 如果某长度两次，且存在比它大的，1刀
  3. 如果某长度一次，且存在是它两倍的，1刀
  4. 如果至少有三根棍子，后两根切出第一根的长度，2刀
  5. 只有两根的情况，看代码（可能有冗余）
  6. 只有一根的情况，必须被3整除才能2刀，其他情况3刀（切出3个1）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int makeEquilateralTriangle(vector<int> &a) {
        map<int,int> cnt;
        int n = a.size();
        sort(begin(a), end(a));
        for (int i=0;i<n;i++) {
            ++cnt[a[i]];
        }
        for (int i=0;i<n;i++) if (i==0 || a[i]!=a[i-1]) {
            if (cnt[a[i]]>=3) {
                return 0;
            }
        }
        for (int i=0;i<n;i++) if (i==0 || a[i]!=a[i-1]) {
            if (cnt[a[i]]==2) {
                if (i+2<n) return 1;
            } else if (cnt[a[i]]==1) {
                if (cnt.count(a[i]*2)) return 1;
            }
        }
        if (n>=3) return 2;
        if (n==2) {
            if (a[1]>a[0]*2) return 2;
            if (a[1]%3==0) return 2;
            if (a[0]%3==0) return 2;
            if (a[0]%2==0) return 2;
            if (a[1]%2==0 && a[0]>=a[1]/2) return 2;
        }
        if (n==1) {
            if (a[0]%3==0) return 2;
        }
        return 3;
    }
};

大楼间穿梭

阅读全文 »

发表于 更新于 Valine：

听说考得好写在简历里很不错，正好也保持一下写题的水平。
仅含题解，代码详见Github，喜欢的话点个star呀。

201912

201912-1 报数

水题。按提意模拟一下。

201912-2 回收站选址

水题。由于一定要在垃圾处建垃圾站，枚举所有垃圾即可。

201912-3 化学方程式

算是词法解析题吧，啥都不管，直接top-down一把梭。

201912-4 区块链（20分）

感觉是个sb题，但是最开始数据结构没设计对，后面就改不对了，一直Wrong Answer。。。

阅读全文 »

发表于 更新于 Valine：

这两天复习组合数学，仔细品了品八种放球问题，感觉还是挺有意思的。
放球问题的基本表述是：将$n$个球放入$m$个盒子中（每个球都必须放到某个盒子里），有多少种方案？
由于有$3$个方面的条件，所以总共有$2^3=8$种，按熟悉程度分别介绍吧。

1. 将$n$个无区别的球放入$m$个有区别的盒子中，不允许空盒

使用经典的插空法，把$m-1$个板插入$n-1$个空中，自然划分出$m$个区，对应$m$个有区别的盒子，如图所示。
插空法示意图
方案数$=C_{n-1}^{m-1}$。
该问题等价于求$\sum_{i=1}^{m}{x_{i}}=n$的正整数解的个数。

2. 将$n$个无区别的球放入$m$个有区别的盒子中，允许有空盒

使用经典的隔板法，把$m-1$个板与$n$个球放在一起。“允许有空盒”意味着板和板可以紧邻地放在一起，这时候就要换一种思维方式，也就是从位置的角度来考虑，在$n+m-1$个位置中选$m-1$个放隔板，剩下的$n$个放球。
隔板法示意图
方案数$=C_{n+m-1}^{m-1}$。
该问题等价于求$\sum_{i=1}^{m}{x_{i}}=n$的非负整数解的个数，通过换元法可以转化为问题1。

3. 将$n$个有区别的球放入$m$个有区别的盒子中，允许有空盒

第1个球有$m$种选择，第2个球也有$m$种选择，第3个……。
方案数$=m \times m \times \cdots \times m = m^{n}$。

4. 将$n$个有区别的球放入$m$个无区别的盒子中，不允许空盒

这是第二类斯特林数的定义。
方案数$=S(n,m)$，递推式为$S(n,m)= S(n-1,m-1) + S(n-1,m) \times m$，包含了两种情况，

  1. 第$n$个球单独放一个盒子，也就是之前的$n-1$个球放入了$m-1$个盒子；
  2. 第$n$个球放入已经存在的盒子，由于不能有空盒，此时$m$个盒子内部的情况肯定是不一样的，所以可以直接乘以$m$。
阅读全文 »

发表于 更新于 Valine：

Oblivious Transfer一般译为“不经意传输”，也有人译为“茫然传输”。

在不经意传输中，有两个参与者Alice（发送方）和Bob（接收方）。Alice输入一个位 $b\in \{ 0,1 \}$，Alice和Bob通过一定方式交互后，Bob只能以$\frac{1}{2}$的概率接收到 $b$（对Alice的隐私性），而且，Alice无法知道Bob是否得到了 $b$（对Bob的隐私性）。Bob可以确信地知道他是否得到了 $b$（正确性）。

不经意传输还有其他的形式，如$2$取$1$不经意传输协议:

Alice的输入为$2$个位 $b_{0},b_{1} \in \{ 0,1 \}$，Bob的输入位为$c\in \{ 0,1 \}$，Alice和Bob通过一定方式交互后，Bob可以得到 $b_{c}$（正确性），Alice无法知道Bob的选择 $c$（对Bob的隐私性），Bob无法同时得到 $b_{0}$ 和 $b_{1}$（对Alice的隐私性）。

同理也可以得到$n$取$1$不经意传输协议和$n$取$m$不经意传输协议的概念。

不经意传输协议是设计其它密码协议的基础，可以构造更为复杂的协议，如不经意电路计算。

以上转载自：不经意传输（Oblivious Transfer）

阅读全文 »

发表于 更新于 Valine：

各个课的作业都做得太久了，
但是又无法接受明明还有时间却不把一件事情搞好。

组合数学的小论文用 $\LaTeX$ 写的，写了好久，
但是竟然没找到一个正常的中文期刊模板，只好自己随便搞了。

姑且算是跟博客的内容有点关系，
还是放上来吧，关于堆数据结构相关操作时间复杂度的分析。

阅读全文 »

发表于 更新于 Valine：

本文要解决的问题是网络中的负载均衡问题，什么是负载均衡呢？负载均衡是云计算的基础组件，是网络流量的入口，是一个既经典又重要的问题。用户输入的流量通过负载均衡器按照某种负载均衡算法把流量均匀的分散到后端的多个服务器上，接收到请求的服务器可以独立的响应请求，达到负载分担的目的。从产品形态角度来说，可以分为硬件负载均衡和软件负载均衡。硬件负载均衡器常见的有F5、A10，它们的优缺点都比较明显，优点是功能强大，有专门的售后服务团队，性能比较好，缺点是缺少定制的灵活性，维护成本较高；现在的互联网公司更活跃的思路是通过软件负载均衡来实现，这样可以满足各种定制化需求，常见的软件负载均衡有Nginx、Haproxy。本文中实现的Ananta也属于一种软件负载均衡。

本文的作者都是微软的员工，主要动机是在保证Web服务仍然高并发高可用的情况下尽可能地减小负载均衡的花费，为此他们设计并实现了Ananta。这是一种在商品硬件上运行并且支持横向扩展（scale-out）的layer-4（connection-level）负载均衡器，可以同时满足了多租户云计算环境中的性能、可靠性和操作要求。

图1 Ananta Data Plane Tiers

在具体介绍之前首先需要介绍本文中的一些基本概念：

  • DIP：private Direct IP address，私有的直接IP地址，专用网内部的任何一台虚拟机或者本地机器都会被分配一个DIP，即仅在本专用网内使用的专用地址；
  • VIP：public Virtual IP address，公有的虚拟IP地址，一般情况下一个服务会被分配一个VIP；
  • 服务：在本文中，“服务”和“租户”将作为可替换的概念；
  • NAT：Network Address Translation，网络地址转换，当专用网内部需要提供对外服务时，外部地址发起主动连接，由路由器或者防火墙上的网关接收这个连接，然后将连接转换到内部，此过程是由带有公网IP的网关替代内部服务来接收外部的连接，然后在内部做地址转换，此转换称为NAT，主要用于内部服务对外发布；
  • SNAT：Source Network Address Translation，源网络地址转换，内部地址要访问公网上的服务时（如web访问），内部地址会主动发起连接，由路由器或者防火墙上的网关对内部地址做地址转换，将内部地址的私有IP转换为公网的公有IP，网关的这个地址转换称为SNAT，主要用于内部共享IP访问外部；
  • 横向扩展：横向扩展是一种可以通过简单地添加更多类似容量的设备来处理更多带宽的模型；
  • 纵向扩展：纵向扩展是一种为了处理更多带宽需要更高容量的设备的模型。

Ananta的设计原则有两条：

  1. 横向扩展网络内（in-network）处理：传统的NAT和负载平衡算法需要了解所有活动的（active）流，因此同一VIP的所有流量都必须通过相同的负载平衡器，这迫使负载均衡器只能进行纵向扩展。而路由器遵循横向扩展模型，这是因为它们不维护任何需要跨路由器同步的每流（per-flow）状态。Ananta的设计将负载均衡所需的网络内功能简化，使得多个网络元素可以同时处理同一VIP的数据包，而无需每流状态的同步。
  2. 将工作负载卸载（offload）到端系统：端系统中的管理程序已经可以进行高度可扩展的网络处理。Ananta利用此分布式可扩展平台，将重要的数据平面和控制平面功能卸载到终端系统中的管理程序。

Ananta是一个松散耦合的分布式系统，包含三个主要组件：Ananta管理员（Ananta Manager，AM)，多路复用器（Multiplexer，Mux)和主机代理（Host Agent，HA)，如图2所示。

图2 The Ananta Architecture

AM实现了Ananta的控制平面。他提供配置VIP的API，他会根据VIP的配置来配置HA和Mux池，并且监视DIP运行状况的任何更改。AM还负责跟踪Mux和主机的健康状况，并采取适当的行动。

阅读全文 »

发表于 更新于 Valine：

5 函数调用约定

创建一个栈帧的最重要步骤是主调函数如何向栈中传递函数参数。主调函数必须精确存储这些参数，以便被调函数能够访问到它们。函数通过选择特定的调用约定，来表明其希望以特定方式接收参数。此外，当被调函数完成任务后，调用约定规定先前入栈的参数由主调函数还是被调函数负责清除，以保证程序的栈顶指针完整性。

函数调用约定通常规定如下几方面内容：

  1. 函数参数的传递顺序和方式

最常见的参数传递方式是通过堆栈传递。主调函数将参数压入栈中，被调函数以相对于帧基指针的正偏移量来访问栈中的参数。对于有多个参数的函数，调用约定需规定主调函数将参数压栈的顺序(从左至右还是从右至左)。某些调用约定允许使用寄存器传参以提高性能。

  1. 栈的维护方式

主调函数将参数压栈后调用被调函数体，返回时需将被压栈的参数全部弹出，以便将栈恢复到调用前的状态。该清栈过程可由主调函数负责完成，也可由被调函数负责完成。

  1. 名字修饰(Name-mangling)策略

又称函数名修饰(Decorated Name)规则。编译器在链接时为区分不同函数，对函数名作不同修饰。

若函数之间的调用约定不匹配，可能会产生堆栈异常或链接错误等问题。因此，为了保证程序能正确执行，所有的函数调用均应遵守一致的调用约定。

阅读全文 »