树状数组

2014-11-01

介绍

所谓树状数组，就是将线性的数组预处理成树状的结构以降低时间复杂度。先来看一幅经典的图：

其中的 a 数组为原生数组，c 数组为辅助数组，计算方式为：

$$c_1=a_1——{(1)}_{10}={(1)}_2$$ $$c_2=a_2+c_1——{(2)}_{10}={(10)}_2$$ $$\ldots$$

不难发现，$c_k$存储的实际上是从 $k$ 开始向前数 $k$ 的二进制表示中右边第一个 $1$ 所代表的数字个元素的和。这样写的好处便是可以利用位运算轻松计算 sum。上代码。

Code

var
    n, i: longint;
    a, c: array [1..10000] of longint;

//计算x最右边的1所代表的数字。
//如：lowbit(0b1100)=0b100
function lowbit(x: longint): longint;
begin
    lowbit := x and (-x);
end;

//给a[index]加上x
procedure add(index, x: longint);
begin
    inc(a[index], x);
    while index<=n do
    begin
        inc(c[index], x);
        inc(index, lowbit(index));
    end;
end;

//求a[1~index]的和
function sum(index: longint): longint;
begin
    sum := 0;
    while index>0 do
    begin
        inc(sum, c[index]);
        dec(index, lowbit(index));
    end;
end;

var
    s: longint;
    op: longint;
    x,y: longint;

begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);

    readln(n);
    for i := 1 to n do
    begin
        read(a[i]);
        add(i, a[i]);
    end;

    while not eof do
    begin
        read(op);
        if op = 1 then //添加操作
        begin
           read(x, y);
           Add(x, y);
        end
        else           //求和操作
        begin
            read(s);
            writeln(sum(s));
        end;
    end;

    close(input); close(output);
end.

二进制的启示

2014-11-01

在学习数论时我们都知道：只用 2 的幂次可以组合出所有的正整数。这便是二进制的魅力——状态简单而又变化万千。

引子

实际算法中，常常有一些线性的但数据量特别大的问题，如区间求和、求最小值等。很多时候，为了把时间复杂度从 $O(n^2)$ 甚至更高的地方降下来，我们需要对数据进行一些预处理，以提高计算的速度。在这其中，有很大一部分是来自二进制运算特点的启发。

最小生成树（Kruscal & Prim）

2014-10-26

测试位置：WikiOI1078

type
    TEdge = record
        start, terminal: longint;
        weight: int64;
    end;
    TEdgeArr = array of TEdge;

operator <(e1, e2: TEdge)res: boolean;
begin
    res := e1.weight < e2.weight;
end;

operator >(e1, e2: TEdge)res: Boolean;
begin
    res := e1.weight > e2.weight;
end;

procedure SortEdge(A: TEdgeArr; l, r: longint);
var
    i, j: longint;
    t, m: TEdge;
begin
    i := l; j := r; m := A[(i+j) >> 1];
    repeat
        while A[i]<m do inc(i);
        while A[j]>m do dec(j);
        if i<=j then
        begin
            t := A[i];
            A[i] := A[j];
            A[j] := t;
            inc(i); dec(j);
        end;
    until i>j;
    if i<r then SortEdge(A, i, r);
    if l<j then SortEdge(A, l, j);
end;

const
    INF: int64 = 1<<60 div 3;
var
    map: array [1..100, 1..100] of int64;
    n, i, j: longint;

{
    @param x: 起始搜索节点
    算法思想：用一个数组维护从各个未加入顶点到
    树的最短边长度，操作n次，每次将距离最短的
    边加入到树中，并更新与之相邻的点的距离值。
}

function prim(x: longint): int64;
{
    lowest: 储存各个节点到树的最短距离
    visited: 标记是否已加入树中
}
var
    lowest: array [1..100] of int64;
    visited: array [1..100] of boolean;
    min: int64;
    i, j, minindex: longint;
begin
    fillchar(visited, sizeof(visited), 0);
    visited[x] := true;

    //先将初始节点加入树中，更新lowest
    for i := 1 to n do
        lowest[i] := map[i, x];

    prim := 0;
    for i := 2 to n do
    begin
        min := INF;

        //找出树到外部节点最短的一条边
        //并将该边加入树中
        for j := 1 to n do
            if (not visited[j]) and (min > lowest[j]) then
            begin
                min := lowest[j];
                minindex := j;
            end;
        visited[minindex] := true;
        prim := prim + min;

        //对新加入的那个节点，
        //更新与其相邻的未加入树的节点的lowest值
        for j := 1 to n do
        begin
            if visited[j] then continue;
            if map[j, minindex] < lowest[j] then
                lowest[j] := map[j, minindex];
        end;
    end;
end;

{
    算法思想：
    1\. 先将边按照长度排序。
    2\. 遍历所有的边，若该边的两个顶点都在树中则跳过；
    否则将其加入树中。
}

function Kruscal: int64;
var
    Edges: TEdgeArr;
    //并查集，储存自己的父亲，若自己为根结点则为自己
    //这是一种常用的写法：否则如果存成0的话，想把两棵
    //树并在一起需要多一步判断。
    UnionSet: array [0..100] of longint;
    i: longint;

    procedure InitEdges; //将邻接矩阵转化为边数组。
    var
        i, j: longint;
        E: TEdge;
    begin
        for i := 1 to n do
            for j := 1 to i-1 do
            begin
                E.start := i;
                E.terminal := j;
                E.weight := map[i, j];
                SetLength(Edges, Length(Edges)+1);
                Edges[High(Edges)] := E;
            end;
        SortEdge(Edges, Low(Edges), High(Edges));
    end;

    //寻找自己的根节点，并把自己直接连到根结点上。
    function Find(x: longint): longint;
    var
        root: longint;
    begin
        root := x;
        while root <> UnionSet[root] do
            root := UnionSet[root];
        UnionSet[x] := root;
        exit(root);
    end;

    //尝试将边的两个顶点并在一个并查集中，如果两个
    //顶点都在同一个集合中则返回False，否则执行合
    //并操作。
    function Union(x, y: longint): boolean;
    var
        px, py: longint;
    begin
        px := Find(x);
        py := Find(y);
        if px = py then
            exit(False);
        UnionSet[px] := py;
        exit(True);
    end;

begin
    Kruscal := 0;
    fillchar(UnionSet, sizeof(UnionSet), 0);
    InitEdges;
    for i := 1 to n do
        UnionSet[i] := i;
    for i := Low(Edges) to High(Edges) do
        if Union(Edges[i].start, Edges[i].terminal) then
        begin
            Kruscal := Kruscal + Edges[i].weight;
        end;
end;

begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);

    readln(n);
    for i := 1 to n do
        for j := 1 to n do
            read(map[i, j]);
    writeln(Kruscal);

    close(input); close(output);
end.

NOIP2013 Day1 火柴排队：快速求逆序对

2014-10-26

题目

涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为： $$\sum_{i=1}^{n}{(a_i-b_i)^2}$$
其中 ai 表示第一列火柴中第 i 个火柴的高度，bi 表示第二列火柴中第 i 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。

分析

这真是一道好题——断断续续想了几天才完全 AC。

事实上，由排序不等式可知：

$$当 a_i, b_i 从小到大排序时，距离最小$$

这是一个重要的信息。因此，我们只需把 $a_i,b_i$ 进行排序，并把对应项“捆绑”成一项，再按 $a_i$ 原有的顺序进行复原，此时，可以得到由 $b_i$ 原先的下标组成的一个序列。也就是说，我们要求 $1,2,\ldots,n$ 至少经过多少步才能变为该序列。这可以用逆序对来解决。

只可惜，传统的逆序对算法时间复杂度为 $O(n^2)$，这里 $n$ 可达 $200000$，一定会超时 ¹。因此我们需寻求更好的算法。

用归并排序求逆序对

在归并排序的过程中，有一个步骤称为合并。在这个步骤中，需要轮流判断左右区间的第一个数的大小关系。注意到：左右区间已经有序，从而若左区间的第一个数大于右区间的第一个数，则左区间之后的所有数都大于右区间的第一个数，从而我们可以在合并时做一些修改：

procedure nx(l, r: longint);
var
    mid, i, j, k: longint;
begin
    if l = r then
    begin
        tmp[l] := a[l];
        exit;
    end;
    mid := (l + r) shr 1;
    nx(l, mid);
    nx(mid+1, r);
    i := l;
    j := mid+1;
    k := l;
    while k <= r do
    begin
        if (j>r) or (i<=mid) and (a[i]<=a[j]) then //注意这里为等号
        begin
            tmp[k] := a[i];
            inc(i);
        end
        else
        begin
            cnt := cnt + mid - i + 1; //加上逆序数
            tmp[k] := a[j];
            inc(j);
        end;
        inc(k);
    end;
    for i := l to r do
        a[i] := tmp[i];
end;

这个算法复杂度为$O(n\log n)$，是一种比较理想的算法，实现起来也简单。但他有个缺点：会打乱原数组顺序。

原题代码

//AC
const
    MODN = 99999997;
type
    rec = record value, index: longint; end;
    TArr = array [1..100000] of rec;
var
    n: longint;
    a, b, c, tmp: TArr;
    ok: Boolean;
    l, r, i, j: longint;
    cnt: int64;

procedure sort(var arr: TArr; l, r: longint);
var
    i, j: longint;
    m, t: rec;
begin
    i := l;
    j := r;
    m := arr[(i+j) shr 1];
    repeat
        while arr[i].value < m.value do inc(i);
        while arr[j].value > m.value do dec(j);
        if i <= j then
        begin
            t := arr[i];
            arr[i] := arr[j];
            arr[j] := t;
            inc(i);
            dec(j);
        end;
    until i >j;
    if i < r then sort(arr, i, r);
    if l < j then sort(arr, l, j);
end;

procedure nx(l, r: longint);
var
    mid, i, j, k: longint;
begin
    if l = r then
    begin
        tmp[l] := c[l];
        exit;
    end;
    mid := (l + r) shr 1;
    nx(l, mid);
    nx(mid+1, r);
    i := l;
    j := mid+1;
    k := l;
    while k <= r do
    begin
        if (j>r) or (i<=mid) and (c[i].index<=c[j].index) then
        begin
            tmp[k] := c[i];
            inc(i);
        end
        else
        begin
            cnt := cnt + mid - i + 1;
            cnt := cnt mod MODN;
            tmp[k] := c[j];
            inc(j);
        end;
        inc(k);
    end;
    for i := l to r do
        c[i] := tmp[i];
end;

begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);

    readln(n);
    for i := 1 to n do
    begin
        read(a[i].value);
        a[i].index := i;
    end;
    for i := 1 to n do
    begin
        read(b[i].value);
        b[i].index := i;
    end;
    sort(a, 1, n);
    sort(b, 1, n);

    for i := 1 to n do
        c[a[i].index] := b[i];

    cnt := 0;
    nx(1, n);
    writeln(cnt);

    close(input); close(output);
end.

事实上，只过了 70% 的点

NOIP2011 Day2 计算系数：快速求组合数

2014-10-25

题目大意

输入 $a, b, k, n, m$，计算 $a^n\times b^m\times C_k^n$ 模 $10007$ 的余数。

分析

对于幂数的计算并不难，关键在于对组合数$C_n^k$的计算。

通常来说，组合数的计算一般是这样的：$$C_n^k=\frac{n}{k}\times\frac{n-1}{k-1}\times\ldots\times\frac{n-k+1}{1}$$ 这对于单精度的计算来说是十分快捷的，但如果要对结果取模的话就不起作用了——取模运算对于除法不成立。因此只能另辟蹊径了。

注意到加减乘法对于取模都是成立的，从而想到：能否将组合数转化成加法？我们自然而然想到了组合恒等式：$$C_n^k=C_{n-1}^{k}+C_{n-1}^{k-1}$$ 思路到此完成。

Code

const
    modn = 10007;
var
    a, b, k, m, n: longint;
    map: array[0..1000,0..1000] of int64; //缓存
//快速幂
function power(a, x: longint): int64;
var
    t: longint;
begin
    if x = 1 then
        exit(a);
    if x = 0 then
        exit(1);
    t := power(a, x shr 1);
    power := t * t mod modn;
    if odd(x) then
        power := power * a mod modn;
end;
//快速组合数
function C(n, k: longint): int64;
begin
    if map[n, k] > 0 then
        exit(map[n, k]);
    if (n <= k) or (k = 0) then
        C := 1
    else if k = 1 then
        C := n
    else
        C := (C(n-1, k)+C(n-1, k-1)) mod modn;
    map[n, k] := C;
end;

var
    t: longint;
    ans: int64;

begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);

    readln(a, b, k, n, m);
    a := a mod modn;
    b := b mod modn;
    ans := power(a, n);
    ans := ans * power(b, m) mod modn;
    //C(k,n)与C(k,m)是等效的，计算较小者即可
    if n > m then n := m;
    ans := ans * C(k, n) mod modn;
    writeln(ans);

    close(input); close(output);
end.

UVa1647 Computer Transformation

2014-10-24

链接：Link 耗时：0.679s

分析

本质上，这是一道求数列通项的题目。我们列出前几个字符串： $$01,$$ $$1001,$$ $$01101001,$$ $$1001011001101001,$$ $$\ldots$$

如果用$S_i$表示第 i 个字符串中“00”的个数，则有： $$S_1=0,\ S_2=1,\ S_3=1,\ S_4=3,\ S_5=5,\ S_6=11,\ldots$$

经过观察可以发现有如下规律： $$S_n=2\times S_{n-1}+{(-1)}^n$$

求通项就简单了，换个元即可： $$S_n=\frac{1}{3}[{(-1)}^n+2^{n-1}]$$

程序采用高精度实现。

Code

const
    JINDU = 100000;
var
    n: Integer;
//在数字前补0
procedure PrintANumber(x: longint);
var
    t: longint;
begin
    if x = 0 then
        write('00000')
    else
    begin
        t := JINDU;
        while t > x * 10 do
        begin
            write(0);
            t := t div 10;
        end;
        write(x);
    end;
end;

var
    ans: array [1..300] of longint;
    len, i: integer;
//计算2^(n-1)
procedure calc2;
var
    i, x, t, mul: longint;
begin
    len := 1;
    ans[1] := 1;
    t := n-1;
    while t > 0 do
    begin
        if t < 6 then
            mul := 1 << t
        else
            mul := 64;
        x := 0;
        for i := 1 to len do
        begin
            ans[i] := ans[i] * mul + x;
            x := ans[i] div JINDU;
            ans[i] := ans[i] mod JINDU;
        end;
        if x > 0 then
        begin
            inc(len);
            ans[len] := x;
        end;
        dec(t, 6);
    end;
end;
//除以3
procedure div3;
var
    i, x, t: longint;
begin
    i := len;
    x := 0;
    while i > 0 do
    begin
        t := (x * JINDU + ans[i]);
        ans[i] := t div 3;
        x := t mod 3;
        dec(i);
    end;
    while ans[len] = 0 do dec(len);
end;

begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);

    while not eof do
    begin
        readln(n);
        if n=1 then   //特殊情况处理
        begin
            writeln(0);
            continue;
        end;
        fillchar(ans, sizeof(ans), 0);
        calc2;
        if odd(n) then
            dec(ans[1])
        else
            inc(ans[1]);
        div3;
        write(ans[len]);
        for i := len-1 downto 1 do
            PrintANumber(ans[i]);
        writeln;
    end;

    close(input); close(output);
end.

Sublime configuration for Pascal

2014-10-23

鉴于 U 盘中 Sublime 的配置常常莫名其妙地消失，在此将其记录一下。

Code

{
    "cmd": ["fpc", "-S2", "${file}", "-o${file_path}/${file_base_name}.exe"],
    "file_regex": "^(..[^:]*):([0-9]+):?([0-9]+)?:? (.*)$",
    "working_dir": "${file_path}",
    "selector": "source.pascal",

    "variants": [
        {
            "name": "Run",
            "cmd": ["cmd", "/c", "fpc", "-S2", "${file}", "-o${file_path}/${file_base_name}.exe",
    "&&", "${file_path}/${file_base_name}.exe"]
        }
    ],

    "osx":
    {
        "path": "/usr/local/bin:/usr/bin:/bin:${path}"
    }
}

UVa11526 H(n)

2014-10-18

链接：Link 耗时：2.232s

分析

粗看题目，不过就是要求这样一个式子：$\sum_{i=1}^n{[\frac{n}{i}]}$的值。但注意到：题目给的数据范围极大，有$2^{31}-1$之多，若遍历计算，则时间复杂度为$O(n)$，将严重超时，不可取。

而事实上，通过尝试我们可以发现：$\sum_{i=1}^{n}{[\frac{n}{i}]}=2*\sum_{i=1}^{\sqrt n}{[\frac{n}{i}]}-{[\sqrt n]}^2$，这是一个重要的结论。因为这条式子一旦成立，时间复杂度即可从$O(n)$降为$O(\sqrt n)$，这是一个极为可观的改善。下面我们来证明一下这个结论：

事实上，

$$ \begin{aligned} \sum_{i=[{\sqrt n}]+1}^{n}{[\frac{n}{i}]} &=1\times(n-[\frac{n}{2}])+2\times([\frac{n}{2}]-[\frac{n}{3}])+\ldots+[\sqrt{n}]\times([\frac{n}{\sqrt{n}}]-{[\frac{n}{\sqrt n}+1]}) \\ &=n+[\frac{n}{2}]+[\frac{n}{3}]+\ldots+[\frac{n}{\sqrt n}]-[\sqrt n]\times[\frac{n}{[\sqrt n]+1}] \\ &=\sum_{i=1}^{[\sqrt n]}{[\frac{n}{i}]}-{[\sqrt n]}^2 \end{aligned}$$

从而，命题得证。

Code

var
    n, _, i: longint;

function h: int64; inline;
var
    k, t: longint;
begin
    h := 0;
    t := trunc(sqrt(n));
    k := 1;
    while k <=t do
    begin
        h := h + n div k;
        inc(k);
    end;
    h := h * 2 - t * t;
end;

begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);

    readln(_);
    while _ > 0 do
    begin
        dec(_);
        readln(n);
        if n <= 0 then
            writeln(0)
        else
            writeln(h);
    end;

    close(input);
    close(output);
end.

UVa817 According to Bartjens

2014-10-17

链接：Link 状态：WA

分析

做了两个小时，很可惜最终还是 WA 了。非常奇怪——和网上的 C++ 代码运行结果完全一样，但却 WA 了。不过，在这里我还是记录一下解题的过程。这道题数据量很小，直接爆搜每个空位，用 *, +, -, #0 来代表符号或不填。

Code

const
    operators: array [1..4] of char = ('*', '+', '-', #0); //符号
var
    s: string;
    _, n: integer;
    op: array [0..10] of char;
    yes: Boolean;

function toValue(ch: char): integer;
begin
    exit(ord(ch) - ord('0'));
end;

procedure calcAndPrint;
var
    numtop, opstop: Integer;  //数字栈，符号栈
    num: array [1..10] of longint;
    ops: array [1..10] of char;
    i: integer;
begin
    i := 1;
    numtop := 1;
    num[numtop] := toValue(s[1]);
    opstop := 0;
    while i <= n do
    begin
        while (i < n) and (op[i] = #0) do
        begin
            inc(i);
            num[numtop] := num[numtop] * 10 + toValue(s[i]);
        end;
        if (op[i] in ['+', '-']) or (i >= n) then
        begin
            while (opstop > 0) and (ops[opstop] = '*') do
            begin
                dec(opstop);
                num[numtop - 1] := num[numtop] * num[numtop -1];
                dec(numtop);
            end;
        end;
        if i >= n then break;
        inc(opstop);
        ops[opstop] := op[i];
        inc(i);
        inc(numtop);
        num[numtop] := toValue(s[i]);
    end;
    i := 1;
    while i < numtop do
    begin
        if ops[i] = '+' then
            num[i+1] := num[i] + num[i+1]
        else
            num[i+1] := num[i] - num[i+1];
        inc(i);
    end;
    if (num[numtop] = 2000) and (opstop > 0) then
    begin
        yes := True;
        write('  ');
        for i := 1 to n do
        begin
            write(s[i]);
            if op[i] <> #0  then
                write(op[i]);
        end;
        writeln('=');
    end;
end;

procedure dfs(t: integer); //搜索第t个位置
var
    i: Integer;
    ch: char;
begin
    if t = n then
    begin
        calcAndPrint;
        exit;
    end;
    for i := 1 to 4 do
    begin
        ch := operators[i];
        if (ch = #0) and (s[t] = '0') and ((t = 1) or (t > 1) and (op[t-1] <> #0)) then continue;
        op[t] := ch;
        dfs(t+1);
    end;
end;

var
    i: Integer;

begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);

    readln(s);
    _ := 0;
    while not eof and (s[1] <> '=') do
    begin
        i := 1;
        while not (s[i] in ['0'..'9', '=']) do
        begin
            inc(i);
        end;
        delete(s, 1, i-1);
        n := pos('=', s) - 1;
        inc(_);
        writeln('Problem ', _);
        yes := False;
        fillchar(op, sizeof(op), 0);
        dfs(1);
        if not yes then
            writeln('  IMPOSSIBLE');
        readln(s);
    end;

    close(input); close(output);
end.

UVa225 Golygons

2014-10-15

链接：Link 耗时：0.699s

思路

dfs(t, x, y, d, s) 表示当前走了 t 步，在 (x,y)，上一个方向为 d，s 为一个求和用的辅助变量。

当前位置无法走完剩下的路时直接回溯。可节省接近 2s 的时间。

p.s. 这道题虽然没有明说每个城市只走一次，但它的确那样判了，这一点坑了我好久。

Code

//Accepted.
const
    dx: array [1..4] of integer = (1, 0, 0, -1);
    dy: array [1..4] of integer = (0, 1, -1, 0);
    dir: array [1..4] of char = ('e', 'n', 's', 'w');

var
    a: array [1..50, 1..2] of integer; //障碍物
    k, i, n, _, x, y: integer;
    ans: array [1..20] of char;
    tot: longint;
    vis: array [-220..220, -220..220] of boolean;

function judge(x1, y1, x2, y2: longint): Boolean; //判断刚刚走过的路上是否有障碍物
var
    i: Integer;
begin
    judge := False;
    if x1 = x2 then
    begin
        for i := 1 to k do
            if (a[i, 1] = x1) and ((a[i, 2] - y1)*(a[i, 2] - y2) <= 0) then exit;
    end
    else
        for i := 1 to k do
            if (a[i, 2] = y2) and ((a[i, 1] - x1)*(a[i, 1] - x2) <= 0) then exit;
    judge := True;
end;

procedure print;
var
    i: Integer;
begin
    for i := 1 to n do write(ans[i]);
    writeln;
    inc(tot);
end;

procedure dfs(t, x, y, d, s: integer);
var
    i, sum: Integer;
    tx, ty: longint;
begin
    if t = n then
    begin
        if (x = 0) and (y = 0) then print;
        exit;
    end;

    sum := s - t - 1;
    inc(t);

    for i := 1 to 4 do
    begin
        if (i = d) or (i + d = 5) then continue;   //方向相同或相反
        tx := x + dx[i] * t;
        ty := y + dy[i] * t;
        if vis[tx, ty] then continue;              //走过
        if abs(tx) + abs(ty) > sum then continue;  //回不去，剪枝
        if not judge(x, y, tx, ty) then continue;  //有障碍物
        ans[t] := dir[i];
        vis[tx, ty] := True;
        dfs(t, tx, ty, i, sum);
        vis[tx, ty] := False;
    end;
end;

begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);

    readln(_);
    while _ > 0 do
    begin
        dec(_);
        read(n, k);
        fillchar(vis, sizeof(vis), 0);
        for i := 1 to k do
            read(a[i, 1], a[i, 2]);
        fillchar(ans, sizeof(ans), 0);
        tot := 0;
        dfs(0, 0, 0, -1, n * (n+1) div 2);
        writeln('Found ', tot, ' golygon(s).');
        writeln;
    end;

    close(input); close(output);
end.

介绍

Code

引子

目录

题目

分析

用归并排序求逆序对

原题代码

题目大意

分析

Code

分析

Code

Code

分析

Code

分析

Code

思路

Code