CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » namespace » week_summary_1
2020-2021:teams:namespace:week_summary_1

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版 		前一修订版
2020-2021:teams:namespace:week_summary_1 [2020/05/09 12:13]
kongyou [kongyou] 		2020-2021:teams:namespace:week_summary_1 [2020/07/09 20:49] (当前版本)
great_designer
行 1: 行 1:
-====== 2020/05/02--2020/05/08 周报 ======+====== 2020/05/04--2020/05/10 周报 ====== 
 + 
 +后一篇：[[week_summary_2]]
  
 ===== 团队训练 ===== ===== 团队训练 =====
行 19: 行 21:
 本来还有最经典的背包问题想总结（灌水）一下，奈何实在没有时间，鸽了。 本来还有最经典的背包问题想总结（灌水）一下，奈何实在没有时间，鸽了。
  
-另外更新了BUAAOJ代码库大概几十道吧。BUAAOJ计划：[[https://​github.com/​Great-designer/​BUAA-OJ-Project]]+另外更新了BUAAOJ代码库大概几十道吧。BUAAOJ计划：[[https://​github.com/​Great-designer/​BUAA-OJ-Project|GitHub：BUAAOJ计划]]
  
 之前搞数竞的Designer，准大三苟，喜欢逻辑向、精巧工整的代码，讨厌冗长，目前正压在Java、软工、数据库和系统编程四座大山下。 --- //​[[ljscan@163.com|李淳一]] 2020/05/08 19:32// 之前搞数竞的Designer，准大三苟，喜欢逻辑向、精巧工整的代码，讨厌冗长，目前正压在Java、软工、数据库和系统编程四座大山下。 --- //​[[ljscan@163.com|李淳一]] 2020/05/08 19:32//
行 57: 行 59:
 ==== Great_designer ==== ==== Great_designer ====
  
-（历史题解）我的第一个中等题题解推荐给各位：[[https://​www.bilibili.com/​read/​cv3575020]]+（历史题解）我的第一个中等题题解推荐给各位：[[https://​www.bilibili.com/​read/​cv3575020|生日蛋糕问题]]
  
 ==== kongyou ==== ==== kongyou ====
-====== ​一道让我有所收获的题（线性表的组织） ====== +一道洛谷上的题，通过对数组和链表各自的特点来解决TLE等问题 [[线性表的实现]]
- +
-​ 洛谷链接：https:​%%//​%%www.luogu.com.cn/​problem/​P1160 +
- +
-​ 考察点：线性表的组织、插入删除与查找 +
- +
-===== 题目描述 ===== +
- +
-一个学校里老师要将班上N个同学排成一列，同学被编号为1∼N，他采取如下的方法： +
- +
-  - 先将1号同学安排进队列，这时队列中只有他一个人； +
-  - 2−N号同学依次入列，编号为i的同学入列方式为：老师指定编号为i的同学站在编号为1∼(i−1)中某位同学（即之前已经入列的同学）的左边或右边； +
-  - 从队列中去掉M(M<​N)个同学，其他同学位置顺序不变。 +
- +
-在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号。 +
- +
-===== 输入格式 ===== +
- +
-第1行为一个正整数N，表示了有N个同学。 +
- +
-第2−N行，第i行包含两个整数k,​p，其中k为小于i的正整数，p为0或者1。若p为0，则表示将i号同学插入到k号同学的左边，p为1则表示插入到右边。 +
- +
-第N+1行为一个正整数M，表示去掉的同学数目。 +
- +
-接下来M行，每行一个正整数x，表示将x号同学从队列中移去，如果x号同学已经不在队列中则忽略这一条指令。 +
- +
-===== 输出格式 ===== +
- +
-1行，包含最多N个空格隔开的正整数，表示了队列从左到右所有同学的编号，行末换行且无空格。 +
- +
-===== 输入输出样例 ===== +
- +
-**输入** +
- +
-<​code>​ +
-4 +
-1 0 +
-2 1 +
-1 0 +
-2 +
-3 +
-3 +
-</​code>​ +
-**输出** +
- +
-<​code>​ +
-2 4 1 +
-</​code>​ +
-===== 说明/​提示 ===== +
- +
-==== 样例解释： ==== +
- +
-将同学2插入至同学1左边，此时队列为：21 +
- +
-将同学3插入至同学2右边，此时队列为：231 +
- +
-将同学4插入至同学1左边，此时队列为：2341 +
- +
-将同学3从队列中移出，此时队列为：241 +
- +
-同学3已经不在队列中，忽略最后一条指令 +
- +
-最终队列：241 +
- +
-==== 数据范围 ==== +
- +
-对于20%的数据，有N≤10；对于40%的数据，有N≤1000；对于100%的数据，有N,​M≤100000。 +
- +
- +
-===== 解题说明 ===== +
- +
-<​code>​ +
-    本题考查点为线性表。由于我们需要对题目进行按照要求采用双向链表进行操作即可。但是如果单纯的用链表会产生TLE等情况。这时想到数组具有查找快的特点，链表具有插入删除快的特点。同时注意到学生的顺序是依次连续增加的。所以可以将二者的优点结合起来，用结构体数组存链表。这样就解决了TLE的问题。 +
-</​code>​ +
-==== 参考代码 ==== +
- +
-<code c> +
-#include <​stdio.h>​ +
-#include <​stdlib.h>​ +
- +
-struct Node { +
-    int flag; +
-    int id; +
-    struct Node *left; +
-    struct Node *right; +
-}queue[100010]; +
- +
-int main() { +
-    struct Node *head; +
-    head = &queue[0]; +
-    head->id = 1; +
-    head->​flag = 0; +
-    head->​left = NULL; +
-    head->​right = NULL; +
-    int i; +
-    int n; +
-    scanf("​%d",​ &n); +
- +
-    for (i = 2; i <= n; i++) { +
-        int k, p; +
-        struct Node *next = NULL; +
-        next = &​queue[i - 1]; +
-        scanf("​%d%d",​ &k, &p); +
-        struct Node *temp = &​queue[k - 1]; +
-        if (p == 0) { +
-            next->id = i; +
-            next->​flag = 0; +
-            next->​right = temp; +
-            if (temp->​left != NULL) { +
-                next->​left = temp->​left;​ +
-                temp->​left->​right = next; +
-            } +
-            else { +
-                head = next; +
-            } +
-            temp->​left = next; +
-        } +
-        else { +
-            next->id = i; +
-            next->​flag = 0; +
-            next->​left = temp; +
-            if (temp->​right != NULL) { +
-                next->​right = temp->​right;​ +
-                temp->​right->​left = next; +
-            } +
-            temp->​right = next; +
-        } +
-    } +
- +
-    int m; +
-    scanf("​%d",​ &m); +
-    for (i = 0; i < m; i++) { +
-        int temp; +
-        scanf("​%d",​ &​temp);​ +
-        queue[temp - 1].flag = 1; +
-    } +
- +
-    struct Node *temp = head; +
-    while (temp != NULL) { +
-        if (temp->​flag != 1) { +
-            printf("​%d ", temp->​id);​ +
-        } +
-        temp = temp->​right;​ +
-    }+
  
-    return 0; 
-} 
-</​code>​ 
 ==== serein ==== ==== serein ====
  
 [[常量数组]] [[常量数组]]
2020-2021/teams/namespace/week_summary_1.1588997595.txt.gz · 最后更改: 2020/05/09 12:13 由 kongyou

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3