——Light!

保研经历

发表于 2018-10-12 更新于 2022-10-11 Valine：

Here's something encrypted, password is required to continue reading.

0x0 Toddler’s Bottle

0x00 fd

首先稍微学习一下file descriptor，然后登录上去看看到底是什么情况。

fd@ubuntu:~$ ls -alh
total 40K
drwxr-x---  5 root   fd   4.0K Oct 26  2016 .
drwxr-xr-x 92 root   root 4.0K Aug 12 10:28 ..
d---------  2 root   root 4.0K Jun 12  2014 .bash_history
-rw-------  1 root   root  128 Oct 26  2016 .gdb_history
dr-xr-xr-x  2 root   root 4.0K Dec 19  2016 .irssi
drwxr-xr-x  2 root   root 4.0K Oct 23  2016 .pwntools-cache
-r-sr-x---  1 fd_pwn fd   7.2K Jun 11  2014 fd
-rw-r--r--  1 root   root  418 Jun 11  2014 fd.c
-r--r-----  1 fd_pwn root   50 Jun 11  2014 flag

可以看到除了隐藏文件就是 fd fd.c flag ，所以目标就是获取flag中的内容然后提交到网站上。
但是由于权限问题我们是不能直接查看flag文件的，实际上在不能成为root的情况下只有通过可执行文件fd才有可能操作flag文件，因为fd带有Set UID权限，在它运行的时候可以暂时获得fd_pwn这个用户的权限。那么剩下的那个fd.c文件可以推测是fd文件的源代码。
另外，fd用户对当前目录没有write权限，所以要通过查看fd.c分析fd的行为。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char buf[32];
int main(int argc, char* argv[], char* envp[]){
        if(argc<2){
                printf("pass argv[1] a number\n");
                return 0;
        }
        int fd = atoi( argv[1] ) - 0x1234;
        int len = 0;
        len = read(fd, buf, 32);
        if(!strcmp("LETMEWIN\n", buf)){
                printf("good job :)\n");
                system("/bin/cat flag");
                exit(0);
        }
        printf("learn about Linux file IO\n");
        return 0;

}

程序里用到的file descriptor竟然不是open返回的，而是根据命令行参数变换出来的，也就是说要给出一个数字，使得这个数字作为文件描述符对应的文件里的内容是特定的字符串。这在正常情况下是不可能的，因为一个文件的文件描述符只在同一个进程里是确定的，更何况当前用户也不能新建文件。但是UNIX下确实有三个文件的文件描述符是绝对确定的，它们就是 stdin stdout stderr 。所以只要让fd变量等于0，我们就可以输入任意的内容，我觉得至少有三种方法：

非常普通的输入0x1234对应的十进制数，./fd 4660
看起来太fancy但是实际上非常有用的命令，涉及到shell语言的弱引用以及python的命令行执行字符串
1
./fd `python -c "print 0x1234"`
gdb可用，应该可以直接set fd甚至set buf（没有实际尝试）

最后把打出来的内容贴到网站上这题就通过了。

0x01 collision

阅读全文 »

HHUACM 暑假专题数学

发表于 2018-09-02 更新于 2022-10-11 Valine：

A - 求递推序列的第N项

矩阵快速幂，帮助大家搭建/测试自己的模板。
简单地讲一下原理，可以看到每一项用到了前两项的值，首先构造一个二维的向量$\left(\begin{matrix}
f(i-1) \\
f(i-2) \\
\end{matrix}\right)$，如果有常数就再加一维。那么将这个向量作为自变量，下一项就是$\left(\begin{matrix}
f(i) \\
f(i-1) \\
\end{matrix}\right)$。最后稍微动一下脑子配一个$2\times2$的系数矩阵使得$Cx_{i-1}=x_{i}$：
$$\left(\begin{matrix}
A & B \\
1 & 0 \\
\end{matrix}\right)
\left(\begin{matrix}
f(i-1) \\
f(i-2) \\
\end{matrix}\right)
=\left(\begin{matrix}
f(i) \\
f(i-1) \\
\end{matrix}\right)$$
复杂度$O(M^3logN)$，其中$M$为矩阵的大小，等于$2$。

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

typedef long long ll;
const int MO=7;

struct Matrix {
    int r,c;
    ll e[2][2];
    Matrix() {}
    Matrix(int _r,int _c) {
        r=_r;c=_c;
        memset(e,0,sizeof(e));
    }
    Matrix(ll x) {
        r=c=2;
        memset(e,0,sizeof(e));
        for (int i=0;i<r;i++) {
            e[i][i]=x;
        }
    }
    Matrix operator *(const Matrix &b) {
        Matrix C(r,b.c);
        for (int i=0;i<r;i++) {
            for (int j=0;j<b.c;j++) {
                for (int k=0;k<c;k++) {
                    C.e[i][j]+=e[i][k]*b.e[k][j]%MO;
                    if (C.e[i][j]>=MO) C.e[i][j]%=MO;
                }
            }
        }
        return C;
    }
};

Matrix fpow(Matrix x,ll n)
{
    Matrix res(1);
    while (n) {
        if (n&1) {
            res=res*x;
        }
        x=x*x;
        n>>=1;
    }
    return res;
}

int main()
{
    int a,b,n;
    scanf("%d%d%d",&a,&b,&n);
    if (n<=2) {
        puts("1");
    } else {
        Matrix A(2,2);
        A.e[0][0]=a;
        A.e[0][1]=b;
        A.e[1][0]=1;
        A.e[1][1]=0;
        Matrix X(2,1);
        X.e[0][0]=1;
        X.e[1][0]=1;
        A=fpow(A,n-2);
        X=A*X;
        int ans=(X.e[0][0]%MO+MO)%MO;
        printf("%d\n",ans);
    }
    return 0;
}

B - Kinds of Fuwas

题意：四个角为同一种福娃的子矩形有多少个？
题解：从样例可以看出，一行或一列的矩形都不算。从数据范围来看，直接四个循环复杂度太高了，但是每个元素的值域很小，只有五个种类，所以可以考虑枚举每个种类来做。对于每个种类，比如H，我们可以利用类似最大子矩阵的套路，枚举两行作为上下界，然后再枚举每一列，对上下都是H的列进行计数，在这之中任取两列就是符合要求的矩形，所以把答案加上$C^{2}_{m}$即可，这个组合数可以$O(1)$求得。
复杂度$(KM^2N)$，其中$K$等于$5$。

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

const char PP[9]="BJHYN";
const int N=256;
char mp[N][N];

int main()
{
    int T;
    scanf("%d",&T);
    while (T--) {
        int n,m;
        scanf("%d%d",&n,&m);
        for (int i=0;i<n;i++) {
            scanf("%s",mp[i]);
        }
        long long ans=0;
        for (int p=0;p<5;p++) {
            for (int i=0;i<n;i++) {
                for (int j=i+1;j<n;j++) {
                    int t=0;
                    for (int k=0;k<m;k++) {
                        if (mp[i][k]==PP[p]&&mp[j][k]==PP[p]) ++t;
                    }
                    ans+=t*(t-1)/2;
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

C - GCD is Funny

题意：
在黑板上写有$n$个数，每次删掉$a,b,c$三个数并把$d$写两遍，$d$可以是$(a,b),(a,c),(b,c)$。在$n-2$次操作后会留下两个相同的数，输出这个数的所有可能情况。

题解：
这个题很难~~虽然出在某一场BC的A题~~。
首先要思考一下脱离具体过程，这个数到底是什么。题中的过程以下简称为“擦黑板”。

如果已经存在两个相同的数$x$，再取一个数$y$进行一次擦黑板，那么可以令$d=(x,x)=x$，剩下的数为$x,x$。可以发现$y$没有产生影响，两个$x$直接“吃掉”了$y$；
由1，我们可以单独考虑每一个$size\ge 3$的子集，它的结果一定是两个相同的数，其他的数直接吃掉就好。为了保证枚举的不重不漏，该子集内应该有尽量多的数参与$gcd$运算（注意，参与擦黑板$\neq$参与$gcd$运算），也就是$size-1$个数。因为第一次擦黑板一定有一个数无法参与$gcd$运算，而从第二次开始，有前一次得到的两个数$x$，再取一个数$y$进行一次擦黑板，那么可以令$d=(x,y)$，$y$一定能参与$gcd$运算。

阅读全文 »

C语言函数调用栈（一）

发表于 2018-07-19 更新于 2022-11-04 Valine：

程序的执行过程可看作连续的函数调用。当一个函数执行完毕时，程序要回到调用指令的下一条指令(紧接call指令)处继续执行。函数调用过程通常使用堆栈实现，每个用户态进程对应一个调用栈结构(call stack)。编译器使用堆栈传递函数参数、保存返回地址、临时保存寄存器原有值(即函数调用的上下文)以备恢复以及存储本地局部变量。

不同处理器和编译器的堆栈布局、函数调用方法都可能不同，但堆栈的基本概念是一样的。

1 寄存器分配

寄存器是处理器加工数据或运行程序的重要载体，用于存放程序执行中用到的数据和指令。因此函数调用栈的实现与处理器寄存器组密切相关。

Intel 32位体系结构(简称IA32)处理器包含8个四字节寄存器，如下图所示：

最初的8086中寄存器是16位，每个都有特殊用途，寄存器名城反映其不同用途。由于IA32平台采用平面寻址模式，对特殊寄存器的需求大大降低，但由于历史原因，这些寄存器名称被保留下来。在大多数情况下，上图所示的前6个寄存器均可作为通用寄存器使用。某些指令可能以固定的寄存器作为源寄存器或目的寄存器，如一些特殊的算术操作指令imull/mull/cltd/idivl/divl要求一个参数必须在%eax中，其运算结果存放在%edx(higher 32-bit)和%eax (lower32-bit)中；又如函数返回值通常保存在%eax中，等等。为避免兼容性问题，ABI规范对这组通用寄存器的具体作用加以定义(如图中所示)。

对于寄存器%eax、%ebx、%ecx和%edx，各自可作为两个独立的16位寄存器使用，而低16位寄存器还可继续分为两个独立的8位寄存器使用。编译器会根据操作数大小选择合适的寄存器来生成汇编代码。在汇编语言层面，这组通用寄存器以%e(AT&T语法)或直接以e(Intel语法)开头来引用，例如mov $5, %eax或mov eax, 5表示将立即数5赋值给寄存器%eax。

在x86处理器中，EIP(Instruction Pointer)是指令寄存器，指向处理器下条等待执行的指令地址(代码段内的偏移量)，每次执行完相应汇编指令EIP值就会增加。ESP(Stack Pointer)是堆栈指针寄存器，存放执行函数对应栈帧的栈顶地址(也是系统栈的顶部)，且始终指向栈顶；EBP(Base Pointer)是栈帧基址指针寄存器，存放执行函数对应栈帧的栈底地址，用于C运行库访问栈中的局部变量和参数。

注意，EIP是个特殊寄存器，不能像访问通用寄存器那样访问它，即找不到可用来寻址EIP并对其进行读写的操作码(OpCode)。EIP可被jmp、call和ret等指令隐含地改变(事实上它一直都在改变)。

不同架构的CPU，寄存器名称被添加不同前缀以指示寄存器的大小。例如x86架构用字母“e(extended)”作名称前缀，指示寄存器大小为32位；x86_64架构用字母“r”作名称前缀，指示各寄存器大小为64位。

阅读全文 »

2018广东工业大学校赛题解

发表于 2018-03-25 更新于 2022-10-11 Valine：

C-平分游戏

先不考虑是隔$k$个人，直接当成每次逆时针加$k$。那么原图中的$n$个人划分为若干个环，每个环都是独立的，这里取一个四元环继续讲解。

假设四个人原先有的钱为$S_i$，逆时针收到的钱为$x_i$（负数即反向），需要达到平均值$A$，那么有
$$
\left\{
\begin{array}{c}
S_1+x_1-x_2=A \\
S_2+x_2-x_3=A \\
S_3+x_3-x_4=A \\
S_4+x_4-x_1=A
\end{array}
\right.
$$
一行一行加，解得：
$$
\left\{
\begin{array}{c}
x_1=&x_1 &\triangleq x_1-y_1 \\
x_2=&x_1-(A-S_1) &\triangleq x_1-y_2 \\
x_3=&x_1-((A-S_1)+(A-S_2)) &\triangleq x_1-y_3 \\
x_4=&x_1-((A-S_1)+(A-S_2)+(A-S_3)) &\triangleq x_1-y_4
\end{array}
\right.
$$
这个环所需要的总时间为$T=|x_1|+|x_2|$ $+|x_3|+|x_4|$ $=|x_1-y_1|+|x_1-y_2|$ $+|x_1-y_3|+|x_1-y_4|$，由绝对值数形结合的知识可知当$x_1$取$y_i$的中位数（不计平均）时该式最小。
对于这道题，可以先求出总的平均值$A$，然后每个环都用这个$A$列方程和验证，答案累加即可。
最后说一下$k$的问题，题意不是很清晰，最终确定隔$n-1$个人是可以的（相当于相邻），隔$n$个人是不可以的（没有实际意义）。

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

typedef long long ll;
const int N=1000010;
ll s[N];
bool vis[N];

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    ++k;
    ll sum=0;
    for (int i=0;i<n;i++) {
        scanf("%lld",&s[i]);
        sum+=s[i];
    }
    if (sum%n) {
        puts("gg");
        return 0;
    }
    ll A=sum/n,ans=0;
    int cnt=0;
    for (int i=0;i<n;i++) {
        cnt+=(s[i]==A);
    }
    if (cnt==n) {
        puts("0");
        return 0;
    }
    if (k>n) {
        puts("gg");
        return 0;
    }
    bool good=true;
    for (int i=0;i<n;i++) {
        if (vis[i]) continue;
        int j=i;
        ll tmp=0;
        vector<ll> ve;
        do {
            vis[j]=true;
            tmp+=A-s[j];
            ve.push_back(tmp);
            j=(j+k)%n;
        } while (j!=i);
        if (tmp) {
            good=false;
            break;
        }
        sort(begin(ve),end(ve));
        ll x=ve[ve.size()/2];
        for (auto y:ve) {
            ans+=abs(x-y);
        }
    }
    if (!good) {
        puts("gg");
    } else {
        printf("%lld\n",ans);
    }
    return 0;
}

阅读全文 »

HHUACM 寒假专题动态规划

发表于 2018-02-25 更新于 2022-10-11 Valine：

F - 数塔

经典问题，数塔。
使用动态规划解决问题的（最重要）前提是：

问题具有最优子结构
最优子结构的状态可以记录

例如上图中，以第二层$12$为顶层的数塔就是一个最优子结构。
再回到原来的顶层，想得到最终的结果只需要知道第二层两个子结构能得到的最大和，这是可记录的。
所以，我们从底层往顶层进行动态规划就可以了。

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

int a[111][111];

int main()
{
    int T,n;
    scanf("%d",&T);
    while (T--) {
        scanf("%d",&n);
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=i;j++) {
                scanf("%d",&a[i][j]);
            }
        }
        for (int i=n-1;i>=1;i--) {
            for (int j=1;j<=i;j++) {
                a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
            }
        }
        printf("%d\n",a[1][1]);
    }
    return 0;
}

G - 免费馅饼

可以发现时刻的范围不是很大，把每个时刻看作每一层，这个问题就是三条边的数塔。
代码中平移一下是为了避免越界问题。

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

const int N=100010;
int dp[N][13];

int main()
{
    int n;
    while (scanf("%d",&n),n) {
        memset(dp,0,sizeof(dp));
        int m=0;
        for (int i=1;i<=n;i++) {
            int x,t;
            scanf("%d%d",&x,&t);
            ++dp[t][x+1];
            m=max(m,t);
        }
        for (int i=m;i>=0;i--) {
            for (int j=1;j<=11;j++) {
                dp[i][j]+=max(max(dp[i+1][j-1],dp[i+1][j]),dp[i+1][j+1]);
            }
        }
        printf("%d\n",dp[0][6]);
    }
    return 0;
}

A - 饭卡

首先排除余额已经少于$5$的情况，然后分为$m-5$和$5$两部分，前面的$m-5$是个01背包问题，后面的$5$用来买最后一次。若用$dp(x)$表示$x$能买到的最大价值，那么答案为$m-dp(m-5)-a_i (1\le i\le n)$。
可以证明，最后买最贵的是最优的。比较复杂，这里仅通过$m-dp(m-5)-a_p$这个式子简要说明，如果最后买的不是最贵的，即 $p’ \neq p$：

阅读全文 »

CSP超级合集

发表于 2018-01-16 更新于 2022-10-11 Valine：

Before

听说考得好写在简历里很不错，准备参加三月份的CSP。
仅含题解，代码详见github。~~喜欢的话点个star~~

201712-1 最小差值

sb-t。随便暴力一下。

201712-2 游戏

sb-t。BUT，读题的时候没读到或其末位数（即数的个位）为k，直接当约瑟夫做了。。。
最垃圾的做法就是拿数组标记一下，手动控制环。（没错我就是这么做的，写起来还是很快的

201712-3 Crontab

还没读完题头都大了，写完第4题的第一稿才开始动手做。题目虽然很长，题意其实还是挺清晰的。
核心算法就是模拟，用了一次蔡勒公式算出星期几。输入处理简单来讲的话就是，先按‘ ’（空格）split，每段再按‘,’（逗号）split，每段再按‘-’（减号）split，然后再转换成非负整数标记到这个$crontab$对应的布尔数组，比如周一周二那就是在一周的数组中标记$1$和$2$，详见代码。最后从起始到终止一分钟一分钟往上加，每一分钟都枚举$n$个$crontab$判断一下是否满足。算了一下极限复杂度稍微有点方，不过看了一下输出不超过10000行，应该不会TLE。
思考加打代码估计有一个多小时。。。最后交上去一看，85分，难道还是TLE了？结果点进去一看是WA，有点懵逼。又读了一遍题，还是没啥发现。查了查别人代码发现好像英文缩写不区分大小写，然后回到题目里一看，中间有一句确实写着，唉。。。

201712-4 行车路线

ps. 201712-4.cpp是60分代码，201712-4S.cpp是满分代码。
其实核心思想跟之前是差不多的。首先因为小道的费用（和的平方）没有可加性，所以就要把小道全都做成$tp$（传送卷轴）：启动$tp$以后可以花费一定的费用从一个点传送到另一个点。其次为了保证小道的费用不可加，要限制$tp$不能连续使用，连续使用时费用缩水（$1^2+1^2<(1+1)^2$）。
具体实现是：首先用$Floyd$求出只用小道的任意点对间的距离，把这些距离的平方作为$tp$的费用存下来。然后用$SPFA$求单源最短路，分别用两个数组记录$tp$过来的（$dis1$）和从大道过来的（$dis0$），对于边$u\rightarrow v$，$tp$到$u$的不能再通过$tp$到$v$，其它的不作限制。最后输出$min(dis0(n),dis1(n))$即可。
ps. $Floyd+SPFA$有风险，一点不考虑常数优化的话交上去只有50分，比$dijkstra$乱搞还低。

阅读全文 »

2017 CCPC 秦皇岛站游记

发表于 2017-12-08 更新于 2022-10-11 Valine：

正文

BEFORE

我校网赛打出来一个名额，教练钦定我们队去。
现在都是固定队了，我的队友是 wenwenla 和 jxc 。

自从听说浙大出题以后，我就一直努力想把zimpha出过的bestcoder都过一遍。
【虽然他不出这场但是我感觉题目风格可能有传承？咸鱼的挣扎 ←_←
结果发现他出过的bc题实在是太多了。。。于是就按照vj的规格拉了最近的26题练了练。。。非常重视思维，怎么说呢，感觉上没什么套路题，详见zimpha的bc出题录。

Oct 26

翻了翻高中通讯录，有一个东秦的同学，非常高兴地问她借了词典~
晚上让队友把这个简要题解也都过一遍，然后买了泡面和小香肠啥的第二天吃。

Oct 27

没有老师带队，我们自己坐高铁去，睡睡觉吃吃面看看片，日子过得还是挺开心的。路上感觉河北的污染确实比较严重，然后在高铁上问AA姐姐要了几个口罩2333333
下了高铁坐公交，跟wc一路。找到宾馆直接从人家后厨就进去了。。。还好找到了报到的地方，真的发了环卫工人服，一切正常。
安顿了一下就是饭点了，出去吃了个酱骨自助，竟然有个烧烤和小锅一体的机器！长见识。
吃了很久，筒骨还是蛮油的，差点肉醉[笑cry]
很饱的我们于是就想散个步，强行在老虎石公园拍了很多照片【基本看不清啥
逛完了出来看到卖手链的，问了问看了看，然后每个人买了个指尖陀螺？？？

Oct 28

早上吃饭，宾馆的实在是没啥想吃的东西，咖啡也不给喝。。。
坐主办方的车过去，结果报过到的队啥都不用干。。。
然后我们就开始瞎逛，不抱希望地联系了一下同学【因为她说周六早上没空
结果我们还没正式开始逛她就回复我啦，而且一下子就找到了我们~
她说是参加高数竞赛，然后水了水就出来了hhhhhhh

阅读全文 »

zimpha的bc出题录（部分）

发表于 2017-10-18 更新于 2022-10-11 Valine：

A - GCD is Funny

题意：在黑板上写有$n$个数，每次删掉$a,b,c$三个数并把$d$写两遍，$d$可以是$(a,b),(a,c),(b,c)$。在$n-2$次操作后会留下两个相同的数，输出这个数的所有可能情况。
题解：给跪了。。。其实是所有大小超过$1$的子集的$gcd$的集合。。。

注意点：值域限制，说是子集当然不可能直接按子集做，而是利用值域很小这一点标记着做；gcd下降速度，两个不一样的数取$gcd$，最大也只能是大数的一半，即对数级别次就可以到$1$。

B - Square Distance

题意：给一个串$s$，长度为$n$(保证偶数)，输出一个串$t$，要满足：$t$由两个相同的串拼接而成；$s$到$t$的汉明距离恰好为$m$；$t$是所有满足条件的串中字典序最小的。$s,t$均只含小写字母，若$t$不存在输出Impossible。
题解：后半段放到前半段综合考虑，用dp可以求出前$i$个字符产生$j$个距离可不可行。因为要输出字典序最小，所以最终的贪心一定是从前往后从小往大，若是直接在这种dp上贪心，会导致最后的距离不一定是$m$。所以这里需要倒着dp，即从第$\frac{n}{2}$个到第$i$个字符产生$j$个距离可不可行。

注意点：看着很像贪心但是没有具体策略的时候一定要想一想dp！不一定只贪心或者只dp，也不一定是用贪心优化dp，像这题就是在dp得到的表上进行贪心。

C - LCIS

题意：给出$n$个数的序列$a$和$m$个数的序列$b$，问公共的上升的并且数值连续的子序列的最长长度。
题解：对$a$扫一遍得到以$x$结尾的连续值上升子序列的最长长度，同样地对$b$扫一遍，最后枚举结尾是什么数字，取两个结果的较小值更新答案。

注意点：当对子序列的限制非常强时，很有可能可以每个序列分开做，最后再合并到答案。

D - Black White Tree

阅读全文 »

2017ICPC乌鲁木齐网络赛全题解

发表于 2017-09-25 更新于 2022-10-11 Valine：

Tips

仅含题解，代码详见github。~~喜欢的话点个star~~

A. Banana

直接暴力。

B. Out-out-control cars

可以看作相对运动，然后三条射线跟三条线段判相交。
要注意的是大三角形的射线不碰到小三角形也可以yes，这个我们可以通过两个都判一遍来解决。
还有一种情况（数据里好像没有）是两者相对静止并且一个套一个，按照题意也是yes。

C. Coconut

直接模拟。

D. Hack Portals

poj原题。~~没做过，所以比赛的时候也没做~~
按照坐标排序后，有一个贪心的结论：i到j这一段区间中，最优情况下最后一个做的不是i就是j。
考虑区间dp，我们用dp[i][j][0]表示i到j这一段最后做i的最小花费，dp[i][j][1]表示i到j这一段最后做j的最小花费。
转移还是挺容易的，转移了以后还要再考虑一下开放的时间。

阅读全文 »