列举常用网站开发技术_电子商务网站策划方案_2021年十大热点事件_短网址生成网站

1. 第一题

题目描述

给定两个 IP 地址和一个子网掩码，如果两个 IP 地址分别与子网掩码按位与之后的结果相同，则认为这两个 IP 地址属于同一个网段。

例如，IP 地址 192.168.1.1 与子网掩码 255.255.255.240 按位与操作后结果为 192.168.1.0。

输入描述

输入的格式为：

IP 地址 1, IP 地址 2, 子网掩码

三个字段之间用空格分隔。输入的 IP 地址和子网掩码均为合法值。

输出描述

输出 0 或 1，以及第一个 IP 地址与子网掩码按位与之后的 IP 地址：

0 表示不在同一个网段。
1 表示在同一个网段。

题解

这道题目要求判断两个给定的IP地址是否属于同一网段。网段判断的核心在于IP地址和子网掩码的二进制按位与操作。如果两个IP地址分别与同一个子网掩码按位与操作之后的结果相同，则可以认为它们属于同一个网段，否则属于不同网段。

首先需要理解IP地址和子网掩码的二进制表示。IP地址由四个八位字节（即四个octet）组成，每个八位字节的取值范围是0到255。因此，将IP地址的点分十进制形式转换为二进制形式后，每个IP地址将形成32位的二进制数。同样地，子网掩码也是由四个八位字节构成，用来决定IP地址中哪些位用于标识网络，哪些位用于标识主机。子网掩码通常具有一系列的连续1后跟一系列的连续0，例如 255.255.255.0 表示前24位用于标识网络，剩余8位用于标识主机。

对于本题，我们首先需要将给定的IP地址和子网掩码从点分十进制格式转换为32位的整数表示，以便能够进行按位运算。具体来说，可以将每个八位字节依次左移并加总，形成一个唯一的整数表示。例如，对于IP地址“192.168.1.1”，其32位的整数表示为 $192 \times 2^{24} + 168 \times 2^{16} + 1 \times 2^8 + 1 \times 2^0$ 。

在得到整数表示后，我们可以将两个IP地址与子网掩码分别进行按位与运算，公式如下：

$IP1_Network = IP1 & Mask IP2_Network = IP2 & Mask \text{IP1\_Network} = \text{IP1} \& \text{Mask} \\ \text{IP2\_Network} = \text{IP2} \& \text{Mask}$

其中，按位与操作“&”将仅保留IP地址和子网掩码中均为1的那些位。通过这个操作，所有主机位将被屏蔽，只留下网络位。

如果两个IP地址的网络位相同，即 $IP1_Network = IP2_Network \text{IP1\_Network} = \text{IP2\_Network}$ ，则说明两个IP地址在同一网段内，输出1；否则输出0。无论是否在同一网段内，输出中还需要包含IP1与子网掩码按位与后的结果，即网络地址 $IP1_Network \text{IP1\_Network}$ ，它表示IP1所在的网络地址。

def ip_str_to_int(ip_str):octets = ip_str.split('.')ip_int = 0for octet in octets:ip_int = (ip_int << 8) + int(octet)return ip_intdef int_to_ip_str(ip_int):octets = []for i in range(4):octet = (ip_int >> (24 - 8*i)) & 0xFFoctets.append(str(octet))return '.'.join(octets)def main():input_line = input().strip()ip1_str, ip2_str, mask_str = input_line.split()ip1_int = ip_str_to_int(ip1_str)ip2_int = ip_str_to_int(ip2_str)mask_int = ip_str_to_int(mask_str)ip1_network = ip1_int & mask_intip2_network = ip2_int & mask_intsame_network = 1 if ip1_network == ip2_network else 0ip1_network_str = int_to_ip_str(ip1_network)print(f"{same_network} {ip1_network_str}")if __name__ == "__main__":main()

2. 第二题

题目描述

我们的系统仅能接受指定格式的命令输入，但调皮的小伙伴总是会输入一些系统无法识别的命令，从而引起干扰。请实现一个简单的命令合法性判断程序，帮助判断命令的合法性。

系统仅能接受的命令格式描述如下：

单命令：仅支持小写字母命令，如 a，b 等。
AND 命令：通过 AND 拼接的命令，如 a AND b。
OR 命令：通过 OR 拼接的命令，如 a OR b。
NOT 命令：以 NOT 为前缀的命令，如 NOT a。
组合命令：通过 AND，OR，NOT 组合的命令，如 a AND b OR c OR NOT d。

特别地：

AND，OR，NOT 为系统关键字，必须大写。
系统不接受连续 NOT 拼接的命令，例如 NOT NOT a 为不合法命令。
系统不接受括号拼接命令，例如 (a AND b) OR c。

输入描述

多行待判断合法性的命令，每行命令长度小于 100。无需考虑长度越界情况。

输出描述

多行 0 或 1：

0：表示命令不合法。
1：表示命令合法。

题解

题目定义了四种命令模式：单命令、AND命令、OR命令和NOT命令。在分析命令合法性之前，明确命令结构的要求至关重要。合法命令的构成包括以下几点：

单命令是最基本的命令形式，仅由一个小写字母组成，表示一个操作数，如 a 或 b。对于系统而言，单字母是合法操作数。
AND和OR是二元操作符，用于连接两个操作数或表达式。具体而言，AND命令需要两个操作数，例如 a AND b，而OR命令则是对若干操作数的选择性拼接，如 a OR b OR c。这些命令对顺序有要求，操作数与操作符需严格间隔出现。
NOT是单目操作符，仅适用于单个操作数。例如，NOT a 为合法命令。注意NOT只能对单操作数使用，不允许连续NOT命令拼接，例如 NOT NOT a 为不合法。
系统仅识别大写的AND、OR和NOT关键词，如果有小写或其他变体，则直接判为不合法。
命令拼接不能使用括号，因此 (a AND b) OR c 等结构均被视为不合法。

为了实现合法性判断，需要定义命令解析的状态机模型。解析流程从一个初始状态“等待操作数”开始，并在遍历每个命令中的令牌（token）时不断更新状态，以确保符合要求。在实现过程中，状态机通常会维护当前的解析状态和前一个令牌（token）信息，来帮助判断合法性。

解析命令时，首先会检查每个令牌是否为大写的操作符（即AND、OR、NOT）或小写的单字母操作数。若遇到操作符AND或OR，则系统应处于“等待操作数”的状态，因为AND和OR是二元操作符，要求前后各有一个操作数。若遇到单字母操作数，系统应处于“等待操作符”状态，表明下一个合法令牌只能是操作符。如果不符合上述期望，则该命令结构不符合系统要求，直接判为不合法。

特殊处理的令牌是NOT。若令牌为NOT，系统允许在“等待操作数”状态下使用，但不可连续出现。若遇到连续NOT（即前一个令牌也是NOT），则直接判定命令不合法。最后一个判断点在于命令结束后的状态要求，合法命令应当结束于操作数，即最终状态应是“等待操作符”，否则判为不合法。

import sysdef is_operator(token):return token in {'AND', 'OR', 'NOT'}def is_operand(token):return len(token) == 1 and token.islower()def validate_command(command):tokens = command.strip().split()if not tokens:return 0state = 'Expecting Operand'  # 初始状态，期望操作数prev_token = Nonefor token in tokens:if is_operator(token):if token == 'NOT':# 连续的 NOT 不符合要求if prev_token == 'NOT':return 0prev_token = 'NOT'elif token in {'AND', 'OR'}:# AND 或 OR 之前必须为操作数if state != 'Expecting Operator':return 0prev_token = tokenstate = 'Expecting Operand'else:return 0elif is_operand(token):if state != 'Expecting Operand':return 0prev_token = 'OPERAND'state = 'Expecting Operator'else:return 0if state != 'Expecting Operator':return 0return 1def main():lines = sys.stdin.readlines()for line in lines:command = line.strip()if not command:print(0)continueresult = validate_command(command)print(result)if __name__ == "__main__":main()

3. 第三题

题目描述

一次完整的基因测序流程由多个小任务组成。任务之间具有顺序要求，即某个任务需要依赖其他任务完成后才能执行。例如，c:[a,b] 表示任务 c 依赖任务 a 和 b，即只有在 a 和 b 都执行完成且 b 执行完成后，才能开始执行 c。每个小任务均有其自身的运行时长，没有依赖关系的任务可以并行执行。

例如，b:[a]:3 表示任务 b 依赖任务 a，且 b 的运行时长为 3 分钟。

此外，由于计算资源限制，执行任务时存在并发限制，即最大可同时执行的任务数量是有限的。例如，当最大并发数为 2 时，由于资源限制，等待中的任务必须等待前面的任务完成后才能开始执行。

注意事项：

若有多个任务可以同时运行，优先按照任务出现的顺序执行；若顺序相同则按字母序优先处理。
例如，b:[a]:3/2 表示任务 b 依赖任务 a，任务 b 的运行时长为 3 分钟，最大并发数量为 2。

输入描述

多个依赖关系的描述用分号分隔，最大并发数量用斜杠分隔。输入可能包含空格或其他不可见字符，需自行去除（题例本身无空格）。

输出描述

输出该基因测序流程的总运行时间。

题解

在这个基因测序任务调度问题中，每个任务有一个唯一的执行时长，并且各任务之间可能存在依赖关系。若任务 $c$ 依赖任务 $a$ 和 $b$ ，则只有当 $a$ 和 $b$ 完成后， $c$ 才可开始。此外，题目引入了一个并发限制，即任意时间点最多只能同时执行给定数量的任务。这就要求我们在任务调度中不仅要满足依赖关系，还要保证并发约束，从而优化整体执行时间。

对于输入的解析，需去除空白字符并分割依赖关系描述与并发限制。每个任务由一个唯一标识、依赖任务集合和执行时长描述。例如，b:[a]:3 表示任务 b 依赖于任务 a 且其执行时间为3分钟。对于 h:[e,f,g]:2;e:[b]:6 这样的更复杂输入，任务 h 依赖于 e、f 和 g，而任务 e 依赖于任务 b。这种层级依赖关系构成了一个有向无环图(DAG)，我们必须对其进行拓扑排序以确保按依赖关系依次启动任务。

我们还需构建一个任务调度的执行系统。此调度系统的实现中，使用一个优先队列维护事件队列，用于追踪正在运行任务的完成时间。这种方法可以在保证任务按顺序完成的前提下，尽早释放资源并调度新任务。每个任务的状态分为 未开始、运行中、已完成 三个阶段，以便在计算时实时更新任务状态。

在调度的具体实现中，初始将所有无依赖任务加入可执行任务列表，并按任务定义顺序和字母顺序调度。调度时，根据并发限制最多选择符合条件的任务开始执行。对于每个开始的任务，记录其开始时间和结束时间，并将其加入正在运行任务列表。当某任务完成时，从事件队列中移除该任务，并检查该任务的依赖任务以确定新一轮可执行任务。

import sys
import re
import heapqdef parse_input(input_line):input_line = input_line.replace(' ', '')if '/' in input_line:tasks_part, concurrency_limit = input_line.rsplit('/', 1)concurrency_limit = int(concurrency_limit)else:tasks_part = input_lineconcurrency_limit = 1task_defs = tasks_part.split(';')tasks = {}order = 0for task_def in task_defs:# 匹配任务名称、依赖和执行时间match = re.match(r'([^:\[\]]+):\[(.*?)\]:(\d+)', task_def)if not match:continuetask_name, deps_str, exec_time = match.groups()dependencies = deps_str.split(',') if deps_str else []dependencies = [dep for dep in dependencies if dep]exec_time = int(exec_time)tasks[task_name] = {'name': task_name,'deps': dependencies,'dependents': [],'exec_time': exec_time,'unmet_deps': len(dependencies),'status': 'not_started','order': order,'start_time': None,'end_time': None,}order += 1# 建立任务间的依赖关系for task in tasks.values():for dep in task['deps']:if dep in tasks:tasks[dep]['dependents'].append(task['name'])else:tasks[dep] = {'name': dep,'deps': [],'dependents': [task['name']],'exec_time': 0,'unmet_deps': 0,'status': 'completed','order': order,'start_time': None,'end_time': None,}order += 1return tasks, concurrency_limit# 调度任务，计算总执行时间
def schedule_tasks(tasks, concurrency_limit):current_time = 0event_queue = []ready_tasks = []running_tasks = []tasks_remaining = len(tasks)# 初始可执行任务加入就绪队列for task in tasks.values():if task['unmet_deps'] == 0:ready_tasks.append(task)ready_tasks.sort(key=lambda x: (x['order'], x['name']))while tasks_remaining > 0:# 分配任务到并发池while len(running_tasks) < concurrency_limit and ready_tasks:task = ready_tasks.pop(0)task['status'] = 'running'task['start_time'] = current_timetask['end_time'] = current_time + task['exec_time']# 立即完成的任务处理依赖if task['exec_time'] == 0:task['status'] = 'completed'tasks_remaining -= 1for dep_name in task['dependents']:dep_task = tasks[dep_name]dep_task['unmet_deps'] -= 1new_ready_tasks = [tasks[dep_name] for dep_name in task['dependents']if tasks[dep_name]['unmet_deps'] == 0 and tasks[dep_name]['status'] == 'not_started']ready_tasks.extend(new_ready_tasks)ready_tasks.sort(key=lambda x: (x['order'], x['name']))else:running_tasks.append(task)heapq.heappush(event_queue, (task['end_time'], task['order'], task))# 处理任务完成事件if event_queue:next_event_time, _, next_task = heapq.heappop(event_queue)current_time = next_event_timenext_task['status'] = 'completed'running_tasks.remove(next_task)tasks_remaining -= 1for dep_name in next_task['dependents']:dep_task = tasks[dep_name]dep_task['unmet_deps'] -= 1new_ready_tasks = [tasks[dep_name] for dep_name in next_task['dependents']if tasks[dep_name]['unmet_deps'] == 0 and tasks[dep_name]['status'] == 'not_started']ready_tasks.extend(new_ready_tasks)ready_tasks.sort(key=lambda x: (x['order'], x['name']))elif running_tasks:next_end_time = min(task['end_time'] for task in running_tasks)current_time = next_end_timeelse:breaktotal_time = current_timereturn total_timedef main():input_line = sys.stdin.read().strip()tasks, concurrency_limit = parse_input(input_line)total_time = schedule_tasks(tasks, concurrency_limit)print(total_time)if __name__ == '__main__':main()

列举常用网站开发技术_电子商务网站策划方案_2021年十大热点事件_短网址生成网站

目录

1. 第一题

2. 第二题

3. 第三题