THUWC 2019 Problems

Day 1

邮件(mail)

Description

n 封信和 n 个邮筒,第 i 封信需要被寄往 a_{i} 处,第 i 个邮筒中的信会被寄往 b_{i} 处。一个邮筒只能装一封信。

q 次询问,每次询问给定 c,d,e,f ,问若将编号在 \left[c,d\right] 中的邮件随机投到编号在 \left[e,f\right] 中的邮筒里,会被寄往正确地址的信的期望封数。

Constraints

1\le n\le 10^{5},1\le q\le 10^{5}

1\le n\le 5\times 10^{4},1\le q\le 10^{6}

路途(journey)

Description

给定一个 r\times c 的网格图,有下列移动方式:

  1. 每行每列内部可以乘火车移动(费用给定且不尽相同)。
  2. a 个格点被定为机场,机场间可以乘飞机移动(费用给定且固定)。

有下列影响:

  1. m 个格点在一个前缀时间有雷雨,当行当列的火车在该前缀时间内停开。
  2. 所有的机场在一个前缀时间被影响,在该前缀时间内无法通过飞机到达该机场,也无法通过飞机从该机场离开。

乘坐火车或飞机移动不需要时间。
q 次询问,每次询问给出起点终点,求所需的最短时间及在时间最短前提下所需的最小费用。

Constraints

1\le r,c\le 10^{5}

0\le m,a\le\max\left\{r\cdot c,2\times 10^{5}\right\}

0\le dr_{i},da_{i}\le 10^{8}

0\le cr_{i},cc_{i},ca\le 10^{9}

0\le q\le 10^{6}

令人印象深刻的题目名称(impressive)

Description

给定一个长为 n ,值域为 \left[1,n+1\right] 的初始序列 \{a_{n}\}
现在允许做至多 m 次操作,每次选定一个区间 [l, r] 和一个数 v ,将 \{a_{n}\} 中下标在 [l, r] 中的元素对 v \min
计算有多少种不同的操作序列,使得在且仅在操作完时序列 \{a_{n}\} 与目标序列 \left\{b_{n}\right\} 相等。

答案对 10^{9}+7 取模。

Constraints

1\le n\le 100,1\le m\le 10^{9}

Day 2

畅游清华园(campus)

Description

给定一棵有 n 个点的树,每条边有两个权值 a,b ,每个点有两个权值 c,d
从点 i 出发的人经过边 j 的花费是 \min\left\{a_{j}+c_{i},b_{j}+d_{i}\right\}
现在对于 1\le i,j\le n,i\ne j 都有一个人要以最短路径从点 i 出发到点 j ,求他们的花费之和。

答案对 10^{9}+7 取模。

Constraints

100\le n\le 5\times 10^{5}

1\le a_{i},b_{i},c_{i},d_{i}\le 10^{5}

地形勘察(survey)

Description

这是一道交互题。

有一棵 n 个点的树,边权均为 1 ,其形态未知。

你需要通过调用如下所述的两个函数来求出树的形态:


feature1(int m,const int *a) : min

m 为一个整数,表示有 m 个人需要集合。

a 为一个数组, a_{i}\left(0\le i<m\right) 表示第 i 个人一开始处在编号为 a_{i} 的点。可能有多个人处在同一个点。

返回值 \min 为这 m 个人集合到一个点所需走的路程之和的最小值。


feature2(int m,const int *a) : pos

m 为一个整数,表示有 m 个人需要集合。

a 为一个数组, a_{i}\left(0\le i<m\right) 表示第 i 个人一开始处在编号为 a_{i} 的点。可能有多个人处在同一个点。

返回值 pos 表示若要使这 m 个人集合到一个点所需走的路程之和最小,则需在编号为 pos 的点集合。

当有多个点均满足上述条件时,该函数会返回其中的任意一点。


你需要实现一个函数 work(int n,int lim1,int lim2,int *x,int *y)。其中:

n 为树的节点总数。

lim1 为调用 feature1 函数的次数限制。

lim2 为调用 feature2 函数的次数限制。

你的答案需要存放在 x,y 两个数组中, \left<x_{i},y_{i}\right>\left(0\le i<n\right) 表示一条原树上的边。

一个测试点的计分方式如下:

\text{scorerate}=\min\left\{f\left(cnt_{1},lim1\right),f\left(cnt_{2},lim2\right)\right\}

其中 \text{scorerate} 为你的程序在该测试点上的得分与该测试点总分数的比值。 f 定义如下:

f\left(cnt,lim\right)=\begin{cases} 1 & cnt\le lim\\ 0.7\sqrt{\frac{lim}{cnt}} & lim<cnt\le 2\times lim\\ 0 & 2\times lim<cnt \end{cases}

Constraints

1\le n\le 4000

3999\le lim1,3997\le lim2

10^{5}\le lim1,lim2=0

计算几何(geometry)

Description

给定平面上的 n 个点,可以选出一些点为顶点组成一个面积非零的凸包。

求所有可选出的凸包的面积的平均值和方差。

Constraints

1\le n\le 400

0\le x_{i},y_{i}\le 10^{9}

Day 2+

图像处理 1000 合 1

本题为给出资料的学习型题目,为提交答案题。

  1. (20pts): 计算一个序列的 ADLER32 校验码.
  2. (30pts): 计算一个序列的 CRC32 校验码.
  3. (50pts): 读取一个 png 文件,输出其 RGB 矩阵.
  4. (50pts): 读取 RGB 矩阵,输出对应的 png 文件.
  5. (20pts): Sobel 算子 边缘检测.
  6. (20pts): Halton 序列 随机采样.
  7. (30pts): 基于像素的纹理合成.
  8. (80pts): 基于块的纹理合成.