关于
联系
Oi大佬们
keyboard_arrow_down
本站已运行
载入天数...载入时分秒...
Woshiluo's Notebook
Woshiluo
2018年3月11日
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判断结尾时去掉了许多多余的代码