炸表*2
jxtxzzw edited 5 年,10 月前
编号 | 名称 | 难度 | 来源 | 出题人 | 题解 | 备注 |
---|---|---|---|---|---|---|
0001 | A+B Problem | Naive | 题库 | 题库 | ||
0002 | A+B Problem Templated | Naive | 题库 | 题库 | 模板题 | |
0003 | 数据结构开课啦 | Naive | 新题 | jxtxzzw | 查看讨论区 | 填空题 |
1001 | 线性表插入删除操作 | Naive | 新题 | 10165102128 | ||
1002 | 线性表的比较 | Easy | 新题 | 10165102128 | ||
1003 | 线性表插入删除操作 | Easy | 新题 | Robin | ||
1004 | 环形双向链表的删除操作 | Medium | 新题 | 10165102128 | ||
1005 | 线性表去重 | Easy | 新题 | Robin | ||
1006 | 线性表顺序查找 | Naive | 新题 | Robin | ||
1007 | 线性表二分查找 | Easy | 新题 | Robin | ||
1008 | 经典的猜数游戏 | Medium | 题库 | 题库 | jxtxzzw的EOJ博客:EOJ-3342-交互题初体验 | 经典的二分查找 |
1009 | 环形队列 | Easy | 新题 | Robin | ||
1010 | 医疗调度系统 | Hard | 新题 | jxtxzzw | 本博客文末附题解 | |
1011 | 循环打印 | Medium | 新题 | 10165102128 | ||
1012 | 查词典 | Medium | 新题 | Robin | ||
1013 | 欣赏书法 | Hard | 新题 | Robin | Robin的EOJ博客:数据结构 1013 欣赏书法题解 | |
1014 | 座位分配 | Medium | 新题 | 10165102128 | ||
1015 | 银行排队夹塞 | Hard | 新题 | 10165102128 | 本博客文末附题解 | |
1016 | 玩具谜题 | Medium | 题库 | 题库 | ||
1017 | 题库整理 | Medium | 新题 | Robin | ||
1018 | 铁路调度 | Hard | 新题 | jxtxzzw | ||
1019 | 可旋栈 | Medium | 题库 | 题库 | ||
1020 | 波兰表达式 | Hard | 题库 | 题库 | ||
1021 | 一元多项式乘法 | Super | 题库 | 题库 | ||
1022 | 表达式 | Super | 题库 | 题库 | ||
1023 | 迷宫 | Hard | 新题 | jxtxzzw | ||
1024 | 皇后问题 | Medium | 题库 | 题库 | ||
1025 | 皇后问题(SPJ) | Medium | 新题 | jxtxzzw | ||
1026 | 百万皇后 | Super | 新题 | jxtxzzw | 跳转到jxtxzzw个人博客 | 局部搜索,随机算法 |
1027 | 游程长度编码 | Easy | 题库 | 题库 | ||
1028 | 方言翻译 | Hard | 新题 | jxtxzzw | ||
1029 | 统计字符串个数 | Naive | 题库 | 题库 | ||
1030 | 字串排序 | Naive | 题库 | 题库 | ||
1031 | 删除子串 | Naive | 题库 | 题库 | ||
1032 | 构造字典序最小字符串 | Naive | 题库 | 题库 | ||
1033 | 字符串的交织 | Naive | 题库 | 题库 | ||
1034 | 字符串替换 | Medium | 题库 | 题库 | ||
1035 | 字符串消除 | Easy | 题库 | 题库 | ||
1036 | 反转字符串 | Medium | 题库 | 题库 | ||
1037 | 最长连续公共子序列 | Medium | 题库 | 题库 | ||
1038 | 最长回文子串 | Easy | 题库 | 题库 | ||
1039 | 字符串模式匹配简单匹配 | Naive | 新题 | Robin | ||
1040 | 字符串模式匹配KMP算法 | Hard | 新题 | Robin | ||
1041 | 字符串模式匹配BM算法 | Medium | 新题 | Robin | ||
1042 | GPS数据处理 | Hard | 新题 | jxtxzzw | 本博客文末附题解 | |
1043 | 网址的替换 | Hard | 新题 | jxtxzzw | 本博客文末附题解 | |
1044 | 密码碰撞 | Medium | 题库 | 题库 | 博客入口 | |
1045 | 稀疏矩阵三元组转化 | Naive | 题库 | 题库 | ||
1046 | 三元组稀疏矩阵相加 | Easy | 题库 | 题库 | ||
1047 | 冒泡排序 | Easy | 新题 | 10165102128 | ||
1048 | 插入排序 | Naive | 新题 | Robin | ||
1049 | 选择排序 | Naive | 新题 | Robin | ||
1050 | 选择排序(构造) | Super | 新题 | jxtxzzw | ||
1051 | 快速排序 | Easy | 新题 | Robin | ||
1052 | 快速排序的优化 | Medium | 新题 | Robin | ||
1053 | 统计工龄 | Naive | 新题 | jxtxzzw | ||
1054 | 排名汇总 | Medium | 新题 | 10165102128 | ||
1055 | 成绩排序 | Easy | 新题 | Robin | ||
1056 | 恢复古诗 | Hard | 新题 | jxtxzzw | 恢复古诗 | |
1057 | 数组排序 | Naive | 题库 | 题库 | ||
1058 | 二维数组排序 | Easy | 题库 | 题库 | ||
1059 | 鞍点 | Naive | 题库 | 题库 | ||
1060 | 树的双亲存储法 | Medium | 题库 | 题库 | ||
1061 | 树的层号表示法 | Easy | 新题 | Robin | ||
1062 | 还原二叉树 | Easy | 新题 | jxtxzzw | ||
1063 | 目录树 | Super | 新题 | jxtxzzw | 随课程进度逐步开放 | |
1064 | 最小权值路径 | Medium | 新题 | Robin | ||
1065 | 二叉树路径和 | Super | 新题 | 10165102128 | 随课程进度逐步开放 | |
1066 | 下落的小球 | Medium | 新题 | 10165102128 | 随课程进度逐步开放 | |
1067 | 平衡二叉树 | Medium | 新题 | Robin | 随课程进度逐步开放 | |
1068 | 二叉搜索树 | Medium | 新题 | jxtxzzw | 随课程进度逐步开放 | |
1069 | 圆上相交弦 | Super | 题库 | 题库 | 进入jxtxzzw个人博客阅读 | 红黑树 |
1070 | 最优二叉搜索树 | Easy | 题库 | 题库 | 随课程进度逐步开放 | |
1071 | 寻找EMB富豪 | Hard | 新题 | jxtxzzw | 随课程进度逐步开放 | 堆排序,在线处理 |
1072 | 树种统计 | Easy | 新题 | jxtxzzw | ||
1073 | Windows消息队列 | Medium | 新题 | jxtxzzw | ||
1074 | Huffman树的最小外部加权值 | Medium | 题库 | 题库 | ||
1075 | 构造Huffman树 | Super | 新题 | jxtxzzw | 随课程进度逐步开放 | |
1076 | Huffman解密 | Medium | 新题 | Robin | 随课程进度逐步开放 | |
1077 | 朋友圈 | Medium | 新题 | jxtxzzw | 随课程进度逐步开放 | |
1078 | Virtual Friends | Easy | 题库 | 题库 | 随课程进度逐步开放 | |
1079 | 小强的烦恼 | Medium | 题库 | 题库 | 随课程进度逐步开放 | |
1080 | 食物链 | Medium | 题库 | 题库 | 随课程进度逐步开放 | |
1081 | 华师大卫星照片 | Easy | 题库 | 题库 | ||
1082 | 哥尼斯堡的七桥问题 | Medium | 新题 | jxtxzzw | 随课程进度逐步开放 | |
1083 | 地下迷宫探索 | Medium | 新题 | jxtxzzw | ||
1084 | 最短路径 | Medium | 新题 | jxtxzzw | 随课程进度逐步开放 | |
1085 | 路由器 | Easy | 题库 | 题库 | ||
1086 | Arbitrage | Easy | 题库 | 题库 | ||
1087 | 六度空间 | Medium | 新题 | jxtxzzw | ||
1088 | 组网计划 | Medium | 题库 | 题库 | ||
1089 | 哈利·波特的考试 | Medium | 新题 | 10165102128 | ||
1090 | 寻找航海路线 | Hard | 题库 | 题库 | 随课程进度逐步开放 | |
1091 | 公路村村通 | Easy | 新题 | jxtxzzw | ||
1092 | Building Roads | Easy | 题库 | 题库 | ||
1093 | Hub Connection plan | Easy | 题库 | 题库 | ||
1094 | 旅游规划 | Medium | 新题 | 10165102128 | ||
1095 | 城市间紧急救援 | Hard | 新题 | jxtxzzw | 随课程进度逐步开放 | |
1096 | 检查点 | Super | 新题 | jxtxzzw | 随课程进度逐步开放 | |
1097 | 酒精饮料 | Hard | 新题 | jxtxzzw | 随课程进度逐步开放 | |
1098 | 任务调度问题 | Medium | 新题 | jxtxzzw | 随课程进度逐步开放 | |
1099 | 关键活动 | Hard | 新题 | jxtxzzw | 随课程进度逐步开放 | |
1100 | 旅行商问题 | Super | 新题 | jxtxzzw | 跳转到jxtxzzw个人博客 | 随机算法 |
9001 | 异常的葡萄 | Super | 新题 | jxtxzzw | 弃用题,无题解,有疑问私聊jxtxzzw | 聚类 |
9002 | 电子邮件地址验证 | Super | 新题 | jxtxzzw | 弃用题,无题解,有疑问私聊jxtxzzw | 字符串处理 |
对于一个给定的队列$1,2,\cdots , n$,在默认情况下,每次都是第一个元素出队且加入到队尾,即依次变成$2,3,\cdots,n,1$,之后是$3,4,\cdots, n-1,n,1,2$……
但是当遇到E
命令时,需要将指定的元素(无论他处在队列的什么位置)强行移动到队首,例如对于上述$3,4,\cdots, n-1,n,1,2$情况下,如果要求E 5
,那么元素$5$移动到队首,队列变成$5,3,4,6,\cdots, n-1,n,1,2$,下次要求出队的时候,应该是$5$出队并且移动到队尾。
写一个程序实现这个过程,并针对输入数据模拟输出出队的每一个元素。
需要注意的是E
命令只是强行移动到队首,不需要输出,只有N
命令需要输出。
可能会有连续的E
命令操作多个人到队首,或者连续E
同一个人(甚至就已经是队首的人)。
具体的实现上,当遇到N
命令时,输出队首元素。
int x = queue.peek();
queue.pop();
queue.add(x);
当遇到E
指令时,将给定元素移动到队首。
int index_of_element = queue.find(x);
queue.delete(index_of_element);
queue.addToFront(x);
由于每个人的编号是唯一的,所以可以很容易地找到需要提前的人现在在什么位置,然后将它提前到队首。
如果是用链表实现的,找到这个人以后,直接修改前后元素的指针即可。
x->prev->next = x->next
x->next->prev = x->prev
head->next = x
x->prev = head
如果是用数组实现的,找到这个人以后,将他移动到队首,一种方法是移动数组剩下所有的元素,另一种方法是用$0$来表示这种情况,当遍历到数组元素值为$0$时,跳过即可。
while(que[pos] == 0)
pos++;
for(int j = BEGIN; j < END;j++)
if(que[j] == X)
que[j] = 0;
不少同学在第5组测试数据错误,注意这组数据只有$2$个人,在一系列E
和N
操作后,不少同学把$2$号居民弄丢了,只剩下了$1$号居民。
理解题意以后,发现和 $1010$ 其实是类似的,也是一个可以让某些元素提前的队列。
这里模拟的是一个银行排队的队列,正常情况下,每次队首的元素出队,办理业务以后这个元素就没有了。
但是,后面的 $B$ 可以找到在他前面的、是自己朋友的人 $A$ 帮忙办事情,那么,当 $A$ 办理完自己的业务的时候,会顺便把 $B$ 的事情一起办完。
这时候,可以认为, $B$ 从队列后面某个位置,插队到了 $A$ 的后面, $A+B$ 办理业务的时间是他们两个人各自办理业务的时间的和,办理业务后两个人同时消失。
那么,处理的逻辑就是,每次队首元素出队,表示队首这个人已经办理完毕,接下来从队列后面某个位置找一个人,把他提前到队首。
这个人,默认情况下应该是当前队首出队前,队列中的第二个元素,由于此人已经办理业务(元素出队),所以原来队列中的第二个元素自动成为队首,是下一个办理业务的人。
但是现在考虑“夹塞”,那么这个人就应该是当前队首出队这个人的朋友,他要在队列中找一个到达时间不晚于自己离开时间的自己的朋友,把他提前到自己的后面,如果找不到这样一个朋友,就按顺序找自己后面这个人。
不断循环,直到队列为空。
核心代码以及需要注意的地方如下:
for(i = 0 to n) { // 寻找一个到达时间不晚于自己办理结束时间的朋友
if(visited[i]) continue; // 已经办理过的人
if(arrive[i] > last) break; // 后面的人都是自己办理完业务才会到达的
if(friend) { // 例如HashMap一一对应,或者数组、映射、count等都可以
// 入队,标记为已处理;
// 更新数据
sum += last - arrive[i];
last += process[i];
break;
}
}
// 如果没找到朋友,则取下一个人
sum += max(0, last - arrive[i]); // 等待时间可能为 0(窗口空闲一段时间)
因为本题是实际生活中的情况,所有数据都是完全真实的,所以不可避免的会有各种可能的情况(例如 GPS 传输时候少了两个 ,
,例如不同的设备终端在时间的处理上对秒的精度不同……)。
所以 it is your responsibility to 处理输入,而不是由出题人事先准备好完美是数据就等着你去推导数学公式去做,这与算法竞赛的数据不同。
那么对于本题来说,我特意提醒了 3 次,请再次注意:每个字段的大小(长度)不一,并不能认为字段的大小就如上述例句一样。
对于部分同学提出的意见,要求题干中基于全局的字段3和5的描述应换为『整数部分.小数部分』就不会理解错了
,我给出如下答复。
我确实在出题之初就考虑过这个问题,是不是要给一组样例提醒同学们,但是后来经过查阅资料,发现确实按照无线电通讯标准GPRMC
的要求,是hhmmss.sss
,只是部分终端在实现的时候并没有严格按照这个标准。由此,我并没有修改题面。
但是本题的数据来源是 100% 真实的,所有的数据都是真实的 GPS 传输的数据,所以,你可能会遇到hhmmss.ss
的情况。
同时,有些字段未必会在所有的终端中被统计,或者,就算本地统计了,也未必会发送到 GPS 数据上,因此,你会遇到很多字段为空,即两个,
中间并不是如预期那样有信息,而是会出现,,,,
的可能。
同时,有可能,有些数据传着传着就丢了。
那么,这道题应该怎么做呢?
所以,首先你应该判断这是不是一条$GPRMC
,即判断字符串是不是以$GPRMC
开头。
然后,你要去看看字段的个数是不是满足要求,即,
的个数是不是满足要求。
取出各个字段唯一的方法,是用,
分隔,而不能用加上一个长度来获取。
对于正确取出各个字段之后的结果,你要去看是不是已定位的,即是不是A
,然后计算校验值。
for (int i = 2; i <= st.lastIndexOf('*') - 1; i++)
tmp = tmp ^ st.charAt(i);
检查校验值是不是正确。
if (Integer.parseInt(st.substring(st.lastIndexOf('*') + 1), 16) == (tmp % 65536))
如果以上步骤都成立,取出表示时间的那个字段,然后换算成北京时间。
System.out.printf("%02d:%s:%s\n", (Integer.parseInt(ans.substring(0, 2)) + 8) % 24, ans.substring(2, 4), ans.substring(4, 6));
更多信息可以阅读讨论区
因为本题是实际生活中的情况,与 GPS 那题类似,所有数据都是完全真实的,所以不可避免的会有各种可能的情况(例如 GPS 传输时候少了两个,,例如用户输入网址的时候懒得前后加空格……)。
所以 it is your responsibility to 处理输入,而不是由出题人事先准备好完美是数据就等着你去推导数学公式去做,这与算法竞赛的数据不同。
本题题面描述已经非常清楚了,只要按照题目要求一步步做,提取出难度,然后按照格式输出就可以了。
如果是完全正常的数据,那么,只要取出难度字段和题目编号,然后,按照给定网址的格式,格式化输出对应的题目编号和难度,之后照抄即可。
但是,往往会有人不按照标准格式写文档。
(现在知道为什么文档格式一定要严格按照规范了吧,你会给很多人带来成倍成倍的工作量)
对于更多特殊情况的处理,请阅读讨论区。
我就是不太懂那个等待时间到底是怎么算的
就是帮朋友做事情的这个人的等待时间是他的事务处理时间与他所有能帮到的朋友的时间之和吗?
被帮的朋友的事情一旦完成之后就立即离开队伍了是吗?
这种情况一定是你的本地环境的问题,如果你输出答案正确,那只是凑巧正确,因为本题只要求输出
yes
或者no
。OJ环境一定是没问题的。
看你的代码
例如,
4321
,你会先做if
,然后pin++
,然后到了for
循环的自增,pin++
这里的
pin++
加了 $2$ 次显然是错误的可以输出看看
$6$ 不等于 $4$, 于是输出的是
no
。请再次检查你的本机环境,因为这个
pin
值你是可以用手动推导的,画张图,只有四列火车,还是很容易发现问题的。