排序算法(2) — 非常规排序 — sort/桶排

写在前面 为什么说这两个是非常规排序,第一个是stl库,第二个是真的暴力出奇迹233

sort

理论最优时间复杂度: O(n log2(n)) 因为这个东西忘记了所有排序的人估计不止我一个
sort(start,end,cmp);
此函数位于algorithm库中
  • start 开始排序的位置<必选项>
  • end 结束排序的位置<必选项>
  • cmp() 排序的优先级实际上如果要用优先队列你还会见到他<可选项,不填写的话就是升序排列啦>

示例


这个东西真的是超级好用的,吹暴sort!!! 数组排序<升序>:
sort(a,a+n)// 从a[0]到a[n-1]
数组排序<降序>:
bool cmp(int c,int d){
    return c>d;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++) printf("%d",a[i]);
}
相比你们也已经猜到了结构体排序的方法:
bool cmp(node c,node d){
    if(c.a>d.a) return true;
    else if(c.b>d.b) return true;
    else return false;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d%d",&a[i].a,&a[i].b);
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++) printf("%d %d\n",a[i].a,a[i].b);
}
所以说这玩意这么好为什么还要用别的呢对吧 如果你想验证一下自己是否学会sort可以试试这道题:[https://www.luogu.org/problemnew/show/P1093]

桶排

时间复杂度:O(max)(max是指数列中间的最大值) 空间复杂度:常数级别 不知道大伙还记不记得在bfs时我们所打的哈希表,桶排与这个东西神似 不知道也没关系 我们想一下,我们打一张表,出现过得数字为true,没有出现过的为false,然后从头遍历,这真的一点都不常规排序…… 伪代码:
    for(int i=1;i<=n;i++){
        scanf("%d",&temp);
        if(temp>max) max=temp;
        x[temp]++;
    }
    for(int i=1;i<=max;i++) {
        for(int j=1;j<=x[i];j++){
            printf("%d ",i);
        }
    }
皮到一个境界2333

End

总而言之,这篇讲的两个不常规排序并不需要理解方法,并且时间复杂度真的是一低再低了233,可谓是简单粗暴还省时,不过缺陷也是有的啦,sort速度终究还是快不过归并,桶排的内存就很感人了… ]]>

排序算法(1) — O(n^2)类型 — 冒泡排序/插入排序/选择排序

写在开头

为什么会有这个系列的文章


因为博主发现自己对排序算法似乎一无所知…所以打算来一发补习

其他


实际上关于对数据的排序一直是一个非常大的问题,我们会发现当数据规模小的时候,多重循环比挨个对并不是什么问题的说,但是在我们的生活当中,我们会发现,数据量讲绝对不止1000这道卡,所以我们必须要在中间找到更多更快更好的算法,至于我为什么没有去讲一些奇怪的排序方法(比如猴子排序)是因为它们是一些人们突发奇想的东西,我们虽然不能说它们坏,不过在实际生活中,用处 可能 并不大,所以我们就不会再去提及它们了,有兴趣的话,自己查查吧. 不要去百度!不要去百度!

冒泡排序

时间复杂度: O(n^2) 空间复杂度: 常数级反正就是你只需要存下来就没啥事了 伪代码:
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      if(a[i]>a[j]){
            int temp=a[j];
            a[j]=a[i];
            a[i]=temp;
      }
    }
}
很明显我们可以看得出来,所谓冒泡排序,就是两个两个之间互相比对,然后大的往上交换(冒泡),于是打了最后,就完成了排序。 所以时间也就意料之中的高2333

插入排序


时空复杂度: 同上 伪代码:
for (int i=1;i<=n;i++){
    if (a[i-1]>a[i]){
        int temp=a[i];
        int j=i;
        while(j>0&&a[j-1]>temp){
            a[j]=a[j-1];
            j--;
        }
        a[j]=temp;
    }
}
为什么我感觉比上面的那种还暴力 暴力出奇迹233 这种办法的本质就是直接插入,找到比自己大的很比自己小的,然后往中间插队(插入),然后出来就算排序好了 巧了入学时队伍就是这么排出来的的

选择排序

时空复杂度:仍然同上
for(i=1;i<=n;i++){
    min=i;
    for(j=i+1;j<=n;j++){
        if(a[j]<a[min])
            min=j;
    }
    if(min!=i) swap(a[i],a[min]);
}
真是越来越暴力了 然而我们会有很多的排序算法会从这里优化而来,所以说多少还是要学的,起码要知道概念的说不然初赛考到,博主就凉了 这一种排序算法是找到最大和最小然后交换 突然想起初一上时学有理数是疯狂对绝对值排序

End


O(n^2)的算法基本上到此为止,后面的排序算法有很多都是从此衍生的,所以说暴力出奇迹是真的2333 ]]>

UVA12657 Boxes in a Line

我左移箱子,右移箱子,最后来了个倒着玩

日常简要分析


题目链接[https://www.luogu.org/problemnew/show/UVA12657]
明明是uva的题我为什么要放上luogu的链接 因为luogu访问快啊 题目中实际上我们是可以开看出我们要分去处理比较方便 我们先来看看这几层
  • 初始化
  • 读入
    • n,m
    • 操作
      1. 左移
      2. 右移
      3. 翻转
  • 求和并输出
那么我们挨个讲吧
#include <cstdio>
using namespace std;
struct node{
    int next,last;
    int n;
}a[110000];
int head,last;
int n,m,x,y,mcnt;
int temp;
node tmp1,tmp2;
bool zf=false;
struct node – 链表项 a – 链表 head – 链表头 last – 链表尾 n,m,x,y – 题目中有讲 mcnt – 判断第几个case temp,tmp1,tmp2 – 临时项 zf – 判断是否颠倒

读入

inline void init(){
    mcnt++;
// 先把箱子挨个排起来
    for(int i=1;i<=n;i++){
        a[i].n=i;
        a[i].next=i+1;
        a[i].last=i-1;
    }
    zf=false;// 一开始是不倒的
// 确定头和尾部
    head=1;
    last=n;
}

1. 左移

|    n   |
|last|next|
|  1  |    | 2  |    |  3  |  |  4   |
|   | 2|    |1|3 |    |2| 4|   | 3|   |
如果我们要将1移动到3左边,也就是说输入1 1 3 那么就要讲3的last改为1 1的next改为3 将1的nxet与1的last链接 将3的last的next改为1
inline void bian1(){
    scanf("%d%d",&x,&y);
    if(a[y].last==x||x==y) return ;
    tmp1=a[x];tmp2=a[y];// tmp1,tmp2临时储存以防后面倒不动
    if(x==last) last=a[x].last;// 如果需要移动是尾,那就更改尾部尾需要更改的last项上
    if(x==head) head=tmp1.next;// 如果是头部,那就进行移动
    else if(y==head) head=x;// 同上
/* 那么就要讲3的last改为1
1的next改为3
将1的nxet与1的last链接
将3的last的next改为1*/
    a[tmp1.next].last=tmp1.last;
    a[tmp1.last].next=tmp1.next;
    a[tmp2.last].next=x;
    a[x].last=tmp2.last;
    a[x].next=y;
    a[y].last=x;
}

2.右移

与上面一样,自己理解一下不一样的地方,思考
  • 为什么更新headlast地方发生了改变
inline void bian2(){
    scanf("%d%d",&x,&y);
    tmp1=a[x];tmp2=a[y];
    if(a[y].next==x||x==y) return ;
    if(y==last) last=x;
    else if(x==last) last=a[x].last;
    if(x==head) head=tmp1.next;
    a[tmp1.next].last=tmp1.last;
    a[tmp1.last].next=tmp1.next;
    a[x].last=y;
    a[y].next=x;
    a[tmp2.next].last=x;
    a[x].next=tmp2.next;
}

3.交换

实际上本质依旧与前两个相同,但是我们要注意两个是相邻的状况,对于移动的部分是讲两者和两者的next与last更新,方法可以参照一种的图,依旧需要思考
  • 为什么当x在y后面需要交换?
  • 为什么不直接交换两者的n?
inline void bian3(){
    scanf("%d%d",&x,&y);
    if(x==y) return ;
    if(x==head) head=y;
    else if(y==head) head=x;
    if(x==last) last=y;
    else if(y==last) last=x;
    if(a[y].next==x) {int te;te=x;x=y;y=te;}
    tmp1=a[x];tmp2=a[y];
    if(a[x].next==y){
        a[tmp1.last].next=y;
        a[y].last=tmp1.last;
        a[y].next=x;
        a[x].last=y;
        a[tmp2.next].last=x;
        a[x].next=tmp2.next;
    }
    else {
        a[tmp1.next].last=y;
        a[y].next=tmp1.next;
        a[tmp1.last].next=y;
        a[y].last=tmp1.last;
        a[tmp2.next].last=x;
        a[x].next=tmp2.next;
        a[tmp2.last].next=x;
        a[x].last=tmp2.last;
    }
}

4.倒

简单到我不想讲
inline void bian4(){zf=!zf;}

读入


思考: 为什么颠倒时要用3相减
inline void read(){
    for(int i=1;i<=m;i++){
        scanf("%d",&temp);
        if(temp==4) bian4();
        if(zf&&temp!=3) temp=3-temp;
        if(temp==1) bian1();
        if(temp==2) bian2();
        if(temp==3) bian3();
    }
}

求和输出


注意: 务必使用long long (在样例中有体现) 思考: 为什么不在循环中判断break
inline void sum(){
    long long sum=0,cnt=0;
    if(!zf)// 正过来
        for(int i=head;;i=a[i].next){
            cnt++;
            //printf("%d ",a[i].n);
            if(cnt%2!=0) sum+=a[i].n;
            if(i==last){
                printf("Case %lld: %lld\n",mcnt,sum);
                break;
            }
        }
    else {// 反过来
        for(int i=last;;i=a[i].last){
            cnt++;
            //printf("%d ",a[i].n);
            if(cnt%2!=0) sum+=a[i].n;
            if(i==head){
                printf("Case %lld: %lld\n",mcnt,sum);
                break;
            }
        }
    }
}

End

int main(){
//    freopen("233.in","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF){
        init();
        read();
        sum();
    }
}
主程序貌似没有什么必要解释 你会发现把这些块连起来就是一个完整的代码qwq

思考的(非标准)答案||思路


这个是我脑洞大开的方法,毕竟这个程序真的不太好说 右移:
  • 为什么发生了改变
  • 原因十分简单,因为像左移会发生移动到头的情况,然而向右移虽然没有这个,但是有可能移到结尾 交换:
  • x,y颠倒
  • 简化处理步骤
  • 不直接交换
  • 你可以调试或者拿这个程序对拍,你会明白的 读入:
  • 相减
  • 如果你将倒过来,那么它的左右也就以然会颠倒,所以左移就变成了右移,反之亦然 求和输出:
  • 不在循坏条件中判断
  • 因为这样可能会漏掉最后一个,然后继续思考为什么会漏掉吧
如果你思路基本上和博主的对上了,那么开始自己写吧 如果没有对上,建议重新看并思考,必要时可以画画图,当然也可以直接留下评论问我 ]]>

一次爬虫与反爬的简单斗争

实际上这次完全就是对方占完全优势,然而对方不懂css,然后就开始一场十分智障的作死

Rand 1

依靠老杨的指令我对博客加了一些简单的东西防止复制,然后SpinMry大佬说他要造福班级同学,然后他就开始python建dom上来直接爬,然后dalao就成功用python把我博客上的代码爬了下来qwq 然后我就尝试来了一波反爬虫,当然我不会什么高深的动态方法,于是我就打算坑一把,采用了iframe嵌套,然后成功的使用了碍眼发Qwq

Rand 2

结果过了一会儿他就发现了我的方法,然后成功找到嵌套链接,又一次成功的爬上当然我的内心是mmp的 然后我发现他只能够抓取到第一次浏览上的部分,然后机智的我加了一层跳转qwq,然后成功卡了对方卡一会

Rand 3

结果dalao直接上curl模拟链接,然后接下来就到了上课的时候,我就放弃了反爬

一些后续思想

实际上可以用储存时间的mdz当加密密码,然后把时间存入数据
这些全都建立在他不对我的服务器进行攻击或者盗取数据的方法 毕竟能做到这点的,估计写出这些代码也不难了
首先我们可以对代码进行中途加密qwq,也就是说它既是找到了也是加密后的代码,其次就是对与加密密码的保库当中,没次取出来后在通过js取md5然后在进行解密qwq也就是说中间过程即使暴露也不会出特别大的事,甚至可以不是单纯md5加密,通过这一个办法可以继续衍生,以确保中间不被爬去qwq

End

当然最终代码都会呈现到网页上的,你们就是复制不上一个图片识别文字就可以qwq 不过刷题的代码终究都是为了自己好,如果你想那我的博客做做写爬虫的练手来爬也无妨qwq,但题终究是为了自己的能力二刷的,你就是复制出来a了又能怎么样呢,所以还是劝大家自己写吧,毕竟为了自己嘛~ ]]>

新年欢乐赛 解题报告

考试链接:[http://180.76.159.115:5283/contest/5] 学长的考试,渣渣的我就做了三道题,那就写个及结题报告吧,毕竟我才是个普及组蒟蒻

1.这是一道大水题

题目链接:[http://180.76.159.115:5283/problem/3]
学长真皮

简单解析


题目第一眼看过去n,m<=100那么很显然这是搜索大法可以做到的,然而dfs有这很大的 TLE 的风险,所以当然是bfs大法好了 对于人而言把他的范围都设为不可走就可以了

代码


#include <cstdio>
using namespace std;
struct node{
    int x,y,deep;
}st,dl[110000];
int n,m;
char te[110];//读入
int a[110][110];// 存图
int dx[4]={0,0,-1,+1};//dx[] dy[] 增量
int dy[4]={+1,-1,0,0};
bool x[110][110];// x[ ][ ]记录走过的路
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%s",te);// 字符串总是稳定的,毕竟总比字符读入个'\n'好qwq
        for(int j=0;j<m;j++){// 所以要对读入的字符串
            if(te[j]=='S') {// 是出口就放入s
                st.x=i;
                st.y=j;
            }
            if(te[j]=='#') a[i][j]=-1;// 桌子是不能过的
            if(te[j]=='!'){//愤怒的oier
                a[i][j]=-1;
                a[i-1][j]=-1;
                a[i+1][j]=-1;
                a[i][j-1]=-1;
                a[i][j+1]=-1;
            }
            if(te[j]=='D') a[i][j]=1;
        }
    }
    a[st.x][st.y]=0;// 开头可以走
// 加入队列
    int h,l;
    h=l=1;
    dl[1]=st;
    while(h<=l){//日常bfs
        node now;
        now=dl[h];
        for(int i=0;i<4;i++){// 模拟上下左右
            node temp=dl[h];
            temp.x+=dx[i];
            temp.y+=dy[i];
            if(temp.x>=0&&temp.x<n&&temp.y>=0&&temp.y<m){// 判断越界
                if(a[temp.x][temp.y]==0&&(!x[temp.x][temp.y])){// 可以走
                    temp.deep++;
                    x[temp.x][temp.y]=true;
                    dl[++l]=temp;
                }
                else if(a[temp.x][temp.y]==1){// 到了大门
                    printf("%d",temp.deep+1);
                    return 0;
                }
            }
        }
        h++;
    }
    printf("Ahhhhhhh!!!");// 搜完了都没做到,那么就死吧、
}

2.缘生意转

题目链接:[http://180.76.159.115:5283/contest/5/problem/2]
这种题目看过去第一眼就是打表啊,把该存1到100存到一个二维数组,然后挨个儿比对

代码


#include <cstdio>
#include <cstring>
using namespace std;
int n,len[110],ans;
char dic[120][22]={"one","two","three","four","five","six","seven","eight","nine","ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen","twenty","twenty-one","twenty-two","twenty-three","twenty-four","twenty-five","twenty-six","twenty-seven","twenty-eight","twenty-nine","thirty","thirty-one","thirty-two","thirty-three","thirty-four","thirty-five","thirty-six","thirty-seven","thirty-eight","thirty-nine","forty","forty-one","forty-two","forty-three","forty-four","forty-five","forty-six","forty-seven","forty-eight","forty-nine","fifty","fifty-one","fifty-two","fifty-three","fifty-four","fifty-five","fifty-six","fifty-seven","fifty-eight","fifty-nine","sixty","sixty-one","sixty-two","sixty-three","sixty-four","sixty-five","sixty-six","sixty-seven","sixty-eight","sixty-nine","seventy","seventy-one","seventy-two","seventy-three","seventy-four","seventy-five","seventy-six","seventy-seven","seventy-eight","seventy-nine","eighty","eighty-one","eighty-two","eighty-three","eighty-four","eighty-five","eighty-six","eighty-seven","eighty-eight","eighty-nine","ninety","ninety-one","ninety-two","ninety-three","ninety-four","ninety-five","ninety-six","ninety-seven","ninety-eight","ninety-nine"};
char a[22];
int main(){
    for(int i=0;i<99;i++){// 存入长度
        len[i]=strlen(dic[i]);
    }
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",a);// 读入
        int alen=strlen(a);
        for(int j=0;j<99;j++){// 比对
            if(len[j]!=alen) continue;// 字符串长度不同直接gg
            if(strcmp(a,dic[j])==0) {
                ans+=j+1;
                break;
            }
        }
    }
    printf("%d",ans);
}

3.绿豆沙冰

题目链接: [http://180.76.159.115:5283/problem/7]

简单分析


博主一上来就是floyd,然后被多组数据坑的…… 所以这次我们就要一换方法——spfa 先来介绍一下吧
inline void spfa(){
    int h,l;
    h=l=1;
    d[1]=0;
    x[1]=true;// 避免自己走到自己
    dl[1]=1;// 加入队列头
    while(h<=l){
        int temp=dl[h];
        for(int i=1;i<=n;i++){//尝试每一个点
            if(d[temp]+a[temp][i]<d[i]){// 优于就放入队列
                d[i]=a[temp][i]+d[temp];
                if(!x[i]){
                    x[i]=true;
                    dl[++l]=i;
                }
            }
        }
        x[temp]=false;
        h++;
    }
}
可以很明显的发现,这是个基于bfs并有贪心思路的算法; 首先是bfs模拟,其次是如果优于前者才放近队列; 虽然不是多源最短路,但是其速度是相当快的qwq

代码


#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;
int T,n,m,k;
int a[1100][1100];
int d[1100],dl[110000];
bool x[1100];
inline void init();
inline int read(){// 读入优化不解释
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
inline void floyd(){// floyd,会超时的qwq
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            if(a[i][k]>k) continue;
            for(int j=1;j<i;j++){
                if(a[i][k]+a[k][j]<a[i][j]){
                    a[i][j]=a[i][k]+a[k][j];
                    a[j][i]=a[i][j];
                }
            }
        }
    }
}
inline void spfa(){// 不用解释了吧
    int h,l;
    h=l=1;
    d[1]=0;
    x[1]=true;
    dl[1]=1;
    while(h<=l){
        int temp=dl[h];
        for(int i=1;i<=n;i++){
            if(d[temp]+a[temp][i]<d[i]){
                d[i]=a[temp][i]+d[temp];
                if(!x[i]){
                    x[i]=true;
                    dl[++l]=i;
                }
            }
        }
        x[temp]=false;
        h++;
    }
}
inline void readin(){// 读入并加边
    n=read();m=read();k=read();
    init();
    for(int i=1;i<=m;i++){
        int u,v,t;
        u=read();v=read();t=read();
        a[u][v]=t;
        a[v][u]=t;
    }
}
inline void init(){ // 清空/初始化
    memset(dl,0,sizeof(0));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            a[i][j]=0x3fffffff;
        }
        d[i]=0x3fffffff;
        x[i]=false;
    }
}
int main(){
    scanf("%d",&T);
    for(int i=1;i<=T;i++){//多次数据
        readin();
//        floyd();
        spfa();
        if(/*a[1][n]*/d[n]*2<=k) printf("Yes \n");
        else printf("No\n");
    }
}

End

]]>

2018.3.10 链表考试 解题报告

Start 杨老师突然就考试把我慌得一批 第四题被读入方法坑了一波,造成了oj能过评测机死活过不了的尴尬问题 前面三道题总体来说没有什么难度 第四题老杨没讲双向链表就考,搞得我怀疑自己是不是该加last项qwq

1.数列

题面


老师给我们的题面压根没法说,还是我来翻译吧 现在你要对一个空数列进行操作,你有两种书操作方法—’1’和’2’-分别代表添加和查询

输入

第一行一个n 后面n行每行两个数,a,b a表示操作方法,b表示被操作数 (1 1 表示往数列中加1 , 2 3表示查询3是否在数列中

输出

有几个 2 操作就输出几行,”Yes”表示存在,”No” 表示不存在

分析


老师上课讲过的 实际上二分优先队列也是一种办法/有大佬这么做 然而链表考试,我们把这个读入进来的数和一个大数(最好是质数)取模,对余数相同的见一个链表,到时候只需要查找这个余数就可以了

代码


#include <cstdio>
using namespace std;
struct node {
    int a;
    int next;
}dl[1100000];// dl[] 链表
int n,head[101000],len;// head[i] 余数为i的链表的开头
// len 表示链表长度
int main(){
    freopen("shulie.in","r",stdin);
    freopen("shulie.out","w",stdout);
    scanf("%d",&n);
    for(int i=0;i<=n;i++){
        dl[i].a=-1;
    }
    for(int i=1;i<=n;i++){
        int c,b;
        scanf("%d%d",&c,&b);
        if(c==1){// 添加
            int tmp=b%99997;// 求余
            len++;
            dl[len].next=head[tmp];
            dl[len].a=b;
            head[tmp]=len;
        }
        else {// 查询
            bool x=false;
            int tmp=b%99997;
            for(int i=head[tmp];dl[i].a!=-1;i=dl[i].next){// 遍历链表
                if(dl[i].a==b) {
                    x=true;
                    printf("Yes\n");
                    break;
                }
            }
            if(!x) printf("No\n");
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

2.约瑟夫问题

题面自己找,解析不用讲,我直接上代码吧qwq

代码


#include <cstdio>
using namespace std;
struct node{
    int next,data;// data 可废弃
}a[110000];// a[] 链表
int n,m;
int main(){
    freopen("king.in","r",stdin);
    freopen("king.out","w",stdout);
    int p,q;
    scanf("%d%d",&n,&m);// 读入
    for(int i=1;i<=n;i++){// 初始化,每个人的下一个都是自己旁边的
        a[i].data=i;
        a[i].next=i+1;
    }
    p=n;// 从 1 开始报数
    a[n].next=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m-1;j++){
            p=a[p].next; // 往下一个找
        }
        q=a[p].next;// 更新
        a[p].next=a[q].next;
        if(i==n)printf("%d",q);// 输出最后的赢家编号
    }
    fclose(stdin);
    fclose(stdout);
}

3.法雷队列

题面就简单说吧:
求分母小于n的所有最简真分数,然后再加上0/1,1/1然后按顺序输出就行了
分析???不存在的 因为我用的暴力,还需要解释? 因为题目中讲了: n<=100 暴力出奇迹

代码


#include <cstdio>
#include <algorithm>
using namespace std;
struct node {
    int m,s;
}d[100000];
int n,cnt,len;
bool cmp(node a,node b){
    double ta=double(a.s)/double(a.m);
    double tb=double(b.s)/double(b.m);
    return ta<tb;
}
// gcd判断互质
bool gcd(int a,int b){
    int r;
    while(b>0){
         r=a%b;
         a=b;
         b=r;
    }
    if(a==1) return true;
    else return false;
}
int main(){
    freopen("falei.in","r",stdin);
    freopen("falei.out","w",stdout);
    scanf("%d",&n);
    len++;
    d[len].m=1;
    d[len].s=0;
    // 枚举
    for(int i=1;i<=n;i++){// 转分母
        for(int j=1;j<i;j++){// 转分子
            if(j==1) {// 分子是1,100%最简分数
                len++;
                d[len].m=i;
                d[len].s=j;
            }
            else {
                if(gcd(i,j)){
                    len++;
                    d[len].m=i;
                    d[len].s=j;
                }
            }
        }
    }
    len++;
    d[len].m=1;
    d[len].s=1;
// sort排序万岁
    sort(d+1,d+len,cmp);
// 输出
    for(int i=1;i<=len;i++){
        printf("%d/%d ",d[i].s,d[i].m);
        if(i%10==0) printf("\n");
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

4. TXT Editor

题面


现在你要编写一个文本编辑器,该编辑器支持以下4个操作: 1、L:光标左移一格 (若光标已在最左边就无视这次操作) 2、R:光标右移一格 (若光标已在最右边就无视这条操作) 3、a-z:在光标处插入一个字母 4、B:删除光标前的一个字母 (等同Backspace键,若光标已在最左边就无视这次操作) 初始文本为空,现在给你一个操作的序列S,求操作结束后文本编辑器里面的内容。

解析


虽然我们只学了单向链表,但也应当很容易想到双向队列:多加一个last 另外我们通过now表示目前的光标,就很容易想通了

代码


之前用\n判断输入结束然后t了简直心累,跑到oj上结果AC了233,改成EOF后出了一点莫名奇妙的问题qwq(总是在输出结尾加一个^@符号,也不知道是什么 虽然理论上ac但是安全起见我还是放EOF判断结尾法的代码吧qwq 刚好改EOf判断结尾时去掉了许多多余的代码 ]]>

链表入门 – Luogu 1996 约瑟夫问题

链表? 通常而言,我们说链表都是一种动态的数据结构,但是显然对于我这样的蒟蒻以及普通的竞赛考试而言,通过半静态的数组模拟也可以基本上完成对链表的模拟。 日常的日常—简单画图:

a         [ 0 ]            [1]            [2]           [3]
head -> |next|data| -> |next|data| -> |next|data| -> |next|data|
        |  2 | 2  |    |  3 | 4  |    | 1  | 3  |    | 0  |  1 |
如果我们想要遍历这个链表,就是这个顺序:
a[0]->a[2]->a[1]->a[3]-|
相信你已经看出来了next的作用,所以把一个数直接添加进链表的时间复杂度不比数组高哪去了2333 让我们来看看下面这道题:

题面


我们现在有两种操作 ‘ 1 ‘ 与 ‘ 2 ‘ , ‘ 1 ‘ 表示插入,’ 2 ‘表示询问一个数是否添加过 我们先看看这个样例 输入
5
1 3
1 5
2 3
1 4
2 2
输出
Y
N
不用说我们也知道,桶排是可以是解决一切,但是我们如果我们内存不够呢? 这是就要祭出链表了。 我们把要插入的数对大整数进行取模,然后存入p[i]数组及链表当中当中(i表示取模得到的结果) 这样一来我们就对取模解过相同的数建立了链表,接下来只需要递归遍历,这个速度查找,比大多数方法快好多了

约瑟夫问题

题面


题目链接:[https://www.luogu.org/problemnew/show/P1996]
无聊的约瑟夫 很好因为约瑟夫的无聊我们不得不去做这道题。 显然模拟以及数学方法都可以轻松 AC Qwq 不过我肯定还是要讲链表的方法的啦~

代码


可以去除data项
#include <cstdio>
using namespace std;
struct node{
    int next,data;// 不解释
}a[110000];// 假装自己是链表的 a[]
int n,m;
int main(){
// 初始化
    int p,q;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        a[i].data=i;
        a[i].next=i+1;
    }
    p=n;// 从 1 开始报数
    a[n].next=1;// 建立循环队列
    for(int i=1;i<=n;i++){// 每个人都要输出
        for(int j=1;j<=m-1;j++){// 把数传到下一个人
            p=a[p].next;
        }
        q=a[p].next;
        a[p].next=a[q].next;// 去除q节点
        printf("%d ",q);
    }
}
为什么我感觉还是模拟qwq

END

过不了几天, ]]>

论 dfs 与 bfs 的优化:NOIP 2017 普及组 第三题 – 棋盘

题目

参考题目:[https://www.luogu.org/problemnew/show/P3956]
相信大家都做过这道题吧,毕竟真的是到很明显的搜索/dp dp就不说了,有兴趣可以去题解去瞅瞅,不过因为有可能往回走,dp写起来会很麻烦让你怀疑你写的不是dp 但是同样是因为有可能回走,dfs与bfs无法进行像 bool x[][] 这样的剪枝办法(已经走过的路不走的办法) 所以就需要优化

骗分

既然是考试题目,那么我就就可以骗分

5 分


输出特殊状况—’-1′

10 分


在5分的情况下考虑输出0的情况

15-65 分


dfs大法,不加任何优化版 但是分数可能会有一定波动,需要注意下面几点
  • 尽可能递归 RE
  • 做一点微小的剪枝
  • 平时代码习惯不好可能会比较容易得低
  • 小心魔法
注意完以上几点,你就是一等大佬了

65 分


在15-65分做法中去除向上和向左,防止打转

100 分做法

博主在这里说两种搜索法-bfs/dfs 最短路以及dp大家有心情可以试试 这题用最短路这是杀鸡用牛刀 使用这两种方法都要建一个best[][]数组表当前最优花费,这样就可以避免一些不必要的地方,达成剪枝的目的。 先单独拿出来一行代码讲一下
col[now.x][now.y]!=0?col[now.x][now.y]:temp.tu_col
可以转化为这个
int wh(){
    if(col[now.x][now.y]!=0) return col[now.x][now.y];
    else return temp.tu.col;
}
wh();
这个符号我们叫三目运算符/问号表达式

bfs


#include <cstdio>
#include <cstring>
using namespace std;
struct que{
    int tu_col,money,x,y;
// tu_col 目前变化的颜色
// money 目前所花钱数
// x y 目前走到(x,y)上
}q[110000];// q[] 队列
int n,m,x,y,c;
// dx[] dy[] 增量
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int best[110][110],col[110][110];
// best[i][j] 目前位于(i,j)的已知最优解
// col[i][j] (i,j)格子上的颜色
int main(){
    memset(best,0x3f,sizeof(best));// 初始化
// 读入
   scanf("%d%d",&m,&n);
   for(int i=1;i<=n;i++){
        scanf("%d%d%d",&x,&y,&c);
        col[x][y]=c+1;
    }
// 加入队列首
    q[1].x=q[1].y=1;
    q[1].money=q[1].tu_col=0;
    int h,t;
    h=t=1;
    best[1][1]=0;// 第一个格子设为0
    while(h<=t){// 开始bfs
        que now;
        now=q[h];
// now 仅仅为了方便写,在下面的循环中可替换为q[h],也就是用于储存队列首
        for(int i=0;i<4;i++){// 模拟上下左右
            que temp=q[h];
            temp.x+=dx[i];
            temp.y+=dy[i];
            // temp 用于临时修改
            if(temp.x<=0||temp.y<=0||temp.x>m||temp.y>m) continue;// 判断越界
            if(col[temp.x][temp.y]==0/*如果当前格子上没有颜色*/&&temp.tu_col==0/*并且上一个格子没有用魔法*/){
                if(temp.money+2<best[temp.x][temp.y]){// 如果当前解优于已知最优解,才能放入队列
                    temp.money+=2;
                    temp.tu_col=col[now.x][now.y];// 存入临时颜色
                    q[++t]=temp;// 加入队列
                    best[temp.x][temp.y]=temp.money;// 更新 best 数组
                }
            }
            else if(col[temp.x][temp.y]!=0&&col[temp.x][temp.y]!=(col[now.x][now.y]!=0?col[now.x][now.y]:temp.tu_col)){// 颜色不相等
                 if(temp.money+1<best[temp.x][temp.y]){// 不解释
                    temp.money+=1;
                    temp.tu_col=0;
                    q[++t]=temp;
                    best[temp.x][temp.y]=temp.money;
                }
            }
            else if(col[temp.x][temp.y]!=0){// 接下来只有可能颜色相等
                if(temp.money<best[temp.x][temp.y]){
                    temp.tu_col=0;
                    q[++t]=temp;
                    best[temp.x][temp.y]=temp.money;
                }
            }
        }
        h++;// 踢出对首
    }
    if(best[m][m]<0x3f3f3f3f) printf("%d",best[m][m]);// 不是预设值就输出
    else printf("-1");// 是预设值说明没有路通向那,输出-1
}

dfs


请参照 bfs 方法的注释来理解这个,所有变量含义一样
#include <cstdio>
#include <cstring>
using namespace std;
int n,m,x,y,c;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int best[110][110],col[110][110];
void dfs(int x,int y,int tu_col,int money){
    for(int i=0;i<4;i++){
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(tx<=0||ty<=0||tx>m||ty>m) continue;
        if(col[tx][ty]==0&&tu_col==0){
            if(money+2<best[tx][ty]){
                best[tx][ty]=money+2;
                dfs(tx,ty,col[x][y],money+2);
            }
        }
        else if(col[tx][ty]!=0&&col[tx][ty]!=(col[x][y]!=0?col[x][y]:tu_col)){
            if(money+1<best[tx][ty]){
                best[tx][ty]=money+1;
                dfs(tx,ty,0,money+1);
            }
        }
        else if(col[tx][ty]!=0){
            if(money<best[tx][ty]){
                best[tx][ty]=money;
                dfs(tx,ty,0,money);
            }
        }
    }
}
int main(){
    memset(best,0x3f,sizeof(best));
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&x,&y,&c);
        col[x][y]=c+1;
    }
    best[1][1]=0;
    dfs(1,1,0,0);
    if(best[m][m]<0x3f3f3f3f) printf("%d",best[m][m]);
    else printf("-1");
}

END

要是考场上没有删掉自己的dp就好了qwq ]]>

初学DP(5) – 棋盘型DP – NOIP 2000 提高组 第四题 方格取数 & POJ 2948 Martian Mining

棋盘型DP 棋盘型DP,是DP中比较坑的一种,大多数都可以用深搜AC拿上部分分,剩下的tle2333 所以这个就需要DP,通常我们是从左上朝右下找,当然了,棋盘DP却常常有种暴力的感觉

方格取数

题目链接: [http://codevs.cn/problem/1043/]
输入的方法很简单,也并没有什么复杂的预处理 对于这样一个棋盘,我们很容易想到他的阶段:从 f(i,j) 到 f(k,l) 的最优解 很明显这里已经不能用区间DP了,我们需要对 i j k l 进行枚举,另外,我们很容易发现,要是值最大,两条路径不应重合 针对与 f[i][j][k][l] 他是由两个坐标所组成的,所以我们就要分别考虑第一个坐标与第二个坐标的变化,每个坐标都有两种变化的可能,所以我们的状态转移方程应是:
f [ i ] [ j ] [ k ] [ q ] = max ( max ( f [ i – 1 ] [ j ] [ k – 1 ] [ q ] , f [ i ] [ j – 1 ] [ k ] [ q – 1 ] ) , max ( f [ i ] [ j – 1 ] [ k – 1 ] [ q ] , f [ i – 1 ] [ j ] [ k ] [ q – 1 ] ) ) +a [ k ] [ q ] + a [ i ] [ j ]
经过了这一步,我们就可以得到代码:

代码


#include <iostream>
#include <cstdio>
using namespace std;
int n,x,y,c;// 读入用
int a[20][20],f[20][20][20][20];//a[][] 存图 f[][] 动归
int main(){
// 读入
    scanf("%d",&n);
// 并不知道有多少组,那就无限输入吧
    while(1){
        scanf("%d%d%d",&x,&y,&c);
        if(x==0&&y==0&&c==0) break;// 全是 0 就该出来了
        a[x][y]=c;
    }
// 枚举
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                for(int q=1;q<=n;q++){
                    f[i][j][k][q]=max(max(f[i-1][j][k-1][q],f[i][j-1][k][q-1]),max(f[i][j-1][k-1][q],f[i-1][j][k][q-1]))+a[k][q]+a[i][j];//进行决策
                    if(i==k&&j==q) f[i][j][k][q]-=a[i][j];//如果两点相同,去掉重复的
                }
            }
        }
    }
// 输出
    printf("%d",f[n][n][n][n]);
}

Martian Mining

题目链接: [http://poj.org/problem?id=2948]

翻译


本人才疏学浅,无法做到完全翻译,所以我只会翻译题干,如果有不明确之处请指出 火星上有一个被分为n*m个格子的矿区,每格子中有两种矿石,在北边有一个厂子炼一种矿,西边也有一个厂子炼另一种矿,现在有两种传送带-自南向北与自东向西,并且一个格子上只能安一种,传送带还不能转弯. 如果矿石没有被送进它所属的厂子,就是废石,现在,问你最多能采多少矿

题目


第一眼过去dfs+记忆化搜索 可是确实可以通过这个推出来 我们在进行搜索时,从右下往左上搜。搜到最优解,然后保存下来,于是我们可以翻过来,从左上到右下然,找出每一段的最优解,然后相加,ok! 通过这个问题我们应当把每一种矿石的 i – j 的区域有多少存下来,让后我们可以得出 dp 方程
f [ i ] [ j ] = max ( f [ i – 1 ] [ j ] + yr [ i ] [ j ] , f [ i ] [ j – 1 ] + bl [ i ] [ j ] )
其中 f[][] 为动归用数组 yr[i][j] 与 bl[i][j] 都是一种矿石从第 i 个格子到第 j 个格子的对应矿石个数

End

]]>