月度归档:2018年04月

线性代数相关OJ题选讲

这篇文章是关于线性代数的OJ题选讲,这几道题目都不难,主要是考察思维的灵活程度。


Fast Matrix Calculation

2014 Multi-University Training Contest 9, available at HDUOJ 4965

给定 \(N\times k\) 的矩阵 \(A\),\(k \times N\) 的矩阵 \(B\) \((2 \leq k \leq 6, 4 \leq N \leq 1000)\):
Step 1. 计算 \(N \times N\) 的矩阵 \(C = AB\).
Step 2. 计算 \(M = C^{N \times N} \bmod 6\).
Step 3. 输出 \(M\) 中所有元素的和.

题解

根据矩阵乘法的结合律,

\[M = (AB)^{N \times N} = A (BA)^{N \times N – 1} B\]

时间复杂度由裸的快速幂\(O(N^3 \log N)\)变成了\(O(N^2k + Nk^2 + k^3 \log N)\)。


Matrix Multiplication

2014 Multi-University Training Contest 5, available at HDUOJ 4920

给定\(n \times n\)的矩阵\(A, B\),求模3意义下的乘积。 \((1 \leq n \leq 800)\)

题解

令 \(M_x\): \(M_x(i, j) = [M(i, j) = x]\).

\[ AB = (A_1 – A_2)(B_1 – B_2) = A_1B_1 – A_1B_2 – A_2B_1 + A_2B_2 \]

其中 \(A_1, A_2, B_1, B_2\) 是 01矩阵. 使用 std::bitset,可以做做到\(O(4n^3/wordsize)\)。

(当然,使用其他一些优秀的卡常方法也能过这题)


Matrix Revolution

HDUOJ 1759

给定一个 \(n \times n\) 的矩阵 \(A\),计算下述矩阵的非零元素的数量

\[ A + A^2 + \cdots + A^k\]

\(A\) 是稀疏矩阵,用 \(m\) 个三元组 \((a, b, c)\) 表示,每个三元组代表 \(A_{ab} = c\)。此外,保证主对角线上的元素全为 1。其他元素均为0。

\((0 \leq n \leq 1000, 0 \leq m \leq 10n, n < k < 10^{100}, 0 < c < 10^9)\)

题解

利用图的邻接矩阵表示,可知答案就是距离不超过 \(k\) 的点对数。


Matrix Multiplication

POJ 3318

给定 \(n \times n\) 的矩阵 \(A, B, C\)。判断\(A B = C\)是否成立。\((n \leq 500, |A_{ij}|, |B_{ij}| \leq 100, |C_{ij}| \leq 10,000,000)\)

提示:有多组测试数据,\(O(n^3)\) 的算法会 TLE。

题解

随机生成 \(n\) 维列向量 \(\vec{x}\),判断 \(AB\vec{x} = C\vec{x}\) 是否成立。可在 \(O(n^2)\) 时间内完成。

算法出错当且仅当 \((AB-C)\vec{x} = 0\) 而 \(AB – C \neq 0\)。 假设我们在 \(\mathbb{F}_p\) 里做。令 \(M = AB – C\), 则 \(\vec{x}\) 在 \(M\) 的零空间中。仔细想一想 \(M\) 的零空间最多 \(n-1\) 维,因此出错的概率不会超过\(1/p\)。

(当然,使用三次方的算法加一些优秀的卡常,也许也能过)

Remark: 

这一算法被称为Freivalds算法,是一种单边错Monte Carlo随机算法。对于整数矩阵,存在确定性的\(O(n^2)\)的算法判断乘法是否正确。不过由于Freivalds算法非常易于实现,目前实际上仍然大量使用该算法 。


Square

UVA 11542, also available at vjudge

给定 \(n\) 个整数的集合你可以生成 \(2^n-1\) 个非空子集。求有多少个子集,其中的数之积为完全平方数。

\(1 \leq T \leq 30\), \(1 \leq n \leq 100\), 所有整数在 1 和 \(10^{15}\) 之间。整数的素因子最多为 500。

题解

每个整数的唯一分解序列都看成 \(\mathbb{F}_2\) 上的一个的向量,就是要求这些向量构成矩阵的零空间的大小。

运行在裸机上的俄罗斯方块游戏

操作系统课的第一个大实验…

Github:https://github.com/wx-csy/OSLab0-Tetris

因为关于硬件的具体细节都在AM里面封装好了,所以写起来和写正常的程序并没有太大的区别,只是轮子得重新再造一遍…

玩法说明

运行make run,进入游戏。注意,工程的Makefile文件已经被修改,请运行修改过后的Makefile文件。

进入qemu后,首先运行自检程序,并在终端中打印当前机器的基本情况、设备信息和时间信息。随后,播放Splash界面(可按return键跳过)。按C键进入游戏。

左右键控制当前方块的位置,上键顺时针旋转当前方块,下键逆时针旋转当前方块,空格键加速下落。消除单行可获得1分,单次消除2行获得3分,单次消除3行获得5分,单次消除4行可获得8分。其他规则和经典的俄罗斯方块游戏基本一致。由于Wall kick系统尚未实现,诸如L-spin等骚操作暂时无法使用…

主要技术说明

图片和文字

游戏中的图片素材,除ProjectN的logo外,均使用GIMP工具制作。

使用GIMP的export功能,可将图片导出为C源代码格式,然后逐点绘制在屏幕上即可。

文字使用点阵字模。每个ASCII文字的形状以16*8点阵的形式存储在程序中,绘制时根据字模数据逐点绘制即可。

Splash界面的渐变效果

绘制图片时,可以附加一个透明度参数\(\alpha\),使得绘制出的颜色满足下式

\[
\begin{cases}
r = r_f \alpha + r_b (1 – \alpha) \\
g = g_f \alpha + g_b (1 – \alpha) \\
b = b_f \alpha + b_b (1 – \alpha)
\end{cases}
\]

其中\(r_f, g_f, b_f\)为图像颜色的三个分量,\(r_b, g_b, b_b\)为背景色的三个分量。

在播放渐变动画时,只需要将\(alpha\)从0逐渐调整为1,就可实现渐变效果。

Gameover界面的变灰效果

在绘制图片时,还可附加一个颜色矩阵\(M\)。\(M\)是\(3\times3\)的矩阵,用于对颜色的三个分量进行线性变换:

\[
\begin{cases}
r’ = rM_{11} + gM_{12} + bM_{13} \\
g’ = rM_{21} + gM_{22} + bM_{23} \\
b’ = rM_{31} + gM_{32} + bM_{33}
\end{cases}
\]

其中,\(M_I = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\) 表示恒等变换,
\(M_G = \begin{bmatrix} 0.33 & 0.59 & 0.11 \\ 0.33 & 0.59 & 0.11 \\ 0.33 & 0.59 & 0.11 \end{bmatrix}\)表示灰度变换(即将彩色图片变换为黑白图片)。

这样,只需设置一个混合因子\(\lambda\),并且使用\(\lambda M_G + (1-\lambda)M_I\)绘制图片,同时将\(\lambda\)从0逐渐调整为1,即可实现逐渐变灰的效果。