月度归档: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,即可实现逐渐变灰的效果。