头像

jackrrr


访客:321

离线:1天前


活动打卡代码 AcWing 1498. 最深的根

jackrrr
2天前
#include <iostream>
#include <vector> //因为要用到vector.clear(), 所以不用普通数组
#include <cstring> //memset()

using namespace std;

const int N = 10010, M = 2 * N; //因为边数是点数的2倍
int h[N], e[M], ne[M], ind; //因为h[N]是存储每个节点的token, e[M]是存储很多条边
int p[N]; //并查集

void add(int a, int b){
    e[ind] = b, ne[ind] = h[a], h[a] = ind++;
}

int find(int a){
    if(p[a] != a) p[a] = find(p[a]); //如果我的爸爸不是我的爷爷,就让我的爸爸成为我的爷爷,一直到我的爸爸是我的祖宗
    return p[a]; //这里返回的条件是 p[a] == a, 也就是a其实就是祖先.
}

int dfs(int cur, int source){
    int depth = 0;
    for(int i = h[cur]; ~i; i = ne[i]){
        int son = e[i];
        if(son == source) continue;
        depth = max(depth, dfs(son, cur) + 1);
    }
    return depth;
}
int main(){
    int n;
    cin >> n;

    //初始化单链表
    memset(h, -1, sizeof h);
    //初始化并查集
    for(int i = 1; i <= n; i++) p[i] = i;

    //读入n-1条边
    int k = n; //用于计算连通分量
    int a, b;
    for(int i = 0; i < n-1; i ++) {
        cin >> a >> b;
        add(a,b), add(b,a);
        if(find(a) != find(b)) //假如他们之前不是一个集合,但是现在input他们之间有边了
        {
            k--;
            p[find(a)] = find(b);
        }
    }   

    vector<int> res; //存output需要的节点
    int max_depth = -1;
    if(k >= 2){
        printf("Error: %d components", k);
    }
    else{
        for(int id = 1; id <= n; id ++){
            int depth = dfs(id, -1);
            if(max_depth < depth)
            {
                max_depth = depth;
                res.clear();
                res.push_back(id);
            }
            else if(max_depth == depth){
                res.push_back(id);
            }
        }
    }

    for(auto i : res) cout << i << endl;
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

思路:
1. 老师这里是暴力枚举了所有点是否是正确答案,因为一共有10^4个点,但是有2s,足够用了
2. 考察了:
1. 连通分量
逻辑:如果a,b两个点不属于同一个,并且这次input中a,b是链接的,就会少一个连通分量
使用:并查集find()
2. 如果是树,若有N个点,一定是N-1条边,(不多不少),多了就有环,少了就不连通(存在多个连通分量)
3. 但是如果N个点,N-1条边,不一定是树. 例如:6个点,其中4个点是环,另2个点链接.虽然也是5条边,但是一个是环,一个是连通分量.

  1. 老师说:
    1. 可以用bfs来看某个节点的每个叶子节点到该节点的距离
    2. 可以用dfs来遍历所有的叶子,然后返回值+1(因为高度+1)
  2. 因为是无向图,所以在遍历的过程中,我们可能会遍历到过来的点.
    例如,假设我们是认为a点是根节点,往下遍历
    其中b点是a的子节点,我们会遍历b,但是遍历b的临点的时候也会遍历到a(因为无向图存储)
    所以我们要判断b的子节点是否等于b的父亲a,如果等于,就continue
  3. dfs()在本题中的语意是:参数是int u,也就是u的叶子节点中到u节点的最大高度.
  4. dfs()中,叶子节点的高度是0, 如果是叶子结点,会返回depth == 0
  5. 注意: h[a]中的a是节点的编号:从1-N,所以很多for(int i = 1; …) 而不是for(int i = 0; …)


活动打卡代码 AcWing 1497. 树的遍历

jackrrr
2天前
#include <iostream>
#include <unordered_map> //用户哈希表存LR

using namespace std;

const int N = 40;
int postorder[N];
int inorder[N];
unordered_map<int, int> pos; //给一个节点的值(节点的值都不相同),返回这个节点在inorder中的位置.
unordered_map<int, int> l, r; //因为我们要重构二叉树.但这里不用单链表,老师说是二叉,所以设置每个节点的左右孩子就好了.
                                    //存的是左右孩子的值,而不是ind
int q[N];//用于bfs

int build(int il, int ir, int pl, int pr){
    //找root的值
    int root_val = postorder[pr];//根节点的值
    int k = pos[root_val];//知道根节点在中序中的位置

    //判断有无左右子树, 通过看k在中序中的位置
    if(il < k) //有left, 如果il == k说明没有left树
    {
        l[root_val] = build(il, k-1, pl, pl + (k-1-il));//见解释
    }
    if(k < ir)
    {
        r[root_val] = build(k+1, ir, (pr-1) + (k+1-ir), pr-1);//bug!容易错的地方,pr是root(回忆int root_val = postorder[pr]]),所以是pr-1!
    }
    return root_val; //返回根的值
}

void bfs(int root){
    q[0] = root;

    int h, t;//queue的队首和队尾
    h = t = 0;//或者直接://int h = 0, t = 0; 

    while(h <= t) //说明还有元素
    {
        int top = q[h ++]; //如果有元素, 取出, h指向下一个
        if(l.count(top)) q[++t] = l[top]; //有左孩子, t移到空位, 放入孩子
        if(r.count(top)) q[++t] = r[top];
    }
    //走到这里,q里面留下来了所有的顺序,注意这里不是真的pop掉了,所以q里面是有数据的.

    cout << q[0];
    for(int i = 1; i < h; i++) cout << ' ' << q[i]; //之所以写在这里,因为h是局部变量
    cout << endl;
}

int main(){

    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> postorder[i];
    for(int i = 0; i < n; i++)
    {
        cin >> inorder[i];
        pos[inorder[i]] = i; //给一个节点的值(节点的值都不相同),返回这个节点在inorder中的位置.
    }

    int root_val = build(0, n-1, 0, n-1);

    bfs(root_val);

    return 0;
}


//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
  1. 这道题经常考
  2. 知识点: 如果知道前序+中序, 或者后续+中序, 是可以求出二叉树的. 但是知道前序 + 后序就不行.\
  3. 求的过程
    1. 后序的最后一个节点是root(前序是第一个节点是root)
    2. 在中序中找到这个root, 左侧就是root的左子树(求出左侧长度n),右侧柚子树(求出右侧长度m)
    3. 后续中,因为是左子树+右子树+root,所以可以知道左子树是哪一段(截取长度为n),右子树是哪一段
    4. 后序中,左子树的最后一个节点是root
    5. 重复到2.
      老师用了递归

重新构建二叉树方法:
1. 在在中序中找到这个root,就是已知值, 找index, 所以我们用哈希表存, 快, 知道某个值的下标是多少
2. 重建二叉树,是一个递归的过程. 返回当前子树的根节点.
3. 老师在构建二叉树的时候,没有使用链接表,而是使用了两个哈希表.其实非常好
1. 二叉树的重要内容就是, 某个节点(值)的左右儿子的ind是多少
2. 一个哈希表存某个节点(用值表示)的左子树,一个存右边的


  1. build()两种思路:
    已知左子树在中序的ind是[il, k-1]
    求左子树在后序的ind是[pl, ?]
    1. 长度
      因为在中序中, 左子树的长度是(k-il), 因为是[il, k), k是指向左子树最后一个节点的下一位
      所以在后续中, 右子树的最后一个节点的下一位是 pl + (k-il)
      但是我们要求的是右子树的最后一个节点的位置, 所以是 pl + (k-il) - 1;
    2. 差相等
      老师说 ? - pl == k - 1 - il
      ? == pl + (k - 1 - il)
  2. 解释l[root] = build(il, k - 1, pl, pl + (k - 1 - il));
    build(il, k - 1, pl, pl + (k - 1 - il))返回root的左子树的根
    root的左子树的根,也就是root的左儿子

  1. bfs()中,tt是指向了元素的,而不是元素的下一个

  1. 思考:
    中序: 需要建立值和位置之间的map
    后序: 不需要建立上面的map, 因为每次只要取最后一位.

  2. 思考:
    中序: 左子树+根+右子树
    后序: 左子树+右子树+根

  3. 思考:
    build的参数传入的是相同的一个树,但是build()里面又有两个build()分别服务于左子树和右子树

  4. 易错
    右子树的后序的右侧节点是Pr-1,不是pr,因为pr是根节点
    build(k+1, ir, (pr-1) + (k+1-ir), pr-1);//bug!容易错的地方,pr是root(回忆int root_val = postorder[pr]]),所以是pr-1!

  5. 思考
    重构二叉树,除了记录每个节点left,right,还需要知道root,最后通过root找左右,通过左右继续找左右.

  6. 其他错误:
    似乎不能用left,会和系统重名

  7. 语法

  8. 定义的时候
    应该是 int h = 0, t = 0;
    而不是int h = t = 0;
  9. 如果已经定义了
    int h,t;
    h = t = 0;是没问题的


活动打卡代码 AcWing 826. 单链表

jackrrr
2天前
#include <iostream>

using namespace std;

const int N = 100010;
int head, e[N], ne[N];
int ind;

void init(){
    head = -1;
    ind = 0;
}

void add_head(int a){
    e[ind] = a, ne[ind] = head, head = ind++;
}

//假设之前是 (头结点) a --> b --> c --> d --> -1, 其中b是a的next,现在要变成a --> b --> e --> c --> d --> -1
//其中b是第3个加入的节点, 在b的后面加上一个数, 这里的后面是next
void add_k(int a, int k){
    e[ind] = a, ne[ind] = ne[k], ne[k] = ind++; //也就是我ind要指向你k的下一位,你k指向我
}


void remove(int k){
    ne[k] = ne[ne[k]]; //我k不指向我的下一个了,我指向我next的next
}
int main(){

    init();

    int m;
    cin >> m;
    while(m--){
        char op; //老师用的是char
        int k, x;
        cin >> op;
        if(op == 'H'){
            cin >> x;
            add_head(x);
        }
        else if(op == 'I'){
            cin >> k >> x;
            add_k(x, k-1); //因为说的是第1个加入的元素,其实是ind==0的位置,所以k-1
        }
        else{
            cin >> k;
            if(!k) head = ne[head]; //head的next是ne[head], 所以head变成head的next
            remove(k-1);//因为说的是第1个加入的元素,其实是ind==0的位置,所以k-1
        }
    }

    for(int i = head; ~i; i = ne[i]){
        cout << e[i] << " ";
    }
    cout << endl;

    return 0;

}


活动打卡代码 AcWing 1476. 数叶子结点

jackrrr
2天前
#include <iostream>
#include <cstring> // memset()

using namespace std;

const int N = 110;
int h[N], e[N], ne[N];
int ind; //全局变量初始是0
int cnt[N];
int maxdepth;// 需要记录maxdepth, 因为我们打印的时候, 需要打印cnt[N]的前maxdepth个元素

void add(int a, int b){
    e[ind] = b, ne[ind] = h[a], h[a] = ind++;
}

void dfs(int a, int depth){
    if(h[a] == -1) //叶子,所以要插入到我们的cnt中
    {
        cnt[depth]++;
        maxdepth = max(maxdepth, depth);
        return;
    }

    for(int i = h[a]; i != -1; i = ne[i]){
        dfs(e[i], depth+1);
    }
}

int main(){
    int n, m;
    cin >> n >> m;

    memset(h, -1, sizeof h);

    while(m--){
        int id, k;
        cin >> id >> k;
        while(k--){
            int son;
            cin >> son;
            add(id, son);//将b链接到a上
        }
    }

    dfs(1,0); //为什么是(1,0),因为题目说了根节点的值是01, 所以a==01==1, 然后第一层高度是0

    cout << cnt[0]; //一定能保证有一个叶子,因为如果只有一个根节点, 根节点就是叶子
    for(int i = 1; i <= maxdepth; i++) cout << " " << cnt[i];

    cout << endl;

    return 0;
}

思路:
1. 存树的形状
3. 一般用dfs能做的bfs也能做,但是dfs代码短,不像bfs需要维护queue

  1. 主要考察树:
    h[a]其实是a这个节点的叶子节点的token,这个token其实是ind,可以帮我们索引到一个链表,也就是说这个链表的所有元素,都是a这个节点的叶子节点
    假设h[a] == ind, 那么e[ind] == b说明节点a的一个子节点是b
    ne[ind] == ind2说明这个子节点b也有一个链表, 这个链表的token是ind2
    因为之前设置的时候ne[ind] = h[b]?

故事是这样的,假设我们要给a节点的链表中插入一个b节点, 现在空余的token是ind
h[a]表示的是, a节点的链表的头结点的token, 我们要注意, 加的方式是新来的元素是插入头结点, 想象:
刚开始是h[a] = -1是什么都没有加过,之后分别加入cdf之后,链表是-1 – c – d – f(头结点), 所以最后一个进入的f是在头结点
谁是谁的next!!! c是d的next, 所以这是我之前纠结的地方,next是在左边, 其实你如果想象成f – d – c – -1就是next在右边了!
所以假设d当时拿到的token是ind, ne[ind] == c的token!! 也就是b的next是c

现在空余的token是ind,既然ind还没用过, 我们就用吧
e[ind] = b, 将e[ind]这个没有用过的地方, 放入b的值
ne[ind] = h[a], 也就是我们将b的next,设置为之前的老的头结点(h[a])
h[a] = ind++, 现在a节点的新的头节点是ind了!

我给一个例子吧, 刚开始ind == 0, h[]所有初始化是-1
void add(int a(8), int b(9))
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ;
相当于是:
e[0] = 9, ne[0] = -1, h[8] = 0, ind = 1;
}
void add(int a(8), int c(7))
{
e[idx] = b, ne[idx] = h[a], h[a] = idx
;
相当于是:
e[1] = 7, ne[1] = 0, h[8] = 1, ind = 2;
}

遍历的时候:
for (int i = h[u]; ~i; i = ne[i]) //注意-1的0x是1111 1111,所以~(-1) == 0
dfs(e[i]);
i = h[8] == 1
e[i] == e[1] 也就是c的值7
i = ne[i] == ne[1] == 0, 也就是去到token是0的地方
e[i] == e[0] 也就是b的值8
i = ne[i] == ne[0] == -1
结束




jackrrr
3天前

思路:
1. 老师说插入排序的特点: 左侧的元素都是拍好的(递增的),右侧的元素都是和原来的元素一样
2. 老师说堆排序的特点: 左侧是堆的顺序, 右侧是最大的前k个数. 总之,堆顶的元素i是 <= 右侧的所有元素的
3. 因为题目是保证唯一解, 所以肯定是分了左右侧,没有分左右侧说明排序完了,排序结束两种方法的结果都一样,所以即可以说是堆排序也可以说是插入排序,答案不唯一.
4. 回忆插入排序: 右侧的元素一直跟左侧的元素打擂台,一直到打不过
5. 回忆堆排序: 左侧的堆顶(最大值),插入到数组末尾,siftdown()之后,左侧的堆顶又是一个最大值,插入到数组末尾
6. 因为插入排序好判断(左侧有序,右侧原封不变),堆排序不好判断(需要看左侧是否满足堆还是比较麻烦的)
7. 所以,先判断是否是插入,是,就继续插入排序.不是,说明是堆排序,找到数组的左右两侧(by 堆顶的元素i是 <= 右侧的所有元素的),最后继续堆排序
8. 很多bug,很容易写错


#include <iostream>

using namespace std;

const int N = 110;

int a[N];
int b[N];

void siftdown(int pos, int size){
    int t = pos;
    if(2*pos+1 < size && b[t] < b[2*pos+1]) t = 2*pos+1; //bug,主义是t = 2*pos+1, 而不是pos = 2*pos+1 //这句话:如果存在做儿子 && left儿子比自己大
    if(2*pos+2 < size && b[t] < b[2*pos+2]) t = 2*pos+2; //bug, 这里是b[t] < b[2*pos+1]而不是b[pos] < b[2*pos+1], 因为这里一共有两个if,所以上面的t = 2*pos+1 可以影响我们这个t, 所以假设上一句 left比自己大, 但是现在发现right 比 left大, 那么我们就要把父亲和right交换.
    if(t != pos ){//是否被修改过
        swap(b[t], b[pos]); //交换
        siftdown(t, size); //注意这里是size,因为堆的大小没变
    }
}
int main(){
    int n;
    cin >> n;



    for(int i = 0 ; i < n ; i ++) cin >> a[i];
    for(int i = 0 ; i < n ; i ++) cin >> b[i];

    //插入排序比较容易检查,所以检查插入
    int p = 1; 
    while(p < n && b[p-1] <= b[p]) p++; //bug, 注意是 b[p-1] <= b[p], 也就是可以相等或者单调递增

    //此时的p是指向右侧的第一个元素
    int k = p;
    while(p < n && a[p] == b[p]) p++;

    if(p == n){ //说明是插入排序, bug, 容易错, p如果指向数组的最后一个ind,应该是n-1, 所以n-1+1 = n, 而不是if(p == n+1)
        puts("Insertion Sort");

        //进行插入排序之后的事情,从k开始向左打雷
        while( k >= 1 && b[k-1] > b[k]) { //只有k左边有人才能打,所以k至少是ind == 1
            swap(b[k-1], b[k]);
            k--;
        }

    }
    else{ //因为一定有解,所以是堆排序
        //接下来确定右侧在哪里
        int top = b[0];
        int p = n-1;
        while(p >= 1 && b[p] >= top) p--;

        //此时p是左侧堆的最末尾的节点
        swap(b[0],b[p]); //bug! 注意是先将堆顶给移到后面,然后我们在对前面0到q-1索引的元素排序
        siftdown(0, p); //因为是0到p-1,所以size == p
        puts("Heap Sort");
    }

    cout << b[0];
    for(int i = 1; i < n; i ++) cout << " " << b[i];
    cout << endl;

    return 0;
}



活动打卡代码 AcWing 1561. PAT 评测

jackrrr
3天前
  1. 数据规模只有10000, 10^4所以不用scanf()
  2. 构造了一个struct, 其中有total总分, 也有cnt满分题目个数
  3. 使用的技巧: 重载操作符, 构建函数
  4. 因为需要排序, 所以要用到了vector<>
  5. 在input的时候, 完成了记录一个人每道题的最大成绩
  6. 之后,在遍历的时候,计算了一个人是否编译通过并提交过, 如果提交过, 就计算这个人的total,cnt, 最后将这个人push到vector
  7. 用sort(),所以重载了操作符.
  8. 厉害的地方, 用grade = -2,-1,0,x分别代表了没有提交,编译错误,答案错,部分正确. 其中用Max(0,grade)来输出总分(因为没有提交和编译错误不算成负分), 用 if(grade >= 0)来判断是否提交过(因为-2和-1都是没有提交和编译错误)
  9. 因为题目中grade只会是-1,0,x不会是-2,所以你设置成-2就有必要.我也想试试(不行,因为-2和-1在output严格区分了)
  10. 超级容易错!
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

const int K = 10; //最多5道题

int full_grade[K];
int n, k, m; //k要是全局变量,因为struct Student用到了

struct Student{
    string id;
    int grade[K]; //bug, 这里应该是K, 而不能是k, 因为k现在还不确定. 如果写k会报错:array bound is not an integer constant before ']' token
    int total; //总分
    int cnt; //满分个数
    int rank; //排名

    Student() {} //default初始
    Student(string _id) : id(_id){ //这里: id(_id)相当于直接初始了id
        total = 0;
        cnt = 0;
        rank = -1;
        for(int i = 0; i < k; i ++) grade[i] = -2; //必须是-2, 而不是-1. -2表示从未提交,-1表示编译错误, 题目中output是严格区分两者了
    }

    bool has_submit(){
        for(int i = 0; i < k; i++)
        {
            if(grade[i] >= 0){ //因为0和正整数都表示成功提交了
                return true;
            }
        }
        return false;
    }

    void calc(){
        for(int i = 0 ; i < k; i++){ 
            if(grade[i] >= 0) total += grade[i]; //bug, 小心-1是算作0加入总分的 
            if(grade[i] == full_grade[i]) cnt ++;
        }
    }

    bool operator< (const Student& t) const{
        if(total != t.total) return total > t.total;
        if(cnt != t.cnt) return cnt > t.cnt;
        return id < t.id;
    }
};

int main(){

    scanf("%d%d%d", &n, &k ,&m); //bug! 我之前写成&n, &m ,&k, 一直导致了segmentation fault

    //读满分
    for(int i = 0; i < k; i++){ 
        scanf("%d", &full_grade[i]);
    }

    //读提交
    unordered_map<string, Student> map;

    for(int i = 0; i < m; i ++){
        char u_id_s[10];
        int p_id, g;
        scanf("%s %d %d", u_id_s, &p_id, &g);
        string u_id = u_id_s;

        if(map.count(u_id) == 0) //如果学生没有遇见过,就初始化
        {
            map[u_id] = Student(u_id); //这里调用了初始化函数.
        }

        p_id--; //bug!, 因为题目K的编号是从1开始的!
        //之后我们判断题目p_id的成绩g是不是这个学生最好的成绩
        map[u_id].grade[p_id] = max(map[u_id].grade[p_id], g);
    }

    //到此为止, 所以学生都初始完了,并且都保留了最好成绩
    //接下来看哪些学生虽然初始化了,但是没有提交
    //提交的,计算total和cnt,并且push到vec里面
    vector<Student> vec; //将提交的学生放到vec中, 之后去排序
    for(auto& item : map){ //注意, 这里的item不是Studnet,而是<string, Student>
        auto& s = item.second;
        if(s.has_submit()){
            s.calc(); //计算total和cnt;
            vec.push_back(s);
        }
    }

    sort(vec.begin(), vec.end()); //用了操作符重载

    //计算排名
    for(int i = 0; i < (int)vec.size(); i++){
        if(!i || vec[i].total < vec[i-1].total)
            vec[i].rank = i + 1;
        else
            vec[i].rank = vec[i-1].rank;
    }

    //打印
    for(auto& s : vec){
        printf("%d %s %d", s.rank, s.id.c_str(), s.total);
        for(int i = 0 ; i < k ; i++) { 
            if(s.grade[i] == -2) cout << " -"; //bug, 题目说了(如果未提交就是-, 如果编译出错或者没有写对还是0)
            else cout << " " << max(0,s.grade[i]); //bug, 因为可能s.grade[i]依旧是初始值-2
        }
        cout << endl;
    }

    return 0;
}



活动打卡代码 AcWing 1538. 链表排序

jackrrr
3天前
  1. 这个代码厉害的地方在于, 我们用哈希表来找一个链表了
    unordered_map[HTML_REMOVED] student;
    for(string i = head; i != “-1”; i = student[i].next)
  2. 找到链表之后,推入vector,对vector进行排序(需要重载Node的符号),最后输出
  3. 这道题, N = 10^5, 所以不能用cin,cout
  4. 老师说,我们之所以喜欢在算法比赛中,开一个结构体数组,是因为:
    1. 时间短,只有1s,如果你一个结构体一个结构体的new, 时间不够
      因为new本质上是malloc,new一次很快,但是很多次的话,就会超时
    2. 如果我们开了一个结构体数组
      相当于就只new了一次,但是new的空间很大
      new的次数多对时间的影响大,但是new的空间大对时间影响不大
    3. 在工程中,喜欢不停new,是因为没有时间限制
      1. 假设来一个用户,new一次
      2. 不可能1s中内,来10^5个客户(除了11.11)
        其他bug
  5. 忘记加c_str()
  6. printf(“%s %d %s\n”, vec[i].addr.c_str(), vec[i].val, vec[i+1].addr.c_str()); //小心bug! 最后是s %d %s,不是s %d %d, 另一个bug, 最后输出的是vec[i+1].addr而不是vec[i].next;
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>

using namespace std;

struct Node{
    string addr;
    int val;
    string next;

    bool operator< (const Node& t) const{
        return val < t.val; //我优先(排在左边)的条件, 我的值更小
    }
};

int main(){
    int n;
    char head[6];
    scanf("%d %s", &n, head);

    char addr[10], next[10];
    int val;
    unordered_map<string, Node> map;
    while(n --){
        scanf("%s %d %s", addr, &val, next);
        map[addr] = {addr, val, next};
    }   

    //制作链表,把每个节点都推入vector
    vector<Node> vec;
    for(string i = head; i != "-1"; i = map[i].next ) vec.push_back(map[i]);

    printf("%d ", (int)vec.size());
    //对vec排序, 会用到Node的小于号
    if(vec.size())
    {
        sort(vec.begin(), vec.end());
        printf("%s\n", vec[0].addr.c_str()); //打印头结点地址, 注意要c_str()

        for(int i = 0; i < (int)vec.size(); i++){ //注意如何判断是否是最后一个节点
            if(i == (int)vec.size()-1)
                printf("%s %d %d\n", vec[i].addr.c_str(), vec[i].val, -1);  //尾结点的next是-1
            else
                printf("%s %d %s\n", vec[i].addr.c_str(), vec[i].val, vec[i+1].addr.c_str()); //小心bug! 最后是%s,不是%d, 另一个bug, 最后输出的是vec[i+1].addr而不是vec[i].next;
        }
    }
    else{
        puts("-1");
    }
    return 0;
}



活动打卡代码 AcWing 1523. 学生课程列表

jackrrr
3天前
  1. 其实这道题很简单,关键看你怎么存
  2. 它的input是一个ind,后面包含了若干个string
  3. 他需要的output是给一个string,你输出若干个int
  4. 所以你存的时候,可以是一个string + 若干个int, 所以就是用map, 因为这里不涉及到排序,所以是unordered_map
  5. 因为输出的int是升序的,所以记得用sort
  6. 用auto的时候,想清楚这个到底是什么类型
  7. 我们用cin, 因为输入是40000, 还不到10^5
#include <unordered_map>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

unordered_map<string, vector<int>> students;

int main(){
    int n, m;
    cin >> n >> m;

    while(m--){
        int id, p;
        cin >> id >> p;
        while(p--){
            string name;
            cin >> name;
            students[name].push_back(id); //注意不是student[name] = p;
        }
    }

    //method 1
    /*
    for(auto& s : students){ //s是<string, vector<int>>, 所以记得是s.second
        sort(s.second.begin(), s.second.end());
    }

    while(n--){
        string name;
        cin >> name;
        cout << name << " " << students[name].size();
        for(auto& id : students[name]) //如果student[name]都没有就是不会走这个for loop
                cout << " " << id;
        cout << endl;
    }
    */

    //method 2
    while(n--){
        string name;
        cin >> name;

        cout << name << " " << students[name].size();
        sort(students[name].begin(), students[name].end());
        for(auto id : students[name]){
            cout << " " << id;
        }
        cout << endl;
    }

    //method 1,2 end
    return 0;
}




活动打卡代码 AcWing 1505. 列表排序

jackrrr
3天前

思路:
1. 遇到复杂的结构,用结构体
2. 这道题需要用多种排序,但是重载标识符只能用一次,所以我们是自定了3个比较函数
3. sort()如果没有第三个参数,就是看容器(vector)里面的数据的小于操作符,如果有第三个参数,第三个参数就是比较函数
4. 什么时候用cin,cout/scanf(),printf()
1. 在数据量很小的时候用cin, cout
2. 在数据量很大(10^5)时候,用scanf(),printf().否则会超时.
注意,这里说的用scanf()和printf()是排他的用
也就是一个cin,cout都不能有!一个都不行
否则会因为什么同步?的问题,削弱scanf()
3. 在数据输入比较复杂的时候,用scanf(),printf()
5. cin,cout / scanf(), printf()
1. cin,cout可以输出输入string
2. 但是scanf()不能输入string,需要我们先输入成char xx[10], 然后再 = {xx} 来当做string push进去
记得scanf()输入%d的时候,需要 &, 例如scanf(“%d”, &yy);
3. printf()也不能输出string,需要我们printf(“%s”, xx.c_str()), 否则输出乱码
6. 定义结构体
1. 可以通过数组的方式: struct _xx{}XX[N];
1. 插入是: XX[i] = {a,b,c};
2. 适用于题目告诉我们size
3. 如果是用数组的话,我们记得就不要用while(n–), 而使用for(int i = 0; i < n ; i++) 因为一个我们需要XX[i] = xx, 另一个因为之后需要用n来知道XX的size
2. 可以通过vector的方式: struct _xx{}; vector<_xx> XX;
1. 插入是: XX.push_back({a,b,c});
2. 适用于题目没有告诉我们size,我们需要用.size(), 否则自己开新变量存size很麻烦
2. 使用于需要比较运算

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

struct Row{
    string id;
    string name;
    int grade;
}row[N];

bool cmp1(Row a, Row b){
    return a.id < b.id; 
}

bool cmp2(Row a, Row b){
    if(a.name != b.name) return a.name < b.name;
    return a.id < b.id;
}

bool cmp3(Row a, Row b){
    if(a.grade != b.grade) return a.grade < b.grade;
    return a.id < b.id;
}

int main(){
    int n, m;
    scanf("%d%d", &n, &m);

    char id[10], name[10]; //只能用char[]来用scanf()读
    int grade;
    for(int i = 0; i < n; i++)
    {
        scanf("%s %s %d", id, name, &grade);
        row[i] = {id, name, grade};
    }

    if(m == 1){
        sort(row, row + n, cmp1);
    }
    else if(m == 2){
        sort(row, row + n, cmp2);
    }
    else{
        sort(row, row + n, cmp3);
    }

    for(int i = 0; i < n; i++){
        printf("%s %s %d\n", row[i].id.c_str(), row[i].name.c_str(), row[i].grade);
    }

    return 0;
}


活动打卡代码 AcWing 1502. PAT 排名

jackrrr
4天前

思路
1. 读取student的内容(创建student struct,因为复杂的内容用struct处理会简单一些)
2. 创建n个分地区的vector,vector[HTML_REMOVED] local[N]
3. 创建1个总地区vecotr, vector[HTML_REMOVED] all;
4. 每次读取就分别向分和总插入(主义是分地区加工后,再加入总地区),分插入的时候按照ind来索引是哪个local[N]
5. 对分总排序.
6. 老师最后的计算排名的方法:
1. 假设是 0 1 2 3 4 5
2. 100 99 99 99 98 98
3. 排名 1 2 2 2 3 3
方法: 从0开始,假设不等于左侧:排名就是自己的ind+1, 如果等于左侧:就是左侧的排名

  1. 关于重载标志服
    1. 只需要思考, 返回我优先: 因为我的grade大我优先, 所以return grade > t.grade
    2. 只需要思考, 返回我优先: 因为我的id小我优先, 所以return id < t.id
  2. 其实没有我设想的vector[HTML_REMOVED] studnets; 创建了一个学生的vecotor,而都是地区的vector
  3. 所以其实是一个学生的信息其实是复制了两次,一次给了local地区一个是global地区
  4. 易错,我们是local进行加工之后,然后将id, grade, location, local_rank加入总
  5. 最后是从总来打印
#include <iostream>
#include <algorithm> //sort
#include <vector>

using namespace std;

const int N = 110; //最多100个地区
const int M = 310; //每个地区最多300人

//构建student
struct Student{
    string id;
    int grade;
    int location;
    int local_rank;
    int global_rank;

    bool operator< (const Student& t) const{ //用于sort()的时候比较Student
        if(grade != t.grade) return grade > t.grade; //返回的是我优先,如果我的grade大的话,就是我优先
        else return id < t.id; //返回的是我优先
    }
};

vector<Student> local[N]; //不能写成vector<int> local[N], 因为我们在sort()的时候不单单要
vector<Student> global;

int main(){
    int n;
    cin >> n;

    for(int i = 0; i < n; i ++){ //这里的i可以当做地区名
        int m;
        cin >> m;
        while(m--){
            string id;
            int g;
            cin >> id >> g;
            local[i].push_back({id, g, i + 1}); //后面的会自动补齐,也就是0, 注意: 地区编号按输入顺序依次为 1∼N
        }

        //加下来对i地区的人进行排名,然后local_rank记录进去
        auto& l = local[i]; //l是vector<Student>
        sort(l.begin(), l.end()); //这里会用到标志服重载,所以grade大的,id小的在前面
        for(int j = 0; j < l.size(); j++){
            if(!j || l[j].grade != l[j-1].grade)
                l[j].local_rank = j+1;
            else
                l[j].local_rank = l[j-1].local_rank;

            global.push_back(l[j]);//因为最后需要全部内容打印, 所以我们将global存了全部内容
            //注意,这里不是push_back({id, grade, local_rank}), 而是直接将l[j], 也就是一个studnet插入了里面
        }
    }

    sort(global.begin(), global.end());
    for(int j = 0; j < global.size(); j++){
            if(!j || global[j].grade != global[j-1].grade)
                global[j].global_rank = j+1;
            else
                global[j].global_rank = global[j-1].global_rank;
    }

    //目前为止,global里面的每个学生,拥有了global_rank,然后global本身的排序也是题目要的
    cout << global.size() << endl;
    for(auto& s : global){
        cout << s.id << " " << s.global_rank <<" " << s.location << " " << s.local_rank << endl;
    }

    return 0;
}