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<stdio.h>
#include<string.h>
#include<windows.h>
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<=sec_num;i++)
	{
		sec_begin=sec_head[i].VirtualAddress;sec_end=sec_head[i].VirtualAddress+sec_head[i].Misc.VirtualSize;
		if(rva<sec_begin || rva>sec_end) continue;
		return sec_head[i].PointerToRawData+rva-sec_head[i].VirtualAddress;
	}
	return 0;
}
void read_error(int ret)
{
	if(!ret) 
	{
		printf("read error\n");
		CloseHandle(hfile);
		exit(1);
		return;
	}
	return;
}
void read_sechead()
{
	int i,j;
	for(i=1;i<=sec_num;i++)
	{
		SetFilePointer(hfile,dos_and_nt+(i-1)*sizeof(IMAGE_SECTION_HEADER),0,FILE_BEGIN);
		int ret=ReadFile(hfile,&sec_head[i],sizeof(sec_head[i]),&readsize,0);
		read_error(ret);
	}
	return;
}
bool judge(IMAGE_IMPORT_DESCRIPTOR _import)//判断IMAGE_IMPORT_DESCRIPTOR是否读取完毕
{
	if(_import.OriginalFirstThunk==0 && _import.FirstThunk==0 && _import.ForwarderChain==0 && _import.Name==0 && _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,&import[dll_num],sizeof(IMAGE_IMPORT_DESCRIPTOR),&readsize,0);
		read_error(ret);
		if(!judge(import[dll_num])) {dll_num-=1;break;}
	}
	return;
}
void print_exp_and_imp()
{
	printf("type		rva			size\n");
	printf("导出表		%x			%x\n",pdata_dir[0].VirtualAddress,pdata_dir[0].Size);
	printf("导入表		%x			%x\n",pdata_dir[1].VirtualAddress,pdata_dir[1].Size);
	return;
}
void print_sec_info()
{
	int i;
	printf("the information of section:\n");
	printf("%10s%8s%15s%6s%14s%18s\n","name","rva","VirtualSize","raw","SizeOfRawData","Characteristics");
	for(i=1;i<=sec_num;i++)
	{
		printf("%10s%10x%10x%10x%10x%18x\n",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,&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,&thunk,sizeof(thunk),&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,&readsize,0);
		read_error(ret);
		printf("%s\n",s);
	}
	printf("\n");
	return;
}
void print_import()
{
	int i,j;
	char dll_name[30];
	printf("以下是导入表函数信息:\n");
	for(i=1;i<=dll_num;i++)
	{
		get_dllname(i,dll_name);
		printf("%s\n",dll_name);
		print_dllfunc(i);
	}
	return;
}
int main()
{
	int i,j;
	char filename[1010];
	printf("请输入PE文件的绝对路径:");
	while(~scanf("%s",filename))
	{
		hfile=CreateFile(filename,GENERIC_READ,FILE_SHARE_READ,0,OPEN_EXISTING,FILE_ATTRIBUTE_NORMAL,0);
		if(hfile==INVALID_HANDLE_VALUE)
		{
			printf("file_open_error\n");
			return 0;
		}

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

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

		print_exp_and_imp();
		
		sec_num=pfile_head->NumberOfSections;
		ophead_size=pfile_head->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("请输入PE文件的绝对路径:");
	}
	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
*/

莫队算法相关

分块?

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 17   Accepted Submission(s) : 6

Font: Times New Roman | Verdana | Georgia

Font Size:

Problem Description

  给定n个数,记为ai(1<=i <= n),求区间内某两个数和为给定的sum的对数。

Input

  第一行输入整数T,表示共有T组.
  接下来共T组,首先输入n,sum分别表示共n个数以及给定的和,再下一行依次输入n个数ai,然后输入一个q,表示共有q个询问,接下来q行每行输入l,r,表示要求的是区间[l,r].

范围:
T<=20
n <= 20000,sum <= 20000
1 <= ai < sum
q <= 20000,1<= l < r <= n

Output

  输出q行,回答每个询问的值.

Sample Input

1
4 4
1 2 2 3
3
1 2
2 3
1 4

Sample Output

0
1
2

Source

test

关于莫队算法,个人觉得这篇讲的比较通俗易懂,关于复杂度上界O(n^1.5)也证明的比较详细。。(大致上来说就是按左边界分块且每块内按右边界排列之后,将每次r的转移最坏O(n),变成一个块内的询问转移完毕最坏O(n),l的转移总复杂度可以类似分析)
真正的莫队算法是要求最小曼哈顿生成树的,但是其实有一种简洁的分块方法,具体见上面链接中的文章
其实突然发现自己以前是碰到过这种分块题目的,在一片论文中讲了一种支持修改的动态rmq算法,就是分块的,每次询问时sqrt(n),自己还写了模板,坑爹啊,全忘光了。。
这里还是简述下怎么分块:将长度为n的数列划分成每段长为sqrt(n)的一些段,这样可以保证复杂度上界是O(n^1.5)(当然前提是单步转移是O(1),如果是lgn,那么总复杂度是O((n^1.5)*lgn))。证明见上面说的文章,里面讲的很清楚。
这道题的话,数的范围在20000以内,所以可以用一个数组cnt[i],表示数i出现了几次。这样从(l,r)转移到(l,r+1)是O(1)的。像这种单步转移能做到O(1)或者O(lgn)的,都可以用莫队算法来搞。然后先O(n)算出第一个询问的答案,之后转移到第二个询问的时候,要注意如果是较少一个数,也就是差不多(l,r)->(l+1,r)这种转移类型,那么如果data[l]等于sum-data[l]时注意特判,因为这时候减少的对数不是cnt[sum-data[l]],而是cnt[sum-data[l]]-1。(试想,现在有3个2,sum为4,那么有3对数它们的和为4,然后减少一个2,显然减少了2对,而不是3对)

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
typedef struct Query{
    int l,r,g,num,ans;
}Q;
Q q[20010];
int n,sum,data[20010],m;
bool cmp(Q a,Q b)
{
    if(a.g==b.g) return a.r<b.r;
    return a.g<b.g;
}
bool cmp2(Q a,Q b)
{
    return a.num<b.num;
}
int cnt[20010];
void cal(Q &a,Q &b)
{
    int i,tmp=a.ans;
    int l1=a.l,r1=a.r,l2=b.l,r2=b.r;
    if(r1<=l2 || r2<=l1)
    {
        for(i=l1;i<=r1;i++) (data[i]*2==sum?tmp-=(cnt[sum-data[i]]-1):tmp-=cnt[sum-data[i]]),cnt[data[i]]--;
        for(i=l2;i<=r2;i++) tmp+=cnt[sum-data[i]],cnt[data[i]]++;
    }
    else if(l1<=l2 && l2<=r1 && r1<=r2)
    {
        for(i=l1;i<=l2-1;i++) (data[i]*2==sum?tmp-=(cnt[sum-data[i]]-1):tmp-=cnt[sum-data[i]]),cnt[data[i]]--;
        for(i=r1+1;i<=r2;i++) tmp+=cnt[sum-data[i]],cnt[data[i]]++;
    }
    else if(l2<=l1 && l1<=r2 && r2<=r1)
    {
        for(i=l2;i<=l1-1;i++) tmp+=cnt[sum-data[i]],cnt[data[i]]++;
        for(i=r2+1;i<=r1;i++) (data[i]*2==sum?tmp-=(cnt[sum-data[i]]-1):tmp-=cnt[sum-data[i]]),cnt[data[i]]--;
    }
    else if(l1<=l2 && r2<=r1)
    {
        for(i=l1;i<=l2-1;i++) (data[i]*2==sum?tmp-=(cnt[sum-data[i]]-1):tmp-=cnt[sum-data[i]]),cnt[data[i]]--;
        for(i=r2+1;i<=r1;i++) (data[i]*2==sum?tmp-=(cnt[sum-data[i]]-1):tmp-=cnt[sum-data[i]]),cnt[data[i]]--;
    }
    else
    {
        for(i=l2;i<=l1-1;i++) tmp+=cnt[sum-data[i]],cnt[data[i]]++;
        for(i=r1+1;i<=r2;i++) tmp+=cnt[sum-data[i]],cnt[data[i]]++;
    }
    b.ans=tmp;
}
int main()
{
    int i,j;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&sum);
        memset(cnt,0,sizeof(cnt));
        int len=(int)sqrt(n*1.0);
        //int cnt=(len*len==n?len:len+1);
        for(i=1;i<=n;i++) scanf("%d",&data[i]);
        scanf("%d",&m);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&q[i].l,&q[i].r);
            q[i].g=q[i].l/len+1;
            q[i].num=i;q[i].ans=0;
        }
        sort(q+1,q+1+m,cmp);
        for(i=q[1].l;i<=q[1].r;i++) q[1].ans+=cnt[sum-data[i]],cnt[data[i]]++;
        for(i=2;i<=m;i++) cal(q[i-1],q[i]);
        sort(q+1,q+1+m,cmp2);
        for(i=1;i<=m;i++) printf("%d\n",q[i].ans);



    }
    return 0;
}

其他题目:
bzoj2038
poj3241
WC 2013 糖果公园
UVALive 3662 Another Minimum Spanning Tree
hdu5213

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=29469