_slb's Code Style | _slb 的博客

本文介绍 _slb 的代码规范。关于我的代码规范，她非常地正经、非常地合理。

基本参考了 _rqy 的风格。

概述

不使用 #include <bits/stdc++.h>，头文件顺序不做要求。

可以使用 using namespace std;。

尽量不使用 #define，多使用 typedef，const。

一行长度尽量不超过 $120$ 字符或者不超过屏幕 $80\%$ 的宽度。要易于阅读。

缩进

每个代码块使用四个空格缩进，包括流程控制语句、namespace 下等。

空格及换行

大部分时候使用大括号换行风格，例：

if (orz)
{
    // do something	   
}
else
{
    // do something
}

偶尔会使用大括号不换行的风格，例：

if (orz) {
    // do something
} else {
    // do something
}

加空格地方：

二目、三目运算符两侧；
,，; 的右边（前提是不处于行末）；
流程控制关键字与其后面的括号之间；
do-while 中的 while 与其左面的大括号之间；
当整组大括号都在一行时，左大括号前打一个空格；
常成员函数的 const 两侧。

不加空格地方：

小括号、中括号与其内部表达式等之间；
函数名与左括号之间；
单目运算符前后；
.，::，-> 的两侧；
operator 与重载的运算符之间。

表达式过长可以分多行——缩进的关键是对齐。

很短的函数可以写到一行。

空行

所有#include <foobar>与using foo::bar;之间不应空行，之后应空一行。

一系列常量定义的上下应有空行。

函数/结构体定义两侧可以有空行（一系列短小到可以写到一行的函数，如min, max，之间可以不空行）。

一系列全局变量定义的上下应有空行。

语句之间可根据其意义酌情空行。

任何位置不能出现连续的两个（或以上）空行。

函数

main 函数返回值最好是 int。

传自定义结构体/类的时候尽量传引用并加 const。

单个函数不应过长。

命名

并没有什么特殊的命名方法，一般使用下划线。

大写字母一般较少使用。

一些正式的数据结构的开头字母会大写，而单纯的模块化并不会大写开头字母。

其他

不进行压行，一行最多一个语句。

如果语义连续，可以酌情使用逗号。

三目运算符合适就用。尽量做到易于阅读。

if，while，for 等流程控制语句，即使后面只有单个语句，也不能放在一行。

尽量少利用不是非常显然的返回值（如逗号）来简化代码（如 return p.push_back(x), void() 等）。

关于指针与数组，当用指针写起来没啥太大问题时，可能更偏向指针，当用指针容易出问题时，偏向数组（这条实际上比较看习惯）。

代码结构

注：此部分内容可能会经常调整，此处写的未必是正在用的代码结构。

有一个 namespace IO，但不会经常使用，大部分用 cin。

namespace solve 里的代码是有用的，其他均为不变的模板。

example

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <queue>
#include <vector>
#include <cmath>
#include <cctype>
#include <utility>
#include <cassert>
#include <map>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

bool MEM1;

namespace IO
{
    const int mxsiz = 1 << 20;
    char inbuf[mxsiz], *p1, *p2;
    char outbuf[mxsiz], *op = outbuf;
    struct endio
    {
        endio(){};
        ~endio() { fwrite(outbuf, 1, op - outbuf, stdout); }
    } useless_var;
    inline char gc() { return p1 == p2 && (p2 = (p1 = inbuf) + fread(inbuf, 1, mxsiz, stdin), p1 == p2) ? EOF : *p1++; }
    inline int read()
    {
        int x = 0, f = 1;
        char ch = gc();
        for (; !isdigit(ch); ch = gc())
            if (ch == '-')
                f = -1;
        for (; isdigit(ch); ch = gc())
            x = x * 10 + ch - '0';
        return x * f;
    }
    template <typename T>
    inline void read(T &x)
    {
        x = 0;
        int f = 1;
        char ch = gc();
        for (; !isdigit(ch); ch = gc())
            if (ch == '-')
                f = -1;
        for (; isdigit(ch); ch = gc())
            x = x * 10 + ch - '0';
        x *= f;
    }
    inline bool ischar(char x)
    {
        return x >= 'A' && x <= 'z';
    }
    inline char readchar()
    {
        char ch = gc();
        while (!ischar(ch))
            ch = gc();
        return ch;
    }
    inline void push(char ch)
    {
        if (op - outbuf == mxsiz)
            fwrite(outbuf, 1, mxsiz, stdout), op = outbuf;
        *op++ = ch;
    }
    template <typename T>
    inline void work_wt(T x)
    {
        if (x > 9)
            work_wt(x / 10);
        push(x % 10 + '0');
    }
    template <typename T>
    inline void write(T x)
    {
        if (x < 0)
            x = -x, push('-');
        work_wt(x);
    }
    inline void writestr(char *s)
    {
        int n = strlen(s);
        for (int i = 0; i < n; i++)
            push(s[i]);
    }
    inline void endln() { push('\n'); }
    inline void space() { push(' '); }
    template <typename T>
    inline void writeln(T x) { write(x), endln(); }
}
using namespace IO;

namespace solve
{
    const int maxn = 2e6 + 10;
    typedef pair<int, int> pii;

    int father[maxn], mx[maxn];
    int ch[maxn][26];
    int tot, lst, dfn[maxn], n, pos[maxn], cnt_dfn;
    int arcdfn[maxn];
    ll sum[maxn / 2];
    char s[maxn / 2];
    struct SAM
    {
        SAM() { lst = tot = 1; }
    } SAM__;
    void insert(int c, int id)
    {
        int p = ++tot, f = lst;
        lst = p, mx[p] = mx[f] + 1, pos[p] = id;
        while (f && !ch[f][c])
            ch[f][c] = p, f = father[f];
        if (!f)
            father[p] = 1;
        else
        {
            int q = ch[f][c];
            if (mx[q] == mx[f] + 1)
                father[p] = q;
            else
            {
                int nq = ++tot;
                memcpy(ch[nq], ch[q], sizeof(ch[q]));
                father[nq] = father[q], mx[nq] = mx[f] + 1;
                father[p] = father[q] = nq;
                while (f && ch[f][c] == q)
                    ch[f][c] = nq, f = father[f];
            }
        }
    }
    
    struct edge
    {
        int nxt, y, w;
        bool operator<(const edge &b) const { return w < b.w; }
    } e[maxn];
    int hd[maxn];
    int cnt[maxn], topo[maxn];
    struct tmpp
    {
        int a, b, c;
    } alle[maxn];
    struct md
    {
        int time;
        pii opt;
    } change[maxn * 2];
    int totch;
    int tote, ee;
    void add(int x, int y, int w)
    {
        alle[++tote] = {x, y, w};
    }
    void addall()
    {
        sort(alle + 1, alle + 1 + tote, [&](const tmpp &a, const tmpp &b) { return a.c > b.c; });
        for (int i = 1; i <= tote; i++)
        {
            ee++;
            int x = alle[i].a, y = alle[i].b, w = alle[i].c;
            e[ee] = {hd[x], y, w}, hd[x] = ee;
        }
    }
    void build()
    {
        for (int i = 1; i <= tot; i++)
            cnt[mx[i]]++;
        for (int i = 1; i <= n; i++)
            cnt[i] += cnt[i - 1];
        for (int i = tot; i >= 1; i--)
            topo[cnt[mx[i]]--] = i;
        for (int i = tot; i >= 1; i--)
        {
            int x = topo[i];
            sum[mx[father[x]] + 1]++, sum[mx[x] + 1]--;
            pos[father[x]] = max(pos[x], pos[father[x]]);
        }
        for (int i = 2; i <= tot; i++)
        {
            totch++;
            change[totch] = {mx[father[i]] + 1, pii(i, 1)};
            totch++;
            change[totch] = {mx[i] + 1, pii(i, -1)};
        }
    }
    void build2()
    {
        for (int i = 2; i <= tot; i++)
            add(father[i], i, s[pos[i] - mx[father[i]]] - 'a');
        addall();
        sort(change + 1, change + 1 + totch, [&](const md &a, const md &b) { return a.time < b.time; });
    }
    void dfs2(int x)
    {
        dfn[x] = ++cnt_dfn, arcdfn[cnt_dfn] = x;
        for (int p = hd[x]; p; p = e[p].nxt)
            dfs2(e[p].y);
    }
    
    struct Segtree
    {
        static const int maxn = solve::maxn << 2;
        int sum[maxn];
        inline int ls(int x) { return x * 2; }
        inline int rs(int x) { return x * 2 + 1; }
        void push_up(int k)
        {
            sum[k] = sum[ls(k)] + sum[rs(k)];
        }
        void modify(int l, int r, int x, int v, int k)
        {
            if (l == r)
            {
                sum[k] += v;
                return;
            }
            int mid = (l + r) / 2;
            if (x <= mid)
                modify(l, mid, x, v, ls(k));
            else
                modify(mid + 1, r, x, v, rs(k));
            push_up(k);
        }
        int query(int l, int r, int x, int k)
        {
            if (l == r)
                return l;
            int mid = (l + r) / 2;
            if (sum[ls(k)] >= x)
                return query(l, mid, x, ls(k));
            else
                return query(mid + 1, r, x - sum[ls(k)], rs(k));
        }
    } t;
    
    struct Q
    {
        ll k;
        int id;
        int res1, res2;
        bool operator<(const Q &b) const { return k < b.k; }
    } q[maxn];
    
    int m;
    
    int main()
    {
        scanf("%s", s + 1);
        n = strlen(s + 1);
        reverse(s + 1, s + 1 + n);
        for (int i = 1; i <= n; i++)
            insert(s[i] - 'a', i);
        build(), build2(), dfs2(1);
        for (int i = 1; i <= n; i++)
            sum[i] += sum[i - 1];
        for (int i = 1; i <= n; i++)
            sum[i] += sum[i - 1];
        sum[0] = 0;
        m = read();
        for (int i = 1; i <= m; i++)
            read(q[i].k), q[i].id = i;
        sort(q + 1, q + 1 + m);
        int now = 1;
        for (int i = 1; i <= m; i++)
        {
            int len = lower_bound(sum + 1, sum + 1 + n, q[i].k) - sum;
            if (len > n)
            {
                q[i].res1 = -1, q[i].res2 = -1;
                continue;
            }
            int k = q[i].k - sum[len - 1];
            // cerr << k << " " << now << endl;
            while (change[now].time <= len)
            {
                t.modify(1, tot, dfn[change[now].opt.first], change[now].opt.second, 1);
                now++;
            }
            int uu = t.query(1, tot, k, 1);
            uu = arcdfn[uu];
            int tmpl = pos[uu] - len + 1;
            int tmpr = pos[uu];
            q[i].res1 = n - tmpr + 1;
            q[i].res2 = n - tmpl + 1;
        }
        sort(q + 1, q + 1 + m, [&](const Q &a, const Q &b) { return a.id < b.id; });
        for (int i = 1; i <= m; i++)
            write(q[i].res1), space(), writeln(q[i].res2);
        return 0;
    }
}

bool MEM2;

int main()
{

#ifdef local
    cerr << "memory : " << abs(&MEM1 - &MEM2) / 1024. / 1024 << " mb" << endl;
#endif

    int cases = 1;
    while (cases--)
        solve::main();

#ifdef local
    cerr << "time : " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
#endif

    return 0;
}

注：此为 CF gym103409J。

概述¶

缩进¶

空格及换行¶

空行¶

函数¶

命名¶

其他¶

代码结构¶

example¶

概述

缩进

空格及换行

空行

函数

命名

其他

代码结构

example