[CTF]USTC Hackergame 2018 划水记

最近无事,见USTC有CTF比赛,便去玩了玩。

题目存档可在此查看https://hack2018.lug.ustc.edu.cn

看了别人的题解后感觉自己非常傻逼 好几道题都是只差一步就做出来了。

后面也没有时间打了。本来是周二中午结束,结果从上周五凌晨开始就没看过题了。

就这样还能拿41名(

简述一下自己做出来的题和快做出来的题的题解

由于有些题是在学校傻逼机子上做的,也没有存具体题解,代码等。

0x01 签到题

input里面输key就行了,只不过限制了输入框长度。改HTML或者手动curl或用浏览器Dev Tool都可以。

0x02 猫咪问答

谷歌题。第二题好像需要推理一下?

0x03 游园会的集章卡片

拼图题。随手开了个An拼了一下就行。

0x04 猫咪和键盘

这个题目就是把一个cpp 有几列交换了一下。

因为之前见过可纵向选择的editor,于是查了一下,然后用npp手动交换了几列就完成了任务。

运行下这个cpp就行了。

0x05 Word 文档

这题先给了你一个Word文档,告诉你docx本质是zip,那我们就用压缩文件打开,发现里面有flag,复制进去即可。

0x06 猫咪银行

这题肉眼看上来只有两种赚钱的方法。一个是大力投理财,另外一个是利用币种汇率差赚钱。

然而这题限制每2s交易一次。

于是我们观察题目中唯一有输入框的地方,看如何构造卡掉。

我和同学试了负数,截断卡intval等,卡了半天才想起来用正数overflow。

这个时间是无上限的,显然当你输入$x$的时候,时间戳会加$60x$,如果只投资一元,钱会加$0.043x$,显然这个随手构造让时间戳爆成负数,钱不会爆的$x$。

然后我们构造就行,之后大力购买flag。

0x07 黑曜石浏览器

这站的robots好像只放了Google?我当时百度和必应都没搜到(sb学校上Google有点麻烦)。最后看某个地方,都说是卡到开不开Dev Tool,我就很懵。后来才发现是需要Google搜黑曜石浏览器。开源代码什么的,大力Ctrl+U就行了。之后能看到有一段js,是拿来鉴黑曜石浏览器的。是个UA判定。之后我们复制下UA,大力curl就0行了。

0x08 回到过去

给你一堆ed操作,输出结果。

这里面有个小坑,就是有一个指令是退出ed,我们只需要大力删除这条和这条上面的指令就行。

连上vps,打开ed,粘贴内容,大力cat。

0x09 我是谁

习惯性打开Dev Tool,看Network。

HTTP ERROR 418。

输入teapot,第一关完事。

第二关去翻RFC,最开始没看懂(

第二天又看了一遍,照着RFC的说明过了。

0x0A 家里有矿

第一题做不出来真的是能力不足..没研究过hash碰撞。

不过我看到这一题后,第一想到了BTC(实际上第三关SHA256就是用BTC的链解的)。

第二关是个md5,王小云曾经做过相关研究,不过好像并无卵用。

实际上碰102/128概率并不小,暴力碰就行了,也跑不了几小时(扔vps美滋滋),然而还是没去实践。

第三关就是爬BTC的blockchain,因为BTC的区块hash本来就要求有开头不少0,所以两个异或0,0也不少,大力算就行了(还是人菜)。

0x0B 秘籍残篇

第一关只需要把它转为normal format就行了。。

https://zb3.me/malbolge-tools/

之后发现这是个Art(实力眼瞎选手当然是转了之后看不出是Art),缩小下就行了。

第二关不会

0x0C 猫咪遥控器

这一题给你了一个操作序列,按照这个序列胡乱写个cpp,移动下cur,并染色,然后发现也是个Art,缩小下,就能看到flag。

0x0D 她的诗

这题给了你一个使用uuencode编码的文件,要求找出flag。

(这题我也是实力傻逼)

仔细研究uuencode格式发现第一位是表示的字节长度。

我们大力观察,感觉每一行的字节长度可能都少了点。

我们大力+3,然后decode,发现最后几列竖着读就能找到flag。

0x0E 猫咪克星

这题是给你一个socket服务器,让你计算它给定的python表达式。算够一定数量后才会给你flag。

用手随便试了几下,发现只能写py,然后就大力exec(和eval有一定区别)。

结果发现后面有几个点有time.sleep(100) os.system(“find ~”) exit()。

不慌,大力替换下就行了。

然后拿到flag

0x0F 猫咪电路

给你一个mc红石电路,构造制定输入使之输出1。

观察一下这个地图,发现整个电路构造很有层次,而且最高的几层输入都是唯一的。

慢慢递推下去,最后会推到10个四元组。这几个四元组有些推起来很方便。对于推起来不方便的,我们大力试一试就行了。

最后把原始输入序列转成flag就行

0x10 FLXG的秘密

第一关0分。

第一关按照六十四卦表decode后,我大力file了一下,发现是个tar.gz

然后就解压了,虽说看到了文件结尾错误,不过我并没有管他。

之后发现解压下来的文件里面似乎还有个可执行文件,然后就大力IDA,感觉不可做,就跑路了。

实际上,大力 cat file | hexdump -C | tail 就能看到flag。

以明文写在文件的末尾。

(我明明开过plain,然而没看末尾,实力眼瞎++)

0x11 C语言作业

下载exe,拉进IDA,第一眼以为是要卡栈然后随机执行。

之后发现init里面有东西,其实只要把程序卡崩就可以找flag了。

之后试了半天,没发现怎么卡崩。最后暴力瞎跑,跑出来了-2147483648/-1。

找文件,先试了各种方法开sh,之后又试了各种方法绕strstr等。

后来想到可以开编辑器。然后我试了vi emacs nano ed(忘了有没有试vim了),但是由于我是手动开的socket(当时电脑不是Linux+有py+懒得连vps),并没有发现什么,最后跑路了。

后来发现,其实就是editor开,只不过是用的vim。

后面有Linux的时候大力nc过去,开vim,瞎找一番,找到了flag。

0x12 加密算法和解密算法

土球出的题(雾)

拿到手,找了半天bf format工具,最后只找到一个jar。

然后大力装JRE,下好后突然想起本机是有JRE的。

大力format,发现了这个bf是有规律的。

具体来说,这10个变量均是关于原10个输入的多元一次函数。

我们大力跑高斯消元就行了。

就是逆元处理得注意下。

(因为当时人懒,直接用的行列式求值,结果因为少加个等号调了半天)

后面的题就没做了

(跑路跑路)

后面没时间打是真的伤

还有什么好玩的CTF求推荐(雾)

[BZOJ2616][SPOJ PERIODNI] Periodni (树形背包)

BZOJ传送门

SPOJ传送门

简易题意

有$n$个$1 \times h_i$的空地,顺次拼成一个大的空地,其中不是空地的地方就是墙。现在要求在空地上放车,要求车不能互相攻击到。

数据范围

$n,m\leq500\ h_i\leq1000000$

题解

这题第一感觉是个暴力hash+DP,使用组合数进行转移。

首先先想按列考虑,但是按列考虑空地的高度有可能增长也有可能降低,因此不方便进行转移。

换个思路,我们可以按行考虑。

如果每次从高往低扫,每次截取当前这条线以上的空地图形,与之前相比,会产生新的联通块或者合并旧的联通块。

合并旧的联通块当且仅当这个位置的高度是之前两个旧的联通块内最小的之。

我们可以反方向考虑,从合并联通块变成分裂联通块。

每次分裂的时候,找到这一段内最小的值,之后将其分裂。

对于每一段,我们定义$dp_{j}$表示在当前联通块(段)放$j$个车时的方案数。

容易看出,每次转移的时候,新联通块一定是一堆旧的联通块加上一个矩形

加上一个矩形)

对于新的联通块,我们并不在意上面几个联通块哪些位置放了车,只在意有几列被放了车,即放了几个车。

因此,我们合并的时候先统计旧的联通块有多少种合法情况放了$i$个车,这很明显是一个使用背包的计数题。

处理完上面的联通块后,我们再处理下面新增的矩形。

我们只需要枚举上面联通块车的个数,和下面联通块车的个数,就可以利用组合数算出情况个数。
$$
dp_{i+j}=\sum dp_i\times C_{\Delta h}^j \times A_{len}^j
$$
(似乎$dp_0$要特殊处理)

答案就是总段的$dp_k$

代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<bitset>
using namespace std;
template<typename __T>
inline void read(__T &x)
{
    x=0;
    int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')   f=-1;c=getchar();}
    while(isdigit(c))   {x=x*10+c-'0';c=getchar();}
    x*=f;
}
const int mod=1000000007;
int frac[1000005];
int fracinv[1000005];
long long qpow(long long a,long long b)
{
    long long ans=1;
    while(b)
    {
        if(b&1) ans=(ans*a)%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
int C(int n,int m)
{
    if(n<m) return 0;
    return 1ll*frac[n]*fracinv[n-m]%mod*fracinv[m]%mod;
}
int Cinv(int n,int m)
{
    return 1ll*fracinv[n]*frac[n-m]%mod*frac[m]%mod;
}
int A(int n,int m)
{
    return 1ll*frac[n]*fracinv[n-m]%mod;
}
int h[505];
int n,k;
int dp[505][505];
int tmp[505];
int tot=1;
void dfs(int l,int r,int id,int lasth)
{
    int minz=12345678;
    for(int i=l;i<=r;i++)
        minz=min(minz,h[i]);
    int top=0;
    int sta[505];
    for(int i=l;i<=r;i++)
        if(h[i]==minz)
            sta[top++]=i;
    if(top==r-l+1)
    {
        for(int i=0;i<=top;i++)
            dp[id][i]=1ll*C(minz-lasth,i)*A(top,i)%mod;
        return;
    }
    int laspos=l;
    int edpos=l;
    dp[id][0]=1;
    while(laspos<=r)
    {
        while(h[laspos]==minz)  laspos++;
        if(laspos>r)    break;
        edpos=laspos;
        while(edpos<r && h[edpos+1]>minz)   edpos++;
        int neid=++tot;
        dfs(laspos,edpos,neid,minz);
            memcpy(tmp,dp[id],4*k+4);
            memset(dp[id],0,4*k+4);
        for(int i=0;i<=laspos;i++)
            for(int j=0;j<=edpos-laspos+1;j++)
                dp[id][i+j]=(dp[id][i+j]+1ll*tmp[i]*dp[neid][j])%mod;
        dp[id][0]=1;
        laspos=edpos+1;
    }
    memcpy(tmp,dp[id],4*k+4);
    memset(dp[id],0,4*k+4);
    for(int i=0;i<=r-l+1-top;i++)
        for(int j=0;j<=r-l+1-i;j++)
            dp[id][i+j]=(dp[id][i+j]+1ll*tmp[i]*C(minz-lasth,j)%mod*A(r-l+1-i,j))%mod;
    dp[id][0]=1;
}
int main()
{
    read(n);
    read(k);
    int sbsx=n;
    for(int i=0;i<n;i++)
    {
        read(h[i]);
        sbsx=max(sbsx,h[i]);
    }
    frac[0]=1;
    for(int i=1;i<=sbsx;i++)
        frac[i]=1ll*frac[i-1]*i%mod;
    fracinv[sbsx]=qpow(frac[sbsx],mod-2);
    for(int i=sbsx-1;i>0;i--)
        fracinv[i]=1ll*fracinv[i+1]*(i+1)%mod;
    fracinv[0]=1;
    dfs(0,n-1,1,0);
    printf("%d\n",dp[1][k]);
    return 0;
}

参考

没有

[BZOJ2554]Color 期望神题

传送门

Description

有n个球排成一列,每个球都有一个颜色,用A-Z的大写字母来表示,我们每次随机选出两个球ball1,ball2,使得后者染上前者的颜色,求期望操作多少次,才能使得所有球的颜色都一样?

Input

一行一个字符串,表示球的颜色

Output

一行表示结果,精确到小数点后1位。

Sample Input

AAA

Sample Output

0.0

HINT

数据范围
对于10%的数据,n<=20
对于40%的数据,n<=200
对于50%的数据,n<=1000
对于100% 的数据,n <= 10000

Source

Ctsc模拟赛By 洁妹

题解

首先我们可以发现,这道题其实与字母本身以及具体位置无关,只和各字母的个数有关。

为了方便,下文我将“将所有字母的颜色染成$a$”简称为“$a$全部覆盖”。

对于一种颜色$a$,若我们求出颜色$a$能全部覆盖的概率以及期望步数,我们便可以求出答案。

具体的,答案为$\sum E'(a)\times P'(a)$。

显而易见,若$a$与$b$的个数相同,则$E'(a)=E'(b)$且$P'(a)=P'(b)$。

由此结论,我们可以定义$E(x)$表示当字母个数为$x$时全部覆盖的期望步数。

同理,定义$P(x)$表示当字母个数为$x$时全部覆盖的概率。

现在我们针对某一个字母全部覆盖进行讨论,对于别的不同的字母是等价的。

我们设这个字母是$a$,其余所有字母为$b$。

我们先计算$P(x)$。

显而易见,$P(n)=1,P(0)=0$。

对于一个字符串有$x$个$a$的状态$S_x$,可以在下一步直接转移到状态$S_{x-1},S_{x+1}\ $。对于所有的选法,可以算出有$i\times(n-i)$种可以转移到$S_{x-1}$,有$i\times(n-i)$种转移到$S_{x+1}$,明显这两种转移概率相等。

所以有$P(x)=\frac{P(x-1)+P(x+1)}{2}$,即$P(x)-P(x-1)=P(x-1)-P(x-2)$。所以数列$P$等差。

易得$P(x)=\frac{x}{n}$。

至此,我们求出了$P(x)$,之后我们计算$E(x)$。

由上面所得结论,可以发现每次操作后$x$变化的选择有$2x(n-x)$,可以算出每次操作$x$变化的概率为$\frac{2x(n-x)}{T}$,所以操作使$x$变化的期望轮数为$\frac{T}{2x(n-x)}$。

值得注意的是,由于我们算得期望$E(x)$表示有$x$个字母完全覆盖时的期望步数,而$P(x-1)$与$P(x+1)$不等,所以$E(x-1)$与$E(x+1)$对$E(x)$带来的贡献的权重也不等,而带来的贡献的权重比就等于它们的完全覆盖的概率比。

因此,我们可以得出
$$
E(x)=\frac{P(i-1)\times E(i-1)+P(i+1)\times E(i+1)}{P(x-1)+P(x+1)}+\frac{T}{2x(n-x)}\\=\frac{(x-1)E(x-1)+(x+1)E(x+1)}{2x}+\frac{n(n-1)}{2x(n-x)}
$$
值得注意的是,我们求答案时求的是$\sum \frac{E(Cnt_i)\times i}{n}$。

我们不妨设$f(x)=\frac{E(x)\times x}{n}$。

则上式可化为
$$
\frac{f(x)\times n}{x}=\frac{f(x-1)\times n+f(x+1)\times n}{2x}+\frac{n(n-1)}{2x(n-x)}\\
2f(x)=f(x-1)+f(x+1)+\frac{n-1}{n-x}\\
f(x+1)=2f(x)-f(x-1)-\frac{n-1}{n-x}
$$
容易得到$E(n)=0$,又因为$S_0$永远无法完全覆盖,所以对期望不够成贡献(但是仍然有一定概率被转移到),所以我们令$E(0)=0$。

所以可以得到$f(n)=0,f(0)=0$。

那么如何推出剩余的$f(x)$。

(下面的结论我是先找规律后证明的,过程较乱)

我们先将$x=n-1$带入上式,得到
$$
f(n)=2f(n-1)-f(n-2)-(n-1)=0
$$
我们假设有
$$
(n-x+1)f(x)-(n-x)f(x-1)-(n-x)(n-1)=0
$$
那么我们将$f(x)=2f(x-1)-f(x-2)-\frac{n-1}{n-x+1}$带入,得到
$$
2(n-x+1)f(x-1)-(n-x+1)f(x-2)-(n-1)\\-(n-x)f(x-1)-(n-x)(n-1)\\
=(n-x+2)f(x-1)-(n-x-1)f(x-2)\\-(n-x+1)(n-1)=0
$$
令$X=x-1$,则可以得出
$$
(n-X+1)f(X)-(n-X)f(X-1)-(n-X)(n-1)=0
$$
所以,上式成立。

所以,当$X=1$时,可以得到
$$
nf(1)-(n-1)f(0)-(n-1)(n-1)=0\\
f(1)=\frac{(n-1)^2}{n}
$$
至此,我们得到了$f(0)$与$f(1)$。

我们只需要递推计算$f(x)$即可。

答案为$\sum f(Cnt_i)$。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
using namespace std;
template<typename __T>
inline void read(__T &x)
{
    x=0;
    int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')   f=-1;c=getchar();}
    while(isdigit(c))   {x=x*10+c-'0';c=getchar();}
    x*=f;
}
char str[10005];
int cnt[66];
double dp[10005];
int n;
int main()
{
    scanf("%s",str);
    n=strlen(str);
    for(int i=0;i<n;i++)
        cnt[str[i]-'A']++;
    dp[1]=(n-1.0)*(n-1.0)/n;
    for(int i=1;i<n-1;i++)
        dp[i+1]=2*dp[i]-dp[i-1]-(n-1.0)/(n-i);
    double ans=0;
    for(int i=0;i<26;i++)
        ans+=dp[cnt[i]];
    printf("%.1lf\\n",ans);
    return 0;
}

参考

liu-runda

CQZhangyu

miskcoo

rising_shit