编程之美

参考

• 编程之美

游戏之乐

让 CPU 占用率曲线听你指挥

• 在任务管理器的一个刷新周期内, CPU 忙的时间和刷新周期总时间的比率, 就是 CPU 的占用率
• 解法 1
  • 拼接死循环与休眠
  • 提高切换频率使占用率平滑 ( \(10ms\) , 不要太小, 会导致线程切换频率过快, 调度不稳定)
  • 估算 \(10ms\) 对应的循环次数 (按照想要的占用率来估算)
  • 痛点: 每次都要重新估算
• 解法 2
  • 使用 GetTickCount 让循环进行目标时间
  • 休眠对应比例的时间
  • 痛点: 都假设其它进程不影响 CPU 占用率
• 解法 3
  • 通过 Perfmon.exe 监控 CPU 占用率
  • 小于目标占用率时, 死循环, 否则休眠对应比例的时间
  • 这样再套一个浮点数组, 就可以实现用 CPU 占用率画画了
• 优化
  • 多核情况下, 每个核心都运行一个线程, 每个线程都按照目标占用率来运行 (用 SetThreadAffinityMask 来设置线程运行在哪个核心上)
  • RDTSC 指令 (一个汇编, x64 才有库函数) 用于读取 CPU 运行周期, 再用 CallNtPowerInformation 获取 CPU 频率以计算时间 (更准)

中国象棋将帅问题

枚举所有可能将帅位置, 只可以用一个变量

• 用一个变量高低位 + 位运算表示
• 用结构体表示
• 用商与余表示

一摞烙饼的排序

通过翻转 \(1\) 到 \(m\) 个烙饼, 将 \(n\) 个烙饼排序

• 比尔盖茨唯一一篇学术论文的主题
• 先用一下选择排序的思想, 最多 \(2(n-1)\) 次翻转一定能排好 (每两次排好最下面)
• 思考一下, 本质就是将应该相邻的烙饼放到一起
• 分支限界法处理一下, 当前次数 + 预计最少次数应小于 \(2(n-1)\)
  • 有 \(m\) 对相邻的烙饼它们的半径不相邻, 那么我们至少需要 \(m\) 次才能排好序
• 也可以考虑记忆化搜索

买书问题

五卷书, 每卷买若干本, 其中一次购买不同卷数 \(2 ~ 5\) 本打折, 求最小花费

• 咋一看贪心, 但是 [2,2,2,1,1] 时, 两次购买 \(4\) 本比一次 \(5\) 更便宜
• 贪心正解
  • 由于每卷价格一致, 买 \(3, 5\) 一定贵于 \(4, 4\)
  • 先贪心出所有次购买, 形成 [0,0,1,0,1] 代表不同卷数的购买次数
  • 使用发现的规律进行优化 [0,0,0,2,0]
• 当然, DP 更显而易见
  • 由于每卷价格一致, 状态是一个组合而非排列 [2,2,2,1,1] (随意排序)
  • 五维 DP, 幸好是组合, 只需要遍历升序状态

快速找出故障机器

找出数组中唯一的落单数字

• 异或秒杀
• 现在问题进化, 有两个不相同落单数字
  • 先异或所有数字, 得到的结果是两个落单数字的异或
  • 找到异或结果中为 \(1\) 的位, 说明这两个数字在这一位上不同
  • 按照这一位是否为 \(1\) 将数组分成两部分, 每个部分分别异或, 就可以得到两个落单数字
• 现在问题进化, 有两个相同落单数字
  • 需要预先知道和就秒杀了

饮料供货

帮大家买饮料, 使得大家的满意度总和最大, 饮料总共有 \(L\) 升, 第 \(i\) 种饮料, 单瓶容量为 \(V_i\), 且 \(V_i\) 是 2 的幂次, 满意度为 \(H_i\), 库存最多有 \(C_i\) 瓶, 决定每种饮料买多少瓶 \(B_i\), 在总容量不超过 \(L\) 的前提下, 让总满意度 \(\sum (H_i \times B_i)\) 最大

• 多重背包板子题

// 假设 opt[v][j] 表示: 剩余容量为 v, 面对第 j 种饮料时的最大满意度
// T 是饮料种类的总数
// V_total 是总容量上限

// 从最后一种饮料开始往前推, 或者从第一种开始都可以, 这里假设是填表法
for (int j = T-1; j >= 0; j--) {  // 遍历每种饮料
    for (int v = 0; v <= V_total; v++) { // 遍历每种可能的容量状态

        opt[v][j] = -INF; // 初始化为负无穷

        // 核心循环: 尝试拿 k 瓶第 j 种饮料
        // 限制: k 不能超过库存 C[j], 且 k*Volume[j] 不能撑爆当前容量 v
        for (int k = 0; k <= C[j] && k * Volume[j] <= v; k++) {

            // 剩下的容量给下一种饮料(j+1)去分
            int remain_vol = v - k * Volume[j];
            int current_satisfaction = k * Satisfaction[j];

            // 状态转移
            int total_val = current_satisfaction + opt[remain_vol][j+1];

            // 如果这种拿法更好，就更新记录
            if (total_val > opt[v][j]) {
                opt[v][j] = total_val;
            }
        }
    }
}

• 注意到条件, \(V_i\) 是 2 的幂次
  • 因为所有容量都是 \(2\) 的倍数, 小的饮料一定能完美凑出大的容量
  • 把所有饮料按满意度比容量排序
  • 二进制分解
  • 先看最小单位, 如果我们要买奇数升的饮料, 必须至少买 1 瓶 1L 的 (前提是用满容量一定最优)
  • 从小位向上遍历, 考虑是自己填满 / 用更大的瓶子来覆盖
  • 我们可以比较两瓶小的满意度之和与一瓶大的满意度 (其实刚才排序了)

光影切割问题

一个平面与若干条直线, 求平面中的一个区间被切割成多少个部分

• 显然, 区域数 = 直线数 + 区间内交点数 + \(1\)
• 预处理所有直线的交点
  • 排序 (不去重, 不考虑三线交于一点)
  • 模拟
• 区域内的交点数目就等于一个边界上交点顺序相对另一个边界交点顺序的逆序总数
  • 分治求逆序对

小飞的电梯调度算法

电梯在一楼, 有 \(n\) 个人要去 \(m\) 个不同的楼层, 问电梯只停一次的情况下停在哪一层能够保证所有乘客爬楼梯的层数和最小

• 维护低于当前楼层人数, 当前楼层人数, 高于当前楼层人数, 当前代价
  • 遍历一遍
• 容易发现其实就是中位数
• 如果允许你停 \(k\) 个楼层
  • 序列 DP
  • 设 \(dp[i][j]\) 表示前 \(j\) 层停了 \(i\) 次的最小代价
  • 转移 \(dp[i][j] = \min_{k=0}^{j-1} (dp[i-1][k] + \text{cost}(k+1, j))\)
  • 其中 \(\text{cost}(i, j)\) 表示从 \(i\) 层到 \(j\) 层的代价

高效率地安排见面会

\(n\) 个学生, 对 \(m\) 个见面会中若干个感兴趣, 在保证感兴趣都参加的情况下如何安排使得所有见面会总时间最短

• 显然如果有一位同学同时对两个会感兴趣, 这两个会就不可以同时进行
  • 用图的邻接表示这种关系
  • 显然是一个最少着色问题
  • 太难了不说了
• 这题有一个简化版本, 是每个会给出开始结束时间, 然后问最少需要几个会场, 其实就开始一个会议就加一, 结束会议减去一, 然后找到最大值就完事了

双线程高效下载

略

NIM(1) 一排石头的游戏

一堆按顺序摆放的石头, 每个玩家每次可以取任意一块或者相邻的两块, 将剩下石头一次取光的玩家获胜

• 显然, 先手必胜
  • \(n < 3\) 时, 先手直接取完即可
  • \(n < 5\) 时, 取中间, 剩下两个 \(1\)
  • 其他情况, 先拿正中间, 然后每次都拿对面的石头的对称
• 如果说取光石头的人输
  • \(n > 1\) 时必胜, 先对称拿然后最后多拿一点
• 当然还有我们经典的巴什博弈
  • 只有一堆, 每次最多取 \(k\) 个, 最后取光的人赢
  • 如果总数是 \(k+1\) 的倍数, 那么先手必败, 否则必胜

NIM(2) 分析

有 \(N\) 块石头和两个玩家 A 和 B, 玩家 A 先将石头分成若干堆, 然后接照 BABA⋯⋯ 的顺序不断轮流取石头, 能将剩下的石头一次取光的玩家获胜, 每次取石头时, 每个玩家只能从一堆石头中取任意数量 (大于零) 的石头

• 所有堆的异或和为零时, A 必胜
• 否则 B 必胜
• 偶数堆时, A 可以将石头分成两两异或和为零的堆
• 奇数堆时, A 必败
• 如果取光所有石头的人输
  • 所有堆都为 \(1\) 看奇偶
    • 奇数 A 胜
    • 偶数 B 胜
  • 否则看异或
    • 异或为零 A 胜
    • 否则 B 胜
  • 所以可以分堆的情况 A 必胜

NIM(3) 两堆石头的游戏

有两堆石头, 每次可以从一堆中取任意数量的石头, 或者从两堆中取相同数量的石头, 取光石头的人获胜

• 发现必胜态与必败态可一次转换
  • 类似欧拉筛, 从基本的状态开始上推
• 其实有通项公式
  • \((\lfloor k \times (1 + \sqrt{5}) / 2 \rfloor, \lfloor k \times (3 + \sqrt{5} / 2) \rfloor)\)

NIM(4) 斐波那契博弈

一堆石子, 两个玩家轮流取石子, 先手每次可以取任意数量的石子, 后手每次最多只能取前一手的两倍石子, 取光石子的人获胜

• 如果初始石子数是斐波那契数, 先手必败
  • 否则先手必胜
• 先手必赢策略: 取走齐肯多夫表示法中最小的斐波那契数
  • 任何非斐波那契数都可以唯一表示成若干不连续斐波那契数之和 (即齐肯多夫定理)
• 依赖于 \(F_{k+1} < 2 \cdot F_k < F_{k+2}\)

连连看游戏设计

设计一个连连看游戏 (最多拐弯两次)

• BFS 搜索
  • 从一个点出发
  • 递增拐弯次数, 搜索所有可能到达的位置

构造数独

设计一个数独游戏

• 回溯法找到一个解, 随机挖洞
• 也可以先填充上正中间的一个九宫格, 通过行列交换填充其它格子

24 点游戏

给出四个 \(1 ~ 9\) 的数字, 通过加减乘除和括号得到 \(24\)

• 枚举所有数字排列, 运算符排列, 括号方式
• 也可以转变成集合的形式
  • 集合之间的运算为所有元素对的运算
  • 中间结果天然去重

俄罗斯方块游戏

略

挖雷游戏

略

数字之美

求二进制数中1的个数

汉明重量, 略

不要被阶乘吓倒

计算 \(n!\) 的末尾有多少个零, 求 \(n!\) 的二进制表示中最低位 \(1\) 的位置

• 末尾零的个数等于 \(n\) 中因子 \(5\) 的个数
• 二进制表示中最低位 \(1\) 的位置等于 \(n\) 中因子 \(2\) 的个数 + \(1\)
  • 等于 \(n / 2 + n / 4 + n / 8 + \cdots\)
  • 等于 \(n\) - 二进制表示中 \(1\) 的个数

寻找发帖 "水王"

寻找多于半数发帖的用户

• 摩尔投票法

1 的数目

计算从 \(1\) 到 \(n\) 的所有整数中 \(1\) 出现的次数

• 代码随想录原题

寻找最大的 K 个数

• 减治法
• 二分找分界线
• 优先队列

精确表达浮点数

分数形式表示浮点数

• 我小时候爱玩的一个游戏, 证明无限循环小数与某个分数相等

最大公约数问题

略

找符合条件的整数

给定一个整数 \(n\), 找出整数 \(m\), 使得 \(nm\) 的十进制表示中只包含数字 \(1\) 和 \(0\)

• 从小到大枚举 \(nm\), 记录 nm 取模 n 的结果
• 如果显然有一个比它更小并且余数相同的数可以剪枝 (按位分解, 余数相加)

斐波那契数列

略

寻找数组中的最大值和最小值

• 锦标赛法

寻找最近点对

TODO

快速寻找满足条件的两个数

两数之和, 略

子数组的最大乘积