扯谈压行

wuwendongxi · 2021-09-20 15:22:32 · 个人记录

这是一篇技术含量不高的文章，主要教你如何将代码变短，使代码可读性更高

upd：截止2021.9月，我统计了一下约1000道做过的题（删除调试语句后），除了在压行技术还不太成熟时期的树链剖分模板5个操作等15道左右的题目中代码超过了3k（3.3k），其他代码都保持在3k以内，庆祝！！！1

PS：没写过猪国杀，所以不知道要写多长。

Part.0 扯谈

众所周知，压行是一种邪教好习惯，高效的压行可以使你的代码变短，更容易调试，可读性更高，连贯性更好（鬼扯）

但过度的压行会使别人感到迷惑：

“你这LCT压行太严重了吧”----------当你请别人帮你调题时（亲身经历）

所以，我还是义无反顾跳进了压行大坑，~~深陷其中难以自拔~~: )

压行的好处

现在的码风：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=200003;
int n,m,tot,fa[maxn];
struct node{
    int u,v,t;
    bool operator <(const node& r) const{return t<r.t;}
}e[maxn];
int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
signed main()
{
    scanf("%d%d",&n,&m);
    if(n==1) return puts("0"),0;
    for(int i=1,u,v,t;i<=m;++i) scanf("%d%d%d",&u,&v,&t),e[i]=(node){u,v,t};
    sort(e+1,e+m+1);
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=1,x,y;x=getfa(e[i].u),y=getfa(e[i].v),i<=m;++i) if(x^y){
        fa[x]=y;
        if(++tot==n-1) return cout<<e[i].t,0;
    }return puts("-1"),0;
}

Part.1 怎样减少不必要的语句

1.三目运算符：

简单来说，三目运算符，又称条件运算符，可以代替if，else；速度较if，else更快

使用方法：E.g：

bool cmp(node a,node b){//普通的cmp比较函数
    if(a.x==b.x) return a.y<b.y;
    else return a.x<b.x;
}

bool cmp(node a,node b){return a.x==b.x?a.y<b.y:a.x<b.x;} //三目运算符优化后

多个三目运算符套用：

a ? b : c ? d : e将按a ? b : (c ? d : e)执行

2.运算符优先级：

了解运算符优先级，减少冗余括号，不仅使你的代码更清新，还能使你不在csp初赛挂掉一道选择题

常用C++运算符优先级

括号无条件最优

一级：! ~ ++ -- - (类型)

!逻辑非
~按位取反
++/--自增自减
-负号
(类型)类型强转

二级：+ - * / %
三级：<< >>（左移右移）
四级：< <= > >= != ==
五级：& ^ |
```
&按位与
^按位异或
|按位或
```
六级：&& ||

七级：三目运算符？

a ? b : c ? d : e将按a ? b : (c ? d : e)执行

3.结构体运算符重载：

作用强大运用广泛，使代码更易编写，长度变短，逻辑更清晰

sort排序时，你固然可以使用cmp函数，但重载运算符也是一个好选择：

格式： https://www.cnblogs.com/lyttt/p/11774402.html

~~我不想写了，累了，毁灭吧。~~

Part.2 如何使你的码风紧凑

（压行的精华）

,很强大，可以连接多个语句，除了return，continue，break等。

当然，return puts("0"),0;这样压行是允许的，

所以你可以在线段树中这样写：if(lef<=xl&&rig>=xr) return sum[x]+=d*val[x],tag[x]+=d,void();。

为了节省变量/减小代码长度，你可以这样写：solve(read(),read());//read()读入数据。

巧妙的运用define和typedef同样是个好方法，但要注意打括号，否则会因为运算优先级问题而出现WA,UB。

常规操作for循环压行：for(int i=(build(root[0],1,len),1),tmp;i<=n;++i);（我的可持久化代码节选）

当然while也能压行，比如读入数据：while(scanf("%d%d",&u,&v)，(u+v))，只有当输入u，v皆为0时才会停止输入

在遍历前向星的时候也可以压行：for(int i=head[x],v;v=e[i].to,i;i=e[i].next)

有朋友问能不能int a=1,b=1,c=a+b？当然可以，我的splay就是这么压行的：int y=fa[x],z=fa[y],l=(ch[y][1]==x),r=l^1;，int y=fa[x],z=fa[y];

~~当然还有很多其他的压行方法，我懒不想写了~~

请注意，以下写法有爆0的风险：

函数嵌套使用，如solve1(solve2(x))，因为计算机不一定按照solve2，solve1的顺序运行，出现UB的可能性非常大。

sum[cnt]=sum[cnt++];这样的压行写法也是很危险的，不同评测机跑出的结果不同，前后都有cnt就不要用自加自减了（亲测，校oj、本地AC，洛谷CE）。

Part.3 压行实例

tarjan缩点代码：

void tarjan(int x){
    low[x]=dfn[x]=++cnt,vis[x]=1,stack[++index]=x;
    for(int i=head[x],v;v=e[i].to,i;i=e[i].next)
        if(!dfn[v]) tarjan(v),low[x]=min(low[x],low[v]);
        else if(vis[v]) low[x]=min(low[x],low[v]);
    if(low[x]==dfn[x]) for(++num;stack[index+1]!=x;--index) vis[stack[index]]=0,bel[stack[index]]=num;
}

树链剖分第一遍DFS

//正常版：
void dfs_1(int x){
    siz[x]=1,dep[x]=dep[fa[x]]+1;
    for(int i=head[x],v;v=e[i].to,i;i=e[i].next){
        dfs_1(v),siz[x]+=siz[v];
        if(!son[x]||siz[v]>siz[son[x]]) son[x]=v;
    }
}
//疯狂压行版：
//一行，就问还有谁？
void dfs_1(int x){for(int i=(siz[x]=1,dep[x]=dep[fa[x]]+1,head[x]),v;v=e[i].to,dfs_1(v),siz[x]+=siz[v],i;i=e[i].next) if(!son[x]||siz[v]>siz[son[x]]) son[x]=v;}

看到一个讨论，放一下自己的码风：

//你敢说这样压行不好看？
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,tot,fa[N];
struct node{
    int u,v,t;
    bool operator <(const node& r) const{return t<r.t;}
}e[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
signed main()
{
    cin>>n>>m;
    if(n==1) return puts("0"),0;
    for(int i=1,u,v,t;i<=m;i++) cin>>u>>v>>t,e[i]=(node){u,v,t};
    sort(e+1,e+m+1);
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=1,x,y;x=find(e[i].u),y=find(e[i].v),i<=m;++i) if(x^y){
        fa[x]=y;
        if(++tot==n-1) return cout<<e[i].t,0;
    }return puts("-1"),0;
}

附送一个极其有用的工具：

压行器

可以用来压行；

~~可以用来抄题解，结合ctrl+shift+a，改变你的码风；~~ （这是不被允许的！）；

当然，如果和我一样是英语菜鸡一只，在打atcoder比赛时，再也不用担心 latex 带来的换行符，压行+翻译绝配；

最后，放上那篇被吐槽的LCT代码。。

~~其实挺好康的，不是？~~

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
const int maxn=300003;
int sum[maxn],ch[maxn][2],fa[maxn],rev[maxn],a[maxn];
void getrev(int x){rev[x]^=1,swap(ch[x][0],ch[x][1]);}
bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
void pushdown(int x){if(rev[x]) getrev(ch[x][0]),getrev(ch[x][1]),rev[x]^=1;}
void pushup(int x){sum[x]=sum[ch[x][0]]^sum[ch[x][1]]^a[x];}
void pushtag(int x){if(!isroot(x)) pushtag(fa[x]); pushdown(x);}

void rot(int x){
    int y=fa[x],z=fa[y],l=ch[y][1]==x,r=1-l;
    if(!isroot(y)) ch[z][ch[z][1]==y]=x;
    fa[x]=z,fa[y]=x,fa[ch[x][r]]=y;
    ch[y][l]=ch[x][r],ch[x][r]=y;
    pushup(y),pushup(x);
}
void splay(int x){
    pushtag(x);
    while(!isroot(x)){
        int y=fa[x],z=fa[y];
        if(!isroot(y)) ch[y][0]==x^ch[z][0]==y?rot(x):rot(y);
        rot(x);
    }
}

void access(int x){for(int y=0;x;y=x,x=fa[x]) splay(x),ch[x][1]=y,pushup(x);}
void makeroot(int x){access(x),splay(x),getrev(x);}
int findroot(int x){access(x),splay(x);while(ch[x][0]) x=ch[x][0];return x;}
void split(int x,int y){makeroot(y),access(x),splay(x);}
void link(int x,int y){makeroot(y),fa[y]=x;}
void cut(int x,int y){split(x,y);if(ch[x][0]==y) ch[x][0]=fa[y]=0;}
signed main()
{
    int n,q; scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
    while(q--){
        int opt,x,y; scanf("%lld%lld%lld",&opt,&x,&y);
        if(!opt) split(x,y),cout<<sum[x]<<'\n';
        else if(opt==1){if(findroot(x)!=findroot(y)) link(y,x);}
        else if(opt==2) cut(x,y);
        else a[x]=y,access(x);
    }
    return 0;
}

~~我才不会承认这篇文章是用来抖机灵的。。~~