逆向一个crackme(4)

(注意:本文的代码都是有格式的,但是网页加载比较慢,如果看每格式的代码比较累,可以稍作等待,等网页加载完毕即可显示格式。。。)
这是160个crackme的第23个

 
crackme23
在做这个crackme之前,c/c++或者masm/tasm写的程序我都是直接od载入调试的,但是这个程序的算法昨天折腾了大半天还是没搞明白。无奈,今天第一次(基本上算第一次吧。。)用ida静态的来分析之,忽然就豁然开朗,ida的图形界面方式简直碉堡了。。

首先打开程序

要求输入name和serial,如果正确的话status里就会显示成功

peid载入发现是masm/tasm汇编写的

程序比较小,爆破就不说了,比较简单,下面用ida载入,看看程序流程

sub_401023是main函数,进去,找到窗口过程

进去之后,发现程序是调用了SetTimer定期检测两个输入框

来到WM_TIMER的地方,这里是关键

(注意:因为我分析过,所以函数名之类我已经改过了)

这里有两个全局变量:

dword ptr [403166]  不妨设为a

dword ptr [403167]  不妨设为b

事实上待会还会涉及到一个全局变量dword ptr [403168]  不妨设为c

通过分析call switcha之后的代码可以发现,当a=16,b!=16时注册成功

好,来看关键函数switcha()

不知道为什么ida没有分析完整,第一次用ida,我也不知道怎么弄。。

事实上这里的retn的作用是jmp。并不是真的返回。我们用od分析。

注意下面这几句

00401459 |. 8925 A0314000 mov dword ptr ds:[0x4031A0],esp
0040145F |. 8D25 52314000 lea esp,dword ptr ds:[0x403152] ;
00401465 |. 0FBE05 66314000 movsx eax,byte ptr ds:[0x403166]
0040146C |. 03E0 add esp,eax

把esp保存之后将esp指向内存地址0×403152,然后再add变量a,这样之后retn,那么显然程序会跳到0×403152+a内的值所指向的地方接着执行,相当于jmp dword ptr [0x403152+eax]。(原因在于retn的本质是pop eip;jmp eip)

接着我们该做的事当然是看看0×403152这个地方存了什么东东

我们发现其实是5个地址值。

那么可以判断这个函数其实是根据变量a的值的不同跳转到不同分支去执行,这不就是switch语句吗。

具体来看这5个地址处的指令

 

;跳转0
0040146F  mov esp,dword ptr ds:[0x4031A0]
00401475  push 0x0                                 ; /IsSigned = FALSE
00401477  lea eax,dword ptr ss:[ebp-0x4]           ; |
0040147A  push eax                                 ; |pSuccess
0040147B  push 0x64                                ; |ControlID = 64 (100.)
0040147D  push dword ptr ds:[0x403170]             ; |hWnd = NULL
00401483  call <jmp.&USER32.GetDlgItemInt>         ; \GetDlgItemInt
00401488  mov dword ptr ds:[0x403188],eax          ;  序列号存入变量0x403188,不妨设为p
0040148D  cmp dword ptr ss:[ebp-0x4],0x0           ;  读取是否成功
00401491  je XChafe_1.0040149A
00401493  add byte ptr ds:[0x403166],0x4           ;  a+=4
0040149A  leave
0040149B  retn


;跳转1
00401063  mov esp,dword ptr ds:[0x4031A0]
00401069  push 0x14                                ; /Count = 14 (20.)
0040106B  push Chafe_1.0040318C                    ; |用户名存入0x40318c,不妨设为u
00401070  push dword ptr ds:[0x403174]             ; |hWnd = NULL
00401076  call <jmp.&USER32.GetWindowTextA>        ; \GetWindowTextA
0040107B  mov ecx,0x14                             ;  函数读取20个字符
00401080  sub ecx,eax
00401082  lea edi,dword ptr ds:[eax+0x40318C]
00401088  mov byte ptr ds:[edi],0x0
0040108B  inc edi
0040108C  dec ecx                                  ;  这个循环是把读取的name后的空间填0
0040108D  jnz XChafe_1.00401088                    ;  这样做是因为实际上算法用到了19个byte
0040108F  test eax,eax
00401091  je XChafe_1.004010A3
00401093  add byte ptr ds:[0x403166],0x4           ;  如果成功读取则a+=4
0040109A  mov byte ptr ds:[0x403168],0x0           ;  c=0
004010A1  jmp XChafe_1.004010A9
004010A3  mov byte ptr ds:[0x403166],ah            ;  没有输入用户名则a=0
004010A9  leave
004010AA  retn

;跳转2
00401361  lea edi,dword ptr ds:[0x40318C]
00401367  movsx eax,byte ptr ds:[0x403168]
0040136E  add edi,eax                              ;  u1
00401370  inc byte ptr ds:[0x403168]               ;  c++
00401376  mov eax,dword ptr ds:[0x403188]          ;  eax=p
0040137B  mov esp,dword ptr ds:[0x4031A0]          ;  恢复堆栈
00401381  inc eax                                  ;  p++
00401382  inc dword ptr ds:[0x403188]
00401388  xor eax,dword ptr ds:[edi]               ;  p^=((u1<<24)+(u1<<16)+(u1<<8)+u1)
0040138A  mov dword ptr ds:[0x403188],eax
0040138F  cmp byte ptr ds:[0x403168],0x10          ;  c==16?
00401396  jnz XChafe_1.0040139F
00401398  add byte ptr ds:[0x403166],0x4
0040139F  leave
004013A0  retn

;跳转3
0040149C  mov eax,dword ptr ds:[0x403188]
004014A1  add eax,0x9112478                        ;  p+0x9112478==0?
004014A6  test eax,eax
004014A8  jnz XChafe_1.004014B3
004014AA  add byte ptr ds:[0x403166],0x4
004014B1  jmp XChafe_1.004014BA
004014B3  mov byte ptr ds:[0x403166],0x0
004014BA  mov esp,dword ptr ds:[0x4031A0]
004014C0  leave
004014C1  retn

;跳转4
004014BA  mov esp,dword ptr ds:[0x4031A0]
004014C0  leave
004014C1  retn

这五段代码联系起来看,这个switch就好理解了,用伪代码写写看

 

switch(a):
	case 0:
		if(输入了序列号p) a+=4;
		break;
	case 4:
		if(输入了用户名u[]) a+=4,b=0;
		else a=0;
		break;
	case 8:
		p+=1;
		p^=((u[C+3]<<24)+(u[C+2]<<16)+(u[C+1]<<8)+u[C]);//这里写成小写c会导致显示错误,wp的bug??
		c+=1;
		if(c==16) a+=4;
		break;
	case 12:
		if(p+0x9112478==0) a+=4;
		else a=0;
		break;
	case 16:
		break;

可以发现,这几个case是上面的成功了下次WM_TIMER来的时候就会执行下面的,所以作者写的时候目测是用if语句(因为是masm,所以应该是.if  .endif,win32汇编。。可能记错了语法,别打我。。)
又由于timer相当于while(1)
于是,用正常点的代码来叙述,如下

 

while(1)
{
	if(输入了序列号p)
	{
		if(输入了用户名u[])
		{
			for(c=0;c<16;c++)
			{
				p+=1;
				p^=((u[C+3] <<24)+(u[C+2] <<16)+(u[C+1] <<8)+u[C]);			
			}
			if(p==(uint)(-0x9112478)) 显示注册成功;
		}


	}
	显示注册失败;
}

大功告成,算法逆过来很简单,下面是注册机

 

#include<stdio.h>
#include<string.h>
typedef unsigned int uint;
typedef unsigned char uchar;
uchar s[20];
const uint xh=0x9112478;
int main()
{
    int i;
    while(~scanf("%s",s))
    {
        uint p=-xh;
        for(i=15;i>=0;i--)
        {
            p^=(uint)((s[i+3]<<24)+(s[i+2]<<16)+(s[i+1]<<8)+s[i]);
            p-=1;
        }
        printf("%u\n",p);

    }

    return 0;
}

PE工具编写

前几天把PE结构认真看了一下,顺便写了下类似peinfo的工具练练手,只不过是控制台的(windows sdk没怎么学,win32汇编也忘的差不多了,所以还是写成控制台的吧。。)。以前了解pe文件的时候总是走马观花,所以基本上印象全无。这次认认真真写写代码,收获还是比较大的。
说实话,pe结构的学习真的不难,但是非常考验耐心,特别是数据目录那里和资源结构那里,一层套一层,一定要耐心才行。
记下几个我认为重要的点,或者说收获:
0.rva和raw的转化
先看rva在哪个块(块表里面有一个块的起始rva和VirtualSize),块的起始raw也是可以得到的(也在对应的块表中)。然后raw=块起始raw+(rva-块起始rva)
简单吧。

1.c语言的指针

大家都知道,c语言的指针是所指向的变量的地址,那么这个地址到底是什么地址呢?va?还是rva?
由于我用的是SetFilePointer定位文件光标,再用ReadFile()把相关数据结构读取到内存,所以涉及到怎么定位光标的问题。这就需要知道要获取的数据结构的文件偏移,也就是raw。但是如下图所示,IMAGE_THUNK_DATA里面的AddressOfData是指向IMAGE_IMPORT_BY_NAME的指针,而不是raw。怎么办呢,我用winhex仔细看了下PE文件(把这个值当成rva,转化为raw,发现可以找到对应的IMAGE_IMPORT_BY_NAME),发现其实这个指针的值就是rva。
也就是说:c语言的指针就是所指向变量的rva

2.IMAGE_SECTION_HEADER中的MISC的VirtualSize域,下面这张图中说是未对齐时的真实大小,我觉得应该已经是内存地址空间中按页对齐时的大小(目前的看法)

3.关于IMAGE_IMPORT_DESCRIPTOR

简单来说,每个IMAGE_IMPORT_DESCRIPTOR对应一个导入的dll。以一个全0的IMAGE_IMPORT_DESCRIPTOR结束。

4.最后记一下pe加载到内存时windows加载器对导入表的修改

(1)windows加载器遍历pe文件,IMAGE_DOS_HEADER.elfanew—->IMAGE_NT_HEADERS.IMAGE_OPTIONAL_HEADER32.IMAGE_DATA_DIRECTORY[1].VirtualAddress—->IMAGE_IMPORT_DESCRIPTOR
IMAGE_IMPORT_DESCRIPTOR可能有多个,每个对应一个dll。
(2)然后根据IMAGE_IMPORT_DESCRIPTOR内的Name找到dll的名字,用loadlibrary加载这个dll。
(3)根据IMAGE_IMPORT_DESCRIPTOR的FirstThunk(是IAT数组的rva)找到IAT数组
(4)根据IAT数组元素IMAGE_THUNK_DATA32的AddressOfData找到IMAGE_IMPORT_BY_NAME(注意:IMAGE_THUNK_DATA32里面是一个联合体)
(5)这样就得到了导入函数的名字,然后用GetProcAdress()获取该函数的实际地址,填入IAT数组元素IMAGE_THUNK_DATA32,这样之后IAT数组里面的就是函数的真实(va)地址了

5.dll的加载:

显示:在需要的时候用LoadLibrary()和GetProcAddress()动态加载
隐式:windows加载器在PE文件映射到内存时填充IAT,加载对应dll文件

写的比较挫,暂时先主要把输入表中的函数名字显示出来,要显示其他内容也是一样的

—————————————————————————-
2015.2.6
突然觉得我写复杂了,其实可以一次性把PE文件全部读到一个字符串里面,不用一点一点读文件,不过这样也有好处,文件太大时前者行不通

#include&lt;stdio.h&gt;
#include&lt;string.h&gt;
#include&lt;windows.h&gt;
HANDLE hfile;
IMAGE_DOS_HEADER dos_head;
IMAGE_NT_HEADERS pe_head;
PIMAGE_FILE_HEADER pfile_head;
PIMAGE_OPTIONAL_HEADER32 poptional_head;
PIMAGE_DATA_DIRECTORY pdata_dir;
IMAGE_SECTION_HEADER sec_head[30];
IMAGE_IMPORT_DESCRIPTOR import[110];
IMAGE_THUNK_DATA32 thunk;//IAT
int dll_num;//导入的dll的个数
int sec_num;//块的个数
int ophead_size,dos_and_nt;
DWORD readsize;
DWORD rva2raw(DWORD rva)
{
	int i;
	DWORD sec_begin,sec_end;
	for(i=1;i&lt;=sec_num;i++)
	{
		sec_begin=sec_head[i].VirtualAddress;sec_end=sec_head[i].VirtualAddress+sec_head[i].Misc.VirtualSize;
		if(rva&lt;sec_begin || rva&gt;sec_end) continue;
		return sec_head[i].PointerToRawData+rva-sec_head[i].VirtualAddress;
	}
	return 0;
}
void read_error(int ret)
{
	if(!ret) 
	{
		printf(&quot;read error\n&quot;);
		CloseHandle(hfile);
		exit(1);
		return;
	}
	return;
}
void read_sechead()
{
	int i,j;
	for(i=1;i&lt;=sec_num;i++)
	{
		SetFilePointer(hfile,dos_and_nt+(i-1)*sizeof(IMAGE_SECTION_HEADER),0,FILE_BEGIN);
		int ret=ReadFile(hfile,&amp;sec_head[i],sizeof(sec_head[i]),&amp;readsize,0);
		read_error(ret);
	}
	return;
}
bool judge(IMAGE_IMPORT_DESCRIPTOR _import)//判断IMAGE_IMPORT_DESCRIPTOR是否读取完毕
{
	if(_import.OriginalFirstThunk==0 &amp;&amp; _import.FirstThunk==0 &amp;&amp; _import.ForwarderChain==0 &amp;&amp; _import.Name==0 &amp;&amp; _import.TimeDateStamp==0) return 0;
	return 1;
}
void read_import()
{
	dll_num=0;
	int src=rva2raw(pdata_dir[1].VirtualAddress);
	int offset=sizeof(IMAGE_IMPORT_DESCRIPTOR);
	while(1)
	{
		dll_num++;
		SetFilePointer(hfile,src+(dll_num-1)*offset,0,FILE_BEGIN);
		int ret=ReadFile(hfile,&amp;import[dll_num],sizeof(IMAGE_IMPORT_DESCRIPTOR),&amp;readsize,0);
		read_error(ret);
		if(!judge(import[dll_num])) {dll_num-=1;break;}
	}
	return;
}
void print_exp_and_imp()
{
	printf(&quot;type		rva			size\n&quot;);
	printf(&quot;导出表		%x			%x\n&quot;,pdata_dir[0].VirtualAddress,pdata_dir[0].Size);
	printf(&quot;导入表		%x			%x\n&quot;,pdata_dir[1].VirtualAddress,pdata_dir[1].Size);
	return;
}
void print_sec_info()
{
	int i;
	printf(&quot;the information of section:\n&quot;);
	printf(&quot;%10s%8s%15s%6s%14s%18s\n&quot;,&quot;name&quot;,&quot;rva&quot;,&quot;VirtualSize&quot;,&quot;raw&quot;,&quot;SizeOfRawData&quot;,&quot;Characteristics&quot;);
	for(i=1;i&lt;=sec_num;i++)
	{
		printf(&quot;%10s%10x%10x%10x%10x%18x\n&quot;,sec_head[i].Name,sec_head[i].VirtualAddress,sec_head[i].Misc.VirtualSize,sec_head[i].PointerToRawData,sec_head[i].SizeOfRawData,sec_head[i].Characteristics);
	}

}
void get_dllname(int i,char*dll_name)
{
	SetFilePointer(hfile,rva2raw(import[i].Name),0,FILE_BEGIN);
	int ret=ReadFile(hfile,dll_name,30,&amp;readsize,0);
	read_error(ret);
	return;
}
void print_dllfunc(int i)
{
	DWORD iat_entry=import[i].FirstThunk;
	iat_entry=rva2raw(iat_entry);
	int cc=0;
	while(1)
	{
		cc++;
		SetFilePointer(hfile,iat_entry+(cc-1)*sizeof(thunk),0,FILE_BEGIN);
		int ret=ReadFile(hfile,&amp;thunk,sizeof(thunk),&amp;readsize,0);
		read_error(ret);
		DWORD fname_rva=(DWORD)thunk.u1.AddressOfData;//注意:c语言的指针本质是rva
		if(fname_rva==0) break;
		DWORD fname_raw=rva2raw(fname_rva);//fname_raw为IMAGE_IMPORT_BY_NAME的raw
		char*s[100];
		SetFilePointer(hfile,fname_raw+2,0,FILE_BEGIN);//fname_raw+2是IMAGE_IMPORT_BY_NAME的Name[1]的raw
		ret=ReadFile(hfile,s,100,&amp;readsize,0);
		read_error(ret);
		printf(&quot;%s\n&quot;,s);
	}
	printf(&quot;\n&quot;);
	return;
}
void print_import()
{
	int i,j;
	char dll_name[30];
	printf(&quot;以下是导入表函数信息:\n&quot;);
	for(i=1;i&lt;=dll_num;i++)
	{
		get_dllname(i,dll_name);
		printf(&quot;%s\n&quot;,dll_name);
		print_dllfunc(i);
	}
	return;
}
int main()
{
	int i,j;
	char filename[1010];
	printf(&quot;请输入PE文件的绝对路径:&quot;);
	while(~scanf(&quot;%s&quot;,filename))
	{
		hfile=CreateFile(filename,GENERIC_READ,FILE_SHARE_READ,0,OPEN_EXISTING,FILE_ATTRIBUTE_NORMAL,0);
		if(hfile==INVALID_HANDLE_VALUE)
		{
			printf(&quot;file_open_error\n&quot;);
			return 0;
		}

		int ret=ReadFile(hfile,&amp;dos_head,sizeof(dos_head),&amp;readsize,0);
		read_error(ret);
		if(dos_head.e_magic!=0x5a4d)
		{
			printf(&quot;this is't a valid pe file\n&quot;);
			CloseHandle(hfile);
			return 0;
		}
		
		SetFilePointer(hfile,dos_head.e_lfanew,0,FILE_BEGIN);
		ret=ReadFile(hfile,&amp;pe_head,sizeof(pe_head),&amp;readsize,0);
		read_error(ret);
		if(pe_head.Signature!=0x4550)
		{
			printf(&quot;this is't a valid pe file\n&quot;);
			CloseHandle(hfile);
			return 0;
		}

		pfile_head=&amp;(pe_head.FileHeader);
		poptional_head=&amp;(pe_head.OptionalHeader);
		printf(&quot;the EP is %x\n&quot;,poptional_head-&gt;AddressOfEntryPoint);
		pdata_dir=poptional_head-&gt;DataDirectory;

		print_exp_and_imp();
		
		sec_num=pfile_head-&gt;NumberOfSections;
		ophead_size=pfile_head-&gt;SizeOfOptionalHeader;
		dos_and_nt=dos_head.e_lfanew+4+sizeof(*pfile_head)+ophead_size;//dos头和nt头总大小(不包括块表)
		
		read_sechead();
		print_sec_info();
		read_import();
		print_import();
		


		CloseHandle(hfile);
		printf(&quot;请输入PE文件的绝对路径:&quot;);
	}
	return 0;
}

关于vb反汇编

今天做一个VB写的crackme,程序本身很简单,但是却发现一个很奇怪的地方

看如下代码

0F0FEA42  xor eax,eax
0F0FEA44  mov al,byte ptr ds:[esi]
0F0FEA46  inc esi
0F0FEA47  jmp dword ptr ds:[eax*4+0xF0FED94]

这样的代码随处可见,而且程序几乎一直是在msvbvm50这个dll里面执行上述代码,几乎没有回到用户程序领空。后来搜了下,在看雪看到这个系列的文章,总算搞懂了,这里做下记录
VB P-code — 虚拟机的艺术
VB P-code — 调试器的革命
VB P-code — 伪代码的奥秘
这三篇文章讲的很详细,基本上是说:
vb的编译分两种,一是native,也就是直接编译成机器码,而是p-code,编译成字节码,由虚拟机引擎解释执行
上面的程序正是p-code方式,esi指向的是字节码指令所在的地址,mov al,byte ptr ds:[esi]这句就是取操作码,inc esi则是指针指向操作数(对双字节操作码的指令,则是指向第二级操作码),jmp dword ptr ds:[eax*4+0xF0FED94]这句中的0xF0FED94是跳转地址表的首地址。这个内存区域存放着所有vb字节码对应的机器码程序。上述代码正是利用字节码的操作码部分得出对应的机器指令程序段的地址,然后跳过去执行这条字节码的功能。
这也解决了我的问题。msvbvm50这个dll中存储了vb5.0的虚拟机代码,程序不断的通过虚拟机获取用户程序领空的字节码来执行,所以才会一直在msvbvm50.dll里面打转。而用户代码部分则od无法识别,原因就是这些代码都是字节码嘛。
然后又查了查,找到了一个叫vbdecomplier的反编译器,pcode方式的vb程序基本上都能看源码了。。

破解一个简单的程序

再来看一个。

MrBills

这个也是鱼c解密系列od调试篇里面的一个程序

这个系列的教学视频很不错,很基础,适合初学者。虽然里面讲的东西很多以前都学过,但是每个视频总会让我学到一点新知识。但是注意一点,看视频前一定要自己先尝试破解一下那节课的程序。这样才会有收获。

下面是我尝试破解的过程。

首先打开程序

wps4664.tmp[12]

发现标题中有Unregistered这样的字符串,打开about,发现有注册的按钮,并且文字说明当前版本是非注册版。

好,先以标题中的Unregistered为切入点。

od载入,运行。

查找所有参考文本串,发现找不到Unregistered。。但是发现了这么一个字符串

wps4684.tmp[11]

显然,这是注册后才会显示的字符串,双击来到相关代码处。往上找找看跳转,发现了如下代码:

wps4685.tmp[11]

这个je跳转如果成功,就会跳过刚才那个字符串的地方。显然

00402350  |.  E8 144D0000   call    00407069

这句是关键,因为al的值是否为0直接决定je的结果,所以这个call应该是判断是否有注册有关。

所以在402350处下断,重新载入运行。点about按钮触发一下中断,F7步入看看

往下发现该函数的最后几句如下:

00407125  |.  A0 A0765000   mov     al, byte ptr [5076A0]

0040712A  |.  64:890D 00000>mov     dword ptr fs:[0], ecx

00407131  |.  C9            leave

00407132  \.  C3            retn

可见,al的值来自于5076a0这个地址。

好,试着对该地址常量查找参考,发现如下

wps4696.tmp[11]

对这些地方全部下断。看看程序第一次写入这个地址的代码那里如何

下断后重新载入运行。

wps46B6.tmp[11]

断在这里。我们来观察一下,因为目前我们还未实现破解,所以jnz不会跳转,那么已注册版本显然是要实现跳转的。4070cb处的call显然是判断软件是否已经注册的。由于未注册不会跳转,可见,未注册时call 00406fd1返回0,。那么,答案已经很明显了,做如下修改:

wps46C7.tmp[11]

注意红色的两条指令为修改处。

当然,直接把mov     byte ptr [5076A0], al  改为mov     byte ptr [5076A0], 1逻辑上也是可以的,但是由于指令长度变长,会把下面的跳转指令覆盖掉。。所以不行。

保存一下,看看结果

wps46F7.tmp[11]

看到区别了吧,已经破解了。

这里仅仅实现破解,程序的算法就不逆向了。。(有空再说)

逆向一个非常简单的crackme(2)

再来看一个。

reverseMe

首先打开程序

wpsB4A2.tmp

提示说版本过期之类的。。

od载入

程序很短,不需要跑,直接观察就行

往下拉来到这段

wpsB4E1.tmp

可以看到,程序在初始的一些操作之后,用CreateFile的OPEN_EXISTING这种方式打开一个叫Keyfile.dat的文件,实际上就是检查这个文件是否存在

再往下

wpsB4F2.tmp

发现是读该文件的前70个字节pBytesRead这个指针指向的内存地址存放的是实际读取的字符数

下面一段是关键

004010A9   call    <jmp.&KERNEL32.ReadFile>            ; \ReadFile

004010AE   test    eax, eax

004010B0   jnz     short 004010B4                               ;ReadFile成功时返回非零值

004010B2   jmp     short 004010F7                             ;跳过去则会提示Keyfile is not valid. Sorry.”

004010B4   xor     ebx, ebx

004010B6   xor     esi, esi

004010B8   cmp     dword ptr [402173], 10                 ;key的长度必须>=10h,即16

004010BF   jl      short 004010F7

004010C1   mov     al, byte ptr [ebx+40211A]              ;循环操作读取进来的key

004010C7   cmp     al, 0                                                ;字符串以0结尾,也就是处理到结束

004010C9   je      short 004010D3

004010CB   cmp     al, 47                                              ;ascii码47h=’G’

004010CD   jnz     short 004010D0

004010CF   inc     esi                                                     ;esi是在计算’G’的出现次数

004010D0   inc     ebx

004010D1   jmp     short 004010C1

004010D3   cmp     esi, 8                                                ;’G’至少出现8次才行

004010D6   jl      short 004010F7

004010D8   jmp     00401205                                         ;调到提示成功的地方

由上面的分析可知key的内容是:(1)长度>=16    (2)’G’至少出现8次

这样就可以写出Keyfile.dat了。

wpsB512.tmp

逆向一个非常简单的crackme

 

今天看了下逆向破解的内容,发现大一时学的东西已经忘得差不多了。。本来对这个是挺感兴趣的,但是大二开始入了acm队,专心搞acm去了,所以逆向工程这一块就荒废了,因而至今在逆向破解这一块仍是什么也不懂的弱渣。正好这段时间有空,所以想重新拾起来,然后写下过程,给自己也给想学crack的初学者。

还是先从最简单的开始。

TraceMe
(注:本文写给crack初学者,写的会比较详细。。大牛请直接右上角。。)

K[T{S0{R6HKB5X3H]W%HHBT[4]

发现要输入用户名和序列号,先随意输入

4KZ6(%HY79CY36Q%PZUO5LB

错误时弹出一个messagebox,上面有字符串”序列号错误,再来一次!”

好,od载入,看下字符串参考

U~`DIDY`C6X6Q$B__CPXOKQ

好像没这个字符串。。。

然后ctrl+n看下导入表

6YE~1C{HU4_S951SW82G~2P

发现有GetDlgItemTextA,读入文本框输入不是这个就是GetWindowText,所以在这个函数上下断。

}PIJ2M3M207(AH6K32W9ZTY

重新载入,运行,输入用户名”abcde”

和密码123456.点确认。好,进程断在了刚刚下的断点处,F8单步几下回到程序领空。如下图

Z2IHI5SAX}_1VQN3C7J~IN7

好,继续F8往下

004011CA   .  8A4424 4C     mov     al, byte ptr [esp+4C];数据窗口找一下会发现esp+4c是用户名的地址
004011CE   .  84C0          test    al, al
004011D0   .  74 76         je      short 00401248
004011D2   .  83FB 05       cmp     ebx, 5
004011D5   .  7C 71         jl      short 00401248;到这里为止是判断用户名超度是否合法
004011D7   .  8D5424 4C     lea     edx, dword ptr [esp+4C]
004011DB   .  53            push    ebx;用户名长度
004011DC   .  8D8424 A00000>lea     eax, dword ptr [esp+A0];
004011E3   .  52            push    edx;用户名的内存首地址
004011E4   .  50            push    eax;输入的序列号的内存首地址
004011E5   .  E8 56010000   call    00401340 ;由上面的参数可知这个是关键call,目测是生成序列号并比较,看下下面的代码也可以推断

call    00401340,F7跟进这个call

L{HRFFGEZT0V2)5%N[%3ZKH

先来看最下面这段

00401379  |> \56            push    esi                              ; /<%ld>
0040137A  |.  68 78504000   push    00405078                         ; |Format = “%ld”
0040137F  |.  55            push    ebp                              ; |s
00401380  |.  FF15 9C404000 call    dword ptr [<&USER32.wsprintfA>]  ; \wsprintfA;将esi的内容写入到ebp指向的内容
00401386  |.  8B4424 1C     mov     eax, dword ptr [esp+1C]
0040138A  |.  83C4 0C       add     esp, 0C
0040138D  |.  55            push    ebp                              ; /String2
0040138E  |.  50            push    eax                              ; |String1;我们输入的序列号
0040138F  |.  FF15 04404000 call    dword ptr [<&KERNEL32.lstrcmpA>] ; \lstrcmpA;注意这里
00401395  |.  F7D8          neg     eax
00401397  |.  1BC0          sbb     eax, eax
00401399  |.  5F            pop     edi
0040139A  |.  5E            pop     esi
0040139B  |.  40            inc     eax
0040139C  |.  5D            pop     ebp
0040139D  \.  C3            retn

显然edi是正确的序列号,strcmpA将我们输入的序列号与正确的序列号比较。可见上面得出edi的那部分代码就是关键的生成正确序列号的部分

来看一下

00401340  /$  55            push    ebp
00401341  |.  8B6C24 0C     mov     ebp, dword ptr [esp+C];用户名首址
00401345  |.  56            push    esi
00401346  |.  57            push    edi
00401347  |.  8B7C24 18     mov     edi, dword ptr [esp+18];用户名长度
0040134B  |.  B9 03000000   mov     ecx, 3
00401350  |.  33F6          xor     esi, esi
00401352  |.  33C0          xor     eax, eax
00401354  |.  3BF9          cmp     edi, ecx;用户名长度<=3?
00401356  |.  7E 21         jle     short 00401379
00401358  |.  53            push    ebx
00401359  |>  83F8 07       /cmp     eax, 7;这里开始是关键
0040135C  |.  7E 02         |jle     short 00401360
0040135E  |.  33C0          |xor     eax, eax;eax>7时清零
00401360  |>  33D2          |xor     edx, edx
00401362  |.  33DB          |xor     ebx, ebx
00401364  |.  8A1429        |mov     dl, byte ptr [ecx+ebp];可见,每次取用户名的一个字符,而且是第3个开始
00401367  |.  8A98 30504000 |mov     bl, byte ptr [eax+405030];这里是一组常数,eax在0~7循环,所以是8个常数
0040136D  |.  0FAFD3        |imul    edx, ebx
00401370  |.  03F2          |add     esi, edx
00401372  |.  41            |inc     ecx
00401373  |.  40            |inc     eax
00401374  |.  3BCF          |cmp     ecx, edi;直到用户名的字符取完
00401376  |.^ 7C E1         \jl      short 00401359

这里单步运行一下,观察各个寄存器的值,会发现ebp指向用户名,ecx=3,所以其实是每次把用户名从第3个字符(编号从0开始)开始,每个字符和405030这个地址开始的一组常数分别相乘再相加,结果放在esi里面。

数据窗口查看405030这个地址

X`F%%}HR600UR%8]U6@YZ~3

好,这8个数找到了,接下来写出注册机,代码如下:

#include<stdio.h>
#include<string.h>
int b[]={0x0c,0x0a,0x13,0x09,0x0c,0x0b,0x0a,0x08};
int ans;
int main()
{
    int i,j;
    char s[110];
    while(~scanf("请输入用户名:%s",s))
    {
        ans=0;j=0;
        int len=strlen(s);
        if(len<=3){printf("用户名长度至少为4\n");continue;}
        for(i=3;i<=len-1;i++)
        {
            ans+=s[i]*b[j];
            j++;
            if(j==7) j=0;
        }
        printf("序列号是:%d\n",ans);

    }
    return 0;
}

这样就OK了。

git入门笔记

git add xxx.txt                           把文件修改添加到暂存区
git commit -m “版本说明”       把暂存区的所有内容提交到当前分支
git status                                      查看目前工作区状态(有无文件被修改之类)
git diff                                            查看新旧版本的修改之处
git log                                            查看历史版本记录
git reset –hard HEAD^          向前回退一个版本
git reset –hard HEAD^^       向前回退两个版本
git reset –hard HEAD~n        向前回退n个版本
git reflog                                       查看键入的历史命令

git checkout — file
当修改工作区但未add到暂存区时,取消工作区的修改(应该是用暂存区内容覆盖工作区?)
git reset HEAD file
当已经把工作区的修改add到暂存区时,这条命令可以把add到暂存区的修改回退给工作区(应该是用分支的内容覆盖暂存区?)
git remote add origin https://github.com/github用户名/仓库名.git
把“仓库名”作为远程仓库,名字是origin
git push -u origin master
把当前分支master推送到远程库origin
由于远程库是空的,我们第一次推送master分支时,加上了-u参数,Git不但会把本地的master分支内容推送到远程新的master分支,还会把本地的master分支和远程的master分支关联起来,在以后的推送或者拉取时就可以简化命令。
git push origin master 以后可以这样推送到远程库origin

要关联一个远程库,使用命令git remote add origin git@server-name/path/repo-name.git;
关联后,使用命令git push -u origin master第一次推送master分支的所有内容;
此后,每次本地提交后,只要有必要,就可以使用命令git push origin master推送最新修改;

创建与合并分支:

http://www.liaoxuefeng.com/wiki/0013739516305929606dd18361248578c67b8067c8c017b000/001375840038939c291467cc7c747b1810aab2fb8863508000

查看分支:git branch

创建分支:git branch <name>

切换分支:git checkout <name>

创建+切换分支:git checkout -b <name>

合并某分支到当前分支:git merge <name>

删除分支:git branch -d <name>

又是熬夜

今天偶然看到一本叫《Windows 内核安全与驱动开发》的书。。。。。。。的电子试读版,看的挺过瘾,熬夜看了半宿,现在又陷入什么都想学的状态了。。但是毕业设计都还没做啊。。

python小练习

接下来打算在这几个oj上用python刷刷水题,巩固一下刚学的python语法。刚开始想用zoj刷,但是zoj水题太少了,刚学python感到力不从心。。
leetcode
codeforces
leetcode165

class Solution:
    # @param version1, a string
    # @param version2, a string
    # @return an integer
    def compareVersion(self, version1, version2):
        a=version1.split(".");b=version2.split(".");
        lena=len(a);lenb=len(b);
        for i in range(lena):a[i]=int(a[i]);
        for i in range(lenb):b[i]=int(b[i]);
        if(lena<lenb):
            for i in range(lenb-lena):a+=[0];
        elif(lena>lenb):
            for i in range(lena-lenb):b+=[0];
        if(a>b):return 1;
        elif(a<b):return -1;
        else:return 0;
        

cf#1a

str=raw_input();l=str.split(" ");
n=int(l[0]);m=int(l[1]);a=int(l[2]);
if(n%a==0): n/=a;
else:n=n/a+1;
if(m%a==0): m/=a;
else:m=m/a+1;
print(n*m);

cf#1b
这题在整形的列值转化为字母表示的列序号时不知道怎么办了。。于是看了下题解。’A'~’Z'要映射为1~26,当余数为0时,特殊处理,0代表’Z',而且商要减一。。目前还不太明白为什么这么做就对。。。弱爆~~

def judge(a):
    flag1=0;flag2=0;flag3=0;
    for i in a:
        if(i=='R'):flag1=1;
        if(i=='C'):flag2=1;
        if('0'<=i<='9' and flag1==1 and flag2==0): flag3=1;
    if(flag1==1 and flag2==1 and flag3==1):return 0;
    else:return 1;
n=int(input());
for i in range(n):
    s=input();
    ret=judge(s);
    if(ret==0):
        s=s.split("R");
        s=s[1].split("C");
        r=int(s[0]);c=int(s[1]);
        tmp=[];
        while(c!=0):
            cc=c%26;
            if(cc!=0):
                tmp+=[cc];c//=26;
            else:
                tmp+=[26];c=c//26-1;
        tmp.reverse();
        for i in tmp:
            print(chr(i+ord("A")-1),end="");
        print(r);
    else:
        r=c=0;
        for i in s:
            if('A'<=i<='Z'):c=c*26+ord(i)-ord("A")+1;
            else:r=r*10+ord(i)-ord("0");
        print("R%dC%d" % (r,c));

cf#2a

n=int(input());
name=[];rou=[];score=[];win=[];
for i in range(n):
    tmp=(input()).split(" ");
    tmp[1]=int(tmp[1]);
    rou.append(tmp);
    if(tmp[0] not in name):
        name.append(tmp[0]);
        score.append(tmp[1]);
        win.append(0);
    else:
        index=name.index(tmp[0]);
        score[index]+=tmp[1];
ans=max(score);
for i in range(len(score)):
    if(score[i]==ans):
        win[i]=1;
        score[i]=0;
for a in rou:
    index=name.index(a[0]);
    score[index]+=a[1];
    if(score[index]>=ans and win[index]==1):
        print(a[0]);
        break;

cf#3a

def judge(s,t):
    sx=s[0];sy=s[1];
    tx=t[0];ty=t[1];
    if(sx==tx and sy==ty):return "end";
    if(tx>sx and ty>sy):
        s[0]+=1;s[1]+=1;
        return "RU";
    if(tx>sx and ty<sy):
        s[0]+=1;s[1]-=1;
        return "RD";
    if(tx<sx and ty>sy):
        s[0]-=1;s[1]+=1;
        return "LU";
    if(tx<sx and ty<sy):
        s[0]-=1;s[1]-=1;
        return "LD";
    if(tx==sx and ty<sy):
        s[1]-=1;
        return "D";
    if(tx==sx and ty>sy):
        s[1]+=1;
        
        return "U";
    if(tx<sx and ty==sy):
        s[0]-=1;
        return "L";
    if(tx>sx and ty==sy):
        s[0]+=1;
        return "R";
s=input();t=input();
s=[s[0],s[1]];t=[t[0],t[1]];
s[0]=ord(s[0])-ord('a')+1;s[1]=int(s[1]);
t[0]=ord(t[0])-ord('a')+1;t[1]=int(t[1]);
cnt=0;ans=[];
move=judge(s,t);
while(move!="end"):
    ans.append(move);
    cnt+=1;
    move=judge(s,t);
print(cnt);
for i in ans:print(i);

cf#4a

w=int(input());
if(w%2==0 and w>2):print("YES");
else:print("NO");

cf#5a
现在一般能一次性编译通过了,开始对用python写代码有点感觉啦。

name=[];ans=0;
while(1):
    try:
        s=input();
        if(s[0]=='+'):name.append(s[1:]);
        elif(s[0]=='-'):name.remove(s[1:]);
        else:
            tmp=s.split(":");
            ans+=(len(tmp[1])*len(name));
    except:
        break;
print(ans);

cf#5b
要求将给定的文本居中显示,做这道题使我发现python这种脚本处理文本非常方便。

def change(i):
    global a;global flag;
    l=len(a[i]);
    tmp="";
    space=maxlen-l;
    for j in range(space//2):tmp+=' ';
    if(space%2==0):
        a[i]='*'+tmp+a[i]+tmp+'*';
    else:
        if(flag==0):a[i]='*'+tmp+a[i]+tmp+' *';
        else:       a[i]='*'+tmp+' '+a[i]+tmp+'*';
        flag^=1;
a=[];
maxlen=0;
while(1):
    try:
        tmp=input();
        le=len(tmp);
        if(le>maxlen):maxlen=le;
        a.append(tmp);
    except:
        break;
cnt=len(a);
flag=0;
for i in range(cnt):
    change(i);
tmp="";
for i in range(maxlen+2):tmp+='*';
a.insert(0,tmp);a.append(tmp);
for i in a:print(i);

cf#6a

def judge(li):
    li.sort();
    if(li[0]+li[1]>li[2]):return 1;
    elif(li[0]+li[1]==li[2]):return 0;
    else:return -1;
a=input().split(" ");
for i in range(4):
    a[i]=int(a[i]);
flag1=flag2=0;
for i in range(4):
    for j in range(i+1,4):
        for k in range(j+1,4):
            ret=judge([a[i],a[j],a[k]]);
            if(ret==1):flag1=1;break;
            elif(ret==0):flag2=1;
if(flag1==1):print("TRIANGLE");
elif(flag2==1):print("SEGMENT");
else:print("IMPOSSIBLE");

cf#6b

def judge(x,y):
    if(0<=x<=n-1 and 0<=y<=m-1):return 1;
    else:return 0;

def cal(x,y):
    global room;global color;
    if(judge(x+1,y)):
        if('A'<=room[x+1][y]<='Z' and room[x+1][y]!=c):
            color.add(room[x+1][y]);
    if(judge(x-1,y)):
        if('A'<=room[x-1][y]<='Z' and room[x-1][y]!=c):
            color.add(room[x-1][y]);
    if(judge(x,y+1)):
        if('A'<=room[x][y+1]<='Z' and room[x][y+1]!=c):
            color.add(room[x][y+1]);
    if(judge(x,y-1)):
        if('A'<=room[x][y-1]<='Z' and room[x][y-1]!=c):
            color.add(room[x][y-1]);

        
a=input().split(" ");
n=int(a[0]);m=int(a[1]);c=a[2];
color=set();
room=[];
for i in range(n):
    room.append(list(input()));
for i in range(n):
    for j in range(m):
        if(room[i][j]==c):
            cal(i,j);
print(len(color));

cf#7a

def judge(i,flag):
    global a;
    paint=1;
    if(flag==0):
        for j in range(8):
            if(a[i][j]=='W'):
                paint=0;
                break;
    else:
        for j in range(8):
            if(a[j][i]=='W'):
                paint=0;
                break;
    return paint;
a=[];
ans=0;
for i in range(8):
    r=list(input());
    a.append(r);
for i in range(8):ans+=judge(i,0);
for i in range(8):ans+=judge(i,1);
if(ans==16):print(8);
else:       print(ans);

cf#7b

def alloc(s):
    global m;global size;
    cnt=0;
    for i in range(1,size+2):
        if(m[i]==0):
            cnt+=1;
            if(cnt==s):
                for j in range(i-cnt+1,i+1):m[j]=1;
                return [i-cnt+1,i];
        else:cnt=0;
    return [-1];

def erase(begin,end):
    global m;
    for i in range(begin,end+1):m[i]=0;
    return;

a=input().split(" ");
t=int(a[0]);size=int(a[1]);
m=[0];
b=0;
block=[0];
for i in range(1,size+1):m.append(0);
m.append(1);
while(t!=0):
    com=input().split(" ");
    if(com[0]=="alloc"):
        ret=alloc(int(com[1]));
        if(ret[0]!=-1):
            b+=1;
            ret.append(1);
            block.append(ret);
            print(b);
        else:print("NULL");
    elif(com[0]=="erase"):
        x=int(com[1]);
        if(x<=0 or x>b or block[x][2]==0):print("ILLEGAL_ERASE_ARGUMENT");
        else:
            block[x][2]=0;
            erase(block[x][0],block[x][1]);
    else:
        if(len(block)==0):continue;
        use=0;
        for i in range(1,len(block)):
            if(block[i][2]==0):continue;
            use+=block[i][1]-block[i][0]+1;
            blank=0;
            for j in range(1,block[i][0]):
                if(m[j]==0): blank+=1;
            block[i][0]-=blank;block[i][1]-=blank;
        for i in range(1,use+1):m[i]=1;
        for i in range(use+1,size+1):m[i]=0;
    t-=1;

cf#8a
python处理字符串真的很方便,做这题的时候开始用s.reverse(),结果发现字符串对象没有这个方法。。然后get了一个新技能。
也就是字符串的反向切片:s[begin:end:-step](begin>end)
begin大于end表示此时想反向切片,此时步进要设为负值。
正向切片时不用显式的写出步进字段。
反向切片时则一定写写出步进字段,特别的,如果是对整个字符串进行切片,则begin和end都可以省略。
注意一点:end是不包括在切片内的,即半开半闭区间[begin,end)

s=input();
s1=input();
s2=input();
flag1=flag2=0;
pos1=s.find(s1);
if(pos1>=0):
    pos2=s[pos1+len(s1):].find(s2);
    if(pos2>=0):flag1=1;
s=s[::-1];
pos1=s.find(s1);
if(pos1>=0):
    pos2=s[pos1+len(s1):].find(s2);
    if(pos2>=0):flag2=1;
if(flag1==1 and flag2==1):print("both");
elif(flag1==1):print("forward");
elif(flag2==1):print("backward");
else:print("fantasy");

cf#8b
这道水题让我收获挺多。
首先是让我知道了python中dict的关键字和set的元素不能是list但可以是tuple。
其次,由于python的for语句的特性(貌似上界无法动态改变),所以只好用while或者递归来实现bfs(当然也可以直接用collections里面的deque,但是效率不知怎么样,所以还是用数list模拟)
再者,这道题开始考虑欠佳,以为排除几种特殊情况即可,实际上“特殊情况”很多。。所以把给出路径上的方格设为empty,其余设为obstruct,这样就形成了“最好情况”,然后bfs算最短路径,如果这种情况下都不是最短路径,就一定不存在一种情况它是最短路径

def judge(x,y):
    global m;
    if(m[x][y]==0):return 1;
    return 0;

def bfs():
    global dest;
    q=[];
    q.append([100,100,0]);
    iq=1;
    i=0;
    vis=set();vis.add((100,100));
    while(i<=iq-1):
        x=q[i][0];y=q[i][1];dep=q[i][2];
        if(x==dest[0] and y==dest[1]):return dep;
        else:
            if(judge(x+1,y)==1 and ((x+1,y) not in vis)):
                q.append([x+1,y,dep+1]);iq+=1;vis.add((x+1,y));
            if(judge(x-1,y)==1 and ((x-1,y) not in vis)):
                q.append([x-1,y,dep+1]);iq+=1;vis.add((x-1,y));
            if(judge(x,y+1)==1 and ((x,y+1) not in vis)):
                q.append([x,y+1,dep+1]);iq+=1;vis.add((x,y+1));
            if(judge(x,y-1)==1 and ((x,y-1) not in vis)):
                q.append([x,y-1,dep+1]);iq+=1;vis.add((x,y-1));
        i+=1;

move=input();
m=[];
dest=[100,100];
for i in range(210):
    m.append([]);
    for j in range(210):m[i].append(1);
m[100][100]=0;
for i in move:
    if(i=="U"):dest[1]+=1;
    if(i=="D"):dest[1]-=1;
    if(i=="L"):dest[0]-=1;
    if(i=="R"):dest[0]+=1;
    m[dest[0]][dest[1]]=0;
if(bfs()==len(move)):print("OK");
else:print("BUG");

cf#9a

def gcd(a,b):
    if(a<b):a^=b;b^=a;a^=b;
    if(b==0):return a;
    return  gcd(b,a%b);
a=input().split(" ");
x=int(a[0]);y=int(a[1]);
tmp=max(x,y);
if(tmp==1):print("1/1");
else:
    zi=6-tmp+1;
    g=gcd(zi,6);
    print("%d/%d" % (zi//g,6//g));

cf#9b
这道题不错,学到了python的数学运算,特别是开方,原先不知道怎么开方,查了下可以用math.sqrt(),但是直接**0.5更方便。
第二个是list的sort方法,可以通过参数key实现多关键字排序,非常方便。

inp=input().split();
n=int(inp[0]);vb=int(inp[1]);vs=int(inp[2]);
x=input().split();
for i in range(n):x[i]=int(x[i]);
dest=input().split();
dest[0]=int(dest[0]);dest[1]=int(dest[1]);
ans=[];
for i in range(1,n):
    tmp=(((dest[0]-x[i])**2)+(dest[1]**2))**0.5;
    ans.append((x[i]/vb+tmp/vs,tmp,i+1));
ans.sort(key=lambda x:(x[0],x[1]));
print(ans[0][2]);

容斥专题

容斥专题:容斥专题题集
复习了一下容斥,发现原来容斥可以用位运算写,以前一直使用dfs写的。。弱爆了。。
这两种做法各有适用的场合。
重新做了一下zoj3687
dfs版的容斥
题意:n天n个章节,给你m个约束条件,一个约束条件d,c表示第d天不能复习第c章节。问总共有多少种复习的方式(答案mod 55566677)。
思路:典型的容斥题目。算出满足所有约束的方案数,最后n!减一下即可。以前做的时候忘了约束会有重复,这次做又忘了。。真是渣渣。首先完全相同的约束只保留一个,否则会多算。然后,如果d或c有重复,则说明这两个约束条件同时满足的方案数为0,不能递归下去了。

#include<stdio.h>
#include<string.h>
typedef long long ll;
const ll mod=55566677LL;
typedef struct Node{
    int d,c;
}Node;
Node node[30];
ll fact[55];
int n,m;
ll ans;
bool day[55],chap[55];
void init()
{
    memset(day,0,sizeof(day));
    memset(chap,0,sizeof(chap));
}
void dfs(int flag,int x)
{
    day[node[x].d]=1;chap[node[x].c]=1;
    if(flag&1) ans=(ans+fact[n-flag])%mod;
    else ans=(ans-fact[n-flag])%mod;
    for(int i=x+1;i<=m;i++)
    {
        if(day[node[i].d] || chap[node[i].c]) continue;
        dfs(flag+1,i);
    }
    day[node[x].d]=0;chap[node[x].c]=0;
}
int main()
{
    int i,j;
    fact[0]=1;
    for(i=1;i<=50;i++)
        fact[i]=(fact[i-1]*i)%mod;
    while(~scanf("%d%d",&n,&m))
    {
        ans=0;init();
        int a,b,cnt=0;
        int map[55][55];
        memset(map,0,sizeof(map));
        for(i=1;i<=m;i++) {scanf("%d%d",&a,&b);map[a][b]=1;}
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(map[i][j])
                {
                    node[++cnt].d=i;node[cnt].c=j;
                }
        m=cnt;
        for(i=1;i<=m;i++) dfs(1,i);
        printf("%lld\n",((fact[n]-ans)%mod+mod)%mod);
    }
    return 0;
}

用位运算写的容斥
(待补充)

主席树

今天看了下主席树,感觉好神奇,代码精简而且实用,例如静态区间第k大之类的题,用主席树直接秒杀线段树套平衡树之类的写法。就是空间有点大。。
具体请参考:
1.clj的论文
2.博文一篇,代码写的很精炼:http://im.librazy.org/article/837/note-chairtree-via-functional-segtree/
其实很好理解的。
入门题:
hdu2665
静态区间第k小,注意题目描述可能不恰当。。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define w(i) T[(i)].w
#define lson(i) T[(i)].l
#define rson(i) T[(i)].r
using namespace std;
const int maxn=1e5+10;
int n,m;
int a[maxn],p[maxn],b[maxn];
bool cmp(int i,int j)
{
    return a[i]<a[j];
}
typedef struct Node{
    int l,r,w;
    Node(){l=r=w=0;}
}Node;
Node T[maxn*20];
int root[maxn],sz;
void ins(int &i,int l,int r,int x)
{
    T[++sz]=T[i];i=sz;
    w(i)++;
    if(l==r) return;
    int m=(l+r)>>1;
    if(x<=m) ins(lson(i),l,m,x);
    else ins(rson(i),m+1,r,x);
}
int query(int i,int j,int l,int r,int k)
{
    if(l==r) return l;
    int t=w(lson(j))-w(lson(i));
    int m=(l+r)>>1;
    if(t>=k) return query(lson(i),lson(j),l,m,k);
    else return query(rson(i),rson(j),m+1,r,k-t);
}
int main()
{
    int i,j,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++) {scanf("%d",&a[i]);p[i]=i;}
        sort(p+1,p+1+n,cmp);
        for(i=1;i<=n;i++) b[p[i]]=i;
        root[0]=0;sz=0;
        for(i=1;i<=n;i++)
        {
            root[i]=root[i-1];
            ins(root[i],1,n,b[i]);
        }
        int l,r,k;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&l,&r,&k);
            int tmp=query(root[l-1],root[r],1,n,k);
            printf("%d\n",a[p[tmp]]);
        }
    }
    return 0;
}

类似积分

题目:给你三种图形,圆心在x轴上的圆,中心在x轴上且边与x轴平行的正方形,中心在x轴上且边与x轴成45度的正方形。三种图形的边长、半径都是<=10的非负数。且中心坐标是绝对值<=10的整数。给你n个图形(n<=10),问你共覆盖了多少面积,精确到整数位
思路:这题比赛时没多想,其实抓住答案的精度非常粗略且图形很少,范围很小就比较好做了。用积分的思想,x从-20递增到20,每次增长0.001,对于特定的x,枚举所有图形,找到最大的y,y*0.001就是这个小矩形区域的面积,累加*2即可。

#include<stdio.h>
#include<string.h>
#include<math.h>
inline double max(double a,double b){return a>b?a:b;}
int n;
typedef struct Node{
    int type;
    double x,d;
}Node;
Node node[12];
double cal(double x)
{
    int i;
    double y=0;
    for(i=1;i<=n;i++)
    {
        int type=node[i].type;
        double c=node[i].x,d=node[i].d;
        if(type==1)
        {
            if(c-d/2<=x && x<=c+d/2) y=max(y,d/2);
        }
        if(type==2)
        {
            double x1=c-d/sqrt(2.0),x2=c+d/sqrt(2.0);
            if(x1<x && x<=c) y=max(y,x-x1);
            if(c<x && x<=x2) y=max(y,x2-x);
        }
        if(type==3)
        {
            if(c-d<=x && x<=c+d) y=max(y,sqrt(d*d-(x-c)*(x-c)));
        }
    }
    return y;

}
int main()
{
    int i,j;
    int t;
    scanf("%d",&t);
    while(t–)
    {
        scanf("%d",&n);
        char com[5];
        for(i=1;i<=n;i++)
        {
            scanf("%s%lf%lf",com,&node[i].x,&node[i].d);
            node[i].type=com[0]-’A'+1;
        }
        double ans=0;
        for(double x=-20;x<20;x+=0.001) ans+=0.001*cal(x);
        printf("%.0f\n",ans*2);


    }
    return 0;
}

cf375D Tree and Queries

昨天学了莫队算法,发现真的是很神奇,特别是简化版的,按sqrt(n)分块的算法,非常好写。这道题是佳神推荐的,发现确实很好,写下题解,大牛请直接关闭本页。。
题意:题目的意思是给你一棵树,每个节点都有一个正整数值。然后给你m个询问,每次询问你一棵子树中出现次数至少为kj次的数有多少个。题目中所有数都是<=10^5
思路:这题其实是前面写的树那题和分块那题的结合。首先dfs这棵树,得到dfs序。
于是问题转化为:给出一个长为n的序列,m个询问,每次询问[l,r]上有多少个数出现次数至少为qi次
这个问题可以这样:用一个数组cn[i],表示数i出现的次数。再用一个树状数组cc[],其中第i个元素表示出现次数为i次的数有几个。然后就是前面所讲的分块算法了,这在《莫队算法相关》这篇文章里讲过了。每次单步转移(也就是类似[l,r]->[l,r+1]的转移),需要更新cn[],时间是O(1),更新cc[],时间O(lgn).求解时计算getsum(n)-getsum(qi-1),时间为O(lgn).这样复杂度是O((n^1.5)lgn),n=1e5.算了一下大概在5*10^8左右。开始用线段树出现次数为x的数的个数,结果TLE,改成树状数组就过了,不过应该是数据不卡O((n^1.5)lgn)的原因,因为正解貌似是O(n^1.5)的。。待进一步思考
ps:del和insert的时候,少写了if,导致有时候一个数删去之后出现了0次,这时候对出现0次的数的个数+1,结果就出错了。。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define lson id<<1
#define rson id<<1|1
using namespace std;
const int maxn=1e5+5;
typedef struct Edge{
    int to,next;
}Edge;
Edge edge[maxn*2];
int head[maxn],cnt;
bool visit[maxn];
int n,m,num;
int c[maxn],d[maxn];
void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].to=u;edge[cnt].next=head[v];
    head[v]=cnt++;
    return;
}
typedef struct Node{
    int begin,end;
}Node;
Node node[maxn];
void dfs(int cur)
{
    visit[cur]=1;
    node[cur].begin=(++num);
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(visit[v]) continue;
        dfs(v);

    }
    node[cur].end=num;
    return;
}
typedef struct Q{
    int l,r,id,count,g;
}Q;
Q q[maxn];
int cn[maxn],ans[maxn];
bool cmp(Q a,Q b)
{
    if(a.g==b.g) return a.r<b.r;
    return a.g<b.g;
}
/**
int sum[maxn<<2];
void pushup(int id)
{
    sum[id]=sum[lson]+sum[rson];
}
void update(int id,int l,int r,int pos,int v)
{
    if(l==r)
    {
        sum[id]+=v;
        return;
    }
    int m=(l+r)/2;
    if(pos<=m) update(lson,l,m,pos,v);
    else update(rson,m+1,r,pos,v);
    pushup(id);
}
int query(int id,int l,int r,int L,int R)
{
    if(L<=l && r<=R) return sum[id];
    int m=(l+r)/2;
    int ret=0;
    if(L<=m) ret+=query(lson,l,m,L,R);
    if(R>m) ret+=query(rson,m+1,r,L,R);
    return ret;
}
**/
//树状数组部分
int cc[maxn];
int lowbit(int x)
{
	return x & -x;
}
void add2(int id,int x)
{
	for(int i=id;i<=n;i+=lowbit(i))
		cc[i]+=x;
	return;
}
int getsum(int x)
{
	int sum=0;
	for(int i=x;i>=1;i-=lowbit(i))
		sum+=cc[i];
	return sum;
}
//区间询问转移
void del(int x)
{
    if(cn[d[x]]) {add2(cn[d[x]],-1);cn[d[x]]--;}

    if(cn[d[x]]) add2(cn[d[x]],1);
}
void insert(int x)
{
    if(cn[d[x]]) add2(cn[d[x]],-1);
    cn[d[x]]++;
    if(cn[d[x]]) add2(cn[d[x]],1);
}

void scan(int &num)    //对G++使用
{
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in<'0') && in!='-') ;
    if(in=='-')
    {
        neg=true;
        while((in=getchar()) >'9' || in<'0');
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg)
        num=0-num;
}
int main()
{
    int i,j;
    int a,b;
    while(~scanf("%d%d",&n,&m))
    {
        num=cnt=0;
        memset(head,-1,sizeof(head));
        memset(visit,0,sizeof(visit));
        memset(cn,0,sizeof(cn));
        //memset(sum,0,sizeof(sum));
        memset(cc,0,sizeof(cc));
        for(i=1;i<=n;i++) scan(c[i]);
        for(i=1;i<=n-1;i++) {scan(a);scan(b);add(a,b);}
        dfs(1);
        for(i=1;i<=n;i++) d[node[i].begin]=c[i];
        int x,y;
        int len=(int)sqrt(n*1.0);
        for(i=1;i<=m;i++)
        {
            scan(x);scan(y);
            q[i].l=node[x].begin;
            q[i].r=node[x].end;
            q[i].id=i;
            q[i].count=y;
            q[i].g=q[i].l/len+1;
        }
        sort(q+1,q+1+m,cmp);
        int curl=0,curr=0;
        for(i=1;i<=m;i++)
        {
            int l=q[i].l,r=q[i].r;
            while(curr<r)
            {
                curr++;
                insert(curr);
            }
            while(curr>r)
            {
                del(curr);
                curr--;
            }
            while(curl<l)
            {
                if(curl) del(curl);
                curl++;
            }
            while(curl>l)
            {
                curl--;
                insert(curl);
            }
            if(q[i].count>n) ans[q[i].id]=0;
            else ans[q[i].id]=getsum(n)-getsum(q[i].count-1);
        }
        for(i=1;i<=m;i++) printf("%d\n",ans[i]);
    }
    return 0;
}
/*
10 1
82 48 59 48 32 83 34 46 47 79
2 1
3 1
4 3
5 4
6 1
7 2
8 3
9 2
10 2
4 1
*/