L3HCTF 2021 Reverse 两道题解 (IDAAAAAA double-joy)

这波reverse全军覆没了属于是,最后1/7。。然后队友依然打到了rank3 orz orz

自己全场只看了两个题,最后0输出,麻了。

IDAAAAAA

这题tmd是个misc题吧

tag: 细节+脑洞

错误的分析方法:dump出来elf然后gdb调试

只给了idb,没有elf,直接打开发现是一个将输入解析为按照+号和-号分隔开的三个数字,比如输入-123+5+6,就会得到-123,5,6三个数字。然后这三个数字直接静态看的话必须满足5个约束条件:

image.png

但是直接在2^32的域上求解这5个方程是求不出解的,然后大家就都懵逼了,甚至开始尝试从中选三个出来解。但是这样即使把所有的情况都解出来也是错误的

正确的分析方法:看给的idb

这个idb其实一打开可以发现有一个断点,我当时脑子里大概有一秒钟疑惑了下为啥有个断点,然后就没管他。。然后就错过了

后面我直接用IDA连gdbserver调试的时候,会发现每次执行完scanf都会直接运行结束,当时以为是IDA抽风了。。没想到是故意的,但凡多想一下这个flag也到手了

然后进入正题,这个断点右键编辑,会发现里面的condition是有idapython脚本的(脚本很长,打开这个断点的时候IDA会卡一会儿):

image.png

撸出来之后:

global jIS40A
jIS40A = [...] # 一个长度1000的list,每个item是一堆bytes
N4QKUt = 0
EpUdLx = 4728923
idaapi.add_bpt(EpUdLx)
uwGgnM = idaapi.bpt_t()
idaapi.get_bpt(EpUdLx, uwGgnM)
uwGgnM.elang = "Python"
uwGgnM.condition = "N4QKUt = {}\n".format(N4QKUt) + 'VLzxDy = idaapi.get_byte(5127584 + N4QKUt)\nVLzxDy -= ord(\'a\')\nif VLzxDy == 0:\n    bYsMTa = 287\n    LjzrdT = b\'lqAT7pNI3BX\'\nelif VLzxDy == 1:\n    bYsMTa = 96\n    LjzrdT = b\'z3Uhis74aPq\'\nelif VLzxDy == 2:\n    bYsMTa = 8\n    LjzrdT = b\'9tjseMGBHR5\'\nelif VLzxDy == 3:\n    bYsMTa = 777\n    LjzrdT = b\'FhnvgMQjexH\'\nelif VLzxDy == 4:\n    bYsMTa = 496\n    LjzrdT = b\'SKnZ51f9WsE\'\nelif VLzxDy == 5:\n    bYsMTa = 822\n    LjzrdT = b\'gDJy104BSHW\'\nelif VLzxDy == 6:\n    bYsMTa = 914\n    LjzrdT = b\'PbRV4rSM7fd\'\nelif VLzxDy == 7:\n    bYsMTa = 550\n    LjzrdT = b\'WHPnoMTsbx3\'\nelif VLzxDy == 8:\n    bYsMTa = 273\n    LjzrdT = b\'mLx5hvlqufG\'\nelif VLzxDy == 9:\n    bYsMTa = 259\n    LjzrdT = b\'QvKgNmUFTnW\'\nelif VLzxDy == 10:\n    bYsMTa = 334\n    LjzrdT = b\'TCrHaitRfY1\'\nelif VLzxDy == 11:\n    bYsMTa = 966\n    LjzrdT = b\'m26IAvjq1zC\'\nelif VLzxDy == 12:\n    bYsMTa = 331\n    LjzrdT = b\'dQb2ufTZwLX\'\nelif VLzxDy == 13:\n    bYsMTa = 680\n    LjzrdT = b\'Y6Sr7znOeHL\'\nelif VLzxDy == 14:\n    bYsMTa = 374\n    LjzrdT = b\'hLFj1wl5A0U\'\nelif VLzxDy == 15:\n    bYsMTa = 717\n    LjzrdT = b\'H6W03R7TLFe\'\nelif VLzxDy == 16:\n    bYsMTa = 965\n    LjzrdT = b\'fphoJwDKsTv\'\nelif VLzxDy == 17:\n    bYsMTa = 952\n    LjzrdT = b\'CMF1Vk7NH4O\'\nelif VLzxDy == 18:\n    bYsMTa = 222\n    LjzrdT = b\'43PSbAlgLqj\'\nelse:\n    bYsMTa = -1\nif bYsMTa < 0:\n    cpu.rsp -= 8\n    cpu.rdi = 4927649\n    cpu.rax = 0\n    idaapi.patch_qword(cpu.rsp, 4202616)\n    idaapi.del_bpt(cpu.rip)\n    cpu.rip = 4263680\nelse:\n    zaqhdD = 0x486195\n    bYsMTa = jIS40A[bYsMTa]\n\n    idaapi.patch_bytes(5117568, bYsMTa)\n    idaapi.patch_bytes(5117488, LjzrdT)\n\n    cpu.rsp -= 8\n    idaapi.patch_qword(cpu.rsp, zaqhdD)\n    cpu.rdi = 5117568\n    cpu.rsi = len(bYsMTa)\n    cpu.rdx = 5117488\n    cpu.rcx = 11\n    cpu.r8 = 5117568\n    cpu.rax = 5117568\n\n    idaapi.add_bpt(zaqhdD)\n    jQfwUA = idaapi.bpt_t()\n    idaapi.get_bpt(zaqhdD, jQfwUA)\n    jQfwUA.elang = "Python"\n    jQfwUA.condition = "N4QKUt = {}\\nSdjOr3 = {}\\n".format(N4QKUt, len(bYsMTa)) + \'bYsMTa = idaapi.get_bytes(cpu.rax, SdjOr3).decode()\\nzaqhdD = 4767838\\nidaapi.add_bpt(zaqhdD)\\njQfwUA = idaapi.bpt_t()\\nidaapi.get_bpt(zaqhdD, jQfwUA)\\njQfwUA.elang = "Python"\\njQfwUA.condition = "N4QKUt = {}\\\\n".format(N4QKUt+1) + bYsMTa\\nidaapi.del_bpt(zaqhdD)\\nidaapi.add_bpt(jQfwUA)\\nidaapi.del_bpt(cpu.rip)\\ncpu.rsp -= 8\\nidaapi.patch_qword(cpu.rsp, zaqhdD)\\ncpu.rip = 4447160\\n\'\n    idaapi.del_bpt(zaqhdD)\n    idaapi.add_bpt(jQfwUA)\n    idaapi.del_bpt(cpu.rip)\n    cpu.rip = 4201909\n'
idaapi.del_bpt(EpUdLx)
idaapi.add_bpt(uwGgnM)
cpu.rsp -= 8
idaapi.patch_qword(cpu.rsp, EpUdLx)
cpu.rip = 4202096

不难发现是在这个脚本里面设置了新的断点,而且在新的断点里面加入了新的condition脚本,然后移动eip到一个能执行到断点的位置,我们condition里面的字节解析出来是:
继续阅读“L3HCTF 2021 Reverse 两道题解 (IDAAAAAA double-joy)”

Intel SGX: 基本概念

SGX是Intel实现的可信执行环境,主要面向服务器和桌面端,提供了内存加密(Memory Encryption)、访问控制(Access Control)、远程认证(Remote Attestation)、本地密封(Sealing)等功能。

0x00 Overview

关于应用程序代码与可信执行环境的基本关系:

  1. 每个application分为两部分:安全(可信)部分和不安全(不可信)的部分
  2. application启动后,会在受保护的可信内存中加载一块飞地(enclave)
  3. application通过把机密数据、代码放到enclave里来保证安全性
  4. enclave为application提供调用接口,当application调用enclave内的函数时,其内部的任何内存仅enclave自身可见
  5. enclave内存即使ring 0的攻击者也看不到,因为是CPU层面的保护。实际上在SGX的安全模型里OS、BIOS等等都可以被认为是不可信的

关于可信执行环境与用户进程的关系:

  1. application 本身包括了自身的代码、数据和enclave
  2. enclave里面也有其自身的代码、数据
  3. SGX保证enclave里面的代码和数据的integrity和confidentiality
  4. enclave的entry points在编译期就确定了
  5. enclave可以访问它所在的application里的内存,但是反过来不行
  6. 支持多线程


继续阅读“Intel SGX: 基本概念”

rCore-OS Lab2: Batch Processing and Privileges

In lab 1, we have made our code work on a bare-metal computer (simulated by QEMU) successfully. However, it can do nothing but print some strings we hardcoded in the program on the terminal. Of course you can make it more complicated, such as factoring a large number, calculating the inverse of a matrix, etc. That’s cool but there are two significant drawbacks of this approach:

  1. The CPU runs a single program each time. Since the computing resources are precious(especially in the old time when you don’t have a modern OS), users who have many programs to run have to wait in front of the computer and manually load&start the next program after the previous one finished.
  2. Nobody wants to write the SBI and assembly level stuff every time, and it’s a duplication of efforts.

In order to solve these problems, people invented the Simple Batch Processing System, which can load a batch of application programs and automatically execute them one by one. Besides, the Batch Processing System will provide some “library” code such as console output functions which may be reused by many programs.

A new problem arises when we use the batch process system: error handling. The user’s program may (often) run into errors, unconsciously or intentionally. We do not want the error of any program to affect others or the system, so the system should be able to handle these errors and terminate the programs when necessary. To achieve this goal we introduced the Privileges mechanism and isolate user’s code from the system, which we will refer to as user mode and kernel mode. Note that this mechanism requires some support from hardware, and we will illustrate that with code in the following parts.

0x00 Privileges mechanism

The underlying reason for implementing the privileges mechanism is the system cannot trust any submitted program. Any errors or attacks could happen and may corrupt the system. We have to restrict users’ programs in an isolated “harmless” environment, where they have no access to 1) arbitrary memory or 2) any over-powerful instructions which may break the computer. In this lab, we mainly focus on the last point.

Prohibiting users’ program from using privileged instructions need the help from CPU. In riscv64, 4 levels of privileges are designed:

Level Encode Name
0 00 U, User/Application
1 01 S, Supervisor
2 10 H, Hypervisor
3 11 M, Machine

All modes, except Machine, have to go through binary interfaces provided by higher levels to control the hardware. The privileges level and their relation in our scenario are shown in the following figure:

The binary interfaces between User mode and Supervisor mode are named Application Binary Interface (ABI), or another more famous one: syscall.
继续阅读“rCore-OS Lab2: Batch Processing and Privileges”

公式识别Web端更新 21.11.09

声明: 由于经济原因本人已无力继续维护此服务,有愿意接手的人可以点击本行与我联系,谢谢

最近有一些同学反映他们需要大量使用识别工具,但由于种种原因不想或者不能在自己电脑上装客户端,希望能将第三方API集成到Web端。

这个功能我很早就有意识到有需求,但是我还是比较想让大家用MathpixCsharp,因为Web端不支持快捷键,而我个人认为快捷键对于生产力来说非常重要,没有的话体验会很差。但是由于最近我女朋友换了Mac电脑,我意识到有很多MacOS的同学目前是没有办法用MathpixCsharp的,所以我就打算先把这个功能加到Web端,满足更多平台同学的需求。

昨晚抽空先糊了一个勉强能用的界面提供了这项功能,使用示例参考下图:

payLatex.gif

基本的使用方式跟原来的免费接口是一样的,使用截图工具将要识别的公式截取之后在Web页面粘贴即可。可以参考原版的介绍文章

新增的付费接口的使用方法

  1. 这个网站购买卡密
  2. 在网页中点选 第三方付费接口
  3. 将得到的卡密中的APP_IDAPP_KEY分别填入网页中提示填写的两个文本框内
  4. 然后截图+粘贴使用即可

其中Uses会显示当前卡密的剩余使用次数。

有任何疑问都可以仔细阅读MathpixCsharp的介绍:http://blog.itewqq.cn/mathpixcsharp-opensource-windows-client/ 和免费版Web app的介绍http://blog.itewqq.cn/image-to-latex-convert-app/

新的版本是临时糊出来的,比较粗糙,有各种问题、意见、建议都欢迎大家到github提issues:https://github.com/itewqq/MathF/issues

另:由于我的前端优化和审美UI设计能力几乎为0,所以如果您对于前端界面有自己的想法,也可以直接修改代码( https://github.com/itewqq/MathF/blob/master/index.html ),欢迎PR!

rCore-OS Lab1: A Trilobite OS

Well I admit that I am too lazy to transfer this article back to Chinese.

I am going to practice my operating system skills by learning through the rCore-OS of THU, which is a pretty OS written in Rust. It is Linux compatible and its target platform is RISC-V. In this article, we will build a very naive but bare metal program.

0x00 Get rid of standard library dependencies

This is the first challenge for any software developer start moving to system development: You can not rely on ANY standard libraries (glibc, uclibc, klibc or any other implementations), since the OS itself is the one responsible for providing these libs. Let’s try to get rid of them.

In Rust and C/C++ (and almost all programming languages), before running into main(), the execution environment will do some initialization work, where the std library and other standard libraries (GNU libc) may be used. Thus we have to tell Cargo there is no main and std in our target.

// os/src/main.rs
#![no_std]
#![no_main]

And we need to explicitly write a _start() function, which is the entry Cargo is looking for.

// os/src/main.rs
#[no_mangle]
extern "C" fn _start() {
    // Nothing here now
}

Besides, Cargo requires us to provide panic_handler or it will not compile. Usually the std will take care of that but now we have to manually add a panic_handler.

// os/src/lang_items.rs
use core::panic::PanicInfo;

#[panic_handler]
fn panic(_info: &PanicInfo) -> ! {
    // Nothing here now
}

Note that the rust-core can be used (and very useful) on bare metal.

Next, we need to make it possible to run our program directly on CPU without any OS support.

0x01 Make the CPU run it

For an odinary program, running it is easy: All you have to do is type it’s name in a shell and hit Enter, or double-click the exe file in Windows. That ease is benefiting from the OS. As we are creating an OS, things can get a little more complicated. Let’s first think about what will happen when the CPU starts to working.

The bootloadr for QEMU can be found at: https://github.com/itewqq/rCore-dev/tree/main/bootloader

When the CPU (riscv64 emulated by QEMU in our case) is powered on, the other general registers of the CPU are cleared to zero, and the PC register will point to the 0x1000 location. This 0x1000 location is the first instruction executed after the CPU is powered up (a small piece of boot code solidified in the hardware), and it will quickly jump to 0x80000000, which is the first instruction of the BootLoader program – RustSBI. After the basic hardware initialization, RustSBI will jump to the operating system binary code memory location 0x80200000 (for QEMU) and execute the first instruction of the operating system. Then our written operating system starts to work.

About the SBI: SBI is an underlying specification for RISC-V. The relationship between the operating system kernel and RustSBI, which implements the SBI specification, is somewhat like the relationship between an application and the operating system kernel, with the latter providing certain services to the former. However, SBI provides few services and can help the OS kernel to perform limited functions, but these functions are very low-level and important, such as shutting down the computer, displaying strings, and so on. If RustSBI provides services, then the OS kernel can call them directly.

So it’s clear that we have to put our built OS at the 0x80200000 address (for QEMU). By default, Cargo adopts a usermode memory layout which is not we expected, for example we will not get a entry address at 0x80200000 in the generated binary. To address that we need a custom linker script to make every section’s location right:

OUTPUT_ARCH(riscv)
ENTRY(_start)
BASE_ADDRESS = 0x80200000;

SECTIONS
{
    . = BASE_ADDRESS;
    skernel = .;

    stext = .;
    .text : {
        *(.text.entry)
        *(.text .text.*)
    }

    . = ALIGN(4K);
    etext = .;
    srodata = .;
    .rodata : {
        *(.rodata .rodata.*)
        *(.srodata .srodata.*)
    }

    . = ALIGN(4K);
    erodata = .;
    sdata = .;
    .data : {
        *(.data .data.*)
        *(.sdata .sdata.*)
    }

    . = ALIGN(4K);
    edata = .;
    .bss : {
        *(.bss.stack)
        sbss = .;
        *(.bss .bss.*)
        *(.sbss .sbss.*)
    }

    . = ALIGN(4K);
    ebss = .;
    ekernel = .;

    /DISCARD/ : {
        *(.eh_frame)
    }
}

Then we force Cargo to use it in linking:

// os/.cargo/config
[build]
target = "riscv64gc-unknown-none-elf"

[target.riscv64gc-unknown-none-elf]
rustflags = [
    "-Clink-arg=-Tsrc/linker.ld", "-Cforce-frame-pointers=yes"
]

继续阅读“rCore-OS Lab1: A Trilobite OS”

MIPS PWN 入门

MIPS是一种采取精简指令集(RISC)的指令集架构,突出特点是高性能,广泛被使用在许多电子产品、网络设备、个人娱乐设备与商业设备上,在路由器领域也被广泛应用。虽然今年MIPS所属公司已经宣布放弃对该架构继续进行研发设计,但是其作为x86、arm之后的第三大CPU架构阵营,现在市面上仍有大量的MIPS架构的产品,尤其是路由器芯片。此外,MIPS在学术界也非常受到追捧,很多超算竞赛冠军的设计方案都是MIPS的。就目前来看,MIPS的安全研究还是相对较为有意义的。

MIPS架构基础知识

常用汇编与流水线操作 在MIPS PWN中所常用到的汇编指令如下表所示:

image.png

MIPS架构为精简指令集, 常见的MIPS芯片流水线操作为五级, 如下图

wiki-Fivestagespipeline.png

其中IF =指令提取,ID =指令解码,EX =执行,MEM =存储器访问,WB =寄存器写回. 垂直轴是连续的指令: 横轴是时间. 在图示的情况中,最早的指令处于WB阶段,而最新的指令正在进行指令提取. 对于跳转/分支指令, 当其到达执行阶段且新的程序计数器已经产生时, 紧随其后的下一条指令实际上已经开始执行了. MIPS 规定分支之后的指令总是在分支目标指令之前执行,紧随分支指令之后的位置称为 分支延迟槽. 在没有任何可用操作时,延迟槽将填充空指令(nop)占位. 例如下面这段MIPS汇编代码中,
“`move $a0, $s1“`会在“`jalr“`跳转前执行

.text:0007F944                 move    $t9, $s0
.text:0007F948                 jalr    $t9              
.text:0007F94C                 move    $a0, $s1

这个特性在我们查找gadgets和构造payload的时候要多注意, 这也是MIPS上的PWN相比x86架构来说较为特殊的点之一.

寄存器与调用约定 常用的MIPS寄存器作用如下:

  • “`\$a0“` – “`\$a3“`:函数调用时的参数传递,若参数超过 4 个,则多余的使用堆栈传递
  • “`\$t0“`-“`\$t7“`:临时寄存器
  • “`\$s0“` – “`\$s7“`:保存寄存器,使用时需将用到的寄存器保存到堆栈
  • “`\$gp“`:全局指针,用于取数据(32K访问内);“`\$sp“`:栈指针,指向栈顶
  • “`\$fp“`:栈帧指针;“`\$ra“`:存储返回地址

MIPS的调用约定为被调用者实现堆栈平衡, 参数 1 ~ 4 分别保存在
“`\$a0“` ~ “`\$a3“` 寄存器中,剩下的参数从右往左依次入栈. MIPS的栈布局如下图所示, 某寄存器在堆栈中的位置不是确定的, 例如“`\$ra“`在某函数栈中的偏移是“`\$sp“`+N, 而在另一函数栈中的偏移是“`\$sp“`+M.

image.png

当CPU执行跳转到被调用函数后, 被调用函数将会开辟新的栈帧, 根据本函数内是否还有其他函数调用决定是否将
“`\$ra“` 入栈, 再将“`\$sp“` 入栈. 对于“`\$ra“`, 当本函数为叶子函数(函数内无其他函数调用), 则“`\$ra“`不入栈, 否则将“`\$ra“`入栈. 对于栈溢出攻击而言, 当函数为非叶子函数时, 可以直接通过覆盖栈上的“`\$ra“`来劫持控制流.

缓存非一致性
继续阅读“MIPS PWN 入门”

任意模数的K次剩余 /HDU 3930 Broot/BZOJ 2219 数论之神/51nod 1123 X^A mod B

前言

难以置信, 遇到这个问题竟然是因为做一道CTF Reverse的题, 实际上我以前打ACM的时候都没有写过任意模数的K次剩余这种东西. 最简单的模质数的K次剩余的例题是
“`HDU 3930 Broot“`, 进阶版本(模任意奇数的K次剩余)的例题是“`BZOJ 2219 数论之神“`, 而终极版本(任意模数的K次剩余)似乎可以交的题只有“`51nod 1123“`, 截至本文写作时只有44个AC. 然而这个CTF题本身就有50多个通过了. ~~CTF>ACM 实锤~~ (暴论)

其实是因为这个Reverse的题里面幂指数是质数,所以会跟模数互质,然后就可以用RSA的方法来做了. 其次该题目更多的工作在于去花指令混淆上, 而非算法破解.

OK那么就来看一下这个问题从最简单的版本到终极版本怎么求解吧…

模质数的K次剩余

已知$a$, $b$, $p$, 求使得

$$
x^{a} \equiv b \quad(\bmod \ p)
$$

成立的所有 $x$. 其中 $p$ 是质数.

由于 $p$ 是质数, 所以 $p$ 存在原根 $g$ , 此时对于模 $p$ 意义下的任意数 $w$ ($0\le w \le p-1$) 存在唯一的 $i$ ($0\le i \le p-1$) 使得 $w\equiv g^i\quad(\bmod \ p)$.

由此可以将最终的答案用 $g$ 来表示: $x=g^{c}$, 带入上式转化为求解

$$
(g^{c})^{a}\equiv (g^{a})^c\equiv b \quad(\bmod \ p)
$$

此时 $g$, $a$, $b$, $p$, 已知, 只需要解出来 $c$. 此时相当于求解离散对数, 使用 Baby-Step-Giant-Step 可以在 $\mathcal{O}(\sqrt{p})$ 时间内得到一个特解 $x_0 \equiv g^{c} \quad(\bmod \ p)$.

在已知一个特解的情况下求出所有解是简单的, 由原根的性质可知 $g^{\varphi(p)}\equiv 1 \quad(\bmod \ p)$, 因此:

$$
\forall t \in \mathbb{Z}, x^{a} \equiv g^{c \cdot a+t \cdot \varphi(p)} \equiv b \quad(\bmod \ p)
$$

因此所有的解为:

$$
\forall t \in \mathbb{Z}, a \mid t \cdot \varphi(p), x \equiv g^{c+\frac{t \cdot \varphi(p)}{a}} \quad(\bmod p)
$$

上面幂次部分要能整除必须要有$\frac{a}{\operatorname{gcd}(a, \varphi(p))} \mid t$, 可以设 $t=\frac{a}{\operatorname{gcd}(a, \varphi(p))} \cdot i$, 于是得到所有的解为:

$$
\forall i \in \mathbb{Z}, x \equiv g^{c+\frac{\varphi(p)}{\operatorname{gcd}(a, \varphi(p))} \cdot i} \quad(\bmod p)
$$

HDU 3930 Broot 代码:

继续阅读“任意模数的K次剩余 /HDU 3930 Broot/BZOJ 2219 数论之神/51nod 1123 X^A mod B”

Codeforces Round #700 (Div. 2) 题解

链接 https://codeforces.com/contest/1480

闲着没事翻了翻以前的博客,感觉自己之前的文章质量太低了,尤其是很多题解东一篇西一篇的非常乱,以后类似题解之类的就整套整套地写好了。

image.png

Round 700 Div.2给人的感觉是手速场,基本上没有什么很需要思考的点。
继续阅读“Codeforces Round #700 (Div. 2) 题解”

逆向分析某X视频APP通信协议

声明:破解他人的软件是违法行为,本文的逆向工程仅供学习研究用途。

最近朋友间流行一个国产的X视频App,其特点是使用国内网络便可以自由地观看视频。但是支持国内网络环境的在线服务往往会承担被审查的风险,因此有点好奇他的视频存储和获取是怎么实现的,于是便对其APP客户端进行了逆向分析。本文出发点仅仅是技术学习,因此所有与该App有关的信息都将打码。在下文中将称该App为JK,其对应的几个关键api接口部分字符使用x替换。

  • 目标平台:Android
  • 分析对象:JK.apk,Version=3.13.2
  • 分析工具:Charles,Jadx,IDA Pro,Frida

TL;DR 最终对JK App的视频请求协议逆向分析结果如下图所示:


APP视频获取协议逆向结果

继续阅读“逆向分析某X视频APP通信协议”

[差分][前缀和][细节] codeforces 1452E Two Editorials

codeforces 1452E Two Editorials

题目链接:https://codeforces.com/problemset/problem/1452/E

题意:一次比赛中 2 个dalao来讲题,总共有 $m$ 个选手来听讲,题目总数为 $n$ ,编号从 $1$ 开始到 $n$ 。每个dalao都只会选择连续的 $k$ 个题目进行讲解,两个人可以交叉。而每一个听讲的人都只会选择听一个dalao的讲题,这是由哪个dalao讲的题目中覆盖的他感兴趣的题目数量较多决定的,第 $i$ 个人想听的题目范围是 $[l_i,r_i]$ . 问两个大佬怎么选可以使得两个人所获得的得分加一块最多,其中得分是他们讲的每个题目收听的人数。

数据范围:$1 \leq n, m \leq 2000,1 \leq k \leq n$, $1 \leq l_{i} \leq r_{i} \leq n$

输出:两个人采取某种讲题方案后加一块能获得的最大分数

题解:

把每个听讲的人看成一条线段,问题可以抽象成在数轴上找到两个长度为k的区间使得上述分数最大。从数据范围来看,可以 $O(n^2)$ 枚举两个人讲题的起点,之后如果能使用滑动窗口动态维护, $O(1)$ 更新答案这题就做完了。那么自然可以想到枚举第一个人讲题的范围之后,第二个人的范围在遍历的过程中动态维护。如果我们使用前缀和来做的话,是可以 O1 得到两个人各自的和的,但是题目要求两个人之间如果有均覆盖到的听讲者,那么只有覆盖的较多的讲题人才有得分。这是一个对每个听众来说取max的操作,但是我们要在数轴的维度来说要做到 O1 动态维护就是比较难的。我们假设第一个人对于自己内部的的得分和为sum1.第二个人的得分为sum2.先不考虑取max的情况,此时sum1和sum2都可以通过简单的积分前缀和得到。我们考虑把这个max操作转化成几个不同数组的差分和求和操作。简单的画一下第二个样例,就可以意识到当枚举到第一个人的讲课区间 [i,iend] 的时候,听众对应的线段可以分为三类:(1)在iend之前结束的;(2)在iend之后开始的;(3)在iend之前开始,在iend之后结束的。
继续阅读“[差分][前缀和][细节] codeforces 1452E Two Editorials”