幻影彭的彩虹

记录青春的扇区

折腾 vmware

ubuntu24.04 环境。

config apt source

打开 /etc/apt/source.list.d/ubuntu.sources,在 URIs 一项中,http://archive.ub.... 前面加上 .cn,也就是 https://cn.archive.ub....

第二项那个 security 不用改。

vmware tools

1
2
3
4
5
sudo su
apt-get update
apt-get install open-vm-tools
apt-get install open-vm-tools-desktop
reboot

共享文件夹

开共享后, 客户机共享文件夹目录: /mnt/hgfs/

重安装的网络问题

重新安装 vmware 时,可能会遇到以下问题:

  • 安装程序在 "配置网络驱动" 时卡死
  • 安装后客户机死活连不上网。

这是由于卸载时没有删除注册表导致的,解决方案(参考)如下:

  • 在下载的软件中翻一翻,找到 "注册表"
  • 一键扫描然后修复。
  • vmware 点 "编辑","虚拟网络编辑器",还原默认设置。

输入法

百度输入法很靠谱,它甚至附带了安装说明。

百度输入法

先验概率 VS 后验概率

定义

  • 先验概率是根据主观经验,在没有任何实验的情况下对某件事情发生概率的预测。

  • 后验概率是根据某些已知证据,去估计的事情发生的概率。 \[ P(H|E) = \dfrac{P(E|H)*P(H)}{P(E)} \] 该式子中,每项含义如下:

    • \(P(H|E)\):在证据 \(E\) 成立的前提下,假设 \(H\) 成立的概率。
    • \(P(E|H)\):在假设 \(H\) 成立的前提下,证据 \(E\) 被观测的概率。
    • \(P(E)\):证据 \(E\) 成立的先验概率。
    • \(P(H)\):假设 \(H\) 成立的先验概率。

朱世衡之问

有关朱世衡提出的硬币之问,不妨设 \(E\) 表示抛 \(100\) 次硬币 \(50\) 次正面朝上,\(H\) 表示 \(p=0.9\),也就是正面朝上的概率为 \(90\%\)。那么:

  • 可以计算出 \(P(E|H)\le \epsilon\),也就是如果 \(H\) 成立,那么观测到 \(E\) 的概率会很小

  • 不能说:因为 \(P(E|H)\le \epsilon\),所以 \(P(H|E)\) 很小

  • \(P(E)=\int^1_0{P(p=x)\cdot P(E|p=x) dx}\),显然 \(P(p=x)\) 是个先验概率,是确定不了的,所以 \(P(E)\) 没法计算,同理 \(P(H)\) 也没法计算,故 \(P(H|E)\) 计算不了。

最大似然

一般求解方式

  • 考虑后验概率函数相对简单且为凸函数,对后验概率每个参数求偏导即可解出最大似然。
  • 对后验概率函数使用梯度下降,求解极大似然

EM 算法

算法用途

EM 算法主要用于近似求解一些最大似然问题。

算法流程

  1. 初始化模型参数 \(\theta\)
  2. \(\theta\) 进行迭代,优化 \(Q(\theta | \theta^{(t)}) = \mathbb{E}_{Z|Y,\theta^{(t)}} \left[ \log P(Y,Z|\theta) \right]\)
    • 根据 \(\theta^{(t)}\) 计算 \(Z\) 不同取值的后验概率密度函数 \(F = P(Z=x|\theta^{(t)})\)
    • 根据 \(F, \theta^{(t)}\) 求解上式的最大似然。

算法举例

有三个硬币 \(A,B,C\),正面朝上的概率为 \(\theta_A,\theta_B, \pi\),每次实验先抛硬币 \(C\),如果 \(C\) 正面朝上,则使用 \(A\),否则使用 \(B\),一次实验抛完 \(C\) 后抛 \(A\)\(B\) 五次,记录为:

1
2
3
4
5
6
7
8
9
实验一:2 正 3 反

实验二:4 正 1 反

实验三:1 正 4 反

实验四:3 正 2 反

实验五:4 正 1 反

根据实验结果给出一个最大似然参数估计 \(\theta = (\theta_A, \theta_B, \pi)\)

E 步骤

计算每个实验由 \(A\)\(B\) 生成的后验概率:
\[ \gamma_j(A) = \frac{\pi \cdot \theta_A^{n_j}(1-\theta_A)^{m_j}}{\pi \cdot \theta_A^{n_j}(1-\theta_A)^{m_j} + (1-\pi) \cdot \theta_B^{n_j}(1-\theta_B)^{m_j}} \]

M 步骤

迭代更新: \[ \pi' = \frac{\sum_{j=1}^5 \gamma_j(A)}{5} \]

\[ \theta_A' = \frac{\sum_{j=1}^5 \gamma_j(A) \cdot n_j}{\sum_{j=1}^5 \gamma_j(A) \cdot 5}, \quad \theta_B' = \frac{\sum_{j=1}^5 \gamma_j(B) \cdot n_j}{\sum_{j=1}^5 \gamma_j(B) \cdot 5} \]

迭代

设置一个收敛阈值,似然估计变化小于阈值时令其停止。

EM 原理证明

首先对似然函数取对数,记: \[ L(\theta) = \log(P(Y|\theta))=\log{\sum\limits_{z}P(YZ|\theta)}=\log(\sum\limits_{z}P(Y|Z,\theta)P(Z|\theta)) \] 考虑: \[ \begin{align} L(\theta) - L(\theta^{(i)})&= \log\big({\sum\limits_{z}P(Y|Z,\theta)P(Z|\theta)}\big) \\ &=\log\big({\sum\limits_{z}P(Z|Y, \theta^{(i)})\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y, \theta^{(i)})}}\big) - \log(P(Y|\theta^{(i)})) \end{align} \]\(\text{Jensen}\) 不等式,得 \[ \begin{align} \text{上式} &\ge \sum\limits_{z}P(Z|Y,\theta^{(i)})\log{\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y, \theta^{(i)})}} - \log(P|\theta^{(i)})\\ &= \sum\limits_{z}P(Z|Y,\theta^{(i)})\log{\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y, \theta^{(i)})P(|\theta^{(i)})}}) \end{align} \] 令: \[ \begin{align} B(\theta, \theta^{(i)})&= L(\theta) + P(Z|Y,\theta^{(i)})\log{\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y, \theta^{(i)})P(Y|\theta^{(i)})}}\\ &=L(\theta)+P(Z|Y,\theta^{(i)})\log{\frac{P(YZ|\theta)}{P(YZ|\theta^{(i)})}} \end{align} \] 第二行来自贝叶斯公式。

则有 \(L(\theta)\ge B(\theta, \theta^{(i)})\),且 \(B(\theta,\theta)=L(\theta)\)

所以令: \[ \theta^{(i+1)} = \mathbf{argmax}_\theta B(\theta, \theta^{(i)}) \] 则有: \[ L(\theta^{(i+1)}) \ge B(\theta^{(i+1)}, \theta^{(i)}) \ge B(\theta^{(i)},\theta^{(i)})=L(\theta^{(i)}) \] 即: \[ L(\theta^{(i+1)})\ge L(\theta^{(i)}) \]

算法分析

对比

上面的三硬币问题理论上也可以直接求解最大似然,但是列出来后是一个 PDE,一般 PDE 目前是没有闭式解,所以也只能退而求其次找近似解。

梯度下降也行,但是相比于 EM,梯度下降的梯度计算比较复杂,而且无法保证满足概率约束,可解释性弱,收敛不可靠等等等。

M 步骤最大似然的求解

三个变量是独立的,分别求偏导就能代出值来。

本文是神经网络学习笔记,主要记录了几种常用神经网络的结构和变体,以及一些训练技巧及其原理。

阅读全文 »

本文以现代计算机网络硬件为基础,介绍了现代硬件环境下应该了解的网络知识,能够为网络编程打下一个较好的基础。

阅读全文 »

打算要写的东西

打算要做的事

一些日常可能会用得上的技术(二)

写在前面

虽然很多人能够熟练掌握一门编程语言,也能用这门编程语言方便的批处理数据,但是每次总要借助这门语言的 编译器/解释器,然后调用一些系统函数之类的,总感觉缺了点意思。

Linux/Windows 其实在 shell 中已经提供了一门完备的编程语言来直接处理文件或者数据,这相比与写一份代码来运行它要有趣很多。

你不必记下本文的所有细节,只需要知道有这些所介绍的功能即可,记忆会在你的使用过程中一步步完成,AI 能提供的信息会比本文更详尽。

一些常用命令

grep

1
grep [选项] 模式 [文件...]
  • 选项
    • -i:忽略大小写。
    • -r:递归搜索子目录。
  • 模式
    • 默认是标准正则。
    • -F 参数禁止正则(所有正则符号被视为文本)。
    • -E 支持扩展正则表达式。
  • 文件
    • - 表示标准输入。(第一期讲过 "一切皆文件")
    • 支持多个文件,每个文件用空格隔开。
    • 文件名可以采用通配符语法(见附录,大部分文件名参数都可以支持通配符)。
      • 通配符语法匹配的并不是相对路径,而是对于每一层目录和文件名独立匹配,也就是说 f1/*.txt 不能匹配 f1/ 子目录下的 .txt 文件。
  • Windows 平替
    • 可以去下载一个 ripgrep 加入系统路径后当平替,用法基本一致,命令改为 rg

echo

  • 用于输出字符串。

    1
    echo [一个字符串]
  • 常用参数

    • -e:指定转义 \ 相关的换行(\n),制表符(\t)等。
    • -E:指定不转义。
  • 备注:

    • 不同操作系统的 echo 标准不一样,所以有 -e-E 这种看上去反人类的参数。
    • Windows 系统的 PowerShell 也有 echo,但是它的转义符是 "`",系统默认发生转义操作。

cat

  • 题外话

    • 见下图。

    • 为什么学计算机的很多人都喜欢猫~~?

  • 查看文件内容

    1
    cat [文件...]
    • 会输出结果到终端。
  • 其它用法

    • 写入文件:

      1
      cat [文件...] >> file.txt
      • >:覆盖写入。
      • >>:追加写入。
    • 文件部分可以接受命令行输入,> 或者 >> 前不填写任何参数就使用命令行输入。

    • 使用 EOF

      1
      cat > file.txt << EOF
      • 接下来的输入中,输入 EOF 并回车结束输入,EOF 不会被写入。

      • 如果不使用 << EOF 也不使用管道

wc

  • 统计文件字数

    1
    wc [文件...]
  • 常用参数

    • -l:统计行数。
  • 其它

    • 可以接受命令行输入。

      1
      command | wc -m

head/tail

1
head [文件名...]
  • 用于显示文件的最开始/最后 10 行。
  • 常用参数:
    • -n:紧接着可以指定行数。
  • 其它:
    • 支持命令行输入

rm

1
rm [文件名...]
  • 用于删除文件。

  • 常用参数:

    • -r:用于删除目录。
    • -f:忽略警告直接强制删除。
  • 某个很厉害的命令:

    1
    rm -rf /

    功能是删除本操作系统下所有文件,请不要执行或者被人忽悠执行该命令!

    数据无价,谨慎操作。

zip

1
zip [选项] [压缩文件名] [被压缩文件/被压缩目录...]
  • 用于创建压缩文件。
  • 常用选项:
    • -r--recursive:递归地包含目录,即包括指定目录及其所有子目录。
    • -u--update:更新现有的 zip 文件,添加新文件或更新已存在的文件。如果不用改参数覆盖时会提示。
    • -x--exclude:后面输入一些 [被压缩文件/被压缩目录...],排除指定的文件或目录。
    • -v--verbose:详细模式,显示正在处理的文件名。
    • -q--quiet:安静模式,不显示任何输出。
    • -0-9:设置压缩级别,从无压缩(0)到最大压缩(9)

uzip

1
unzip [压缩文件名] [参数]
  • 用于解压文件,默认解压到当前目录。

  • 常用参数:

    • -d:后面接一个目录,解压到这个目录,不存在会创建。
    • -l:只查看里面的文件,不解压。
  • 其它用法

    • 只解压部分文件

      1
      unzip [压缩文件名] [要解压的文件在压缩文件中的路径...] [参数]

管道

  • 管道的一般用法是 command1 | command2 ,功能是将 command1 的标准输出作为 command2 的标准输入运行。

  • 举例:

    • 使用 sort 对文件内容排序,并用 uniq 去除重复行:

      1
      sort somefile.txt | uniq
    • 使用 ls 列出目录内容,grep 过滤特定模式的文件,然后 sort 排序结果:

      1
      ls -l | grep "^-" | sort

变量

声明

1
key=value
  • = 的左右不能用空格。
  • value 加上双引号被声明为字符串,不加声明为整形变量或者浮点变量。
  • PowerShell 的声明使用 $key=value

变量引用

1
2
${变量名}
$变量名
  • 第一种方式是为了防止歧义。
  • \ 可以转义 $

运算

  • $((expr)) 语法:

    1
    $((算术表达式))
    • 举例:

      1
      2
      3
      4
      a=5
      b=3
      c=$((a + b))
      echo $c # 输出 8
  • 自增自减:

    1
    $((a++))
  • PowerShell 特性:

    1
    $a++
    • 可以直接这样使用,但是在 echo 等命令中这样做不行。
  • Shell 特性:

    1
    let "new_var = var1 + var2"
    • new_var 可以是一个新变量名。

总结

  • 大部分时候,常用命令的正则表达式、通配符等功能就可以完成大部分需要循环和分支的操作,用得上循环和分支的地方实际上不会很多。就算真的需要用到循环这些操作,这个时候使用 Python 等脚本语言可能会更方便了。
  • 好好学习正则表达式。

附录

关于一些语法

  • 可变参数列表:[文件...] 是一个可变参数列表,习惯上命令行参数用空格隔开,所以它实际上表示 [文件1][文件1] [文件2][文件1] [文件2] [文件3] 等等。

关于标准正则(BRE)

  • .:匹配任意单个字符(除换行符外)。
  • ^:匹配每一行的开头(不占位,第一个字符仍需要被模式匹配)。
    • 也用于脱字,放在 [] 内部的最开始表示匹配除了 [] 中表达字符之外的所有字符
  • $:匹配行的结尾。
  • []:匹配括号内的任意字符。
  • |:逻辑或操作符。
  • *:匹配前面的元素0次或多次。
  • +:匹配前面的元素1次或多次。
  • -:行为视上下文而定。
    • [] 内它是一个特殊字符,它表示一个范围,例如[a-z] 可以匹配任何小写字母。
    • [] 外是一个普通字符。
  • ?:匹配前面的元素0次或1次。
  • {n}:精确匹配n次。
  • {n,}:至少匹配n次。
  • {n,m}:至少匹配n次,但不超过m次。
  • \(反斜杠):转义特殊字符或表示特殊序列的开始。
  • ()(圆括号):将多个表达式组合成一个子表达式,用于分组和捕获。

关于拓展正则(ERE)

  • \b:匹配一个单词字符和非单词字符之间的边界。
  • \d:等价于[0-9]
  • \D:等价于[^0-9]
  • \s:等价于[ \t\n\r\f\v]。(空白字符)
  • \S:等价于[^ \t\n\r\f\v]。(非空白字符)
  • \w:等价于[a-zA-Z0-9_]。(单词字符)
  • \W:等价于[^a-zA-Z0-9_]。(非单词字符)
  • \n:匹配换行符。
  • \t:匹配制表符。
  • ?:非贪婪匹配(lazy quantifier)。

关于通配符

通配符拥有部分正则的特性,支持不如正则完整,语法有微小差异,具体细节如下:

  1. *:匹配任意数量的字符(包括零个字符)。
    • 例如:*.txt 匹配所有以 .txt 结尾的文件。
  2. ?:匹配任意单个字符。
    • 例如:file?.txt 匹配 file1.txtfilea.txt 等。
  3. [...]:匹配括号内的任意单个字符。
    • 例如:file[123].txt 匹配 file1.txtfile2.txtfile3.txt
    • 也可以使用范围:file[a-z].txt 匹配 filea.txtfilez.txt
  4. [!...][^...]:匹配不在括号内的任意单个字符。
    • 例如:file[!123].txtfile[^123].txt 匹配除了 file1.txtfile2.txtfile3.txt 之外的所有以 .txt 结尾的文件。
  5. {...}:匹配花括号内的任意选项(选项之间用逗号分隔)。
    • 例如:file.{txt,pdf} 匹配 file.txtfile.pdf
  6. \:用于转义自己和以上特殊符号。

一些日常用的上的计算机技术(一)

写在前面

在 AI 背景下,很多日常处理数据的工作完全可以交给 AI 来完成,学习它们的必要性似乎已经不那么强?

在大模型时代,更重要的是了解一些技术的存在,而非具体掌握这些技术,本文旨在提出某些可能对日常工作有帮助的技术,大致给出一个框架。

最后,我想说,一个全栈工程师,需要掌握的不是整个计算机系统中所有方向的技术,而是整个计算机系统的脉络。当一个需求被提出时,他能够沿着大脑中的脉络找到所需的枝叶技术,并运用自己熟练的信息检索能力来找到它们的技术细节,并最终将这些技术组合成解决方案。

可持久化

  • 其实用 "可持久化" 来形容它并不准确,这也包括把 hardcode 部分分离以便让用户不必修改源代码运行程序的相关技术。

    • 举例来说比如爬虫要爬一个网站,你有可能直接把一些参数写进代码里,例如:

      1
      2
      3
      4
      5
      URL = "www.google.com"
      PROXY = {
      http_proxy: "localhost:7890",
      https_proxy: "localhost:7890"
      }
    • 但是你某一台电脑的代理端口是 localhost:7891,所以一个方案是直接修改源代码,但是这太麻烦了,因为代码可能会比较长然后你需要翻。

    • 所以一个方案是单独把一些可能会变的配置给提出来单独写一个配置文件,然后每次运行代码的时候你输入配置文件的路径,或者仅 hardcode 配置文件路径。这样都比一个个改参数更好。

    • 配置文件可以用 .yaml 或者 .json 文件,我习惯用前者,但其实后者的适用性更广,大部分编程语言内置了处理 .json 文件的相关函数。

  • yaml 使用:

    • 准备:

      1
      pip install PyYaml
    • 读取:你大可直接复制下面的代码。

      1
      2
      3
      4
      5
      6
      def yaml2dict(file_path, encoding='utf-8'):
      if check_suffix(file_path, 'yaml'):
      with open(file_path, 'r', encoding=encoding) as f:
      return yaml.safe_load(f)
      else:
      raise ValueError("file suffix name not support")
    • 写入:用 yaml.safe_dump(obj, stream)

      • obj:一个 Python 对象,一般只支持基本数据类型。
      • stream:一个可写流对象,可以用 with 操作打开。

批量发送电子邮件

  • emailsmtplib 来发送,这俩是标准库,不用安装。

  • 大概可以看看下面的代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    import smtplib
    from email.mime.text import MIMEText
    from email.mime.multipart import MIMEMultipart
    def send_mail(receiver, html, subject):
    message = MIMEMultipart("alternative") # 交替 attach 模式
    message["Subject"] = subject # 邮件标题
    message["From"] = SENDER # 发送者邮箱
    message["To"] = receiver # 接收者邮箱

    part = MIMEText(html, "html", "utf-8") # 三个参数是: html 字符串, 格式名, 编码方式
    message.attach(part) # 将对应的 part 正式加入 message

    # SMTP服务器和端口,这是 google 邮箱的网址和端口,服务器和端口取决于发送者的邮箱。
    smtp_server = "smtp.gmail.com"
    port = 587

    try:
    server = smtplib.SMTP(smtp_server, port) # 建立 SMTP 连接
    server.starttls() # 启用TLS安全传输模式
    server.login(SENDER, PWD) # 两个参数分别为邮箱账号和密码
    server.sendmail(SENDER, receiver, message.as_string()) # 发送
    print("邮件发送成功")
    except Exception as e:
    print("邮件发送失败", e)
    finally:
    server.quit() # 断开服务器连接

Excel/Word 处理

Excel 处理

  • 我使用的是 pandas 库。

    1
    2
    pip install pandas
    pip install openyxl
  • 这样读取:

    1
    2
    3
    4
    import pandas as pd
    xls = pd.ExcelFile(r"C:\Users\huany\Desktop\帆软杯\第六届帆软杯报名信息(" + group + f") - 含准入码.xlsx")
    sheet_name = xls.sheet_names[0]
    df = pd.read_excel(xls, sheet_name=sheet_name)
  • df 是转出来的 DataFrame 对象,有以下几个注意点:

    • 一个表格的第一行自动作为表头,每一列的内容作为索引指标。
    • df['col_name'] 来获取一列,它是一个 iterable 对象。
    • df.iterows() 来迭代每一行,得到的行是一个类 dict 对象,用表头的数据作为指标。

Word 处理

  • word (.docx 文件)是基于 xml 的文档。
  • .docx 文件本质是一个 zip 文件,改一下后缀名就可以解压。
  • 主要文字是放在 /word/document.xml,似乎每个文本可以检索到两次,把这两个都改了,然后压缩回去就可以实现改动 .docx 文件。
  • 可以看看我新开的开源项目

selenium 爬虫

cloudflare 等工具的广泛使用使得传统的 requests 爬虫适用性逐步降低,如果没有太高的性能要求,不妨使用 selenium 这样的更上层的库来实现爬虫功能。

关于消除自动化特征

  • 使用 undetected_chromedriver 库可以消除大部分的自动化特征。

    1
    pip install undetected-chromedriver
  • 使用方式和传统 selenium 几乎相同,有两点注意。

    1
    2
    options = uc.ChromeOptions()
    driver = uc.Chrome(use_subprocess=True, options=options)
    • uc.ChromeOptions() 是该库准备的消除自动化特征的 options 参数
    • use_subprocess 的功能是让 WebDriver 在独立的进程中运行,不受主进程崩溃的影响。(其实可以不管)

关于配置自动下载

  • perfs 可以配置自动下载相关的功能

    1
    options.add_experimental_option("prefs", CONFIG.PREFS)
    • 参数值是一个 dict,常用的参数有:

      1
      download.prompt_for_download: false # 不要弹出提示框选择下载路径
    • 似乎配置默认下载路径的办法无法生效。

lazy load

  • 有时候不太想等待所有资源加载完毕,可以使用 page_load_strategy 来控制

    1
    options.page_load_strategy = 'eager'
    • "eager" 不会加载图片等资源,初步解析完成后便会返回。
    • page_load_strategyChromeOptions 类定义的一个属性。

处理网页

  • 用 BeautifulSoup 库可以来层次化读取和处理整个 html 页面。

    1
    2
    3
    import BeautifulSoup
    soup = BeautifulSoup(driver.page_source, "html.parser")
    all_artist = soup.find("div", class_='home-rows-videos-wrapper')
    • BeautifulSoup.find() 可以通过标签名和 class 属性来查找,返回值同样是一个结构化的 HTML 对象,仍然有 find 等方法。

一些关于 HTTP 请求的小知识

  • 看 http 请求的时候,有时候 payload 是没有数据的,数据可以通过 headers 传递。

    请求一个超大二进制文件时可能的 headers:

    1
    2
    3
    headers = {
    'Range': f'bytes={0}-'
    }

压缩文件的处理

Python 一般选用 zipfile 来出来压缩文件。

zipfile 的打开方式和文件流对象差不多,都需要用 with 指定打开模式,文件名,编码等信息。

解压

1
2
3
with zipfile.ZipFile('example.zip', 'r') as zip_ref:
zip_ref.extractall('extracted/')
zip_ref.extract("folder/subfolder/file.txt", 'extracted')
  • 若不存在,extracted 目录会被自动创建。
  • folder/subfolder/file.txt 是以 .zip 文件中,被压缩文件的目录,解压后,extracted 目录会视为其根目录,然后解压过程保持目录结构不变,中间不存在的目录自动创建,也就是说解压出来 folder/subfolder/file.txt 会位于 extracted/folder/subfolder/file.txt
  • extractall 即对每一个压缩文件中的文件做 extract 操作。

压缩

1
2
3
with zipfile.ZipFile('new_example.zip', 'w') as zip_ref:
zip_ref.write('file1.txt')
zip_ref.write('file2.txt', "folder1/folder2/file3.txt")
  • 注意到 ZipFile.write() 有两个参数,这个函数用于把一个文件添加到压缩文件对象中,第一个参数是被添加的文件的路径,第二个参数是压缩文件中,被压缩文件的路径。

  • 第二个参数如果留空则默认为第一个参数。

  • 例如,这个 new_example.zip 压缩文件的目录结构如下:

    1
    2
    3
    4
    5
    new_example.zip:
    ├── file1.txt
    └── folder1/
    └── folder2/
    └── file3.txt
  • 它不支持直接压缩一个文件夹,所以如果要压缩文件夹需要用 os.path.walk() 方法来遍历文件并添加。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    with zipfile.ZipFile(zip_file_path, 'w') as zipf:
    for root, dirs, files in os.walk(folder_path):
    for file in files:
    # 创建文件的绝对路径
    file_path = os.path.join(root, file)

    # 创建文件在ZIP中的相对路径
    # 这里使用 os.path.relpath() 来获取相对于 folder_path 的相对路径
    # 这样ZIP文件中的目录结构会与原始文件夹结构相同
    arcname = os.path.relpath(file_path, start=folder_path)
    zipf.write(file_path, arcname)
    • root 是正在遍历的目录路径,dirs 是该目录下所有子目录的名字列表(相对 root 的路径),filenames 是该目录下所有文件的文件名(相对 root 的路径)。

0301测试

考试

T1

考虑如何检查一个条件是否合法,如果最高位为任意,那么两边需要都合法,否则要求两边至少有一个合法。

考虑两边的检查,发现第 \(i\) 层的节点个数为 \(2^i\),总的情况数为 \(2^{n-i}\),因此可以记忆化搜索一下。用一个 \(mask\) 的前若干位表示限制,后若干位表示高位的数字即可。

也可以这样想:考虑算所有的情况,设 \(T(n)\) 表示计算第 \(n\) 层所有情况的复杂度,暴力计算有 \(T(n)=2^n+4T(n-1)=2^{2n}\),实际上发现对于只有第 \(n\) 层不同的情况可以只算一次,于是 \(T(n)=2^n+2T(n-1)\),得到 \(T(n)=n2^n\)

T2

做法一

考虑钦定 \(A\) 组先选满,枚举 \(A\) 组选满的位置计算对应概率然后再乘二。对于每一个位置 \(p\)基本情况总数\(\binom{p-1}{n-1}\),每种基本情况等概率取到,概率为 \(2^{-p}\),分三类讨论

  • 如果 \(x_k<p\),那么 \(k\) 个人既可以在 \(A\) 组也可以在 \(B\) 组,对应的基本情况数分别为 \(\binom{p-1-k}{n-1-k}+\binom{p-1-k}{n-1}\)

  • 如果 \(x_k=p\),那么一共有 \(\binom{p-k}{n-k}\) 种基本情况。

  • 如果 \(x_k>p\),首先 \(p\notin X\),然后记 \(c\)\(p\) 之前的 \(x\) 个数,基本情况总数为 \(\binom{p-1-c}{n-1}\)

于是有一个 \(nq\) 的做法。

观察到查询的答案是一个二元函数 \(f(p,x)\) ,对于 \(x\) 较小的情况可以预处理前缀和,对于 \(x\) 较大的情况,查询数比较少,可以暴力。于是有一个 \(n\sqrt q\) 的做法。

进一步观察,\(2^{-p}\binom{p-1-c}{n-1}\) 可以很容易的预处理 \(2^{-p}\binom{p-1}{n-1}\) 的前缀和然后查询时乘上一个 \(2^{-c}\)

对于 \(2^{-p}\binom{p-1-k}{n-1-k}\),答案应该是: \[ \begin{align} \sum_{p=x_k+1}^{2n-1}2^{-p}\binom{p-1-k}{n-1-k}&=\sum_{p=\max(n,x_k+1)}^{2n-1}2^{-p}\binom{p-1-k}{n-1-k}\\ &=\sum_{p=\max(n,x_k+1)}^{2n-1}2^{-p}\binom{p-1-k}{n-p}\\ &=\sum_{p=\max(n,x_k+1)-k-1}^{2n-1-k-1}2^{-p-k-1}\binom{p}{n-k-1}\\ \end{align} \] 注意到 \(\sum k\) 其实很小。

好吧,我不会线性做法,摆了。

做法二

先只算都在 \(A\) 组的情况,然后分 \(B\) 选满的位置 \(p\) 所在的区间讨论。

  • \(p>x_k\):令 \(x_k\) 及之前每一种可能的硬币选择为基本情况,需要计算在 \(x_k\)\(X\) 都取到 \(A\)\(B\) 不能被选满的方案总数,隐含条件是 \(x_k\) 之前 \(A\) 也不能被选满。

    可以暴力的算组合数,枚举剩下的 \(x_k-k\) 个数有多少个分配到 \(A\) 中,可以直接限制 \(A,B\) 都满足要求,即 \(\sum\limits_{i=\max(0,x_k-k-n+1)}^{n-k}\binom{x_k-k}{i}\)

    然后 \(\sum k\) 是比较小的,于是放宽一下限制,算 \(\sum\limits_{i=\max(0,x_k-k-n+1)}^{n}\binom{x_k-k}{i}\) 再减掉,容易发现这个式子只和 \(x_k-k\) 有关,而这个式子本身也不是很难算,进一步的将 \(\max\) 的限制去掉,变成 \(\sum\limits_{i=0}^n \binom{x}{i}\),然后对于 \(x-n\ge0\) 的情况,需要减去 \(\sum\limits_{i=0}^{x-n}\binom{x}{i}\)。都可以拆组合数然后动态规划。 \[ \begin{align} \sum\limits_{i=0}^{x-n}\binom{x}{i}&=\binom{x-1}{0}+\sum\limits_{i=1}^{x-n}\binom{x-1}{i-1}+\binom{x-1}{i}\\ &=\binom{x-1}{0}+\sum_{i=1}^{x-n}\binom{x-1}{i}+\sum_{i=1}^{x-n}\binom{x-1}{i-1}\\ &=\binom{x-1}{x-n}+\sum_{i=0}^{x-n-1}\binom{x-1}{i}+\sum_{i=0}^{x-n-1}\binom{x-1}{i}\\ &=\binom{x-1}{x-n}+2\sum_{i=0}^{x-1-n}\binom{x-1}{i} \end{align} \]

    另一种考虑方式是算一个 \(f_w\) 表示一共 \(w\) 个,\(A,B\) 都不超过的情况总数,然后需要减去 \(B\) 抵到的情况数,然后又因为需要把 \(A\) 超过的情况去掉,\(A\) 超过是因为 \(k\) 个被塞进了 \(A\),分别枚举超过 \(1,2,3\cdots k\) 个减掉对应的基本情况数即可。\(f_w\) 的转移考虑直接放 \(A,B\) 然后去掉不合法的情况。

  • \(x_{i-1}<p<x_{i},i\in[1,k]\)

    将基本情况定为 \(x_i\) 之前(不含)的硬币状态,限制有两个,\(|B|\) 不小于 \(n\),且 \(X\) 内的是必须为 \(A\) 的。满足 \(A\) 限制的总情况数为 \(2^{x_i-i}\)。满足 \(A\) 限制但不满足 \(B\) 限制的情况数为 \(\sum\limits_{i=0}^{n-1}\binom{x_i-i}{i}\),先扣掉。这里不需要考虑 \(A\) 被选满,因为 \(A\) 被选满的情况确实应该扣掉。然后再减去再 \(x_{i-1}\) 之前就满足 \(B\) 限制的所有情况,注意额外带一个 \(2_{x_i-x_{i-1}-1}\) 的系数。

    这里还会有一些误解,其实隐含了 \(|A|<n\) 的限制,实际上如果这两个限制都满足那么这个隐含限制一定满足,因此不管这个隐含限制直接算也是可以的。

当使用容斥计算 "恰好" 时,应该减掉上一次的 "至少" 而不是 "恰好",记录 \(lst\) 的时候要注意。

T3

先考虑构造一种合法的解满足条件。挨个确定值的办法并不好弄。考虑先确定前 \(i\) 个的大小关系,如果前 \(i\) 个合法了,并且第 \(i+1\) 个可以放到一个位置,满足前面没有不小于 \(a_{i+1}\) 且存在至少一个 \(a_{i+1}-1\),那么就合法。于是得到一个有解的充要条件:任何一个前缀 \(a_i\) 值的集合连续。

现在考虑算 \(i\) 位置的答案,它前面的不小于它的元素必须在它后面,它后面的元素可以线性扫一遍,维护前缀连续最大值算出来。

考虑优化,对于一个 \(i\) 算答案的时候,就是要找到依赖它以及它前面不小于它的元素的所有元素。后面的比 \(a_i\) 大的元素如果能在 \(i\) 之后找到一个 \(a_i\) 依赖,那么就可以被放在 \(i\) 前面。

元素的依赖关系好像是构成一棵树的,于是建树,每个元素向它的第一个前驱连边,然后 \(i\) 节点以及它同层左边的兄弟里所有节点都不能放在 \(i\) 前面,于是算出了 \(p_i\) 的最大值。

0%