#P17269. [2025年南开中学集训]网格涂色

[2025年南开中学集训]网格涂色

题目描述

将 n n 行 m m 列的网格中一些格子涂成黑色,第 i i 列恰好涂 ai a_i 格。

你关心的是涂色后的最长递增子序列长度。即最大的 k k ,使得存在黑格 (r1,c1), (r2,c2), ⋯ , (rk,ck) (r_1,c_1),\ (r_2,c_2),\ \cdots,\ (r_k,c_k) 满足 1≤r1<r2<⋯<rk≤n 1\leq r_1<r_2<\cdots<r_k\leq n 和 1≤c1<c2<⋯<ck≤m 1\leq c_1<c_2<\cdots<c_k\leq m 。

构造一种方案,使 k k 的最大值最小。

输入格式

第一行一个整数 T T 。

每组数据:
第一行两个整数 n,m n,m 。
第二行 m m 个整数 a1,⋯ ,am a_1,\cdots,a_m 。

输出格式

每组数据:
第一行输出一个整数 k k 。
接下来 n n 行,每行一个长度为 m m 的字符串, . 表示白色 # 表示黑色。

如果输出格式正确,且所有 k k 均正确,可以获得该测试点 40% 40\% 的分值。

样例1

样例输入

4
2 4
1 1 1 1
3 3
3 3 3
4 4
4 3 2 1
4 5
2 3 4 3 2

样例输出

1
....
####
3
###
###
###
2
###.
#...
####
##..
2
..###
.####
####.
###..

本题不提供更多样例

数据范围

所有数据:

  • 1≤T≤105 1\leq T\leq 10^5
  • 1≤n,m≤2×105 1\leq n,m\leq 2\times 10^5
  • 1≤ai≤n 1\leq a_i\leq n
  • ∑n⋅m≤2×105 \sum n\cdot m \leq 2\times 10^5

子任务分布:

  • 子任务1(10分): T≤10 T\leq 10 , n⋅m≤20 n\cdot m \leq 20
  • 子任务2(10分): T≤10 T\leq 10 , n≤2 n\leq 2
  • 子任务3(10分): T≤10 T\leq 10 , m≤2 m\leq 2
  • 子任务4(10分): T≤10 T\leq 10 , n,m≤10 n,m\leq 10
  • 子任务5(10分): a≤2 a\leq 2
  • 子任务6(50分): 无特殊性质

高塔联络