UOJ Logo huangsi的博客

博客

用最短的代码实现排序

2018-01-08 18:42:11 By huangsi

问题描述:在如下的函数体中添加内容,使S(l,r)a[]中的lr位置进行排序。

void S(int l,int r){}

一开始我觉得选择排序已经够短了。就像这样:

void S(int l,int r){for(int i=l;i<r;i++)for(int j=i+1;j<=r;j++)if(a[i]>a[j])swap(a[i],a[j]);}

这样一共只用了93B,好像已经不能再优化了(可能再卡一卡还是能略微小一些的,但是大的优化是不多了)。

后来我有了一个诡异的想法,可以巧妙地利用递归:

void S(int l,int r){if(r==l+1){if(a[l]>a[r])swap(a[l],a[r]);}else if(r>l+1)S(l,r-1),S(l+1,r),S(l,r-1);}

这是什么原理呢。。。大家一看就明白了吧。如果序列长度小于2,我们直接不管它。如果长度就是2,我们比较a[l]a[r]。如果长度大于2,我们进行一个递归。首先,递归排序S(l,r-1),目的是让最大值不出现在第一个位置。其次,递归排序S(l+1,r),把最大值放到最后一个位置。这样,a[l]a[r-1]就只有第l到第r-1的数了。最后,再调用一次S(l,r-1),完成排序。当然,不要在意它的时间复杂度。(逃

可是这样反而变长了啊。。。那我们再优化一下:

void S(int l,int r){if(a[l]>a[r])swap(a[l],a[r]);if(r>l)S(l,r-1),S(l+1,r);}

我们把r==l+1的条件去掉了。这样省掉了一个if和一个else。同时,由于这样的比较已经保证了a[r]不可能是最小值,第一次递归过后最小值一定在a[l],于是第三次递归也就不需要了。此外,r>l+1的条件也可以换成r>l,没有什么影响。

这份代码只有75B,完虐选择排序。同时,时间复杂度由$O(3^n)$优化到了$O(2^n)$。

这个问题是不是已经有人研究过了啊?如果大家有想法的话也可以和我交流。以及,有没有人会一个比选择排序更短的多项式算法啊。。。

UPD:现在最短的代码74B:

void S(int l,int r){swap(a[a[l]>a[r]?l:r],a[r]);if(r>l)S(l,r-1),S(l+1,r);}

以及,用指针继续缩短到68B:

void S(int*l,int*r){swap(*(*l>*r?l:r),*r);if(r>l)S(l,r-1),S(l+1,r);}

感谢大家的回复!

板子

2017-06-16 08:34:34 By huangsi

写在前面

#include <iostream>
#include <cstdio>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dwn(i,a,b) for(int i=a;i>=b;i--)
#define gma(x,y) x=max(x,y)
#define gmi(x,y) x=min(x,y)
using namespace std;
int main(){
    return 0;
}

邻接表

#define enu() for(node *o=h[u];o;o=o->next)

struct node{
    int v;
    node *next;
}pool[2*MAXN],*h[MAXN];
int cnt;
void addedge(int u,int v){
    node *o=&pool[cnt++];
    o->v=v,o->next=h[u],h[u]=o;
    o=&pool[cnt++];
    o->v=u,o->next=h[v],h[v]=o;
}
#define enu() for(node *o=h[u];o;o=o->next)

struct node{
    int v,d;
    node *next;
}pool[2*MAXN],*h[MAXN];
int cnt;
void addedge(int u,int v,int d){
    node *o=&pool[cnt++];
    o->v=v,o->d=d,o->next=h[u],h[u]=o;
    o=&pool[cnt++];
    o->v=u,o->d=d,o->next=h[v],h[v]=o;
}

树状数组

struct FenwickTree{
    int p[MAXN];
    void Add(int id,int x){
        while(id<=n)p[id]+=x,id+=id&(-id);
    }
    int Query(int id){
        int s=0;
        while(id)s+=p[id],id-=id&(-id);
        return s;
    }
};

网络流

#define enu() for(node *o=h[u];o;o=o->next)

struct node{
    int v,d;
    node *next,*rev;
}pool[2*MAXN],*h[MAXN];
int cnt;
void addedge(int u,int v,int d){
    node *o=&pool[cnt++];
    o->v=v,o->d=d,o->next=h[u],h[u]=o;
    o=&pool[cnt++];
    o->v=u,o->d=0,o->next=h[v],h[v]=o;
    h[u]->rev=h[v],h[v]->rev=h[u];
}

并查集

struct UFS{
    int p[MAXN];
    UFS(){memset(p,-1,sizeof(p));}
    void clear(){memset(p,-1,sizeof(p));}
    inline bool Union(int x,int y){x=Find(x),y=Find(y);if(x!=y){p[x]=y;return 1;}return 0;}
    int Find(int x){if(p[x]<0)return x;return p[x]=Find(p[x]);}
};

读入优化(int)

int _(){
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

读入优化(long long)

long long _(){
    long long x=0;
    int f=1;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

输出优化

void __(ll x){
    if(!x){puts("0");return;}
    char c[30]={};
    int i=0;
    while(x)c[i++]=x%10+'0',x/=10;
    while(i)putchar(c[--i]);
    puts("");
}

线性筛

namespace Mobius{
    int n,t,miu[MAXN],phi[MAXN],pri[MAXN],cnt,d[MAXN];
    void Init(){
        miu[1]=1;
        phi[1]=1;
        for(int i=2;i<=n;i++){
            if(!d[i])pri[++cnt]=i,d[i]=cnt,miu[i]=-1,phi[i]=i-1;
            for(int j=1;i*pri[j]<=n&&j<=d[i];j++){
                t=i*pri[j];
                d[t]=j;
                miu[t]=j<d[i]?-miu[i]:0;
                phi[t]=j<d[i]?phi[i]*(pri[j]-1):phi[i]*pri[j];
            }
        }
    }
}

倍增LCA

#define enu() for(node *o=h[u];o;o=o->next)if(o->v!=pnt[u])

namespace LCA{
    const int LOG=17,MAXL=20;
    int lpnt[MAXN][MAXL];
    void work(int u,int lev){
        if(lpnt[u][lev])lpnt[u][lev+1]=lpnt[lpnt[u][lev]][lev];
        enu()work(o->v,lev);
    }
    int LCA(int u,int v){
        if(dep[u]<dep[v])swap(u,v);
        dwn(i,LOG,0)if(lpnt[u][i]&&dep[lpnt[u][i]]>=dep[v])u=lpnt[u][i];
        dwn(i,LOG,0)if(lpnt[u][i]!=lpnt[v][i])u=lpnt[u][i],v=lpnt[v][i];
        if(u==v)return u;return pnt[u];
    }
    void Init(){rep(i,1,n)lpnt[i][0]=pnt[i];rep(i,0,LOG)work(1,i);}
}

ST表LCA

namespace LCA{
    const int LOG=22,MAXL=25;
    int ST[MAXL][2*MAXN],pos[MAXL][2*MAXN],num[MAXN],pnt[MAXN],Log[2*MAXN],Depth[MAXN];
    int dfn;
    void dfs0(int u,int dep){
        num[u]=++dfn,Depth[u]=dep,pos[0][dfn]=u;
        ST[0][dfn]=dep;
        for(node *o=h[u];o;o=o->next)if(o->v!=pnt[u]){
            pnt[o->v]=u;
            dfs0(o->v,dep+1);
            ST[0][++dfn]=dep,pos[0][dfn]=u;
        }
    }
    void Init(){
        for(int i=0;i<=LOG;i++)for(int j=1;j<=2*n;j++)ST[i][j]=0;
        dfn=pnt[1]=0;
        dfs0(1,1);
        for(int i=0;i<=20&&(1<<i)<=dfn;i++)
            for(int j=(1<<i);j<(1<<i+1)&&j<=dfn;j++)Log[j]=i;
        for(int i=1;i<=20;i++)
            for(int j=1;j+(1<<i)<=dfn+1;j++){
                if(ST[i-1][j]<ST[i-1][j+(1<<i-1)])ST[i][j]=ST[i-1][j],pos[i][j]=pos[i-1][j];
                else ST[i][j]=ST[i-1][j+(1<<i-1)],pos[i][j]=pos[i-1][j+(1<<i-1)];
            }
    }
    int LCA(int u,int v){
        if(u==v)return u;
        int x=num[u],y=num[v];
        if(x>y)swap(x,y);
        y++;
        int t=Log[y-x];
        if(ST[t][x]<ST[t][y-(1<<t)])return pos[t][x];else return pos[t][y-(1<<t)];
    }
}

不算预处理,什么时候线段树比ST表还快?

2017-05-22 11:59:46 By huangsi

当你在上面跑费用流的时候。

BJOI2017day1

2017-04-17 07:54:32 By huangsi

今天(4月16日)总算到了BJ省选day1的日子啦,一大早起来去北WA路考试。到了以后晃了两圈按照要求在机器上装了个Dev-C++5.11就没有事做,过了一会看到别人已经在看PDF了,这才发现考试开始了。。。

第一题。makina?一看这出题人就是个死宅。题目背景好几页,读了五分钟看不懂,果断弃。第二题描述很简练。树分治?想了那么三分钟觉得挺可做的,就去看第三题。第三题是个字符串题,没怎么想,推了推第二题,就开始写,觉得几个数组推一推就搞定了。这时已经八点二十了。问了一下栈的大小,结果两个监考员嘀咕了半天,告诉我在Windows下用cena评测。算了不耽误时间了,BFS保平安吧。

T2写了一会发现分治后数组上扫好像不那么显然,可能要一个set。马上又发现智障了,复杂度还不对,应该是线段树。20w,2s,不开O2,$log^2 n$,线段树?看来要被卡常卡掉几个点了。犹豫了一会,开始写。各种困,各种不想写。

写完了开始编译。max undefined?5.11的锅吧,自己写了一个。queue undefined?什么鬼啊。sort也undefined?总算发现using namespace std;没开,智障。。。十点刚过的时候T2过了样例,敲了个对拍和datamaker。小数据都顺利地过了。测了个20w,发现树分治跑了2s多。又测了一组链的情况,卧槽,22s!这就肯定不是常数问题了,一定是复杂度出了锅。然后各种调试,各种计数器。。。程序还TM跑的那么慢。。。中间等对拍跑的时候看了看第三题,发现前六十分就是裸的AC自动机,很好拿。十点五十的时候我想要是到了十一点T2还没有进展就果断弃聊,先干掉AC自动机。

终于到了十点五十七分,我发现了线段树的Change和Query居然一共调用了60多亿次!计数器都爆int了,开了long long才记下来。线段树还能错?我盯着哪个Query检查。if(left==right)return o->d;???就是说Query的时候一定会递归到底。MDZZ,赶紧改过来。又跑了一组数据。WA了?原来Change也错了,改过来,测了一下极限数据,跑了2.4s,凑活了吧,就当会T两个点。

这时十一点一刻。花了二十分钟把AC自动机写出来,测了测过了样例,应该能有60分。后40分是矩阵快速幂?这跟去年的打字机有什么区别啊,出题人也太省事了吧。后面有20还挺水的,马上开始矩阵快速幂。很快写出来了,结果快速幂部分莫名RE。怎么改也不对,把结构体名字从matrix改成Matrix也没用。最可气的是就算把文件输入输出全注释掉,改成屏幕读写,一运行,直接就RE,连数据都还没有输入。。。在RE的地方前面加个while(1);就好了,莫名其妙。。。折腾来折腾去也没有结果。

过了一会已经十二点半了,想着今天题这么水应该有好多上200的吧。看来要滚粗了。十二点三十四分的时候弃疗,去写T1的30分特大暴力。这时周围的键盘声已经没有那样密集了,很多人已经开始扫雷了。使劲码,WA了几次,到十二点五十几的时候总算过了样例。然后迅速看了看文件名,输入输出,把代码复制进提交文件夹里。看了看表,十二点五十九分零四秒!然后在草稿纸上写下大大的GG,瘫倒在座位上。

预估30+80+60=170

吃饭时moorhsum说他炸了。他跟QHF(初中母校)的wys(和某位大神的姓名缩写重名的另一位大神)互相赌20块钱谁考得低。。。

吃完饭在操场上转了一圈,觉得最放不下心的是AC自动机没对拍。想想也没有关系,今年滚粗了就好好学课内,明年再来。。。

过了好久总算测完了,居然是25+90+60=175,T1暴力有一个地方把n写成m了,WA了5分(居然只少了5分),T2只T了一个点。hld67890好强啊,220rank3。上200的人其实只有4个,看来BJ变得比去年弱了。

正解T1管道取珠,$n^4$的DP。T2单调队列,T3就是快速幂。还是太弱了,T1T2正解都想不出来。

今天还算不错吧,并列rank7,争取下周好好考,进BJ队还是有那么一点点希望的。

huangsi Avatar