ucore OS lab: bootloader启动ucore


理解通过make生成执行文件的过程

1.操作系统镜像文件ucore.img是如何一步一步生成的?(需要比较详细地解释Makefile中每一条相关命令和命令参数的含义,以及说明命令导致的结果)

通过 make V= 命令可看build过程中,make执行了哪些命令。

出现最多的编译命令,如以下形式 (除源文件和目标文件外,其他参数差不多):

gcc -Ikern/init/ -march=i686 -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/ -Ikern/debug/ -Ikern/driver/ -Ikern/trap/ -Ikern/mm/ -c kern/init/init.c -o obj/kern/init/init.o

通过源文件和目标文件进行逐步分析:

  • 编译 kern/init/init.c ,生成 obj/kern/init/init.o
  • 编译 kern/libs 下的 stdio.c readline.c, 在obj/kern/libs 目录下生成对应的.o文件
  • 编译 kern/debug 下的panic.c kdebug.c kmonitor.c, 在obj/kern/debug 目录下生成对应.o文件
  • 编译 kern/driver 下的 clock.c console.c picirq.c intr.c, 同上在对应目录生成.o文件
  • 编译 kern/trap 下的trap.c vectors.S trapentry.S, 在对应目录生成.o文件
  • 编译 kern/mm 下的pmm.c 文件,生成 obj/kern/mm/pmm.o
  • 编译 libs 下的 string.c printfmy.c 文件, 在 obj/libs下生成对应.o文件
  • ld命令指定tools目录下的kernel.ld作为link的script,将上述.o文件链接生成 bin/kernel
  • 编译 tools/sign.c, 生成sign.o并进一步得到 bin/sign
  • 编译 boot目录下的 bootasm.S 和 bootmain.c编译生成相应.o文件,两个文件链接生成 obj/bootblock.o, 最后通过sign工具生成 bin/bootblock
  • 通过 dd 命令将bin目录下的bootloader和kernel写到 ucore.img

对应到 makefile 文件中:

# create ucore.img

UCOREIMG    := $(call totarget,ucore.img)

$(UCOREIMG): $(kernel) $(bootblock)
    $(V)dd if=/dev/zero of=$@ count=10000
    $(V)dd if=$(bootblock) of=$@ conv=notrunc
    $(V)dd if=$(kernel) of=$@ seek=1 conv=notrunc

$(call create_target,ucore.img)

totarget函数的作用是给参数加上路径前缀: \
totarget = $(addprefix $(BINDIR)$(SLASH),$(1))

if: 输入文件 \
of:输出文件 \
count:拷贝的块数\
seek = 1:从输出文件跳过1个块数再开始拷贝 \
conv = notrunc : 输入文件比输出文件小时,不截断输出文件 \
dd命令参考链接:https://www.runoob.com/linux/linux-comm-dd.html

从上可知, ucore.img 的生成需要 bootblock 和 kernel 两个二进制文件。

接下来是 bootblock 对应的makefile部分 :

# create bootblock
bootfiles = $(call listf_cc,boot)
$(foreach f,$(bootfiles),$(call cc_compile,$(f),$(CC),$(CFLAGS) -Os -nostdinc))

bootblock = $(call totarget,bootblock)

$(bootblock): $(call toobj,$(bootfiles)) | $(call totarget,sign)
    @echo + ld $@
    $(V)$(LD) $(LDFLAGS) -N -e start -Ttext 0x7C00 $^ -o $(call toobj,bootblock)
    @$(OBJDUMP) -S $(call objfile,bootblock) > $(call asmfile,bootblock)
    @$(OBJCOPY) -S -O binary $(call objfile,bootblock) $(call outfile,bootblock)
    @$(call totarget,sign) $(call outfile,bootblock) $(bootblock)

$(call create_target,bootblock)

其中,
bootfiles = $(call listf_cc,boot)

listf_cc 函数的作用是从 boot/* 中过滤出所有 .c 和 .S 文件,即 bootmain.c 和 bootasm.S, 在makefile中截取了如下相关描述:

CTYPE   := c S
listf_cc = $(call listf,$(1),$(CTYPE))  
# list all files in some directories: (#directories, #types) 
listf = $(filter $(if $(2),$(addprefix %.,$(2)),%),\
          $(wildcard $(addsuffix $(SLASH)*,$(1)))) 
# wildcard会展开后面的通配符,即返回符合 boot/*的所有内容,且以空格分隔

$(foreach f,$(bootfiles),$(call cc_compile,$(f),$(CC),$(CFLAGS) -Os -nostdinc)) ' \
通过这条命令,从 bootfiles 循环取出源文件名,会批量生成gcc编译命令,具体的过程较为复杂。最后得到 bootasm.o 和 bootmain.o。

实际命令:


gcc -Iboot/ -fno-builtin -Wall -ggdb -m32 -gstabs \
    -nostdinc  -fno-stack-protector -Ilibs/ -Os -nostdinc \
    -c boot/bootasm.S -o obj/boot/bootasm.o

其中关键的参数为:(直接从lab1_result拿过来的,因为的确好多不认识...,有些还难查)
    -ggdb  生成可供gdb使用的调试信息。这样才能用qemu+gdb来调试bootloader or ucore。
    -m32  生成适用于32位环境的代码。我们用的模拟硬件是32bit的80386,所以ucore也要是32位的软件。
    -gstabs  生成stabs格式的调试信息。这样要ucore的monitor可以显示出便于开发者阅读的函数调用栈信息
    -nostdinc  不使用标准库。标准库是给应用程序用的,我们是编译ucore内核,OS内核是提供服务的,所以所有的服务要自给自足。
    -fno-stack-protector  不生成用于检测缓冲区溢出的代码。这是for 应用程序的,我们是编译内核,ucore内核好像还用不到此功能。
    -Os  为减小代码大小而进行优化。根据硬件spec,主引导扇区只有512字节,我们写的简单bootloader的最终大小不能大于510字节。
    -I<dir>  添加搜索头文件的路径

gcc -Iboot/ -fno-builtin -Wall -ggdb -m32 -gstabs -nostdinc    -fno-stack-protector -Ilibs/ -Os -nostdinc -c boot/bootmain.c -o obj/boot/bootmain.o

新出现参数:      
    -fno-builtin  除非用__builtin_前缀,否则不进行builtin函数的优化

下面一段就是将生成的 bootasm.o , bootmain.o 和 sign 进行连接,得到二进制程序 bootblock 的 makefile 部分:

$(bootblock): $(call toobj,$(bootfiles)) | $(call totarget,sign)
    @echo + ld $@
    $(V)$(LD) $(LDFLAGS) -N -e start -Ttext 0x7C00 $^ -o $(call toobj,bootblock)
    @$(OBJDUMP) -S $(call objfile,bootblock) > $(call asmfile,bootblock)
    @$(OBJCOPY) -S -O binary $(call objfile,bootblock) $(call outfile,bootblock)
    @$(call totarget,sign) $(call outfile,bootblock) $(bootblock)

实际命令:

#首先生成bootlock.o
ld -m    elf_i386 -nostdlib -N -e start -Ttext 0x7C00 obj/boot/bootasm.o obj/boot/bootmain.o -o obj/bootblock.o
 其中关键的参数为:
    -m <emulation>  模拟为i386上的连接器
    -nostdlib  不使用标准库
    -N  设置代码段和数据段均可读写
    -e <entry>  指定入口
    -Ttext  制定代码段开始位置

#拷贝二进制代码bootblock.o到bootblock.out
 objcopy -S -O binary obj/bootblock.o obj/bootblock.out
    其中关键的参数为:
        -S  移除所有符号和重定位信息
        -O <bfdname>  指定输出格式

#使用sign工具处理bootblock.out,生成bootblock
  bin/sign obj/bootblock.out bin/bootblock

从上可见 bootblock的生成还需要 sign。实验指导书中解释这是一个C语言小程序,是辅助工具,用于生成一个符合规范的硬盘主引导扇区。
这是生成sign的 makefile 部分:

# create 'sign' tools
$(call add_files_host,tools/sign.c,sign,sign)
$(call create_target_host,sign,sign)

实际命令:

gcc -Itools/ -g -Wall -O2 -c tools/sign.c \
    -o obj/sign/tools/sign.o
gcc -g -Wall -O2 obj/sign/tools/sign.o -o bin/sign

下面是生成 kernel 的 makefile 代码:

# kernel

KINCLUDE    += kern/debug/ \
               kern/driver/ \
               kern/trap/ \
               kern/mm/

KSRCDIR     += kern/init \
               kern/libs \
               kern/debug \
               kern/driver \
               kern/trap \
               kern/mm

KCFLAGS     += $(addprefix -I,$(KINCLUDE))

$(call add_files_cc,$(call listf_cc,$(KSRCDIR)),kernel,$(KCFLAGS))

KOBJS   = $(call read_packet,kernel libs)

# create kernel target
kernel = $(call totarget,kernel)

$(kernel): tools/kernel.ld

$(kernel): $(KOBJS)
    @echo + ld $@
    $(V)$(LD) $(LDFLAGS) -T tools/kernel.ld -o $@ $(KOBJS)
    @$(OBJDUMP) -S $@ > $(call asmfile,kernel)
    @$(OBJDUMP) -t $@ | $(SED) '1,/SYMBOL TABLE/d; s/ .* / /; /^$$/d' > $(call symfile,kernel)

KINCLUDE: 头文件搜索目录 \
KSRCDIR: 源文件目录 \
KOBJS: 包含了所有连接需要的.o文件 \
KCFLAGS: gcc编译命令参数

$(call add_files_cc, $(call listf_cc,$(KSRCDIR)), kernel, $(KCFLAGS))

此条命令批量地生成编译命令,这里生成 .o 文件的编译命令类似,以init.o为例(即开头所述的那条)

gcc -Ikern/init/ -march=i686 -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/ -Ikern/debug/ -Ikern/driver/ -Ikern/trap/ -Ikern/mm/ -c kern/init/init.c -o obj/kern/init/init.o

link 的实际命令:

ld -m    elf_i386 -nostdlib -T tools/kernel.ld -o bin/kernel  obj/kern/init/init.o obj/kern/libs/stdio.o obj/kern/libs/readline.o obj/kern/debug/panic.o obj/kern/debug/kdebug.o obj/kern/debug/kmonitor.o obj/kern/driver/clock.o obj/kern/driver/console.o obj/kern/driver/picirq.o obj/kern/driver/intr.o obj/kern/trap/trap.o obj/kern/trap/vectors.o obj/kern/trap/trapentry.o obj/kern/mm/pmm.o  obj/libs/string.o obj/libs/printfmt.o

# -T 后指定link的script

当bootblock 和 kernel 都准备好后,即可用 dd 装到 ucore.img 中了。

makefile教程参考 : https://seisman.github.io/how-to-write-makefile/index.html

2.一个被系统认为是符合规范的硬盘主引导扇区的特征是什么?

前面提到sign是一个c语言辅助工具,用于生成一个符合规范的硬盘主引导扇区。从sign.c中可发现主引导扇区是512字节大小,第511个字节是0x55,第512个字节是0xAA.


使用qemu执行并调试lab1中的软件

1.从CPU加电后执行的第一条指令开始,单步跟踪BIOS的执行。

修改lab/tools/gdbint:

define hook-stop
x/i $pc
end

set architecture i8086
target remote :1234

gdbint 中的命令在gdb指定-x参数启动时就会被自动执行,等效于在terminal中手动输入。

gdb 通过本地的1234端口与qemu连接,进行远程调试。CPU一开始加电后是8086实模式,hook-stop 是 GDB 在每次发生断点事件时调用的特殊定义,在这里自定义为显示当前执行的指令和EIP值.

在lab1目录下执行 make debug,进入 gdb 后,就可以通过si命令进行单步跟踪了。

2.在初始化位置0x7c00设置实地址断点,测试断点正常。

0x7c00是 bootloader 的开始地址。修改gdbint如下:

set architecture i8086
target remote :1234

b *0x7c00
c 
x /10i $pc

在 makefile 的debug中已经定义qemu等待gdb连接且不自动启动CPU,continue后才继续工作. 所以设置断点后,要添加一个continue命令才会执行到0x7c00.

执行 make debug, 可观察到:

Breakpoint 1, 0x00007c00 in ?? ()
=> 0x7c00:      cli
   0x7c01:      cld
---Type <return> to continue, or q <return> to quit---
   0x7c02:      xor    %eax,%eax
   0x7c04:      mov    %eax,%ds
   0x7c06:      mov    %eax,%es
   0x7c08:      mov    %eax,%ss
   0x7c0a:      in     $0x64,%al
   0x7c0c:      test   $0x2,%al
   0x7c0e:      jne    0x7c0a
   0x7c10:      mov    $0xd1,%al

3.从0x7c00开始跟踪代码运行,将单步跟踪反汇编得到的代码与bootasm.S和 bootblock.asm进行比较。

0x7c00开始反汇编得到的代码即bootasm.S和bootblock.asm的start入口处开始的代码。


分析bootloader进入保护模式的过程

BIOS将通过读取硬盘主引导扇区到内存,并转跳到对应内存中的位置执行bootloader。

1.为何开启A20,以及如何开启A20

为了向下兼容早期8086 PC(只能访问1M内存空间), IBM决定在PC AT计算机系统上加个硬件逻辑,来模仿回绕特征(寻址超过1M,则又从0开始,相当于实际内存地址由取模操作得到),于是出现了A20 Gate。他们的方法就是把A20地址线控制和8042键盘控制器的一个输出进行AND操作,这样来控制A20地址线的打开(使能)和关闭(屏蔽\禁止)。当80386处于保护模式时,需要将A20开启,才能访问全部有效内存空间。

关于A20 Gate的更多描述以及如何操作8042键盘控制器,可见:
https://chyyuu.gitbooks.io/ucore_os_docs/content/lab1/lab1_appendix_a20.html

以下为bootloader中由实模式进入保护模式的相关代码,在此之前将各个数据段初始化好,然后开启A20 :

.code16                        # Assemble for 16-bit mode
    cli                        # Disable interrupts
    cld                        # String operations increment
    # Set up the important data segment registers (DS, ES, SS).
    xorw %ax, %ax              # Segment number zero
    movw %ax, %ds              # -> Data Segment
    movw %ax, %es              # -> Extra Segment
    movw %ax, %ss              # -> Stack Segment
seta20.1:
    inb $0x64, %al             # Wait for not busy(8042 input buffer empty).
    testb $0x2, %al
    jnz seta20.1

    movb $0xd1, %al            # 0xd1 -> port 0x64
    outb %al, $0x64            # 0xd1 means: write data to 8042's P2 port

seta20.2:
    inb $0x64, %al             # Wait for not busy(8042 input buffer empty).
    testb $0x2, %al
    jnz seta20.2

    movb $0xdf, %al            # 0xdf -> port 0x60
    outb %al, $0x60            # 0xdf = 11011111, means set P2's A20 bit(the 1 bit) to 1

2.如何初始化GDT表

lgdt gdtdesc

lgdt命令将如下描述的gdt表的大小和地址载入到GDTR寄存器中。

# Bootstrap GDT
.p2align 2                                          # force 4 byte alignment
gdt:
    SEG_NULLASM                                     # null seg
    SEG_ASM(STA_X|STA_R, 0x0, 0xffffffff)           # code seg for bootloader and kernel
    SEG_ASM(STA_W, 0x0, 0xffffffff)                 # data seg for bootloader and kernel

gdtdesc:
    .word 0x17                                      # sizeof(gdt) - 1
    .long gdt                                       # address gdt

3.如何使能和进入保护模式

经过上面的准备,
将CR0中的保护模式允许位(PE)置1,就启动了保护模式.

    movl %cr0, %eax
    orl $CR0_PE_ON, %eax
    movl %eax, %cr0

接着跳转到保护模式32位下的代码段,

ljmp $PROT_MODE_CSEG, $protcseg

完成段选择子和堆栈的设置后,进入 bootmain 方法


.code32                                             # Assemble for 32-bit mode
protcseg:
    # Set up the protected-mode data segment registers
    movw $PROT_MODE_DSEG, %ax                       # Our data segment selector
    movw %ax, %ds                                   # -> DS: Data Segment
    movw %ax, %es                                   # -> ES: Extra Segment
    movw %ax, %fs                                   # -> FS
    movw %ax, %gs                                   # -> GS
    movw %ax, %ss                                   # -> SS: Stack Segment

    # Set up the stack pointer and call into C. The stack region is from 0--start(0x7c00)
    movl $0x0, %ebp
    movl $start, %esp
    call bootmain

十月(扫描线,分块,点分治)

  • 最近没什么时间更新了,今后更新频率会降低,但同时一次的内容也更多。

  • 这个月的kickstart好可惜啊。。。痛失35分。。其实就是太菜了。。。

  • 开始在AcWing上打卡,逐步完成《算法竞赛进阶指南》的内容。

1. 重温扫描线写法

窗内的星星

#include<bits/stdc++.h>
using namespace std;

int n,W,H;
struct  Line
{
  int x,y1,y2,c;
  bool operator<(const Line &b){
    return x==b.x? x>b.c : x<b.x; //减掉c是在下一个x查询时起作用,因为假设矩形顶点都是整数,虽不影响答案,但实际上离真正的右边界还有些余量

  } 
}L[20005];
unordered_map<int,int> val;
int raw[40005];
struct SegmentTree{
  int l,r;
  int dat;
  int add;

}t[20005*4];

void build(int l,int r,int p){
  t[p].l=l,t[p].r=r;
  t[p].dat=0;
  if(l==r){
    return ;
  }
  int mid= (l+r)>>1;  
  build(l,mid,p<<1);
  build(mid+1,r,p<<1|1);
}

void spread(int x ){
  if (t[x].add){
    t[x*2].add+=t[x].add ;
    t[2*x+1].add+=t[x].add; 
    t[x*2].dat+=t[x].add;
    t[x*2+1].dat+=t[x].add;
    t[x].add=0;
  }

}

void change(int l,int r, int p,int x){
  if (l<=t[p].l && t[p].r <=r) {
    t[p].add +=x;
    t[p].dat +=x;
    return ;
  }
  spread(p);
  int mid = (t[p].l+t[p].r)>>1;
  if (l<=mid) change(l,r,p<<1,x) ;
  if(mid<r) change(l,r,p<<1|1,x);
  t[p].dat = max(t[p*2].dat,t[p*2+1].dat);
}

int main(){
  while(~scanf("%d%d%d",&n,&W,&H)){
    int tot=0,tot2=0;
    memset(L,0,sizeof(L));
    val.clear();
    memset(raw,0,sizeof(raw));
    for(int i=0;i<n;++i){
      int x,y,c;
      scanf("%d%d%d",&x,&y,&c);
      L[tot].x=x,L[tot].y1=y,L[tot].y2=y+H-1,L[tot++].c+=c;
      L[tot].x=x+W-1,L[tot].y1=y,L[tot].y2=y+H-1,L[tot++].c-=c;
      raw[tot2++]=y;
      raw[tot2++]=y+H-1;
    }
    sort(L,L+tot);
    sort(raw,raw+tot2);
    int tot3 = unique(raw,raw+tot2)-raw;
    for(int i=1;i<=tot3;++i){
       val[raw[i-1]] = i;
    }
    build(1,tot3-1,1);
    int ans =0;
    for(int i =0;i<tot;++i){
      change(val[L[i].y1],val[L[i].y2]-1,1,L[i].c);
      ans = max(t[1].dat,ans);
    }
    printf("%d\n",ans);
  }

  return 0;
}

2. 学习了分块,“大段维护,局部朴素”思想。好像还混入了莫队算法这种奇妙的东西。。

(设分块数为T ,会发现要算法复杂度达到最优 ,可根据均值不等式得到T的值。)

蒲公英

#include <bits/stdc++.h>
using namespace std;

int a[40010];
int b[40010];
int cnt[40][40][40010], cnt_temp[40010];
int maxx[40][40];
int res[40][40];
int L[40], R[40];
int pos[40010];
int n, m, t;

int ask(int l, int r) {
  int p = pos[l], q = pos[r];
  int ans = 0;
  int ret;
  if (p == q) {
    for (int i = l; i <= r; ++i) cnt_temp[a[i]] = 0;
    for (int i = l; i <= r; ++i) {
      cnt_temp[a[i]]++;
      if (ans < cnt_temp[a[i]]) {
        ret = a[i];
        ans = cnt_temp[a[i]];
      }
      if (ans == cnt_temp[a[i]] && a[i] < ret) {
        ret = a[i];
      }
    }
    return b[ret];
  } else {
    ans = maxx[p + 1][q - 1];
    ret = res[p + 1][q - 1];
    for (int i = l; i <= R[p]; ++i) {
      cnt_temp[a[i]] = 0;
    }
    for (int i = L[q]; i <= r; ++i) {
      cnt_temp[a[i]] = 0;
    }
    for (int i = l; i <= R[p]; ++i) {
      cnt_temp[a[i]]++;
      if (ans < cnt_temp[a[i]] + cnt[p + 1][q - 1][a[i]]) {
        ret = a[i];
        ans = cnt_temp[a[i]] + cnt[p + 1][q - 1][a[i]];
      }
      if (ans == cnt_temp[a[i]] + cnt[p + 1][q - 1][a[i]] && a[i] < ret) {
        ret = a[i];
      }
    }

    for (int i = L[q]; i <= r; ++i) {
      cnt_temp[a[i]]++;
      if (ans < cnt_temp[a[i]] + cnt[p + 1][q - 1][a[i]]) {
        ret = a[i];
        ans = cnt_temp[a[i]] + cnt[p + 1][q - 1][a[i]];
      }
      if (ans == cnt_temp[a[i]] + cnt[p + 1][q - 1][a[i]] && a[i] < ret) {
        ret = a[i];
      }
    }
    return b[ret];
  }
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    b[i] = a[i];
  }
  t = pow(1.0 * n, 1.0 / 3.0);

  for (int i = 1; i <= t; ++i) {
    L[i] = (i - 1) * (n / t) + 1;
    R[i] = n / t * i;
  }
  if (R[t] < n) t++, L[t] = R[t - 1] + 1, R[t] = n;

  sort(b + 1, b + n + 1);
  int M = unique(b + 1, b + 1 + n) - b - 1;
  for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + 1 + M, a[i]) - b;

  int T = 1;
  for (int i = 1; i <= n; ++i) {
    pos[i] = T;
    if (i >= R[T]) T++;
  }
  for (int i = 1; i <= t; ++i) {
    for (int j = i; j <= t; ++j) {
      for (int k = L[i]; k <= R[j]; ++k) {
        cnt[i][j][a[k]]++;
        if (maxx[i][j] < cnt[i][j][a[k]]) {
          maxx[i][j] = cnt[i][j][a[k]];
          res[i][j] = a[k];
        }
        if (maxx[i][j] == cnt[i][j][a[k]] && a[k] < res[i][j]) {
          res[i][j] = a[k];
        }
      }
    }
  }
  int x = 0;
  int l0, r0, l, r;
  while (m--) {
    scanf("%d%d", &l0, &r0);
    l = (l0 + x - 1) % n + 1;
    r = (r0 + x - 1) % n + 1;
    if (l > r) swap(l, r);

    printf("%d\n", x = ask(l, r));
  }

  return 0;
}

还有做法是保存段边界为端点的区间众数。这个做法涉及到一个技巧,就是顺序保存数a在序列里的出现位置,然后对要求范围的L,R进行二分查找,下标相减可得到a在[L,R]中的出现次数。

磁力块

#include<bits/stdc++.h>
using namespace std;

int x0,Y0,pl;
long long rl;
int N;
struct stone{
  int m,cp;
  long long r; 
  long long cr;
  bool operator<(stone a){
     return  m<a.m;
  }
}A[250050];
bool cmp(stone a,stone b){
  return a.r<b.r;
}
int L[505];
int R[505];
int maxx[505];
int v[250050];
int main(){
  scanf("%d%d%d%lld%d",&x0,&Y0,&pl,&rl,&N);
  A[0].r=0;
  A[0].cr=rl*rl;
  A[0].cp=pl;
  A[0].m=-1;
  for(int i=1;i<=N;++i){
    int x,y,m,p;
    long long r;
    scanf("%d%d%d%d%lld",&x,&y,&m,&p,&r);
    A[i].r=(long long)(x-x0)*(x-x0)+(long long)(y-Y0)*(y-Y0);
    A[i].m=m;
    A[i].cr=r*r;
    A[i].cp=p;
  }
  sort(A+1,A+1+N);
  int t =sqrt(N);
  for(int i=1;i<=t;++i){
    L[i]=(i-1)*(N/t)+1;
    R[i]=i*(N/t);
    maxx[i]=A[R[i]].m;
  }
  if(R[t]<N) t++,L[t]=R[t-1]+1,R[t]=N,maxx[t]=A[N].m;

  for(int i=1;i<=t;++i){
    sort(A+L[i],A+R[i]+1,cmp);
  }

  int ans=0;
  queue<stone> q;
  q.push(A[0]);
  v[0]=1;
  while(q.size()){
    stone S = q.front();
    q.pop();
    for(int i=1;i<=t;++i){
      if(maxx[i]<=S.cp){
        while(L[i]<=R[i] && A[L[i]].r<=S.cr){
          if (!v[L[i]]){
            q.push(A[L[i]]);
            v[L[i]]=1;
            ans++;
          }
         L[i]++;
        }
      }
      else {
        for(int j = L[i];j<=R[i];++j){
          if(!v[j] && A[j].m<=S.cp && A[j].r<=S.cr){
            q.push(A[j]);
            v[j]=1;
            ans++;
          }
        }
        break;
      }
    }
  }
  printf("%d\n",ans);
  return 0;
}

小Z的袜子

莫队离线处理,将询问区间排序、分块,由已经求出的区间推至相邻的区间。

#include <bits/stdc++.h>
using namespace std;

struct query {
  int l, r, id, pos;
  long long ans, base;
  bool operator<(const query& a) { return l < a.l; }
} Q[50005];
int L[50005];
int R[50005];
int num[50005];

int N, M;
int C[50005];
bool cmp(query a, query b) {
  if (a.pos == b.pos) {
    return a.r < b.r;
  } else
    return a.pos < b.pos;
}
bool cmp2(query a, query b) { return a.id < b.id; }

int main() {
  scanf("%d%d", &N, &M);
  for (int i = 1; i <= N; ++i) {
    scanf("%d", &C[i]);
  }
  int t = sqrt(N);
  int T = 0;
  for (int i = 1; i <= M; ++i) {
    int il, ir;
    scanf("%d%d", &il, &ir);
    Q[i].l = il, Q[i].r = ir;
    Q[i].id = i;
    Q[i].pos = il / t + 1;
    T = max(T, Q[i].pos);
  }
  sort(Q + 1, Q + 1 + M, cmp);

  int p = 0;
  for (int i = 1; i <= M; ++i) {
    if (Q[i].pos != p) {
      L[++p] = i;
      if (p > 0) R[p - 1] = i - 1;
    }
  }
  R[p] = M;

  long long temp, bans;
  for (int i = 1; i <= T; ++i) {
    memset(num, 0, sizeof(num));

    int first = L[i];

    int l = Q[first].l, r = Q[first].r;

    for (int j = l; j <= r; ++j) {
      Q[first].ans -= (long long)num[C[j]] * (num[C[j]] - 1) / 2;
      num[C[j]]++;
      Q[first].ans += (long long)num[C[j]] * (num[C[j]] - 1) / 2;
    }

    temp = (long long)(r - l + 1) * (r - l) / 2;
    bans = Q[first].ans;

    if (Q[first].ans == 0) {
      Q[first].base = 1;
    } else if (bans > temp) {
      Q[first].base = 1, Q[first].ans = 1;
    } else {
      Q[first].ans = bans / __gcd(bans, temp);
      Q[first].base = temp / __gcd(bans, temp);
    }

    for (int j = L[i] + 1; j <= R[i]; ++j) {
      int l = Q[j].l, r = Q[j].r;

      Q[j].ans = bans;
      if (Q[j - 1].l > l) {
        for (int k = l; k < Q[j - 1].l; ++k) {
          Q[j].ans -= (long long)num[C[k]] * (num[C[k]] - 1) / 2;
          num[C[k]]++;
          Q[j].ans += (long long)num[C[k]] * (num[C[k]] - 1) / 2;
        }
      } else if (Q[j - 1].l < l) {
        for (int k = Q[j - 1].l; k < l; ++k) {
          Q[j].ans -= (long long)num[C[k]] * (num[C[k]] - 1) / 2;
          num[C[k]]--;
          Q[j].ans += (long long)num[C[k]] * (num[C[k]] - 1) / 2;
        }
      }
      for (int k = Q[j - 1].r + 1; k <= r; ++k) {
        Q[j].ans -= (long long)num[C[k]] * (num[C[k]] - 1) / 2;
        num[C[k]]++;
        Q[j].ans += (long long)num[C[k]] * (num[C[k]] - 1) / 2;
      }

      temp = (long long)(r - l + 1) * (r - l) / 2;
      bans = Q[j].ans;
      if (Q[j].ans == 0) {
        Q[j].base = 1;
      } else if (bans > temp) {
        Q[j].ans = Q[j].base = 1;
      } else {
        Q[j].ans = bans / __gcd(bans, temp);
        Q[j].base = temp / __gcd(bans, temp);
      }
    }
  }
  sort(Q + 1, Q + 1 + M, cmp2);
  for (int i = 1; i <= M; ++i) {
    printf("%lld/%lld\n", Q[i].ans, Q[i].base);
  }
  return 0;
}

3.学习了点分治,也就是树上的分治,相比于线性数组里的序列[L,R],树对应的是两点之间的路径,线性序列二分对应于找树的重心。此题在递归求解时,当前层的需求是得到两点路径经过树根p的情况,考虑到会遍历整棵树,两点在同一棵p的子树(不经过p)的情况也会被包括,但是路径长度却算上了子树树根到父结点p的距离,要减掉这种情况(容斥)

#include<bits/stdc++.h>
using namespace std;

const int maxn  = 40000+100;
struct edge{
  int to,w;
};

int N,K;
int vis[maxn];
int max_part[maxn];
int _size[maxn];
int d[maxn];
int b[maxn];
int len[maxn];
int root;
int tot_node;
int ans;
vector<edge> E[maxn*2];

void addEdge(int x,int y,int z){
  E[x].push_back(edge{y,z});
}

void getRoot(int u,int fa){
  max_part[u] = 0;
  _size[u]=1;

  for(int i = 0;i<E[u].size();++i){
    int v =E[u][i].to;
    if(vis[v]|| v ==fa) continue;
    getRoot(v,u);
    _size[u] += _size[v];
    max_part[u]=max(max_part[u],_size[v]); 
  }
  max_part[u] = max(max_part[u],tot_node - _size[u]);
  if (max_part[u] < max_part[root]){
      root =u;
  }
}

void getDis(int u,int fa){
  len[++len[0]] = d[u];
  for(int i=0;i<E[u].size();++i){
    int v = E[u][i].to;
    if(vis[v] || v == fa ) continue;
    d[v] = d[u]+E[u][i].w;
    getDis(v,u);
  }
}

int cal(int u,int now){
  d[u] = now , len[0]=0;
  getDis(u,0);
  sort(len+1,len+len[0]+1);
  int all = 0;
  for(int l=1,r=len[0];l<r;){
    if(len[l]+len[r]<=K){
      all+=r-l;
      ++l;
    }
    else r--;
  }
  return all;
}

void solve(int u){
  vis[u] = true;
  ans +=cal(u,0);
  for(int i=0;i<E[u].size();++i){
    int v = E[u][i].to;
    if(vis[v] ) continue;
    ans -= cal(v, E[u][i].w);
    tot_node = _size[v];
    root =0;
    getRoot(v,u);
    solve(root);
  }
}

int main(){
  while(~scanf("%d%d",&N,&K) && N && K){
    for(int i=1;i<=N;++i){
      E[i].clear();
    }
    ans = 0;
    memset(vis,0,sizeof(vis));

    for(int i=1;i<N;++i){
      int x,y,z;
      scanf("%d%d%d",&x,&y,&z);
      addEdge(x+1,y+1,z);
      addEdge(y+1,x+1,z);
    }
    tot_node = N;
    max_part[0]=N;
    root = 0;
    getRoot(1,0);
    solve(root);
    printf("%d\n",ans);
  }
  return 0;
}

KickStart 2018 Round D

第一题滑动窗口+multiset的运用
第二题将两个不等式条件转化为两个点的位置关系(一个点在另一个点的右上方),这个转化像整体换元,感觉很巧妙...然后贪心。
第三题四维dp+前缀和处理,参考了【Kickstart】2018 Round D - Funniest Word Search
以下是第三题的代码,值得保存下来复习。

——————————
好难……
——————————

Funniest Word Search

#include<bits/stdc++.h>

using namespace std;

const int SIZE = 105;
int R,C,W;
char in [SIZE][SIZE];
int sumr[SIZE][SIZE][SIZE];
int sumc[SIZE][SIZE][SIZE];
int f[SIZE][SIZE][SIZE][SIZE];
int vr[SIZE][SIZE][SIZE];
int vc[SIZE][SIZE][SIZE];

typedef unordered_multiset<string> DICT;
unordered_map<int,DICT> word;

int  value,_size,cnt;
void check(int i1,int j1,int i2,int j2){
    int  s=i2-i1+j2-j1+2;
    int  v=f[i1][j1][i2][j2];
    if((long long)v*_size>=(long long) value*s){
      if((long long) v*_size==(long long)value*s) cnt++;
      else{
        cnt=1;
        value=v;
        _size=s;
        int divisor=__gcd(value,_size);
        value/=divisor,_size/=divisor;
      }
    }

}

void solve (){

    for(int i=1;i<=R;++i){
      for(int j=1;j<=C;++j){
        string val="";
        for(int k=1;k<=j;++k){
            vr[i][j][k]=vr[i][j][k-1];
            val+=in[i][j-k+1-1];
            vr[i][j][k]+=word[k].count(val)*k;

        }

        string val2="";
        for(int k=1;k<=i;++k){
          vc[i][j][k]=vc[i][j][k-1];
          val2+=in[i-k+1][j-1];
          vc[i][j][k]+=word[k].count(val2)*k;
        }
      }
    }

    for(int i=1;i<=R;++i){
      for(int j=1;j<=C;++j){
        for(int k=1;k<=j;++k){
          sumr[i][j][k]=sumr[i-1][j][k]+vr[i][j][k];
        }

        for(int k=1;k<=i;++k){
          sumc[i][j][k]=sumc[i-1][j][k-1]+vc[i][j][k];
        }

      }
    }

    for(int i1=1;i1<=R;++i1){
      for(int j1=1;j1<=C;++j1){
        for(int i2=i1;i2<=R;++i2){
          for(int j2=j1;j2<=C;++j2){
              if(j2==j1){
                f[i1][j1][i2][j2]=f[i1][j1][i2-1][j2]+vr[i2][j2][1]+vc[i2][j2][i2-i1+1];
                check(i1,j1,i2,j2);
              }
              else{
                f[i1][j1][i2][j2]=f[i1][j1][i2][j2-1]+sumr[i2][j2][j2-j1+1]-sumr[i1-1][j2][j2-j1+1]+sumc[i2][j2][i2-i1+1];
                check(i1,j1,i2,j2);
              }
          }
        }
      }
    }
}

int main(){
    int T,kase=0;
    scanf("%d",&T);
    while(T--){
      _size=1,value=0,cnt=0;
      word.clear();
      scanf("%d%d%d",&R,&C,&W);
      for(int i=1;i<=R;++i){
        scanf("%s",in[i]);

      }
      for(int i=1;i<=W;++i){
        string tmp;
        cin>>tmp;
        int len = tmp.length();
        word[len].insert(tmp);
        reverse(tmp.begin(),tmp.end());
        word[len].insert(tmp);
      }

      solve();
      printf("Case #%d: %d/%d %d\n",++kase, value, _size , cnt );
    }
    return 0;
}

Transformation HDU – 4578 (延迟标记)

对延迟标记要有深入的理解。。。多个标记同时存在时要考虑顺序

参考:http://www.cfzhao.com/2019/04/03/hdu-4578-transformation/

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int SIZE = 100005;
const int MOD = 10007;
int n, q;

struct SegmentTree {
  int l, r;
  int sum,sum2,sum3;
  int lazy_add,lazy_mul,lazy_assign;
 #define l(x) tree[x].l
 #define r(x) tree[x].r
 #define sum(x) tree[x].sum
 #define sum2(x) tree[x].sum2
 #define sum3(x) tree[x].sum3
 #define lazy_add(x) tree[x].lazy_add
 #define lazy_mul(x) tree[x].lazy_mul
 #define lazy_assign(x) tree[x].lazy_assign
} tree[SIZE * 4];

void pushup(int p){
  sum(p)=(sum(p<<1|1)+sum(p<<1))%MOD;
  sum2(p)=(sum2(p<<1|1)+sum2(p<<1))%MOD;
  sum3(p)=(sum3(p<<1|1)+sum3(p<<1))%MOD;
}

void spread(int p){
  if(lazy_assign(p)){
    int s1=lazy_assign(p)%MOD,s2=s1*lazy_assign(p)%MOD,s3=s2*lazy_assign(p)%MOD;
    sum(p<<1|1)=s1*(r(p<<1|1)-l(p<<1|1)+1)%MOD;
    sum(p<<1)=s1*(r(p<<1)-l(p<<1)+1)%MOD;
    sum2(p<<1|1)=s2*(r(p<<1|1)-l(p<<1|1)+1)%MOD;
    sum2(p<<1)=s2*(r(p<<1)-l(p<<1)+1)%MOD;
    sum3(p<<1|1)=s3*(r(p<<1|1)-l(p<<1|1)+1)%MOD;
    sum3(p<<1)=s3*(r(p<<1)-l(p<<1)+1)%MOD;
    lazy_assign(p<<1|1)=lazy_assign(p<<1)=lazy_assign(p);
    lazy_add(p<<1|1)=lazy_add(p<<1)=0;
    lazy_mul(p<<1|1)=lazy_mul(p<<1)=1;
    lazy_assign(p)=0; 
  }
  if(lazy_mul(p)!=1){
    int s1=lazy_mul(p)%MOD,s2=s1*lazy_mul(p)%MOD,s3=s2*lazy_mul(p)%MOD;
    sum(p<<1|1)=sum(p<<1|1)*s1%MOD;
    sum(p<<1)=sum(p<<1)*s1%MOD;
    sum2(p<<1|1)=sum2(p<<1|1)*s2%MOD;
    sum2(p<<1)=sum2(p<<1)*s2%MOD;
    sum3(p<<1|1)=sum3(p<<1|1)*s3%MOD;
    sum3(p<<1)=sum3(p<<1)*s3%MOD;
    lazy_mul(p<<1|1)=lazy_mul(p<<1|1)*lazy_mul(p)%MOD;
    lazy_mul(p<<1)=lazy_mul(p<<1)*lazy_mul(p)%MOD;
    lazy_add(p<<1|1)=lazy_add(p<<1|1)*lazy_mul(p)%MOD;
    lazy_add(p<<1)=lazy_add(p<<1)*lazy_mul(p)%MOD;
    lazy_mul(p)=1;
  }
  if(lazy_add(p)!=0){
    int s1=lazy_add(p)%MOD,s2=s1*lazy_add(p)%MOD,s3=s2*lazy_add(p)%MOD;
    sum3(p<<1|1)=(sum3(p<<1|1)+3*s1%MOD*sum2(p<<1|1)%MOD+3*s2%MOD*sum(p<<1|1)%MOD+s3*(r(p<<1|1)-l(p<<1|1)+1)%MOD)%MOD;
    sum3(p<<1)=(sum3(p<<1)+3*s1%MOD*sum2(p<<1)%MOD+3*s2%MOD*sum(p<<1)%MOD+s3*(r(p<<1)-l(p<<1)+1)%MOD)%MOD;
    sum2(p<<1|1)=(sum2(p<<1|1)+2*s1%MOD*sum(p<<1|1)%MOD+s2*(r(p<<1|1)-l(p<<1|1)+1)%MOD)%MOD;
    sum2(p<<1)=(sum2(p<<1)+2*s1%MOD*sum(p<<1)%MOD+s2*(r(p<<1)-l(p<<1)+1)%MOD)%MOD;
    sum(p<<1|1)=sum(p<<1|1)+lazy_add(p)*(r(p<<1|1)-l(p<<1|1)+1)%MOD;
    sum(p<<1)=sum(p<<1)+lazy_add(p)*(r(p<<1)-l(p<<1)+1)%MOD;
    lazy_add(p<<1|1)=(lazy_add(p<<1|1)+lazy_add(p))%MOD;
    lazy_add(p<<1)=(lazy_add(p<<1)+lazy_add(p))%MOD;
    lazy_add(p)=0;
  }

}

void build(int p, int l, int r) {
  l(p) = l, r(p) = r;
  lazy_add(p)=0,lazy_assign(p)=0,lazy_mul(p)=1;
  if (l == r) {
    sum(p)=sum2(p)=sum3(p)=0;
    return ;
  }
  int mid = (l + r) >>1;
  build(p<<1, l, mid);
  build(p <<1 | 1, mid + 1, r);
  pushup(p);
}

void change(int p, int L,int R, int c,int d) {
  if(L<=l(p) && r(p)<=R){
    ll s1=d%MOD,s2=s1*d%MOD,s3=s2*d%MOD;
    if(c==1){
     sum3(p)=(sum3(p)+3*s1%MOD*sum2(p)%MOD+3*s2%MOD*sum(p)%MOD+s3*(r(p)-l(p)+1)%MOD)%MOD;
     sum2(p)=(sum2(p)+2*s1%MOD*sum(p)%MOD+s2*(r(p)-l(p)+1)%MOD)%MOD;
     sum(p)=(sum(p)+s1*(r(p)-l(p)+1)%MOD)%MOD;
     lazy_add(p)=(lazy_add(p)+d)%MOD;
    }
    if(c==2){
      sum(p)=s1*sum(p)%MOD;
      sum2(p)=s2*sum2(p)%MOD;
      sum3(p)=s3*sum3(p)%MOD;
      lazy_mul(p)=lazy_mul(p)*d%MOD;
      lazy_add(p)=lazy_add(p)*d%MOD;
    }
    if(c==3){
      sum(p)=s1*(r(p)-l(p)+1)%MOD;
      sum2(p)=s2*(r(p)-l(p)+1)%MOD;
      sum3(p)=s3*(r(p)-l(p)+1)%MOD;
      lazy_assign(p)=d;
      lazy_add(p)=0;
      lazy_mul(p)=1;
    }
    return;
  } 
  spread(p);
  int mid=(l(p)+r(p))>>1;
  if(L<=mid) change(p<<1,L,R,c,d);
  if(R>mid) change(p<<1|1,L,R,c,d);
  pushup(p);
} 

int ask(int p,int l,int r,int c){
    if(l<=l(p) && r(p)<=r){
      if(c==1) return sum(p);
      if(c==2) return sum2(p);
      if(c==3) return sum3(p);
    }
    spread(p);
    int mid=(l(p)+r(p))>>1;
    int val=0;
    if(l<=mid)  val+=ask(p<<1,l,r,c);
    if(r>mid)  val+=ask(p<<1|1,l,r,c);
    return val%MOD;
} 

int main() {
  int T,kase=0;
  while(~scanf("%d%d",&n,&q)&&n&&q){
    build(1,1,n);
    while(q--){
      int a,x,y,c;
      scanf("%d%d%d%d",&a,&x,&y,&c);
      if(a!=4) change(1,x,y,a,c);
      else{
        printf("%d\n",ask(1,x,y,c));
      }
    }

  }
  return 0;
}

Kick Start 2018 Round B B题

Sherlock and the Bit Strings

构造一个长度为N的只有‘0’和‘1’的串s,满足K个限制(s[A,B]中含有C个1),且这个串在所有满足限制的合法串当中为字典序第P大.

状压dp,f[i][j]:假设前i个字符已固定,且这前i个中最后16个字符为j时的合法方案数(注意j前面的到底是什么我们不用管,看作前缀是固定的,这个结果统计的是前缀之后的部分可以有多少种变化)。我们从后往前转移,最终得到每个位置的情况。如何转移看代码就很清楚了,再次感到熟练位操作对做状压方面的题目很重要。

官方题解开头就讲到固定前缀的合法方案数与字典序第p大的关系,一开始没理解...就是如果串是i开头的话(我们以字典序的顺序来尝试i),f[1][i]>=p,那么第p大就一定是在这f[1][i]方案中了,否则从P中减掉f[1][i](f[1][i]的方案里都是些比P小的,开头字典序比i大时的方案里第P-f[1][i]大的,就是原来所有方案里第P大的),i再转向下一个字典序更大的选择。然后可以一个一个位置构造出这个串。

#include<bits/stdc++.h>
using namespace std;

long long f[105][1<<16];
vector <pair<int,int> > limits[105];
int cnt[1<<16];
int shl[1<<16];

bool check(int i,int last){
    for(int j=0;j<limits[i].size();++j){
        if(cnt[((1<<limits[i][j].first)-1)&last]!=limits[i][j].second){
            return false;
        }
    }
    return true;
}

int main(){
    int T,kase=0;
    scanf("%d",&T);
    for(int i=1;i<(1<<16);++i){
        cnt[i]=cnt[i>>1]+(i&1);
        shl[i]=(i<<1)&((1<<16)-1);
    }
    while(T--){
        int n,k;
        long long p;
        scanf("%d%d%lld",&n,&k,&p);
        for(int i=1;i<=n;++i) limits[i].clear();
        for(int i=1;i<=k;++i){
            int A,B,C;
            scanf("%d%d%d",&A,&B,&C);
            limits[B].push_back(make_pair(B-A+1,C));
        }
        for(int i=0;i<(1<<16);++i){
            if(check(n,i)){
                f[n][i]=1;
            }
            else f[n][i]=0;
        }
        for(int i=n-1;i>0;--i){
            for(int j=0;j<(1<<16);++j){
                if(check(i,j)){
                    f[i][j]=f[i+1][shl[j]]+f[i+1][shl[j]^1];
                    if(f[i][j]>1e18) f[i][j]=1e18+1;
                }
                else f[i][j]=0;
            }
        }

        printf("Case #%d: ",++kase);
        for(int i=1,j=0;i<=n;++i,j=shl[j]){
            if(f[i][j]>=p){
                printf("0");
            }
            else{
                p-=f[i][j];
                j^=1;
                printf("1");
            }
        }
        printf("\n");

    }
    return 0;
}

SGU385 Highlander

题目来源:SGU 385
图片来自国家集训队论文《浅析竞赛中一类数学期望问题的解决方法》

其中min(j,i-j+1) 更改为min(j-1,i-j)貌似更合适。

#include<bits/stdc++.h>

using namespace std;

double d[105];
double fac[105];
double f[105][105][105];
double g[105][105];

double A(int i,int j){
    return fac[i]/fac[i-j];
}

int main(){
    int n;
    scanf("%d",&n);

    fac[0]=1;
    for(int i=1;i<=n;++i){
        fac[i]=i*fac[i-1];
    }

    d[1]=0,d[2]=1;
    for(int i=3;i<=n;++i){
        d[i]=(i-1)*(d[i-1]+d[i-2]);
    }

    for(int i=2;i<=n;++i){
        for(int j=2;j<i;++j){
            for(int l=2;l<=min(j-1,i-j);l++){
                f[i][j][1]+=g[i-j][l];
            }
            f[i][j][1]*=A(n-i+j,j)/j;
            g[i][j]+=f[i][j][1];
            for(int k=2;k<=i/j;k++){
                f[i][j][k]=f[i-j][j][k-1]*A(n-i+j,j)/j/k;
                g[i][j]+=f[i][j][k];
            }
        }
        f[i][i][1]=A(n,i)/i;
        g[i][i]+=f[i][i][1];
    }

    double res=0;
    for(int j=2;j<=n;++j){
        for(int k=1;k<=n;++k){
            res+=f[n][j][k]*j*k;
        }
    }
    printf("%.10f\n",res/d[n]);

    return 0;
}

[NOI2005]聪聪与可可

聪聪与可可

在一个单位时间内,聪聪根据可可的位置,会先走出最短路中的下一步,然后被抓者可等概率随意走一步,也可原地不动。
在距离一步或者两步的时候,只要一个单位时间就可以抓到了,这是递归基。然后记忆化搜索解决之。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int INF=0x3f3f3f3f;
int ver[2010],edge[2010],Next[2010],head[2010];
int t[1005],v[1005];
int dis[1005][1005]; //i到j的最短路长度
int p[1005][1005]; //p[i][j]从i到j的最短路中,i第一步到达的地方
double f[1005][1005]; //f[i][j] 初始地点i和j,抓到时的期望步数
int N,tot;

void add(int x,int y,int z){
    ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
}

void shortest_path(int *d,int len,int s){
     memset(d,0x3f,len);
     memset(v,0,sizeof(v));
     d[s]=0;
     v[s]=1;
     queue<int> q;
     q.push(s);
     while(q.size()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i];
            if(!v[y]){
                v[y]=1;
                d[y]=d[x]+1;
                q.push(y);
            }
        }
     }
}

double solve(int i,int j){
    if(f[i][j]||i==j) return f[i][j];
    int fir=p[i][j],sec=p[fir][j];
    if(fir==j||sec==j) return f[i][j]=1;
    for(int k=head[j];k;k=Next[k]){
        f[i][j]+=solve(sec,ver[k]);
    }
    f[i][j]+=solve(sec,j);
    return f[i][j]=f[i][j]/(t[j]+1)+1;
}

int main(){
    //freopen("testdata.in","r",stdin);
    int E,C,M;
    scanf("%d%d%d%d",&N,&E,&C,&M);
    for(int i=0;i<E;++i){
        int t1,t2;
        scanf("%d%d",&t1,&t2);
        add(t1,t2,1);
        add(t2,t1,1);

    }

    for(int i=1;i<=N;++i){
        for(int j=1;j<=N;++j){
            dis[i][j]=INF;
        }
    }

    for(int i=1;i<=N;++i){
        shortest_path(dis[i],sizeof(dis[i]),i);
    }

    memset(p,0x3f,sizeof(p));
    for(int i=1;i<=N;++i){
        p[i][i]=i;
        for(int j=head[i];j;j=Next[j]){
            int y=ver[j];
            for(int k=1;k<=N;++k){
                if(dis[y][k]==dis[i][k]-1){
                    p[i][k]=min(p[i][k],y);
                }
            }
            t[i]++;
        }
    }

    printf("%.3lf\n",solve(C,M));

    return 0;
}

扫描线(POJ 1151)

在平面坐标系里给出一些矩形,求面积并.
Atlantis

#include<cstdio>
#include<map>
#include<algorithm>
#include<iostream>
using namespace std;

const int N=106;
int n,m,num=0;

struct P{
    double x,y,z;
    int k;
    bool operator<(const P w) const{
        return x<w.x;
    }
}a[N<<1];

double raw[N<<1];
map<double ,int > val ;

struct Tree{
    int l,r,cnt;
    double len;
}t[N<<3];

void build(int p,int l,int r){
    t[p].l=l;
    t[p].r=r;
    t[p].cnt=0;
    t[p].len=0;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}

void change(int p,int l,int r,int k){
    if(l<=t[p].l&&r>=t[p].r) t[p].len=((t[p].cnt+=k)>0?raw[t[p].r+1]-raw[t[p].l]:0);
    if(t[p].l==t[p].r) return;
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid) change(p<<1,l,r,k);
    if(r>mid) change(p<<1|1,l,r,k);
    t[p].len=(t[p].cnt>0?raw[t[p].r+1]-raw[t[p].l]:t[p<<1].len+t[p<<1|1].len);
}

void  Atlantis(){
    for(int i=1;i<=n;++i){
        int k=i<<1;
        double y,z; //竖直方向坐标
        scanf("%lf %lf %lf %lf",&a[k-1].x,&y,&a[k].x,&z);
        raw[k-1]=a[k-1].y=a[k].y=y;//矩形左边界
        raw[k]=a[k-1].z=a[k].z=z; //矩形右边界
        a[k-1].k=1;
        a[k].k=-1;
    }
    n<<=1;
    //离散化
    sort(raw+1,raw+n+1);
    int m=unique(raw+1,raw+n+1)-(raw+1);
    for(int i=1;i<=m;++i) val[raw[i]]=i;
    sort(a+1,a+n+1);
    build(1,1,m-1);
    double ans=0;
    for(int i=1;i<n;++i){
        int y=val[a[i].y],z=val[a[i].z]-1;  // y:[val[a[i].y], val[a[i].y]+1]  z: [val[a[i].z]-1, val[a[i].z]]
        change(1,y,z,a[i].k); //y~z: [val[a[i].y], val[a[i].z]
        ans+=t[1].len*(a[i+1].x-a[i].x); //t[1].len 整个扫描线覆盖的长度
    }
    printf("Test case #%d\nTotal explored area: %.2f\n\n", ++num, ans);
}

int main() {
    while (cin >> n && n) Atlantis();
    return 0;
}

线段树延迟标记 (POJ3468)

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int SIZE = 100010;

struct SegmentTree{
    int l,r;
    long long sum,add;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define sum(x) tree[x].sum
    #define add(x) tree[x].add
} tree[SIZE*4];

int a[SIZE],n,m;

void build(int p,int l,int r){
    l(p)=l,r(p)=r;
    if(l==r) { sum(p)=a[l];return; }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    sum(p)=sum(p*2)+sum(p*2+1);
}

void spread(int p){
    if(add(p)){
        sum(p*2)+=add(p)*(r(p*2)-l(p*2)+1);
        sum(p*2+1)+=add(p)*(r(p*2+1)-l(p*2+1)+1);
        add(p*2)+=add(p);
        add(p*2+1)+=add(p);
        add(p)=0;
    }
}

void change(int p,int l,int r,int d){
    if(l<=l(p) && r>=r(p)){
        sum(p)+=(long long) d*(r(p)-l(p)+1);
        add(p)+=d;
        return;
    }
    spread(p);
    int mid=(l(p)+r(p))/2;
    if(l<=mid) change(p*2,l,r,d);
    if(r>mid) change(p*2+1,l,r,d);
    sum(p)=sum(p*2)+sum(p*2+1);
}

long long ask(int p,int l,int r){
    if(l<=l(p) && r>=r(p)) return sum(p);
    spread(p);
    int mid=(l(p)+r(p))/2;
    long long val=0;
    if(l<=mid) val+=ask(p*2,l,r);
    if(r>mid) val+=ask(p*2+1,l,r);
    return val;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    while(m--){
        char op[2];
        int l,r,d;
        scanf("%s%d%d",op,&l,&r);
        if(op[0]=='C'){
            scanf("%d",&d);
            change(1,l,r,d);
        }
        else printf("%lld\n",ask(1,l,r));
    }
    return 0;
}

最大连续子段和

RT,线段树单点修改,区间查询.

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <utility>
using namespace std;
const int INF = 1e9;
const int maxn = 1e6;

#define SIZE 500000

int a[SIZE+1];
struct SegmentTree {
    int l,r;
    int dat,sum,lmax,rmax;
    SegmentTree() {
        l = r = sum = 0;
        lmax = rmax  =dat= -INF;
    }
} t[SIZE*4];

void build(int p,int l,int r) {
    t[p].l=l,t[p].r=r;
    if(l==r) {
        t[p].dat=t[p].lmax=t[p].rmax=t[p].sum=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    t[p].dat=max(max(t[p*2].dat,t[p*2+1].dat),t[p*2].rmax+t[p*2+1].lmax);
    t[p].lmax=max(t[p*2].lmax,t[p*2].sum+t[p*2+1].lmax);
    t[p].rmax=max(t[p*2+1].rmax,t[p*2+1].sum+t[p*2].rmax);
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
}

void change(int p,int x,int v) {
    if(t[p].l==t[p].r) {
        t[p].dat=t[p].lmax=t[p].rmax=t[p].sum=v;
        return;
    }
    int mid=(t[p].l+t[p].r)/2;
    if(x<=mid)
        change(p*2,x,v);
    else
        change(p*2+1,x,v);
    t[p].dat=max(max(t[p*2].dat,t[p*2+1].dat),t[p*2].rmax+t[p*2+1].lmax);
    t[p].lmax=max(t[p*2].lmax,t[p*2].sum+t[p*2+1].lmax);
    t[p].rmax=max(t[p*2+1].rmax,t[p*2+1].sum+t[p*2].rmax);
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
}

SegmentTree ask(int p,int l,int r) {
    if(l<=t[p].l&&r>=t[p].r) {
        return t[p];
    }
    SegmentTree res,a,b;
    int mid=(t[p].l+t[p].r)/2;
    if(l<=mid) {
        a=ask(p*2,l,r);
        res.sum+=a.sum;
    }
    if(r>mid) {
        b=ask(p*2+1,l,r);
        res.sum+=b.sum;
    }
    res.lmax=max(a.lmax,a.sum+b.lmax);
    res.rmax=max(b.rmax,b.sum+a.rmax);
    res.dat=max(max(a.dat,b.dat),a.rmax+b.lmax);
    return res;
}

int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; ++i) {
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    while(m--) {
        int k,x,y;
        scanf("%d%d%d",&k,&x,&y);
        if(k==1) {
            if(x>y)
                swap(x,y);
            printf("%d\n",ask(1,x,y).dat);
        } else {
            change(1,x,y);
        }
    }
    return 0;
}