一.
猴子吃桃问题：猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个 第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了。求第一天共摘了多少。
代码如下：
if __name__=='__main__':
x=1;
for i in range(1,10):
x=x+1;
x*=2;
print(x);
1534个桃子。。。。
二.百米
import requests;
import re;
def get_calculate(url,session):
r=session.get(url);
str=re.findall(r"<div name='my_expr'>"+'.*'+'</div>=?',r.text);
cal=str[0].lstrip("<div name='my_expr'>");
cal=cal.rstrip(" </div>=");
cal=cal.replace('x','*');
print(cal);
return cal;
def calcu(cal):
num_list=re.findall(r'\d{2,4}',cal);
for i in range(0,len(num_list)):
num_list[i]=int(num_list[i]);
result=(num_list[0]+num_list[1])*(num_list[2]-num_list[3])-((num_list[4]+num_list[5]-num_list[6]))*num_list[7];
print(result);
return result;
def post_result(result,session):
payload={'pass_key':result};
r = session.post("http://ctf5.shiyanbar.com/jia/index.php?action=check_pass", data=payload);
print(r.text);
if __name__=='__main__':
session=requests.session();
cal=get_calculate('http://ctf5.shiyanbar.com/jia/index.php',session);
result=calcu(cal);
post_result(result,session);
图一
如图，直接上代码解决，有坑是必须同个session get和post不然出不来结果。。。。
三.迷宫大逃亡
解决带啊吗如下所示：
import base64
def openfile():
result="";
f=open('in.txt','r');#open file
total_num=int(f.readline().strip());#get the number of maze
while(total_num!=0):
line=None;
while not line:
line=f.readline().strip();
scale=int(line);#maze scale
start=[];
for x in f.readline().strip().split():#get the start location
start.append(int(x)-1);
end=[];
for x in f.readline().strip().split():#get the end location
end.append(int(x)-1);
maze=[];
for m in range(scale):
maze.append(f.readline().strip());
r=pyqueue(len(maze[0]),start,end,maze);
result+=str(r.run());
total_num=total_num-1;
print(result);
flag = ""
for i in range(0, len(result), 8):
c = result[i:i + 8]
flag += chr(int(c, 2))
print(base64.b64decode(flag))
class pyqueue:
def __init__(self,_len,_start,_end,_maze):
self.len=_len #maze scale
self.start=_start;
self.end=_end;
self.maze=_maze;
self.queue=[self.start];#ininial location
self.steptrace=[];# trace route
self.success=0;# success flag
def Inquque(self,location):
self.queue.append(location);
self.steptrace.append(location);
return True;
def Qqueue(self):
temp=self.queue[0];
del(self.queue[0]);
return temp;
def Void(self,location):
try:
if location in self.steptrace or self.maze[location[0]][location[1]]=='X':
return;
else:
if location == self.end:
self.success = 1;
return;
self.steptrace.append(location);
self.Inquque(location);
return;
except:
print('error');
print(location);
def empty(self):
try:
self.queue[0];
return True;
except IndexError:
return False;
def addx(self,x):
x+=1;
if x>=self.len:
return x-1;
else:
return x;
def subx(self,x):
x-=1;
if x<0:
return x+1;
else:
return x;
def run(self):
return str(self.wayto_mazeend());
def wayto_mazeend(self):
while self.empty():
location=self.Qqueue();
self.Void([self.addx(location[0]),location[1]]);
self.Void([self.subx(location[0]),location[1]]);
self.Void([location[0],self.addx(location[1])]);
self.Void([location[0],self.subx(location[1])]);
if self.success==1:
return 1;
return 0;
if __name__=='__main__':
openfile();
这是用了bfs广度优先算法解决出来的，程序逻辑思路是每一个迷宫能成功走出就返回1，不能就返回0，然后就直接把几百个迷宫走一次，接着直接每八位为一段，返回所谓的ASCII编码字符，最后是一个base64编码解出来URL直接获取flag。
这道题目坑的地方在于要除掉URL后面的字母，接着访问新题目的链接才是flag...
四.三羊生瑞
这道题目就是明显的计算式子，想法不难有点繁琐。。。
'''
祥a 瑞b 生c 辉d
+ 三e 羊f 献g 瑞b
-——————
三e 羊f 生c 瑞b 气h
'''
a=9;
e=1;
f=0;
def find():
for b in range(0,10):
for c in range(0,10):
for d in range(0,10):
for g in range(0,10):
for h in range(0,10):
if((e*10000+f*1000+c*100+b*10+h)==((a*1000+b*100+c*10+d)+(e*1000+f*100+g*10+b))):
if a!=b and a!=c and a!=d and a!=e and a!=f and a!=g and a!=h:
if b!=c and b!=d and b!=e and b!=f and b!=g and b!=h:
if c!=d and c!=e and c!=f and c!=g and c!=h:
if d!=e and d!=f and d!=g and d!=h:
if e!=f and e!=g and e!=h:
if f!=g and f!=h:
if g!=h:
print(a, b, c, d);
print(e, f, g, b);
print(e, f, c, b, h);
return;
if __name__=='__main__':
find();
想起以前做过某道找数字的题目，做完以后还和社长去华师吃饭呢。。。。怀念。。
五.找素数
设一个等差数列，首元素为367，公差为186, 现在要求找出属于该等差数列中的第151个素数并输出。
这道题难点在于素数快速判断，这里学习一波。。。
import math;
def is_prime(num):
if num==2 or num==3:
return 1;
elif num%6!=1 and num%6!=5:
return 0;
else:
temp=math.sqrt(num);
i=5;
while i<=temp:
if num%i==0 or num%(i+2)==0:
return 0;
else:
i+=6;
return 1;
if __name__=='__main__':
a=[];
i=0;
while(len(a)<151):
temp=367+186*i;
if is_prime(temp)==1:
a.append(temp);
i+=1;
print(a[len(a)-1]);
p1
这里的方法还是学下。。。
六.小球下落
这道题目算是二叉树简单概念的应用了，最后要找叶子编号。。。
if __name__=='__main__':
a = [0 for i in range(0, 65536)];
for i in range(12345):
temp=1;
for x in range(0,15):
if(a[temp]==0):
a[temp]=~a[temp];
temp=temp*2;
else:
a[temp]=~a[temp];
temp=temp*2+1;
if i==12344:
print(temp);
难度基本可以接受。。
七.普里姆路径
这道题目是BFS算法思想的应用，主要是中间这一步生成新数字的做法有点没接触过，学习一波了。。。
import math
def is_prime(num):
if num==2 or num==3:
return 1;
elif num%6!=1 and num%6!=5:
return 0;
else:
temp=math.sqrt(num);
i=5;
while i<=temp:
if num%i==0 or num%(i+2)==0:
return 0;
else:
i+=6;
return 1;
class node:
def __init__(self,element,step):
self.element=element;
self.step=step;
def bfs():
start=1373;
end=8017;
Queue=[node(start,0)];
visited=[start];
while(len(Queue)!=0):
now=Queue[0];
del Queue[0];
if now.element==end:
return now.step;
else:
for i in range(4):
for j in range(10):
if i==0 and j==0:
continue;
else:
temp=int(str(now.element)[:i]+str(j)+str(now.element)[i+1:]);
if is_prime(temp)==1:
if temp not in visited:
visited.append(temp);
Queue.append(node(temp,now.step+1));
return False;
if __name__ == '__main__':
print(bfs());
总体还行，学习一波。。
八.大数模运算
这道题目主要是考察几条数学运算式子，如下：
if __name__ == '__main__':
key1 = key2 = key3 = 0;
for i in range(0, 12346):
key1 += 3 ** i % 9901;
key2 += 5 ** i % 9901;
key3 += 823 ** i % 9901;
print((key1 * key2 * key3) % 9901);
p2
九.括号表达式
一个括号表达式可以按照如下的规则表示，就是每个右括号之前的左括号数。
比如(((()()())))，每个右括号之前的左括号数序列为P=4 5 6 6 6 6，而每个右括号所在的括号内包含的括号数为W=1 1 1 4 5 6。
现在给定一个括号表达式为 4 6 6 6 6 8 9 9 9，输出每个右括号所在的括号内包含的括号数。
这道题目主要是要研究规律，从而找到位置差以及括号差之间的关系。代码如下所示：
if __name__ == '__main__':
left=[0,4,6,6,6,6,8,9,9,9];
lists=[];
for i in range(1,len(left)):
j=i-1;
while(left[i]-left[j]<i-j):
j-=1;
print(i-j);
lists.append(i-j);
for i in lists:
print(i);
今天这几道总体难度还行。。。
十.大数据问题
这道题直接暴力求解的。。
if __name__ == '__main__':
sum=0;
for i in range(1,6790):
sum+=math.factorial(i);
print(sum%100000)
十一.斐波那契数列
这个比较熟悉了，不迭代了直接调用如下代码
def function(num):
lists=[1,1,1];
sum=0;
i=0;
if num<=2:
print(3);
else:
while(i<num):
sum=lists[i]+lists[i+1]+lists[i+2];
lists.append(sum);
i+=1;
print(lists[num]);
if __name__ == '__main__':
function(99)
十二.聪明的打字员
这道题目怎么说呢，恕我太蠢，C++的算法写法看不懂，只能上所谓的暴力解法了。。。
def fun(a,depth,b):
if(depth==1):
for i in a:
b[-depth]=i;
yield b;
else:
for i in a:
b[-depth]=i;
for j in fun(a,depth-1,b):
yield j;
def func():
time=0;
step=[0,1,2,3,4,5];
while(1):
time+=1;
for i in fun(step,time,[1]*time):
work=0;
a=[1,2,3,4,5,6];
for j in i:
if(j==0):
a[work],a[0]=a[0],a[work];
elif(j==1):
a[work],a[5]=a[5],a[work];
elif(j==2):
if(a[work]<9):
a[work]+=1;
elif(j==3):
if(a[work]>0):
a[work]-=1;
elif(j==4):
if(work>0):
work-=1;
elif(j==5):
if(work<5):
work+=1;
if(a==[6,5,4,3,2,1]):
print(time);
return;
print(time);
if __name__=='__main__':
func();
解法时间比较长，差不多要五分钟。。。。
十三.二叉树遍历
这个顺便学一波二叉树遍历的python写法，代码如下：
class TreeNode(object):
def __init__(self):
self.data='#';
self.l_child=None;
self.r_child=None;
class Tree(TreeNode):
def create_tree(self,tree):
data=input('->');
if data=='#':
tree=None;
else:
tree.data=data;
tree.l_child=TreeNode();
self.create_tree(tree.l_child);
tree.r_child=TreeNode();
self.create_tree(tree.r_child);
def visit(self,tree):
if tree.data is not '#':
print(tree.data);
print('\t');
def pre_order(self,tree):
if tree is not None:
self.visit(tree);
self.pre_order(tree.l_child);
self.pre_order(tree.r_child);
def in_order(self,tree):
if tree is not None:
self.in_order(tree.l_child);
self.visit(tree);
self.in_order(tree.r_child);
def post_order(self,tree):
if tree is not None:
self.post_order(tree.l_child);
self.post_order(tree.r_child);
self.visit(tree);
if __name__=='__main__':
t=TreeNode();
tree=Tree();
tree.create_tree(t);
tree.pre_order(t);
print('\n');
tree.in_order(t);
print('\n');
tree.post_order(t);
二叉树里面这种递归的做法是真的多。。。
十四.约瑟夫问题
def kill(people,num):
work=0;
while(len(people)>=12):
if people.count(1)<12:
return False;
else:
work=(work+num-1)%len(people);
del a[work];
return True;
if __name__=='__main__':
for i in range(13,2000000):
a = [1] * 12 + [0] * 12;
if kill(a,i)==True:
print(i);
break;
else:
continue;
十五.双基回文数
这道题目主要学习了进制转换法吧，记清楚就行。。
def handle(value,hex_number):
sss='';
while(value!=0):
sss+=str(int(value%hex_number));
value=((value-value%hex_number)/hex_number);
return sss[::-1];
def ok(number):
for i in range(0,int(len(number)/2)):
if number[i]!=number[len(number)-1-i]:
return False;
return True;
if __name__=='__main__':
sum=1600000
while(1):
times=0;
for i in range(2,11):
if(ok(handle(sum,i))):
times+=1;
if times>1:
print(sum);
break;
sum+=1;
十六.两个最大字串和
这道题目看了贼久，最后还是用贪心算法解决的，直接定义贪心算法的条件如下：
p3
就是如果当前子序列和为负数那就直接丢弃掉就行。。
最后上我的代码如下：
a=[-132,133,134,-11,12,-139,-140,62,63,-64,65,66,67,
1,2,3,4,5,-6,7,-48,-49,50,138,16,17,20,
101,102,-103,104,-105,106,146,147,148,-107,108,109,110,96,
21,-22,23,-24,-25,25,-27,-28,-29,30,
41,-42,8,9,10,-46,-47,
51,52,-53,54,-55,-56,57,-58,59,60,
73,-74,75,-71,-72,18,-97,-98,19,-129,130,
-137,136,-13,14,144,-145,15,128,
77,-78,-31,32,35,-76,149,-150,99,100,119,
91,-92,-93,94,95,116,117,114,118,120,
81,82,83,-84,85,-122,-123,
112,111,-43,44,45,-113,-115,36,-37,-38,39,40,25,126,127,
131,-135,61,-69,70,
141,-142,143,-86,68,-87,-90,
121,-88,89,-124,-179,-80,-33,34]
if __name__=='__main__':
value1=[9999]*150;
value2=[9999]*150;
sum,max=0,0;
for i in range(0,len(a),1):
if(sum<0):
sum=a[i];
else:
sum+=a[i];
if sum>max:
max=sum;
value1[i]=max;
sum,max=0,0;
for i in range(149,-1,-1):
if (sum < 0):
sum = a[i];
else:
sum += a[i];
if sum > max:
max = sum;
value2[i] = max;
for i in range(0,149,1):
if(value1[i]+value2[i+1]>max):
max=value1[i]+value2[i+1];
print(max);
算法还是要多学学的。。。
十七.分数拆分
1/400=1/x+1/2y
也即1/x=1/400-1/2y=1/2(1/200-1/y)=1/2((y-200)/200y)=(y-200)/400y
也即x=400y/(y-200)由于x,y皆为正整数，故y>200
当x=y时
1=400/x-200 x-200=400 x=600
代入y=700算出x=560因此y应该小于600
故200<y<600
count=0
num_list=[]
for y in range(201,600):
if (400*y)%(y-200)==0:
count=count+1
str_add=str((400*y)/(y-200))+':'+str(y)
num_list.append(str_add)
print(num_list)
print('CTF{'+str(count)+'}')
十八.ascii art
这道题有点傻逼，就是直接替换而已。。。
import requests;
import re;
if __name__=='__main__':
url='http://ctf5.shiyanbar.com/ppc/acsii.php';
s=requests.session()
response=s.get(url);
patten=r'red">'+'.*'+'</div>';
num=re.findall(patten,response.text)[0];
num = num.replace(' xxx <br />x x<br />x x<br />x x<br /> xxx <br />','0')
num = num.replace(' xx<br /> x x <br /> x <br /> x <br />xxxxx<br />','1')
num = num.replace(' xx<br> x x <br> x <br> x <br>xxxxx<br><br/>','1')
num = num.replace(' xxx <br />x x <br /> xx <br /> x <br />xxxxx<br />','2')
num = num.replace(' xxx <br />x x<br /> xx <br />x x<br /> xxx <br />','8')
num = num.replace('xxxxx<br />x <br /> xxxx<br /> x<br />xxxxx<br />', '5')
num = num.replace(' x x<br />x x<br /> xxxxx<br /> x<br /> x<br />','4')
num = num.replace('xxxxx<br />x <br /> xxxx<br /> x<br />xxxxx<br />', '5')
num = num.replace('<br/>', '');
num=num.replace('red">','');
num=num.replace('</div>','');
response1=s.post(url,data={'inputNumber':num});
print(response1.text);
十九.速度爆破
这题难度很低，代码
import requests;
import re;
import hashlib;
def hash_key(arg):
hash = hashlib.md5();
hash.update(arg.encode());
hash_sha=hashlib.sha1();
hash_sha.update(hash.hexdigest().encode())
return hash_sha.hexdigest()
if __name__=='__main__':
url='http://ctf5.shiyanbar.com/ppc/sd.php';
s=requests.session()
response=s.get(url);
patten=r'red">'+'.*'+'</div>';
num=re.findall(patten,response.text)[0];
num = num.replace('red">', '');
num = num.replace('</div>', '');
for i in range(0,100000):
if hash_key(str(i))==num:
break;
response1=s.post(url,data={'inputNumber':i});
print(response1.text);
二十.海量约瑟夫问题
这个有个公式推导，可以解决一般的约瑟夫问题，如下图：
p4
通用代码如下所示：
def process(n,m):
if(n<1 or m<1):
return False;
else:
flag=0;
result1,result2=0,0;
for i in range(2,n+1,1):
if(flag==0):
result1 = (result2 + m) % i;
flag=1;
else:
result2 = (result1 + m) % i;
flag = 0;
print(i);
return lambda x:result1 if(flag==1) else result2;
if __name__=='__main__':
n = 57109519409189850198608692898492839208109598203852985209815058928520938958906207207017014242749827958752975981705872782758927827398578971498749287481591758917982491;
print(process(n,2)%129119417519);
但是这个并无法解决海量数据时的问题，看了writeup代码也是出错的，有一个答主的代码很神奇却对了，如下：
>>>n=57109519409189850198608692898492839208109598203852985209815058928520938958906207207017014242749827958752975981705872782758927827398578971498749287481591758917982491
>>>((n-2**543)*2+1)%129119417519
想不懂啥道理。。。。不过这一波接触了海量数据以后发现，数据一多真的算法都不一样了。。。。差好大
二十一.Noise
这道题目就主要是处理图片躁点，没学过这个认真学一下。。
if __name__=='__main__':
a = ['0'] * 256 * 256
from PIL import Image
im = Image.open("noise.png")
img = Image.new('RGB', (256, 256), (255, 255, 255))
loding = img.load()
sum = 0
for x in range(0, 256):
for y in range(0, 256):
i = im.getpixel((x, y))[1]
j = im.getpixel((x, y))[2]
loding[i, j] = (0, 0, 0)
sum += 1
if sum > 30000:
break
img.show()
二十二.hashkill
刷多了算法题来做这种程序编写题真是so easy。。。
import hashlib;
import os;
def hash_key(arg):
hash = hashlib.md5();
hash.update(arg.encode());
return hash.hexdigest()
if __name__=='__main__':
location=["thebronx","brooklyn","manhattan","queens","statenisland"];
for i in range(0,1001):
for y in location:
for j in range(10000, 15000):
str1 = 'ctf{' + str(i) + '_' +y+'_'+str(j)+'}'
if(hash_key(str1)=='6ac66ed89ef9654cf25eb88c21f4ecd0'):
print(str1);
os._exit(0);
二十三.求解
这道题就是简单凯撒加密而已，就是string类型可以索引访问这一点学到了。。。
if __name__=='__main__':
list = 'abcdefghijklmnopqrstuvwxyz'
newlist = ''
for i in range(len(list)):
newlist += list[(5 * i + 11) % 26]
y = 'xztiofwhf'
x = ''
for j in y:
x += list[newlist.find(j)] # 查找新列表字符对应的位置，在旧列表同样的位置即为flag
print(newlist.find('x'));
二十四.
