WC 笔记

Day_Tao · 2025-01-19 09:02:26 · 算法·理论

1.18

电脑忘带了。

1.19

上午：AI 时代的编成新范式

主讲人：郑勤锴

目录

• AI 时代的编程范式转变
• 大模型与代码生成
• CodeGeeX？
• \cdots

程序

• 程序是什么
  前面忘了
  差分机。
  压行。
  后面忘了

• 程序的演变
  汇编语言 -> Fortran -> Python -> 自然语言实现？（大模型）

AI 是什么

• 人工智能的范式转变

  • 第一阶段（1950s\sim 1970s）原型阶段：逻辑推理系统
  • 第二阶段（1980s）专家系统，神经网络
  • 第三阶段（1990s\sim2010s）深度学习
  • 第四阶段（2020s\sim 现在）大模型，AGI

• 神经网络

  拟合数据特征的计算模型，能够处理复杂的非线性问题。
  人类神经元：树突胞体轴突。-> 人工神经元：输入计算输出。
  神经元堆叠之后 -> MLP，多层感知机。让模型预测真实数据。
  神经网络训练：

  • 交叉熵损失：（y 为真实，\hat{y} 为模型预测概率，取值在 [0,1] 之间） L(y,\hat{y})=-[y\log(\hat{y})+(1-y)\log(1-\hat{y})]

• 什么是大模型

  广义：大量数据，大量参数，无监督学习的预训练模型。
  狭义：大型语言模型（LLM），代表：OpenAI 的 GPT 系列模型。
  传统机器学习 vs 预训练大模型：后者规模更大，数据更广。

• 大模型的发展历程
  Transformer 之前自然语言处理中最常用的是 RNN。
  缺点为循环方式，难以并行化，建构能力不够强。
  后来 Transformer 成为深度学习的主流架构。

• 大模型核心技术原理：Transformer 架构

  对于输入进行标识符化（Tokenization）
  GPT 生成式预训练提出 Next Token Prediction，相当于给出模型半句话，让它去预测整句话，再对比预测出来的和原话的区别。

• 大模型核心技术原理：注意力机制

  如何预测下一个 token，每次的输入都跟上一个 token 有关。

• 大模型核心技术原理：主流大模型结构分类

  • 自编码模型：完形填空，挖空一些内容尝试补充 -> 理解类的内容。
  • 自回归类型：当今主流，GPT。
  • ？？？后面忘了

• 大模型核心技术原理：传统机器学习 vs 大模型

中间忘了，在查成绩。

• 为什么需要这么大的模型

  大模型是数据和算力不断增长催生的产物。
  大模型的涌现效应。

• 大模型使代码生成进入了全新的阶段

  基于规则的代码生成->局域深度学习的代码生成

• 代码生成 - CodeX

  当今的需求：代码语义相似性×，代码功能的准确性√。
  概念：pass@k，给出 k 组数据，与有一次通过的概率正相关。生成过程有随机性，一般随 200 次左右。
  生成若干代码，只能提交某一份使得得分最大化，没有最有效的采样方案。代码生成模型的采样高效性是一个难题。
  现象：模型可以生成对的内容，这个东西具有随机性，无法很准确回答出正确答案。

• 代码生成 - AlphaCode

  使用大规模采样筛选方法，生成规模很大，通过上百万次采样，对结果聚类筛选，解决更加困难的竞赛祭编程题。总之就是大力砖飞。
  指标：10@k，k 次里面筛选 10 次去提交。启发式筛选方法 + 聚类挑选正确候选结果。
  弊端是效率过低，解决难题需要上百万次采样，通常用于研究上的探索，无法大规模用于日常生过中。

如何实现自己的代码生成的大模型

• CodeGeeX 系列代码生成大模型
• 大规模代码数据处理
  比方说若干个空格可以对应一个 token。可用于 python 这样强制缩进的语言中
  基于 GLM 通用语言模型架构实现，使用自监督学习预训练。
  到这边感觉讲的就没啥意思了啊？好像都在讲 CodeGeeX。
  超过了 54\% 的人类参赛者，OpenAI o1 在 IOI 达到了前 49\% 水平，OpenAI o3 在 Codeforces 上达到了 2727 rating。被吊打了。
  目标明确。后面忘了。润去吃饭了。

下午：线段树的应用

基础线段树

T1

POJ2828 Buy Tickets。

• 值域线段树，即权值线段树，每个位置记录对应的数出现的次数。
• 考虑正难则反，线段树维护一个 \texttt{01} 序列，从后往前删人即可。

数据结构学傻了。。

预言：2026 绍一五月份入学考题。（不是）

T2

HDU2795 Billboard

一个 h\times w 的矩形，每次询问给定一个 L，表示放一个长度为 L，宽为 1 的矩形，要求尽可能地放在靠上的位置，其次尽可能地放在靠左的位置。对于每次询问输出该矩形被放置在了哪里，或者说不能放置。

• 维护区间 \max，线段树上二分。（吗）
• 自己联想：能否改为优先靠左，其次靠上？

update 2025.5.25：绍一五月份入学考 T4。

T3

[懒得找原题了]()

一个序列，求所有与其循环同构的序列的逆序对数量的最小值，要求 n\log n。

• 典。
• 好像是 2024 绍一五月份入学考 T3。

扫描线

T4

POJ1151 Atlantis

• 扫描线板子

T5

P1856 [IOI1998] [USACO5.5] 矩形周长Picture

• 感觉就直接做吧。

T6

POJ2482 Stars in Your Window

• 简单题，我都会嘴巴。
• 不过怎么感觉有点熟悉，是不是之前某一场模拟赛题（？

线段树

T7

CF817F

感觉就是维护一个 \texttt{01} 序列的 \min 覆盖翻转什么的吧（？

• 是这样的，简单题。不过只需要维护 sum 就好了。

动态开点线段树

。空间复杂度是 n\log V 级别的。

听课的时候甚至从来没写过纯种的动态开点线段树。只写过 FHQ-Treap。

自己手搓的第一棵动态开点线段树

T8

CF915E

• 动态开点区间覆盖做完了。

T9

P5459

线段树合并

建立新的线段树，由两棵线段树的信息合并而来。

考虑动态开点地做。然后就做完了。？

T10

CF600E

T11

P4556

T12

P3224

对于每一个集合，维护若干棵动态开点线段树，用并查集维护，线段树合并。

T13

P3521

线段树优化建图

T14

CF786B

板子。

如果区间连区间的话考虑区间连一个虚点，虚点再连区间这样就可以从 \log^2n 条边变为 \log n 条边了。

T15

后面忘了。

1.21

数据结构问题选讲

——动态图联通性。

怎么来之前只看到了 抖 S 选讲没看到动态图连通性。

主讲人：黄洛天

考虑维护一个生成森林，支持加边删边，查询两点是否联通。

？？

他在讲什么

掉线了怎么办。。

斗地主了。

1.22

上午：稀疏图上更快的单源最短路算法

来晚了。

感觉听了没啥用。

而且也听不懂。

上面内容划掉。

来我们第二课堂：

上午：容斥原理

一来就休息了（）

开打 phigros

T4

leetcode 920

• 先只考虑第二个限制。

• 令 f_{n,l,k} 表示满足使用 n 首歌（不要求全部用上），长度为 l，两首相同的歌至少间隔 k 的播放列表数量。

• 维护这个状态考虑用一个长度为 k 的窗口去滑动，每次扔进去一首。

  f_{n,l,k}=A_{n}^{k+1}\times(n-k)^{l-k-1}=\frac{n!}{(n-k)!}(n-k)^{l-k}

多余的部分容斥减掉。S_i 表示不含第 i 首歌的集合，因此只有 n-1 首歌可用，方案为 f_{n-1,l,k}。

答案为 f_{n,l,k}-\sum\limits_{i=1}^n(-1)^{i-1}(n,i)f_{n-1,l,k}=\sum_{i=0}^{n-1}(-1)^i\frac{n!}{i!(n-k-i)!}???。

T5？

有关插板法的东西，这边的组合数部分。

不是怎么有点掉线。。

T5

CCPC 2021 威海的来着吗。

求长度为 n 的 \texttt{01} 串，满足恰好有 m 个 1，并且最长的全 1 子串长度为 k。

考虑将 0 看为隔板，这样就有 n-m+1 段 1，每段长度 \le k。

考虑用不定方程。

即考虑求 \sum_{i=1}^{n-m+1}x_i=m，保证 0\le x_i\le k。

T6

HAOI2008 硬币购物

竟然还有我做过的题。

首先考虑背包，O(4ns)，过不了。

本质上是求解 \sum_{i=1}^{4}c_ix_i=s，且 x_i\le d_i 的非负整数解的个数。

考虑容斥，全集减交集补集去求并集，参考 OI-wiki。

T7

P6076 [JSOI2015] 染色问题

• 先只考虑颜色。
• 考虑用补集的交集做。
• 考虑两个集合 S_i 和 S_j 补集的交集，表示不用第 i 种和第 j 种颜色，其他颜色（c-2 种颜色随便用）的方案集合，方案就是 (c-2+1)^{nm}。
• 摆了回家看题解。。

或者说考虑二项式反演做。

但是我还是不会。

下午：下一代编程语言是怎么样的

但是标题为什么时候从模拟退火到概率编程。。

传奇随机化非确定性算法。

模拟退火

P8212 [THUPC2022 初赛] 喵喵花園

计算几何。反正忘光了。

• 优化问题。为什么是一坨公式看也看不懂。。

• 爬山法。本质上是贪心的局部搜索。考虑上面那个题，确定了一个点就能确定一个答案。但是可能会绕道一个次优解里并认为这是最优解然后爆了。

• 随机游走。rp法。在一定的假设下，可以证明，随机游走充分长时间后，一定能找到最优解。显然没啥用。

• 模拟退火 = 贪心局部搜索 + 随机游走。

  在爬山的每一轮迭代中，随机从邻居中选择下一个解。

  当这个解比当前解更优时，接受它并开始下一轮迭代；当这个解比当前更差的时候，以一定概率接受它。

  对于这个概率，刚开始可以高一些，运行到要 TLE 的时候可以低一些。

• 这个概率用温度 T 表示。

  总的过程跟上面描述的差不多。

  可以参考[OI-wiki](https://oi-wiki.org/misc/simulated-annealing/#%E8%BF%87%E7%A8%8B)。

P5544 [JSOI2016] 炸弹攻击1

• 确定平面上一个不在建筑内的点，就能确定一个解。

P7962 [NOIP2021] 方差

• 直接退火可以得到 48pts±

• 考虑一次操作等价于在差分序列上交换相邻两项。

• 解空间就能变为数列的所有排列，邻居选择就变为随机交换差分序列中的两个元素。

  这样一次操作就相当于上面做法的多次操作。可以获得 88pts±

• 再考虑推一下性质就过了。

总结一下就是在有限的时间内尽可能地找到更优解。

思考：有关概率公式中为什么是 e。

• 最开始是用计算机模拟物体退火的过程，采用一些统计物理的办法。

• 听不懂物理课。。听不懂喵，听不懂喵谢谢喵。

• 一个解就对应一个退火中的一个状态，评价函数对应状态能量函数，寻找一个最优解就是寻找一个最小能量态。

• 应用：预测当前位置，预测时间发展，验证码破解，图片复原。

概率论

前面忘了中间忘了后面忘了。

还是来看看我们猫猫课件。

所以下一代编程语言就是概率论和随机化吗？