逆向一个非常简单的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>

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

Time Limit : 4000/2000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 15   Accepted Submission(s) : 2

Font: Times New Roman | Verdana | Georgia

Font Size:

Problem Description

  给你一棵N个节点的树,其中1为根节点,每个节点有权值。一开始所有节点的权值均为0。现在我们要进行M次操作。
  一共有以下两种操作:
  1)1 u d 节点1到节点u的最短路径上的所有的节点(包括1,u)的权值增加d(1<=d<=300)
  2)2 u 查询节点u的权值

Input

  多组测试数据
  每组测试数据第一行有两个数N,M (1<=N,M<=60000)
  接下来N-1行 每行有两个数u,v (1<=u,v<=N且u!=v)表示节点u和节点v之间有一条边
  接下来M行,即M次操作,含义见题目描述

Output

  对于每个操作2,请输出u的权值

Sample Input

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

Sample Output

3
3
0

Source

test

昨天校赛,这题没想到思路,想到就很简单了。。这题很有意思
思路:如果给某个点加上一个值,从这个点到根的结点都要加上这个值,这样暴力肯定不行。以前做过把树求出dfs序,转化成线段树的题,但是那是对某棵子树的结点都加上一个值,那么这题如果dfs序的话,每次操作要加的那些结点在线段树中时不连续的,怎么解决呢
其实可以这样做,每次操作只修改该点的值,最后求点u的值,只要对以u为根的子树对应的区间求和就行了。。。
当然也可以用树状数组,我比较习惯线段树,虽然慢一些。。

#include<stdio.h>
#include<string.h>
#define lson id<<1
#define rson id<<1|1
const int maxn=6e4+5;
typedef struct Edge{
    int to,next;
}Edge;
typedef struct Node{
    int begin,end;
}Node;
Edge edge[2*maxn];
Node node[maxn];
int head[maxn],cnt;

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;
}
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++;
}
int n,m,num;
bool visit[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;
}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        int u,v;
        cnt=0;num=0;
        memset(head,-1,sizeof(head));
        memset(visit,0,sizeof(visit));
        memset(sum,0,sizeof(sum));
        for(i=1;i<=n-1;i++)
        {
            scanf("%d%d",&u,&v);
            add(u,v);
        }
        dfs(1);
        int c,x,d;
        for(i=1;i<=m;i++)
        {
            scanf("%d",&c);
            if(c==1)
            {
                scanf("%d%d",&x,&d);
                update(1,1,n,node[x].begin,d);
            }
            if(c==2)
            {
                scanf("%d",&x);
                printf("%d\n",query(1,1,n,node[x].begin,node[x].end));
            }
        }

    }



    return 0;
}

zoj3765 Lights 平衡树

好吧,不得不承认,经过一个寒假的颓废啥都忘了。。
一道裸的splay,但是比赛的时候我一直觉得用splay维护gcd会不会出错。。。。因为我居然觉得旋转过程中gcd无法正确维护。。。。
思路:splay节点信息
on:节点是否是开灯状态
val0:该节点关灯时的值,如果该节点灯开着,那么val0=0,不影响结果。
val1:该节点开灯时的值,如果该节点灯关着,那么val1=0,不影响结果。
gcd0:以该节点为根的子树中所有状态为关的灯的gcd
gcd1:以该节点为根的子树中所有状态为开的灯的gcd
num[0]:以该节点为根的子树有多少个状态为关的灯
num[1]:以该节点为根的子树有多少个状态为开的灯
看来这个月要好好复习了。。。。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 500000+100
#define inf 0x3f3f3f3f
inline int max(int a,int b){return a>b?a:b;}
int gcd(int a,int b)
{
    if(a<b) {int t=a;a=b;b=t;}
    return (b==0?a:gcd(b,a%b));
}
struct SplayTree {
#define KT ch[ch[root][1]][0]
#define LC ch[x][0]
#define RC ch[x][1]

	int root;//根节点
	int fa[N];//父亲结点
	int ch[N][2];//孩子结点
	int sz[N];//以结点i为子树的结点数
    int cnt;
    int val0[N],val1[N];
    int on[N];
    int gcd0[N],gcd1[N];
    int data[N],state[N];
    int num[N][2];
	void pushup(int x)
	{
		sz[x]=1+sz[LC]+sz[RC];//如果左子树为空,则LC=0,而sz[0]=0,即如果结点某个结点的子节点不存在,则指向空结点0,空节点的sz=0,不会造成错误
        gcd0[x]=gcd(gcd(gcd0[LC],gcd0[RC]),val0[x]);
        gcd1[x]=gcd(gcd(gcd1[LC],gcd1[RC]),val1[x]);
        num[x][0]=num[LC][0]+num[RC][0]+1-on[x];
        num[x][1]=num[LC][1]+num[RC][1]+on[x];
	}

	void rotate(int x, bool f) //旋转
	{
		int y=fa[x];
		int z=fa[y];
		ch[y][!f]=ch[x][f];
		fa[ch[x][f]]=y;
		fa[x]=z;
		if(z)
		{
			ch[z][ch[z][1]==y]=x;
		}
		ch[x][f]=y;
		fa[y]=x;
		pushup(y);
	}

	void splay(int x, int g) //把结点x转到结点g下
	{
		int y=fa[x];
        while (y!=g)
        {
			int z=fa[y];
			bool f=(ch[y][0]==x);
			if (z!=g && f==(ch[z][0]==y))
			{
				rotate(y,f);
			}
			rotate(x,f);
			y=fa[x];
		}
		pushup(x);
		if(g==0)
		{
			root=x;
		}
	}

	void rotateto(int k,int g) {	//把第k个结点转到结点g下,从第0个开始,因为有附加结点
		int x=root;
		while (sz[LC]!=k)
		{
			if (k<sz[LC])
			{
				x=LC;
			} else
			{
				k-=(sz[LC]+1);
				x=RC;
			}
		}
		splay(x,g);
	}

	void newNode(int &x,int c,int flag)
	{
        x=++cnt;
        on[x]=flag;
        num[x][flag]=1;num[x][1-flag]=0;
        if(!flag) val0[x]=c,val1[x]=0;
        else val1[x]=c,val0[x]=0;
        LC=RC=fa[x]=0;
        gcd0[x]=gcd(gcd(gcd0[LC],gcd0[RC]),val0[x]);
        gcd1[x]=gcd(gcd(gcd1[LC],gcd1[RC]),val1[x]);
        sz[x]=1;
	}

	void makeTree(int &x,int l,int r,int f)
	{
		if (l>r)
		{
			return;
		}
		int m=(l+r)>>1;
		newNode(x,data[m],state[m]);	/*num[m]权值改成题目所需的*/
		makeTree(LC,l,m-1,x);
		makeTree(RC,m + 1,r,x);
		fa[x]=f;
		pushup(x);//建立树的时候,从下往上依次pushup
	}
	void init(int n)
	{
		cnt=0;
		ch[0][0]=ch[0][1]=fa[0]=sz[0]=num[0][0]=num[0][1]=val0[0]=on[0]=val1[0]=gcd0[0]=gcd1[0]=0;//0结点是空节点,代表没有
		//为了方便处理边界,加两个边界顶点
		newNode(root,0,0);
		newNode(ch[root][1],0,0);//这两个边界结点的值不影响正常求解
		fa[cnt]=root;
		sz[root]=2;
		makeTree(KT,1,n,ch[root][1]);
		pushup(ch[root][1]);
		pushup(root);
	}
	int query(int l,int r,int flag)
	{
        rotateto(l-1,0);
        rotateto(r+1,root);
        if(num[KT][flag]==0) return -1;
        return (flag==1?gcd1[KT]:gcd0[KT]);
    }
    void insert(int id,int v,int flag)
    {
        rotateto(id,0);
        rotateto(id+1,root);
        int x=ch[root][1];
        newNode(LC,v,flag);
        fa[LC]=x;
        pushup(x);
        pushup(root);
    }
    void remove(int id)
    {
        rotateto(id-1,0);
        rotateto(id+1,root);
        int x=ch[root][1];
        //fa[LC]=0;
        LC=0;
        pushup(x);
        pushup(root);
    }
    void swap2(int &a,int &b)
    {
        int t=a;a=b;b=t;
    }
    void swap(int x)
    {
        on[x]=1-on[x];
        swap2(val0[x],val1[x]);
        gcd0[x]=gcd(gcd(gcd0[LC],gcd0[RC]),val0[x]);
        gcd1[x]=gcd(gcd(gcd1[LC],gcd1[RC]),val1[x]);
        num[x][0]=num[LC][0]+num[RC][0]+(1-on[x]);
        num[x][1]=num[LC][1]+num[RC][1]+on[x];
    }
    void rev(int id)
    {
        rotateto(id-1,0);
        rotateto(id+1,root);
        int x=ch[root][1];
        swap(KT);
        pushup(x);
        pushup(root);
    }
    void modify(int id,int v)
	{
        rotateto(id-1,0);
        rotateto(id+1,root);
        int x=ch[root][1];
        if(on[LC]==1) val1[LC]=v;
        else val0[LC]=v;
        gcd0[LC]=gcd(gcd(gcd0[ch[LC][0]],gcd0[ch[LC][1]]),val0[LC]);
        gcd1[LC]=gcd(gcd(gcd1[ch[LC][0]],gcd1[ch[LC][1]]),val1[LC]);
        pushup(x);
        pushup(root);
        return;
	}
	void print(int x)
	{
	    if(sz[x]==0) return;
        print(LC);
        printf("on:%d    val0:%d    val1:%d    gcd0:%d   gcd1:%d\n",on[x],val0[x],val1[x],gcd0[x],gcd1[x]);
        print(RC);
	}
	void debug(int x)
	{
        print(x);
        printf("\n");
	}
}spt;
int main()
{
    int i,j;
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        for(i=1;i<=n;i++)
            scanf("%d%d",&spt.data[i],&spt.state[i]);
        spt.init(n);
        char com[5];
        int a,b,state;
        while(m--)
        {
            scanf("%s",com);
            if(com[0]=='Q')
            {
                scanf("%d%d%d",&a,&b,&state);
                printf("%d\n",spt.query(a,b,state));
            }
            if(com[0]=='I')
            {
                scanf("%d%d%d",&a,&b,&state);
                spt.insert(a,b,state);
            }
            if(com[0]=='D')
            {
                scanf("%d",&a);
                spt.remove(a);
            }
            if(com[0]=='R')
            {
                scanf("%d",&a);
                spt.rev(a);
            }
            if(com[0]=='M')
            {
                scanf("%d%d",&a,&b);
                spt.modify(a,b);

            }
            //spt.debug(spt.root);
        }
    }
    return 0;
}

zoj 3761 Easy billiards dfs树

这题如果想到的话,写起来很简单。。
题意:无限大的二维坐标系中有n(0<=n<=2000)个球,可以用一个球沿与x坐标轴或y坐标轴平行的方向打球,如果球A碰到球B,那么球A停在球B的地方,球B以与A相同的方向前进,如果B运动的方向前方没有球了,那么判定球B出局,否则球B会撞到球C,以此类推,但是一个球不能直接出局,它必须是被某个球撞击后出局。
思路:把“相邻的球”(即可以直接撞击的球)连边,可以发现,同一个连通快中的球最后只会剩一个,,所以建图后dfs之,形成dfs树,为了保证一个连通块中的点撞到只剩一个,所以只要从子节点撞向父节点即可(比如,(0,0)、(1,0)、(0,1)三个点,dfs之后(0,0)是父节点,另两个是子节点,如果这时从(0,0)撞向(1,0)或(0,1)就会出错)
代码:

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef struct Edge{
    int to;
    int next;
}Edge;
typedef struct Point{
    int x,y;
    int num;
}Point;
Point p[2010];
Edge edge[8000+10];
int head[2010],cnt;
int x[2010],y[2010];
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;
}
int ansx[2010],ansy[2010];
char dir[2010][10];
int num;
bool visit[2010];
void dfs(int cur)
{
    visit[cur]=1;
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(visit[v]) continue;
        dfs(v);
        ansx[++num]=x[v],ansy[num]=y[v];
        if(x[v]==x[cur])
        {
            if(y[v]>y[cur]) strcpy(dir[num],"DOWN");
            else strcpy(dir[num],"UP");
        }
        else if(y[v]==y[cur])
        {
            if(x[v]>x[cur]) strcpy(dir[num],"LEFT");
            else strcpy(dir[num],"RIGHT");
        }
    }
    return;
}
bool cmp1(Point a,Point b)
{
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
bool cmp2(Point a,Point b)
{
    if(a.y!=b.y) return a.y<b.y;
    return a.x<b.x;
}
int main()
{
    int i,j;
    int n;
    while(~scanf("%d",&n))
    {
        num=cnt=0;
        memset(head,-1,sizeof(head));
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&x[i],&y[i]);
            p[i].x=x[i];p[i].y=y[i];p[i].num=i;
        }
        sort(p+1,p+1+n,cmp1);
        for(i=2;i<=n;i++)
        {
            if(p[i].x==p[i-1].x) add(p[i-1].num,p[i].num);
        }
        sort(p+1,p+1+n,cmp2);
        for(i=2;i<=n;i++)
        {
            if(p[i].y==p[i-1].y) add(p[i-1].num,p[i].num);
        }
        memset(visit,0,sizeof(visit));
        for(i=1;i<=n;i++)
        {
            if(visit[i]) continue;
            dfs(i);
        }
        printf("%d\n",n-num);
        for(i=1;i<=num;i++) printf("(%d, %d) %s\n",ansx[i],ansy[i],dir[i]);
    }
    return 0;
}

hdoj1540 Tunnel Warfare

做了一些区间合并,现在已经比较理解了,关键一点是要知道,任何一个连续区,不断向下,一定会被分隔开。
这道题的query,要求包含节点x的1的连续长度。如果m+1-rmax[lson]<=pos && pos<=m+lmax[rson]那么直接返回这一段,否则x所在的连续1区间必定在左子区间或右子区间,继续往下找即可。

#include<stdio.h>
#include<string.h>
#define lson id<<1
#define rson id<<1|1
const int maxn=5e4;
int lmax[maxn<<2],rmax[maxn<<2],mmax[maxn<<2];
int st[maxn+10],top;
inline int max(int a,int b){return a>b?a:b;}
void pushup(int id,int l,int r)
{
	int m=(l+r)/2;
	int lenl=m-l+1,lenr=r-m;
	mmax[id]=max(mmax[lson],mmax[rson]);
	mmax[id]=max(mmax[id],rmax[lson]+lmax[rson]);
	lmax[id]=lmax[lson];
	rmax[id]=rmax[rson];
	if(lmax[lson]==lenl) lmax[id]+=lmax[rson];
	if(rmax[rson]==lenr) rmax[id]+=rmax[lson];
	return;
}
void build(int id,int l,int r)
{
	lmax[id]=rmax[id]=mmax[id]=r-l+1;
	if(l==r) return;
	int m=(l+r)/2;
	build(lson,l,m);
	build(rson,m+1,r);
	return;
}
void update(int id,int l,int r,int pos,int v)
{
	if(l==r)
	{
		lmax[id]=rmax[id]=mmax[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,l,r);
	return;
}
int query(int id,int l,int r,int pos)
{
	if(l==r) return mmax[id];
	int m=(l+r)/2;
	if(m+1-rmax[lson]<=pos && pos<=m+lmax[rson]) return rmax[lson]+lmax[rson];
	if(pos<=m) return query(lson,l,m,pos);
	else return query(rson,m+1,r,pos);
}
int main()
{
	int i,j;
	int n,m;
	char com[5];
	int x;
	while(~scanf("%d%d",&n,&m))
	{
		top=0;
		build(1,1,n);
		for(i=1;i<=m;i++)
		{
			scanf("%s",com);
			if(com[0]!=’R') scanf("%d",&x);
			else
			{
				if(!top) continue;
				update(1,1,n,st[top--],1);
			}
			if(com[0]==’D') update(1,1,n,x,0),st[++top]=x;
			if(com[0]==’Q') printf("%d\n",query(1,1,n,x));
		}
	}
	return 0;
}

hdoj2871 Memory Control

这题前面部分和hotel那题是差不多的,也是寻找最左边连续的空白,成段更新,但是free时要输出free掉的起始点和结束点,get操作要输出第x个block的起始位置,这就比较烦了。开始用set,发现不行,因为要求kth并删除,我去,,难道要写splay。。这样代码也太长了吧。、果断谷歌之,发现是用vector解决的,vector可以在制定迭代器之前的位置插入元素,但是这样效率是o(n)吧。。。要是有5e4个查询是get x的话,岂不是效率超低?
解决两个问题:
(1)怎样知道unit x是属于哪个block的,可以维护一个域block[],当区间由多个内存块组成时block[id]=-1,block[id]=0表示id区间没有内存块覆盖。
(2)怎样get第x个(block是按起始点排序的)内存块的起始位置,按起始点维护一个vector。如上所述,插入和删除时先二分找到位置。
insert(iter,element);表示在迭代器iter的前面一个位置插入元素element。
这题比较考验耐心。。

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#define lson id<<1
#define rson id<<1|1
using namespace std;
const int maxn=5e4;
int block[maxn<<2],lmax[maxn<<2],rmax[maxn<<2],mmax[maxn<<2];
bool sett[maxn<<2],resett[maxn<<2];
typedef struct Node{
	int begin,len;
	bool operator <(const Node &a) const
	{
		return begin<a.begin;
	}
}Node;
Node mem[maxn+10];
vector<Node> hash;
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
void do_sett(int id,int l,int r,int type)
{
	mmax[id]=lmax[id]=rmax[id]=0;
	block[id]=type;
	sett[id]=1;resett[id]=0;
}
void do_resett(int id,int l,int r)
{
	mmax[id]=lmax[id]=rmax[id]=r-l+1;
	block[id]=0;
	resett[id]=1;sett[id]=0;
}
void pushup(int id,int l,int r)
{
	int m=(l+r)/2;
	int lenl=m-l+1,lenr=r-m;
	if(block[lson]!=block[rson]) block[id]=-1;
	else block[id]=block[lson];
	mmax[id]=max(mmax[lson],mmax[rson]);
	mmax[id]=max(mmax[id],rmax[lson]+lmax[rson]);
	lmax[id]=lmax[lson];
	rmax[id]=rmax[rson];
	if(lmax[lson]==lenl) lmax[id]+=lmax[rson];
	if(rmax[rson]==lenr) rmax[id]+=rmax[lson];
	return;
}
void pushdown(int id,int l,int r)
{
	int m=(l+r)/2;
	if(sett[id]) {do_sett(lson,l,m,block[id]);do_sett(rson,m+1,r,block[id]);sett[id]=0;}
	if(resett[id]) {do_resett(lson,l,m);do_resett(rson,m+1,r);resett[id]=0;}
}
void build(int id,int l,int r)
{
	sett[id]=resett[id]=0;
	lmax[id]=rmax[id]=mmax[id]=r-l+1;
	block[id]=0;
	if(l==r) return;
	int m=(l+r)/2;
	build(lson,l,m);
	build(rson,m+1,r);
	return;
}
void update_sett(int id,int l,int r,int L,int R,int type)
{
	if(L<=l && r<=R)
	{
		do_sett(id,l,r,type);
		return;
	}
	pushdown(id,l,r);
	int m=(l+r)/2;
	if(L<=m) update_sett(lson,l,m,L,R,type);
	if(R>m) update_sett(rson,m+1,r,L,R,type);
	pushup(id,l,r);
	return;
}
void update_resett(int id,int l,int r,int L,int R)
{
	if(L<=l && r<=R)
	{
		do_resett(id,l,r);
		return;
	}
	pushdown(id,l,r);
	int m=(l+r)/2;
	if(L<=m) update_resett(lson,l,m,L,R);
	if(R>m) update_resett(rson,m+1,r,L,R);
	pushup(id,l,r);
	return;
}
int query(int id,int l,int r,int len)
{
	if(mmax[id]<len) return 0;
	if(l==r) return l;
	pushdown(id,l,r);
	int m=(l+r)/2;
	if(mmax[lson]>=len) return query(lson,l,m,len);
	if(rmax[lson]+lmax[rson]>=len) return m+1-rmax[lson];
	return query(rson,m+1,r,len);
}
int query_block(int id,int l,int r,int pos)
{
	if(l==r) return block[id];
	pushdown(id,l,r);
	int m=(l+r)/2;
	if(pos<=m) return query_block(lson,l,m,pos);
	else return query_block(rson,m+1,r,pos);
}
int main()
{
	//freopen("data.in","r",stdin);
	int i,j;
	int n,m;
	char com[10];
	int x;
	vector<Node>::iterator it;
	while(~scanf("%d%d",&n,&m))
	{
		int cc=0;
		if(!hash.empty()) hash.clear();
		build(1,1,n);
		for(i=1;i<=m;i++)
		{
			scanf("%s",com);
			if(com[0]!='R') scanf("%d",&x);
			else
			{
				update_resett(1,1,n,1,n);
				printf("Reset Now\n");
				if(!hash.empty()) hash.clear();
			}
			if(com[0]=='N')
			{
				int pos=query(1,1,n,x);
				if(pos)
				{
					cc++;
					mem[cc].begin=pos;mem[cc].len=x;
					it=lower_bound(hash.begin(),hash.end(),mem[cc]);
					hash.insert(it,mem[cc]);
					printf("New at %d\n",pos);
					update_sett(1,1,n,pos,pos+x-1,cc);

				}
				else printf("Reject New\n");
			}
			if(com[0]=='F')
			{
				int ret=query_block(1,1,n,x);
				if(ret==0) printf("Reject Free\n");
				else
				{
					printf("Free from %d to %d\n",mem[ret].begin,mem[ret].begin+mem[ret].len-1);
					update_resett(1,1,n,mem[ret].begin,mem[ret].begin+mem[ret].len-1);
					it=lower_bound(hash.begin(),hash.end(),mem[ret]);
					hash.erase(it);
				}
			}
			if(com[0]=='G')
			{
				if(x>hash.size()) printf("Reject Get\n");
				else printf("Get at %d\n",hash[x-1].begin);
			}
		}
		printf("\n");
	}
	return 0;
}

hdoj3397 Sequence operation

和前面差不多的区间合并,只不多操作多一些,要同时记录1和0的情况

#include<stdio.h>
#include<string.h>
#define lson id<<1
#define rson id<<1|1
const int maxn=5e5;

inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
inline void swap(int &a,int &b){a^=b;b^=a;a^=b;return;}

int sum[maxn<<2],lmax[maxn<<2],rmax[maxn<<2],mmax[maxn<<2];
int zmmax[maxn<<2],zlmax[maxn<<2],zrmax[maxn<<2];
bool set[maxn<<2],reset[maxn<<2],rev[maxn<<2];

void do_set(int id,int l,int r)
{
	sum[id]=lmax[id]=rmax[id]=mmax[id]=r-l+1;
	zmmax[id]=zlmax[id]=zrmax[id]=0;
	set[id]=1;reset[id]=rev[id]=0;
	return;
}
void do_reset(int id,int l,int r)
{
	sum[id]=lmax[id]=rmax[id]=mmax[id]=0;
	zmmax[id]=zlmax[id]=zrmax[id]=r-l+1;
	reset[id]=1;set[id]=rev[id]=0;
}
void do_rev(int id,int l,int r)
{
	if(set[id]) {do_reset(id,l,r);return;}
	if(reset[id]) {do_set(id,l,r);return;}
	rev[id]^=1;
	sum[id]=r-l+1-sum[id];
	swap(mmax[id],zmmax[id]);
	swap(lmax[id],zlmax[id]);
	swap(rmax[id],zrmax[id]);
	return;
}
void opt(int id,int l,int r,int type)
{
	if(type==0) do_reset(id,l,r);
	if(type==1) do_set(id,l,r);
	if(type==2) do_rev(id,l,r);
	return;
}
void pushup(int id,int l,int r)
{
	int m=(l+r)/2;
	int lenl=m-l+1,lenr=r-m;
	
	sum[id]=sum[lson]+sum[rson];
	
	mmax[id]=max(mmax[lson],mmax[rson]);
	mmax[id]=max(mmax[id],rmax[lson]+lmax[rson]);
	lmax[id]=lmax[lson];
	rmax[id]=rmax[rson];
	if(lmax[lson]==lenl) lmax[id]+=lmax[rson];
	if(rmax[rson]==lenr) rmax[id]+=rmax[lson];

	zmmax[id]=max(zmmax[lson],zmmax[rson]);
	zmmax[id]=max(zmmax[id],zrmax[lson]+zlmax[rson]);
	zlmax[id]=zlmax[lson];
	zrmax[id]=zrmax[rson];
	if(zlmax[lson]==lenl) zlmax[id]+=zlmax[rson];
	if(zrmax[rson]==lenr) zrmax[id]+=zrmax[lson];
	return;
}
void pushdown(int id,int l,int r)
{
    int m=(l+r)/2;
	if(set[id]){do_set(lson,l,m);do_set(rson,m+1,r);set[id]=0;}
	if(reset[id]){do_reset(lson,l,m);do_reset(rson,m+1,r);reset[id]=0;}
	if(rev[id]){do_rev(lson,l,m);do_rev(rson,m+1,r);rev[id]=0;}
	return;
}
void build(int id,int l,int r)
{
	set[id]=reset[id]=rev[id]=0;
	if(l==r)
	{
		scanf("%d",&sum[id]);
		lmax[id]=rmax[id]=mmax[id]=sum[id];
		zmmax[id]=zlmax[id]=zrmax[id]=1-sum[id];
		return;
	}
	int m=(l+r)/2;
	build(lson,l,m);
	build(rson,m+1,r);
	pushup(id,l,r);
	return;
}
void update(int id,int l,int r,int L,int R,int type)
{
	if(L<=l && r<=R)
	{
		opt(id,l,r,type);
		return;
	}
	pushdown(id,l,r);
	int m=(l+r)/2;
	if(L<=m) update(lson,l,m,L,R,type);
	if(R>m) update(rson,m+1,r,L,R,type);
	pushup(id,l,r);
	return;
}
int query_sum(int id,int l,int r,int L,int R)
{
	if(L<=l && r<=R) return sum[id];
	pushdown(id,l,r);
	int m=(l+r)/2,ret=0;
	if(L<=m) ret+=query_sum(lson,l,m,L,R);
	if(R>m) ret+=query_sum(rson,m+1,r,L,R);
	return ret;
}
int query_len(int id,int l,int r,int L,int R)
{
	if(L<=l && r<=R) return mmax[id];
	pushdown(id,l,r);
	int m=(l+r)/2,ret=0;
	if(L<=m) ret=max(ret,query_len(lson,l,m,L,R));
	if(R>m) ret=max(ret,query_len(rson,m+1,r,L,R));
	ret=max(ret,min(R,m+lmax[rson])-max(L,m+1-rmax[lson])+1);
	return ret;
}
int main()
{
	int i,j,t;
	int n,m;
	int op,a,b;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		build(1,1,n);
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d",&op,&a,&b);a++;b++;
			if(op<=2) update(1,1,n,a,b,op);
			if(op==3) printf("%d\n",query_sum(1,1,n,a,b));
			if(op==4) printf("%d\n",query_len(1,1,n,a,b));
		}
	}
	return 0;
}