如何愉快的完成 Linux 的入门

写在开头 身为一名Oier身边有许多优秀的同学想学习 Linux 却又因许多问题不敢学或者尝试后放弃,转而每天吐槽Dev的日常爆炸,在作为一个Linux重度使用党的同时也不由得为惊奇,在结和这些优秀的同学所遇到的问题与自己的经历时,发现一些常见的问题,便写出来给初学者们应对

系统选择与安装

系统选择


看过一个大佬,他使用的是一款贼高端的那种搞网络渗透的 Linux 的系统,我问他为什么装这个,然后 他回答我:”装逼啊” 我:”????”(黑人问号脸.jpg) 显然这位大佬装逼的心我们是管不了的 但是如果你是抱着一颗想要学习 Linux 的态度,还这么选系统的话就凉了像上面这种系统会把你给吓跑的 所以说如果你是一个新手的话,该怎么选择系统呢:
  1. 有着良好的论坛体系或者用户基数较多的系统,因为这样子大多数你遇到的问题,网上都能够找到答案
  2. 选择一款有着良好桌面环境支持的,我知道,怎么说有些人就会喷,说用Linux用什么桌面环境,实则不然,如果最为日常生活使用的话,没有图形化界面终究会遇到一些麻烦
  3. 有着优秀中文环境支持的,虽然说你学Linux最后肯定要车技英语,但是开头先用良好的中文,起码会降低许多误操作的可能
基于这三个基础条件,博主这里有三个比较推荐的系统当然也许还有更好的,但是这是博主用过的,我敢去推荐,当然,你不喜欢也无妨: Deepin, Debian , Ubuntu

安装


首先,如果你像好好学Linux,先将Windows删除,请不要说你需要用,学完在装也无妨(博主就是这样的),毕竟有些工作确实只有Windows能做,删除Windows后,你就会避免遇到什么问题都去Windows,而只有”学习”的时候才会用Linux,这种情况当然学不会,你需要将 Linux 融于生活,这样才能学的更好 其他的坑,自己踩过了,才能明白

日常使用

这是一个大坑,许多人装系统一路过来没毛病,到了这一步,又回到了Win中

命令使用与背


首先 Linux 与大多数 Unix-Like 系统虽然有桌面环境,但是不使用命令来保证日常使用的正常的话,确实很艰难,但是若果讲命令融于日常使用当中,便不会艰难 首先,刻意去背这些命令与用法肯定是无效的,首先你要知道,Linux下大多数命令的通用方式,比如 -是干什么的,--是干什么的呀 之类的 然后用到什么,学什么,多用几次,也就记下来了,你光背不用,不仅忘的快,还不知道什么时候用

实践


学习完必定要有实践的过程,如果你不去实践的话,那么终究是纸上谈兵,你无法熟练的应对各种情况 但是实践总得有目标,你需要以你现在的常有项作为开始,如果你是一名Oier的话,可以从配置 Vim 学习 g++ 与 gdb 开始,如果你是一名网站维护者,可以试着搭一下服务器等等诸如此类的东西

最后要说

首先,这篇博客是基于博主与博主身边的人发生的事情写的,也许他不适合你,如果你有别的方法,欢迎在评论去留言 其次,学习任何一门的东西都不会简单,不开始,不尝试就不可能学会 ]]>

排序算法 — O(d(r+n)) — 基数排序

写在前面


基数排序Redix Sort,是为数不多不是基于比较的排序,至今此类我们学过的,也就只有基数排序和桶排不基于比较,桶排的效率自然快,但是对内存的消耗不容小视,基数排序则在空间和时间都有这不错的表现,在大多数情况基本于归并排序速度相近,如果你会一些高端的优化的话,他甚至能够吊打桶排

基数排序

时间复杂度: O( d ( r + n ) )
空间复杂度: O( rd + n )
相信你已经根据前文知道,基数排序,不是基于比较的排序,哪们我们如何排序呢? 我们知道桶排的思想是确定其有或没有,然后遍历 但是我们能不能简化?简化成将每一位桶排? 当然可以,这就是基数排序 我们在每一位上进行桶排,让后进行下一位,直到最所有数高位 听起来貌似是很简单的问题,不过现在有一个重要的问题,怎么分离位?

十进制分离法


我们的数字是十进制,而且十进制分离位在C++中依旧很方便 代码:
#include <cstdio>
#include <cstring>
using namespace std;
int n;
int a[110000];
int tmp;
int cnt[10],last_cnt[10];;
int last_redix[10][110000];
int redix[10][110000];
inline int ws(int t,int n){
    t--;
    while(t--){
        n/=10;
    }
    return n%10;
}
// ws 分离位数
bool x;// 判断最高位
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        tmp=ws(1,a[i]);
        last_redix[tmp][++last_cnt[tmp]]=a[i];// 完成第一位的桶
    }
    for(int t=2;;t++){
        x=false;
        for(int i=0;i<=9;i++){
            for(int j=1;j<=last_cnt[i];j++){// 按照上一位的顺序,不然排序顺序会乱
                tmp=ws(t,last_redix[i][j]);
                if(tmp!=0) x=true;
                redix[tmp][++cnt[tmp]]=last_redix[i][j];// 桶排
                //j++;
            }
        }
        if(!x) break;
        memcpy(last_redix,redix,sizeof(redix));// 复制当前到上一次
        memcpy(last_cnt,cnt,sizeof(cnt));
        memset(cnt,0,sizeof(cnt));
    }
    for(int i=0;i<=9;i++)// 输出
        for(int j=1;j<=last_cnt[i];j++)
            printf("%d ",last_redix[i][j]);
}

二进制分割法


但是显然这种位数分离法比较耗时,要是我们能够快一点…… 等一下,二进制时直接位运算就可分离二进制位了啊 代码:
#include <cstdio>
#include <cstring>
using namespace std;
int n;
int a[110000];
int tmp;
int cnt[10],last_cnt[10];;
int last_redix[2][1100];
int redix[2][1100];
inline int ws(int t,int n){
    t--;
    while(t--){
        n/=10;
    }
    return n%10;
}
bool x;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        //tmp=ws(1,a[i]);
        last_redix[(a[i])&1][++last_cnt[(a[i])&1]]=a[i];
    }
    for(int t=1;t<=31;t++){
        //x=false;
        for(int i=0;i<=1;i++){
            for(int j=1;j<=last_cnt[i];j++){
                //tmp=ws(t,last_redix[i][j]);
                //if(tmp!=0) x=true;
                redix[(last_redix[i][j]>>t)&1][++cnt[(last_redix[i][j]>>t)&1]]=last_redix[i][j];
                //j++;
            }
        }
        //if(!x) break;
        memcpy(last_redix,redix,sizeof(redix));
        memcpy(last_cnt,cnt,sizeof(cnt));
        memset(cnt,0,sizeof(cnt));
    }
    for(int i=0;i<=1;i++)
        for(int j=1;j<=last_cnt[i];j++)
            printf("%d ",last_redix[i][j]);
}
原理和上面一样,分离位数请参考下一篇: 位运算

End

]]>

Luopu P1525 关押罪犯 —— 初学二分图

二分图

二分图是什么?可以吃吗
可以吃而且很好吃 当然不可以吃,但是使用起来可是个好东西 对于一张无向图,如果他的所有的点可以分成两个点集,且每个点集内的点没有边相连,我们就称这张图为二分图 对于判定二分图,我们有一种非常简单的方法 —— 染色法

染色法


染色?染什么色?
实际上如果有精通小学奥数的同学应该知道,我们在解决一类问题的时候,就会用到染色法来分类,当然,今天的原理,和那个染色法有一点类似 根据二分图的定义每个点集内的点没有边相连,我们可以知道,和一个点相连的两条边一定不在同一个集合中,那么如何判断是不是在同一集合呢? 我们就可以吧同一类的染上一个颜色,然后遍历图,如果我们在遍历某个点的时候,发现下一个点已经遍历过了,且和当前点颜色一样,那么这一定不是二分图 代码如下:
inline bool bfs(int u){// u 起始点
    head=tail=0;// 队列初始化
    col[u]=1;// 初始化起点
    q[head]=u;// 加入对头
    while(head<=tail){// 标准不解释
        int top=q[head];// 去头部
        for(int i=ehead[top];i;i=e[i].next){// 标准遍历不解释
            int to=e[i].to;
            if(col[to]==0){// 如果没有被访问过
                col[to]=3-col[top];// 染色
                q[++tail]=to;// 加入队列
            }
            else {// 访问过
                if(col[to]==col[top]) return false;// 颜色相同当然不是二分图了
            }
        }
        head++;
    }
    return true;
}
但是有的时候,输入数据不保证为一张图,这个时候就要遍历点,如果当前点没有访问过,那么就从当前点起始染色

Luopu P1525 关押罪犯

二分查找二分图 题目链接: [https://www.luogu.org/problemnew/show/P1525]
第一眼看过去,这是什么?可和二分图有啥关系 然后看了看书,突然就明白了 我们可以二分事件的最大影响值,把每个罪犯看做一个点,如果影响值大于mid那么就链接,否则当不存在这条边 所以这道题目就是一个二分模板+染色判二分图

程序


#include <cstdio>
#include <cstring>
using namespace std;
int n,m;
int u,w,v;
int l,r,mid,max;
// edge start
struct edge{
    int to,next,val;
}e[210000];
int ehead[21000],ecnt;
inline void add(int now,int to,int val){
    ecnt++;
    e[ecnt].to=to;
    e[ecnt].val=val;
    e[ecnt].next=ehead[now];
    ehead[now]=ecnt;
}
// edge end
// edge 链表建图部分
// queue start
int q[110000],head,tail;
int col[110000];
inline bool bfs(int u){
    head=tail=0;
    col[u]=1;
    q[head]=u;
    while(head<=tail){
        int top=q[head];
        for(int i=ehead[top];i;i=e[i].next){
            int to=e[i].to;
            if(e[i].val>=mid){// 大于等于mid时建边
                if(col[to]==0){
                    col[to]=3-col[top];
                    q[++tail]=to;
                }
                else {
                    if(col[to]==col[top]) return false;
                }
            }
        }
        head++;
    }
    return true;
}
// queue end
// queue 染色法判图
inline bool rs(){
    for(int i=1;i<=n;i++){
        if(col[i]==0)
            if(!bfs(i)) return false;
    }
    return true;
}
// rs 遍历点
inline void init(){
    memset(col,0,sizeof(col));
}
// init 预处理
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        max=max>w?max:w;// 保留最大用于二分上限
        add(u,v,w);
        add(v,u,w);
    }
    l=0,r=max+1;// 标准二分
    while(l+1<r){
        init();
        mid=(l+r)>>1;
        if(rs()) r=mid;// 如果可以达成[二分图成立] 则缩小范围
        else l=mid;// 不可以就扩大范围
    }
    printf("%d",l);
}
请勿抄袭

END

]]>

科学解决 RMQ 问题 — 线段树/(ST/稀疏表)/分块

RBQRMQ

区间最值问题
大概就是那种给你一串数字,然后问你在区间[l,r]内,求最小值或最大值 一般,我们的操作,就是暴力枚举 然后你就光荣的TLE/MLE 然后让我们来说说区间问题的三种解法—线段树/ST表与分块

线段树


预处理: O( n*log(n) )
查询: O( log(n) )
单点更新: 支持,不破坏查询复杂度
写的爽,调的更爽
线段树是一种数据结构 首先我们需要了解一种东西,哈弗曼树 显然,对于一颗二叉树,如果一个节点号为n那么它的左节点是2n,右节点是2n+1 然后我们就可以愉快的存树了 然后什么是线段树呢? 吃的 它是能够维护一定区间的树 他的根节点是[L,R](最左和最右)的最优值 然后左节点是[L,(L+R)/2]的最优值 右节点是[(L+R)/2+1,R]的最优值 往后以此类推 直到l==r为止 简单代码如下:
这个代码对应[https://www.luogu.org/problemnew/show/P4644]这道题
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,e;
struct whi{
    int left,rig,cost;
}a[11000];
int f[110000];
int tree[11000000];
bool cmp(whi a,whi b){
    return a.rig<b.rig;
}
// 创建
void build(int p,int l,int r){// p 当前下标 l 左端点 r 右端点
    if(l==r) {tree[p]=f[l];return ;}
    build(p<<1,l,(l+r)>>1);
    build(p<<1|1,((l+r)>>1)+1,r);
    tree[p]=min(tree[p<<1],tree[p<<1|1]);
}
// 更新单点
void update(int p,int l,int r,int now,int val){// p 当前下表 l 当前左端点 r 当前右端点 now 当前点的边界 val 更新的值
    if(l==r&&l==now){tree[p]=val;return ;}
    if(now<=((l+r)>>1)) update(p<<1,l,(l+r)>>1,now,val);
    else update(p<<1|1,((l+r)>>1)+1,r,now,val);
    tree[p]=min(tree[p<<1],tree[p<<1|1]);
}
// 求区间最值
int query(int p,int l,int r,int ll,int rr){//p 当前下表  l 当前左端点 r 当前右端点 ll 需求左端点 rr 需求右端点
    if(ll<=l&&rr>=r){return tree[p];}
    int ans=0x7fffffff,mid=(l+r)>>1;
    if(ll<=mid) ans=min(ans,query(p<<1,l,mid,ll,rr));
    if(rr>mid) ans=min(ans,query(p<<1|1,mid+1,r,ll,rr));
    return ans;
}
int main(){
    memset(f,0x3f,sizeof(f));
    scanf("%d%d%d",&n,&m,&e);
    m++;e++;
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&a[i].left,&a[i].rig,&a[i].cost);
        a[i].left++;a[i].rig++;
    }
    sort(a+1,a+n+1,cmp);
    /*for(int i=1;i<=n;i++){
        printf("%d %d %d\n",a[i].left,a[i].rig,a[i].cost);
    }*/
    f[m-1]=0;
    build(1,m-1,e);
    for(int i=1;i<=n;i++){
        if(a[i].rig<m) continue;
        if(a[i].left<=m) f[a[i].rig]=min(f[a[i].rig],a[i].cost);
        else f[a[i].rig]=min(f[a[i].rig],query(1,m-1,e,a[i].left-1,a[i].rig)+a[i].cost);
        update(1,m-1,e,a[i].rig,f[a[i].rig]);
    }
    if(f[e]>=1061109567) printf("-1");
    else printf("%d",f[e]);
}
当然这个并不是线段树的完整用法wq 更详细的用法,请看下篇题解

ST/稀疏表

> 速度虽快,更新却难
预处理: O( n*log(n) )
查询: O( 1 )
单点更新: 支持,需重新预处理
ST/稀疏表(以下统称)ST表,是一种基于倍增思想的玄学算法 比如说我们用f[i][j]储存从 i 位置开始的 2^j个数中的最大值 那么转移的时候我们可以把当前区间拆成两个区间并分别取最大值 查询先计算出 log2(区间长度) 然后对于左端点和右端点分别进行查询,这样可以保证一定可以覆盖查询的区间 然后你就会发现一堆log和换底公式出现于你的程序中 感性理解吧~ 但是不难理解
对应例题:[https://www.luogu.org/problemnew/show/P3865]
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,l,r;
int a[110000];
int f[110000][110];
int st_query(int l,int r){
    int k=log(r-l+1)/log(2);
    return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        f[i][0]=a[i];
    }
    int t=log(n)/log(2)+1;
    for(int j=1;j<t;j++){
        for(int i=1;i<=n-(1<<j)+1;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&l,&r);
        printf("%d\n",st_query(l,r));
    }
}
看起来是不是相当简单qwq 但是要千万注意log时该加1时不该加时不加1

分块


高端的模拟
预处理: O(n)
查询: O(sqrt(n))
更新: O(sqrt(n))
先说说什么是分块算法吧 分块,顾名思义,就是将一个数列分成几块单独处理,比如讲[1,5]分成三块就是[1,2] [3,4] [5]这三个 那么我们查找[1,3]的最小值,只需要查找第一个与第二个块的最小值 经过一些证明,我们可以知道,在分成sqrt(n)块的情况下最优 所以就有了复杂度中的一堆sqrt(n) 那么代码我相信大家心里都有数了 那么和线段树一样,代码下篇题解讲,毕竟都是一道题目嘛wq

End


这几种解法,只是一种板子,而真正的RMQ算法,可能会结合多种东西,或者被多种东西所结合,所以说活学活用是最重要的,无论如何,刷题是最重要的 “Happy Coding Life” ]]>

初学快速幂 — CodeVS 3500 快速幂入门

快速幂

long long ans=1;
for(int i=1;i<=p;i++){
     ans*=a;
     ans%=k;
}
说起求幂,大多数时候,我们用的都是上面这个简单通俗易懂是人都会的暴力循环 但是时间还是相当难受的,譬如求2^2000000%100,多来几次,你的时间就会很感动温暖人心了 所以我们需要优化

怎么优化?


2^n*2^m=2^(n+m)
这个东西大家都学过也都了解,那么我们今天就从这里优化 对于2^p一定有2^p=2^(p/2)+2^(p/2) 比如2^8我们可以拆成2^8=2^4*2^42^4=2^2*2^2,所以三次循环就可以算出原来要8次循环的运算,看起来是不是很合算~

CodeVS 3500 快速幂入门

题意就是纯属模板题木,不过千万不要忘记了要取模

代码


#include <cstdio>
#include <cstring>
using namespace std;
long long a,b,c,ans=1;
int main(){
    scanf("%lld%lld%lld",&a,&b,&c);
    while(b>0){
        if(b&1) ans=((ans%c)*(a%c))%c;
        b>≥1;
        a=(a*a)%c;
    }
    printf("%lld",ans%c);
}
]]>

POJ 3974 Palindrome 回文子串 — 初学Manacher算法

回文的判断 回文数作为一种有着特别性质的数,自然是出题人钟爱的类型,那么,我们应该如何判断呢回文字符串呢? 实际上最朴素的办法就是挨个枚举中间点 表面上看似O(n^2) 实际上更加复杂 为什么呢? 因为回文子串有两种:

  1. 奇数回文,以一个字符为中心
  2. 偶数回文,以中间空格为中心
所以我们除了遍历数字,还要遍历空格… 显然这种算法耗时太大了,我们需要对其进行优化,于是就有了我们今天的主题:Manacher算法

Manacher?

老牛拉破车马拉车算法
为了语言方便,下文全部称Manacher马拉车(手动滑稽) 我们知道回文字符串有着对称性,也就是说,如果目前已知的回文子串中,左边还有一个回文子串,那么右边也会有一个相同长度的回文子串 这样一来,我们的中间的遍历过程会少许多,因为在知道了对称状况下,就可以知道目前以这个位置展开的回文子串最小长度 但是这个方法随之而来的还有两个问题:
  • 偶数回文的处理方法
  • 当前的位置不在已知回文串内

偶数串回文


实际上这个问题是非常好解决的,我们将其中的空隙全部加上相同的符号,问题就被成功的解决了qwq

越界


这问题可谓是相当的好解决与不好解决了,我们会遇到的有三种情况
  1. 回文已知长度在最右边界内 这种状况直接找
  2. 回文长度超过边界 这个时候我们就要注意我们能够推理出来的长度只能到达边界,后面之内去找
  3. 当前位置不在已知回文串内 这个就只能从1开始找了…
代码:
int mlc(char *a){// *a 要处理的字符串
                int len=strlen(a),blen=0;// len 处理字符串长度
                char b[2100000];
                memset(b,0,sizeof(b));//清空
                for(int i=0;i<len;i++){//加入#
                                b[blen++]='#';
                                b[blen++]=a[i];
                }
                b[blen++]='#';//别忘了结尾的
                int cen,mrig,reslen,rescen;// rescen已知最长的中间,reslen已知最长的长度,mrig最右端点,cen目前最右端点的重点
                cen=mrig=reslen=rescen=0;
                memset(p,0,sizeof(p));
                for(int i=0;i<blen;i++){
                                p[i]=mrig > i? min(p[2*cen-i],mrig-i) : 1;// 自己结合上文理解,算法核心
                                while(b[i+p[i]]==b[i-p[i]]&&i-p[i]>=0&&i+p[i]<blen) p[i]++;//开始模拟
                                if(mrig<i+p[i]) {//更新数值
                                                mrig=i+p[i];
                                                cen=i;
                                }
                                if(reslen<p[i]) {
                                                reslen=p[i];
                                                rescen=i;
                                }
                }
                return reslen-1;//别忘了减去#
}

题目

题目链接:[http://poj.org/problem?id=3974]
题目的大意就是求最长回文子串,对于这道题目,我们可以套取上面的算法模板 需要注意的是,尽可能不用STL写,常数过大

END

]]>

初学数据结构:字符串哈希 — Luogu P3370

字符串哈希 在 初学数据结构:哈希表的运用 — POJ 3349 Snowflake Snow Snowflakes 一文中,我们曾提及哈希表的概念。那么,什么是字符串哈希呢? 字符串哈希可以理解为一个P进制的数字,其哈希函数如下

H(i)=( H(i-1)*p+a(i) )%mod
其中i表示从1 – i i-1表示从1 – i-1 a(i) 表示这个字符的值(通常取acill码) p p进制数 mod 取模防止爆炸 仔细一看是个什么???进制转换! 经过这个函数基本上每个字符串都会对应一个整数
是不是有点像 康拓展开? 实际上康拓展开也是一种设计的十分好的哈希
可是我们依然会发现,得出来的值还是有一定几率重的,这个状况就叫做哈希碰撞 一个哈希函数产生碰撞的可能性越低,我们就说这个哈希函数设计的越好 那么如何使自己的字符串哈希函数尽可能的变好呢? 如果mod与p是大质数,那么碰撞可能性会很低Qwq 但是这样依然有可能重复,所以我们一般用两个哈希函数,只有两个值相等时才判等

【模板】字符串哈希

明白了概念就来到模板题目把

题目


题意真的是水到了一个境界,所以我们直接上代码吧qwq

代码


#include <cstdio>
#include <cstring>
using namespace std;
int n;
int p=19260817,mod=1000007,temp,temp2,cnt=0;
int p2=99983,mod2=10000007;
// 双哈希
char a[1600];//读入用
long long hash_tmp[1600],hash_tmp2[1600]// 计算哈希;
bool hash[1100000],hash2[11000000];// 哈希表
long long H(){//第一个哈希函数
    int len=strlen(a+1);
    for(int i=1;i<=len;i++){
        hash_tmp[i]=(hash_tmp[i-1]*p+a[i])%mod;
    }
    return hash_tmp[len];
}
long long H2(){//第二个哈希函数
    int len=strlen(a+1);
    for(int i=1;i<=len;i++){
        hash_tmp2[i]=(hash_tmp2[i-1]*p2+a[i])%mod2;
    }
    return hash_tmp2[len];
}
int main(){// 读入
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",a+1);
        temp=H();
        temp2=H2();
        if((!hash[temp])||(!hash2[temp2])){// 有任意一个没有出现过都表示这个字符串没有出现过
            hash[temp]=true;
            hash2[temp2]=true;
            cnt++;
        }
    }
    printf("%d",cnt);
}

END

]]>

NOIP 2011 普及组 第三题 瑞士轮

认真读题很重要

简单分析


题目链接:[https://www.luogu.org/problemnew/show/P1309]
很容易发现,这道题目考察的排序,排序我们第一个肯定想到的是sort或者是归并排序,的确时间复杂度分别是O(n log2(n) )O(n log(n) )可如果是多次计算呢? 排除快排是因为不稳定性 所以总时间复杂度约为: sort O( r*2n^2*log2(2n) ) 归并 O( r*2n^2*log(2n) ) 看看数据范围emmmm 据说这样会 60 分,剩下的你懂的 所以我们需要优化 很显然sort已经没有优化的余地了,所以我们要从归并考虑 然后我们发现每次增减分的数组是单调的 也就是说我们只需要在开始的时候全部排序,后面我们每次只需要花O(n)的时间合并即可 这样子的时间复杂度约为:O( r*n^2 ) 稳如老狗啊!!!

代码


#include <cstdio>
#include <algorithm>
using namespace std;
int n,r,q;
struct node {
    int n,s,p;// n 号码 s 分数 p 能力
}a[210000],left[110000],right[110000];
int lcnt,rcnt,cnt,result_start;
// cmp 不解释
bool cmp(node a,node b){
    if(a.s==b.s) return a.n<b.n;
    else return a.s>b.s;
}
// 合并区间,参照归并排序
void marge(int left_start,int right_start){
    result_start=1;
    while(left_start<=n&&right_start<=n){
        if(cmp(left[left_start],right[right_start])) a[result_start++]=left[left_start++];
        else a[result_start++]=right[right_start++];
    }
    while(left_start<=n) a[result_start++]=left[left_start++];
    while(right_start<=n) a[result_start++]=right[right_start++];
}
int main(){
// 读入
    scanf("%d%d%d",&n,&r,&q);
    for(int i=1;i<=2*n;i++){scanf("%d",&a[i].s);a[i].n=i;}
    for(int i=1;i<=2*n;i++) scanf("%d",&a[i].p);
    sort(a+1,a+1+2*n,cmp);
    for(int i=1;i<=r;i++){
        lcnt=rcnt=0;// 模拟比赛过程
        for(int j=1;j<=2*n;j+=2){
            if(a[j].p>=a[j+1].p){
                a[j].s+=1;
                //printf("%d\n",++cnt);
                left[++lcnt]=a[j];right[++rcnt]=a[j+1];
            }
            else{
                a[j+1].s+=1;
                //printf("%d\n",++cnt);
                right[++rcnt]=a[j];left[++lcnt]=a[j+1];
            }
        }// 排序不解释
        if(i==1) sort(a+1,a+1+2*n,cmp);
        else marge(1,1);
    }
    printf("%d",a[q].n);
}

End


灵活运用每一种算法是一个非常重要的艺术 ]]>

初学数据结构:哈希表的运用 — POJ 3349 Snowflake Snow Snowflakes

哈希表?

2018.3.10 链表考试 解题报告 中的第一题,所用到的就是哈希表
哈希表,Hash表,又称散列表,是一种基础数据结构,我们使用这个结构是为了让我们在查找或者比对的时候缩小范围以优化时间 其原理大致为,我们将我们要插入的数据经过一些运算并对大质数取模后(哈希函数)得到一个数,我们会直接在head数组中查找其是否存在,存在后在进行比对,不存在则插入 如果哈希函数后的值碰撞了怎么办? 所以我们需要使用链表,对每一个哈希值我们都建一个链表,然后进行查找即可,在哈希函数碰撞少的时候,其查询与插入时间最优复杂度为O(1),平均复杂度是O(n/p)其中n是哈希过后的最大值,p是我们将要取模的大整数

Snowflake Snow Snowflakes

题目链接:[http://poj.org/problem?id=3349]
实际上看到这个题目我第一秒想到的是Snow Halation

简单翻译


我们要寻找相同的雪花 雪花有六个边,边长只要按顺时针或者逆时针顺序比对出来任意一个相同我们就说两个雪花相同(开头不一定在第一个数

简单思路


很明显,这是一道哈希表的问题,但是我们应当注意的是我们需要创建一个哈希函数 首先因为有多个物品,那么求和是肯定的,但是还是有可能产生碰撞,所以我们应当加一个求积的可能,所以我们的哈希函数公式为: \$[J\alpha(x) = \sum{m=0}^\infty \frac{(-1)^m}{m! \Gamma (m + \alpha + 1)} {\left({ \frac{x}{2} h(a)=a1+a2+a3+……+a[n]+a[1a2]a[n]+a[i-n);

程序


#include <cstdio>
#define P 99991// 取与n最接近的质数,以减少碰撞可能
using namespace std;
const int MAXSIZE=110000;// 最大值
int head[MAXSIZE],next[MAXSIZE],snow[MAXSIZE][6],a[6];
// head[i] 哈希后结果为i的表头
// next[i] 链表的下一个项
//snow[][6] 储存雪花
// a 读入雪花用
int n;
int cnt1,tot;
//int P=99991;
long long cnt2;
// n 次数
// cnt1,cnt2 哈希函数
int H(int *a){// 哈希函数// 不想解释
    cnt1=0;cnt2=1;
    for(int i=0;i<6;i++){
        cnt1+=a[i];
        cnt1%=P;
        cnt2*=a[i];
        cnt2%=P;
    }
    return (cnt1+cnt2)%P;
}
bool same(int *a,int *b){// 判断是否相同
// 暴力法
    for(int i=0;i<6;i++){//转a的开头点
        for(int j=0;j<6;j++){// 转b的开头点
            bool x=false;
            for(int k=0;k<6;k++){// 顺时针
                if(a[(i+k)%6]!=b[(j+k)%6]) x=true;
            }
            if(!x) return true;
            x=false;
            for(int k=0;k<6;k++){// 逆时针
                if(a[(i+k)%6]!=b[(j-k+6)%6]) x=true;
            }
            if(!x) return true;
        }
    }
    return false;
}
bool insert(int *a){// 插入雪花
    int val=H(a);// 求哈希值
    for(int i=head[val];i!=0;i=next[i]){// 遍历链表
        if(same(snow[i],a)) return true;
    }
    tot++;//没有的话新建一个链表并插入
    for(int i=0;i<6;i++) snow[tot][i]=a[i];
    next[tot]=head[val];
    head[val]=tot;
    return false;
}
int main(){
    scanf("%d",&n);// 读入
    for(int i=1;i<=n;i++){
        for(int j=0;j<6;j++)scanf("%d",&a[j]);
        if(insert(a)){// 插入
            printf("Twin snowflakes found.");// 如果有相同的输出相同
            return 0;// 退出程序
        }
    }
    printf("No two snowflakes are alike.");// 如果一直没有相同雪花的话,那么输出没有
}

End

]]>

排序算法(3) — O(n log(n)) — 快速排序/归并排序

写在前面 这次是两种大家十分熟悉也是常见的东西,在中间的代码力玩花样的题并非没有,总而言之这是两种十分神奇的算法了qwq

归并排序

时间复杂度: O(n log(n)) 空间复杂度: O(n) 突然间想起几篇前的O(n^2)….真是感人 然后再看看前面的代码长度,在看看下面的… 也是很感人呢2333 我还不如等量子计算机出来直接冒泡
#include <cstdio>
using namespace std;
int n;
int result[110000];
int a[110000];
void marge(int *data,int start,int end,int *result){// 合并区间
    int left_start,result_start,right_start;
    left_start=result_start=start;
    right_start=(start+end+1)/2+1;
    while(left_start<=(start+end+1)/2&&right_start<=end){
        if(data[left_start]<data[right_start]) result[result_start++]=data[left_start++];
        else result[result_start++]=data[right_start++];
    }
    while(left_start<=(start+end+1)/2) result[result_start++]=data[left_start++];
    while(right_start<=end) result[result_start++]=data[right_start++];
}
void margesort(int *data,int start,int end,int *result){// 二分
    if(end-start==1){// 刚好差为1,那么这两个相邻,就可以排序
        if(data[start]>data[end]){
            int temp=data[end];
            data[end]=data[start];
            data[start]=temp;
        }
        return ;
    }
    else if(end-start==0) return ;//相同你排个瓜皮啊
    else {
        margesort(data,start,(start+end+1)/2,result);//继续二分排序
        margesort(data,(start+end+1)/2+1,end,result);
        marge(data,start,end,result);// 合并
        for(int i=start;i<=end;i++) data[i]=result[i];//排序完的总的回去吧233
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    margesort(a,1,n,result);
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
}
我给你讲这个代码还是压过行的 上面的注释我觉得知道原理估计看不懂,说一下归并排序的原理:
  1. 将一个长度为n的数列分成2/n的数列<分>
  2. 分到只剩两个的时候排序<治>
  3. 将每个区间进行合并<和>
所以这是一个分治算法,“分而治之”,“分完要和”。 建议思考两个问题 并不会公布答案,因为不自己想的话根本理解不了 如果你是dalao建议你左上角,这是一篇对你没有用的文章:
  • 在二分排序的时候(start+end+1)/2(start+end+1)/2+1是为了什么,可不可以替换?
  • 中间几个<=是否可以换成<

快速排序

理论最优速度: O(n log(n)) 最差速度: O(n^2) 空间复杂度: O(n log(n)) 我们找出一个“哨兵”,然后找出比他大的和比他小的,然后分成两列<分>,知道最后只剩两个完成排序<治>,然后回溯输出<合> 又是一个分治算法 代码:
#include <cstdio>
using namespace std;
int n;
int a[110000];
void qsort(int *data,int s,int e){
    int o_l=s,o_r=e;
    int base=data[(s+e)/2];//取中快排
    do{
        while(data[s]<base) s++;// 比自己大的
        while(data[e]>base) e--;//比自己小的
        if(s<=e){//上面两个循环都被打断说明顺序不对,交换一下
            int temp=data[s];
            data[s]=data[e];
            data[e]=temp;
            s++;
            e--;
        }
    }while(s<=e);
    if(o_l<e) qsort(data,o_l,e);//确保不越界
    if(s<o_r) qsort(data,s,o_r);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    qsort(a,1,n);
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
}

End

这两种算法是比较常见的排序算法,原理都是分治,不过归并相对稳定一些,不容易翻车 ]]>