【Acwing 周赛复盘】第91场周赛复盘（2023.2.18）

周赛复盘 ✍️

本周个人排名：1286/3115

AC情况：2/3

这是博主参加的第六次周赛，周赛当晚有事，是后来定时自测的 😂

在 20 分钟内 AC 了 2 题，看了一下这个成绩应该是排在 400名左右的。

T1 签到题，考察数字的分解 ✅

T2 考察哈希表/桶思想 ✅

T3 一眼「二分答案」，但是 check 函数中的变量太多，不知道如何写 ❌ （经过复盘，发现自己潜在问题很多，具体见 T3 的分析部分）

不过这次 T3 只有 86 个同学通过（往常都是几百人通过），说明确实有难度，做不出来也算是情有可原。

继续加油，冲冲冲。🚀

周赛信息 📚

时间：2023年 2 月 18 日 19：00-20：15

竞赛链接：https://www.acwing.com/activity/content/introduction/2893/

y总直播间：http://live.bilibili.com/21871779

y总录播讲解视频：【AcWing杯 - 第 91 场周赛讲解】

题目列表 🧑🏻‍💻

题目名称	原题链接	视频讲解	难度
4861. 构造数列	原题链接	视频链接	简单 🟢
4862. 浇花	原题链接	视频链接	简单 🟢
4863. 构造新矩阵	原题链接	视频链接	困难 🔴

题解 🚀

【题目A】构造数列

【题目描述】

我们规定如果一个 正整数 满足除最高位外其它所有数位均为 $0$，则称该正整数为圆数。

例如，$1,8,900,70,5000$ 都是圆数，$120,404,333,8008$ 都不是圆数。

给定一个正整数 $n$，请你构造一个 圆数 数列，要求：

• 数列中所有元素相加之和恰好为 $n$。
• 数列长度尽可能短。

【输入】

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据占一行，包含一个整数 $n$。

【输出】

每组数据输出两行结果，第一行输出数列长度，第二行输出构造数列。

如果方案不唯一，输出任意合理方案均可。

【数据范围】

前三个测试点满足 $1\le T\le 10$。

所有测试点满足 $1\le T\le 10000$，$1\le n\le 10000$。

【输入样例1】

5
5009
7
9876
10000
10

【输出样例1】

2
5000 9
1
7
4
800 70 6 9000
1
10000
1
10

【原题链接】

https://www.acwing.com/problem/content/description/4864/

---

【题目分析】

签到题，考察数字的分解。可以直接对数字 n 进行分解，也可以将 n 转化成字符串分解。

【复盘后的优化代码】✅

数字分解法

#include<bits/stdc++.h>using namespace std;
const int N = 1e5 + 10;
int T, n, a[N];int main() {ios::sync_with_stdio(false);  //cin读入优化cin.tie(0);cin >> T;while (T--) {cin >> n;int cnt = 0; // cnt统计非0位的个数int pow = 1; // pow记录当前数字需要乘上几个0// 分解当前数字nwhile (n > 0) {// 当前末尾数字非0，放入一个圆数if (n % 10) a[++cnt] = (n % 10) * pow;pow *= 10;n = n / 10;}// 输出结果cout << cnt << endl;for (int i = 1; i <= cnt; i++) cout << a[i] << " ";cout << endl;}return 0;
}

字符串分解法

#include<bits/stdc++.h>using namespace std;
const int N = 1e5 + 10;int T, n, a[N];
string str;int main() {ios::sync_with_stdio(false);  //cin读入优化cin.tie(0);cin >> T;while (T--) {cin >> str;int cnt = 0, pow = 1;for (int i = str.length() - 1; i >= 0; i--) {  // 从后往前if (str[i] != '0') a[++cnt] = (str[i] - '0') * pow;pow *= 10;}cout << cnt << endl;for (int i = 1; i <= cnt; i++) cout << a[i] << " ";cout << endl;}return 0;
}

---

【题目B】浇花

【题目描述】

某公司养有观赏花，这些花十分娇贵，每天都需要且仅需要浇水一次。

如果某一天没给花浇水或者给花浇水超过一次，花就会在那一天死亡。

公司即将迎来 $n$ 天假期，编号 $1\sim n$。

为了让花能够活过整个假期，公司领导安排了 $m$ 个人（编号 $1\sim m$）来公司浇花，其中第 $i$ 个人在第 $[a_i,b_i]$ 天每天来公司浇一次花。

领导是按照时间顺序安排的浇花任务，保证了对于 $1\le i\le m-1$，均满足：$b_i\le a_{i+1}$。

给定领导的具体安排，请你判断，花能否活过整个假期，如果不能，请你输出它是在第几天死的，以及那一天的具体浇水次数。

【输入】

第一行包含两个整数 $n,m$。

接下来 $m$ 行，每行包含两个整数 $a_i,b_i$。

【输出】

输出一行结果。

如果花能活过整个假期，则输出 OK。

如果花不能活过整个假期，则输出两个整数 $x,y$，表示花是在第 $x$ 天死的，这一天花被浇了 $y$ 次水。

【数据范围】

前 $4$ 个测试点满足 $1\le n,m\le 10$。

所有测试点满足 $1\le n,m\le 10^5$，$1\le a_i\le b_i\le n$。

【输入样例1】

10 5
1 2
3 3
4 6
7 7
8 10

【输出样例1】

OK

【输入样例2】

10 5
1 2
2 3
4 5
7 8
9 10

【输出样例2】

2 2

【输入样例3】

10 5
1 2
3 3
5 7
7 7
7 10

【输出样例3】

4 0

【原题链接】

https://www.acwing.com/problem/content/description/4865/

---

【题目分析】

本题暴力法就是使用 桶思想，在本题的条件下可以 AC，但是如果去除「保证了对于 $1\le i\le m-1$，均满足：$b_i\le a_{i+1}$」的条件，就会超时了。

所以推荐使用 差分，把模型抽象出来，即每个人都会给一段连续的天数 + 1（浇水），最后求判断每天被浇水了几次即可。

【复盘后的优化代码】✅

差分

#include<bits/stdc++.h>using namespace std;
const int N = 1e5 + 10;int n, m, l, r, b[N];int main() {ios::sync_with_stdio(false);  //cin读入优化cin.tie(0);cin >> n >> m;for (int i = 1; i <= m; i++) {cin >> l >> r;b[l]++, b[r + 1]--;  // 维护差分数组}// 还原for (int i = 1; i <= n; i++) {b[i] += b[i - 1];if (b[i] != 1) {cout << i << " " << b[i] << endl;return 0;}}cout << "OK" << endl;return 0;
}

【周赛现场 AC 代码】

暴力/桶思想

#include<bits/stdc++.h>using namespace std;const int N = 1e5 + 10;
int n, m, x, y;
int b[N]; // 桶int main() {ios::sync_with_stdio(false);  //cin读入优化cin.tie(0);cin >> n >> m;for (int i = 1; i <= m; i++) {cin >> x >> y;for (int j = x; j <= y; j++) // 将当前第i人负责的所有天数，放入桶中b[j]++;}// 判断每个桶中的元素数量是否为1for (int i = 1; i <= n; i++) {if (b[i] != 1) {cout << i << " " << b[i] << endl;return 0;}}cout << "OK" << endl;return 0;
}

---

【题目C】构造新矩阵

【题目描述】

给定一个 $m$ 行 $n$ 列的整数矩阵，行编号 $1\sim m$，列编号 $1\sim n$。

其中，第 $i$ 行第 $j$ 列的元素为 $p_{ij}$。

你可以任意抽取其中不超过 $n-1$ 行元素，这些元素之间保持同一行列关系不变，构成一个新矩阵。

构成新矩阵后，我们可以确定一个最大的整数 $L$，使得新矩阵中每一列都至少存在一个元素不小于 $L$。

我们希望通过合理构造新矩阵，使得 $L$ 的值尽可能大。

请你计算并输出 $L$ 的最大可能值。

注意：矩阵一共有 $m$ 行，但是抽取的行数上限是 $n-1$ 行，而不是 $m-1$ 行，读题时不要搞混行和列。

【输入】

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据首先包含一个空行。

第二行包含两个整数 $m,n$。

接下来 $m$ 行，每行包含 $n$ 个整数，其中第 $i$ 行第 $j$ 个整数表示 $p_{ij}$。

【输出】

每组数据输出一行结果，一个整数，表示 $L$ 的最大可能值。

【数据范围】

前三个测试点满足 $1\le T\le 5$，$2\le n\times m\le 100$。所有

测试点满足 $1\le T\le 10^4$，$2\le n$，$2\le n\times m\le 10^5$，$1\le p_{ij}\le 10^9$，一个测试点内所有数据的 $n\times m$ 值相加不超过 $10^5$。

【输入样例】

52 2
1 2
3 44 3
1 3 1
3 1 1
1 2 2
1 1 32 3
5 3 4
2 5 14 2
7 9
8 1
9 6
10 82 4
6 5 2 1
7 9 7 2

【输出样例】

3
2
4
8
2

【原题链接】

https://www.acwing.com/problem/content/4866/

---

【题目分析】

一眼「二分答案」，但是苦于情况太多，没能够把 check 函数写出来，总结原因如下：

• 审题能力 需要加强，对时间复杂度的恐惧 要降低。自己读题时，分析复杂度应该是：$T\ast log\ast check$（但是本题 T 比较大，check 里面也很大，想着很容易超时，一下子人就比较慌）。但实际上，题目的意思应该是 $T\ast check$ 这一个整体被控制在 $10^5$，所以是不会超时的。
  • 措施 🚀：仔细审题，对时间复杂度不要害怕，在没有更好的优化想法时，先把当前思路的代码敲出来。
• 情况一多，就变得畏手畏脚，不敢动手。一会儿考虑这儿，一会儿考虑那儿，思路不够清晰，不够有逻辑。
  • 措施 🚀：下次做题时，遇到多种情况、边界条件等，像y总那样慢慢分析，把思路更加有条理的在纸上呈现出来（如下图）
• 逻辑推理能力 还需加强，尤其是面对思维题的时候，总是差临门一脚。例如本题中，其实自己已经推导到了，求出每列的 maxV，并且知道要从 「行」 的角度进行转换，用「画点法」来模拟最大值的分布等。但是一直不知道该如何处理「选取 $n-1$ 行」这个过程，导致代码无法书写下去。
  • 措施🚀：多做题，多总结

y总的思路图，详细讲解见：https://www.acwing.com/video/4628/

🍉 PS：本题由于空间限制，不能开 a[N][N] $(N\le 10^5)$ 的数组，需要用二维 vector 来实现。

vector<int> g[N];  // 注意不是g[N][N]

【复盘后的优化代码】✅

#include<bits/stdc++.h>using namespace std;
const int N = 1e5 + 10;int T, n, m, tmp;
int row[N], col[N];
vector<int> g[N];  // 二维vecotr数组bool check(int L) {// 此题对时间卡的比较严，不要使用memsetfor (int i = 0; i < m; i++) row[i] = 0;for (int i = 0; i < n; i++) col[i] = 0;// row[k]存储第k行有几个>=L的数，col[k]存储第k列有几个>=L的数for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (g[i][j] >= L) {row[i]++, col[j]++;}}}// 检查每列是否有值>=Lfor (int i = 0; i < n; i++) {if (col[i] == 0) return false;}// 在每一列都有>=L元素的基础上，检查是否一行中有至少2个>=L的元素for (int i = 0; i < m; i++) {if (row[i] >= 2) return true;}return false;
}int main() {ios::sync_with_stdio(false);  //cin读入优化cin.tie(0);cin >> T;while (T--) {// 读入矩阵cin >> m >> n;for (int i = 0; i < m; i++) {g[i].clear();  // 记得初始化for (int j = 0; j < n; j++) {cin >> tmp;g[i].push_back(tmp);}}//第二种读入方式
//        for (int i = 0; i < m; i++) {
//            g[i].resize(n);
//            for (int j = 0; j < n; j++) {
//                cin >> g[i][j];
//            }
//        }// 对答案二分int l = 1, r = 1e9 + 10;while (l < r) {// l + r + 1的最大值<int_max，但是比较接近了，用LL会保险一点int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}cout << r << endl;}return 0;
}

---