UOJ Logo immortalCO的博客

博客

指针和数组的代码哲学和一些数组的小技巧(雾)

2016-08-07 14:18:20 By immortalCO

一直很喜欢在 struct 时用指针。除了在速度上有优势(数组要做额外的加法),还有一点就是它的代码是符合中英文的语序的。

举个例子:

k->fa->val->max = 1;

如果要解读这段代码,我们可以这样:

设置 
    k 
        的 fa 
            的 val 
                的 max 
为
    1

因为指针的代码是符合我们常用语言的语序的。如果用数组,我们就必须这样写:

max[val[fa[k]]] = 1

强行解读的话,就变成:

设置
    在所有 max 中,是
        在所有 val 中,是
            在所有 fa 中,是
                k
            的那一个 fa
        的那一个 val
    的那一个 max
为
    1

简直佶屈聱牙,难以成颂!然而,一种特殊的 C++ 数组写法可以解决这个问题。在 C++ 中,a[b] 等价于 *(a + b),因此

a[b] = *(a + b) = *(b + a) = b[a]

也就是说,我们可以倒转数组名和下标的位置。比如我们可以

a[i] = i[a]
b[1] = 1[b]
c[2][2] = 2[c[2]] = 2[2[c]] // 每一个 [] 都有两种写法
d[1][2][3][4][5] = 5[4[3[2[1[d]]]]]
A[B[C[D[E[i]]]]] = i[E][D][C][B][A] // [] 是从左往右计算的

这个的第一个用途是混乱代码,防止在 CF 上被 Hack。试想如果你有个 5 维 DP,那么每一维你都有 2 种写法,总共就有 32 种写法,然后你在 DP 中混用这几种写法……(嘿嘿嘿!!!)

观察最后一行左边的那个形式,不正是我们 max[val[fa[k]]] 的形式吗?因此我们可以写成

max[val[fa[k]]] = k[fa][val][max]

嘿嘿嘿!熟悉的语序回来了!而且没有方括号的嵌套,减小了漏打、错打括号导致 CE 的可能性。那么在不方便使用指针(比如 64 位机卡内存)时,我们同样可以用数组做到优美的代码风格。

以下是数组版《树上两点距离》,用树链剖分求 LCA。在 query 时,语序十分自然。

#include <cstdio>
const int MaxN = 1000010;
int to[MaxN << 1], len[MaxN << 1], next[MaxN << 1], fir[MaxN];
void link(int x, int y, int v)
{
    static int tot = 1;
    ++tot, tot[next] = x[fir], tot[to] = y, tot[len] = v, x[fir] = tot;
    ++tot, tot[next] = y[fir], tot[to] = x, tot[len] = v, y[fir] = tot; 
}
int pre[MaxN], dep[MaxN], cnt[MaxN], cho[MaxN], top[MaxN];
void dfs_init(int i)
{
    i[cnt] = 1;
    for(int k = i[fir]; k; k = k[next])
        if(!k[to][cnt])
        {
            k[to][pre] = i;
            k[to][dep] = i[dep] + k[len];
            dfs_init(k[to]);
            i[cnt] += k[to][cnt];
            if(k[to][cnt] > i[cho][cnt])
                i[cho] = k[to];
        }
}
void dfs_make(int i)
{
    i[top] = (i == i[pre][cho]) ? i[pre][top] : i;
    for(int k = i[fir]; k; k = k[next])
        if(!k[to][top]) dfs_make(k[to]);
}
int query(int x, int y)
{
    int ans = x[dep] + y[dep];
    while(x[top] != y[top])
        x[top][dep] > y[top][dep]
            ? x = x[top][pre]
            : y = y[top][pre];
    ans -= (x[dep] < y[dep] ? x[dep] : y[dep]) << 1;
    return ans;
}

int main()
{
    int n, m, x, y, v; scanf("%d%d", &n, &m);
    for(int i = n; --i; ) scanf("%d%d%d", &x, &y, &v), link(x, y, v);
    dfs_init(1), dfs_make(1);
    while(m--) scanf("%d%d", &x, &y), printf("%d\n", query(x, y));
}

评论

scaling
sxbk
xia_xue_QAQ
总感觉...这种写法....非常的...变态....
WrongAnswer
让我们把式子改写一下吧! 我们熟悉的式子: $$F(n)=\sum_{d|n}f(d) \Rightarrow f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})$$ 来,改一改: $$n(F)=\sum_{d|n}d(f) \Rightarrow n(f)=\sum_{d|n}d(\mu)\frac{n}{d}(F)$$
dram
扩展版!c[x][0] = x[c][0],写平衡树的时候最萌啦!
Sengxian
我总感觉更容易写错了呢。。。 还是指针大法保平安
dram
http://codeforces.com/blog/entry/4088 It is forbidden to obfuscate the solution code as well as create obstacles for its reading and understanding. That is, it is forbidden to use any special techniques aimed at making the code difficult to read and understand the principle of its work.
qmqmqm
因为这个就是像函数一样表示的啊。你用x(sin)来表示正弦函数?
ridiculos
cf的数据蛮强大的吧 如果程序有bug 没有被hack也会fst吧
ftiasch
你可以认为这个是一种 Continuous Passing Style...
dram
万物皆可数组!http://uoj.ac/submission/90760
dram
刚刚想到一个哲学问题,对于一个比如二叉树,应该写成这样, int c[2][maxn]; node[c[0]] 还是这样? int c[maxn][2]; node[c][0]
ChlorineHikari
orz 博主我要转走...
longlongzhu123
struct + 数组党 tree[tree[tree[node].fa].son[1]].val(滑稽

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。