第一题 AcWing 4861. 构造数列

一、题目

1、原题链接

4861. 构造数列

2、题目描述

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

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

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

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

输入格式

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

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

输出格式

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

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

数据范围

前三个测试点满足 1≤T≤10。

所有测试点满足 1≤T≤10000，1≤n≤10000。

输入样例：

5
5009
7
9876
10000
10

输出样例：

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

二、解题报告

1、思路分析

（1）经过分析可知，我们直接将每位非0数字取出，然后再乘它在原数字中的权重，得到数列中的一个元素，将每位非0数字均如上操作，即可得到圆数数列，而原数字n中非0的位数即为数列长度。
（2）直接模拟上述过程即可，按题目要求输出即可。

2、时间复杂度

时间复杂度最坏情况为O(n²)

3、代码详解

#include <iostream>
#include <string>
using namespace std;
int t,n;
int cnt;
int main(){cin>>t;while(t--){cin>>n;string tmp=to_string(n);          //tmp存储将n代表的数字转为字符串cnt=0;for(int i=0;i<tmp.size();i++){if(tmp[i]!='0') cnt++;        //cnt统计非零数字的个数}cout<<cnt<<endl;for(int i=0;i<tmp.size();i++){if(tmp[i]!='0'){             //如果当前位置非0，输出它在原数中所代表的数是多少（即该位数字乘它在原数中的权重）cout<<tmp[i];for(int j=0;j<tmp.size()-i-1;j++){cout<<0;}cout<<' ';}}cout<<endl;}return 0;
}

第二题 AcWing 4862. 浇花

一、题目

1、原题链接

4862. 浇花

2、题目描述

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

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

公司即将迎来 n 天假期，编号 1∼n。

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

领导是按照时间顺序安排的浇花任务，保证了对于 1≤i≤m−1，均满足 bi≤ai+1。

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

输入格式

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

接下来 m 行，每行包含两个整数 ai,bi。

输出格式

输出一行结果。

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

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

数据范围

前 4 个测试点满足 1≤n,m≤10。 所有测试点满足 1≤n,m≤10⁵，1≤ai≤bi≤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

二、解题报告

1、思路分析

（1）利用差分，将每天花被浇的次数统计出来。
（2）按题目要求，来判断，如果某天花被浇的次数大于1，则花死了，输出该天和该天的浇水次数；如果某天花被浇的次数小于1，则花死了，输出改天和该天的浇水次数。如果花没死，输出OK即可。

2、时间复杂度

时间复杂度O(n)

3、代码详解

#include <iostream>
using namespace std;
const int N=100010;
int n,m;
int d[N];       //d存储花每天被浇的次数
int a,b;
//差分
void insert(int l,int r,int c){d[l]+=c;d[r+1]-=c;
}
int main(){cin>>n>>m;;for(int i=1;i<=m;i++){cin>>a>>b;insert(a,b,1);}//差分数组求前缀和得到原数组for(int i=1;i<=n;i++){d[i]+=d[i-1];if(d[i]==0){            //如果某天花没有被浇，花死了，输出该天以及该天的浇水次数cout<<i<<' '<<d[i];return 0;}if(d[i]>1){            //如果某天花被浇了超过1次，花死了，输出该天以及该天的浇水次数cout<<i<<' '<<d[i];return 0;}}cout<<"OK";              //如果花没死，输出OKreturn 0;
}

第三题 AcWing 4861. 构造数列

一、题目

1、原题链接

4863. 构造新矩阵

2、题目描述

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

其中，第 i 行第 j 列的元素为 pij。

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

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

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

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

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

输入格式

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

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

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

接下来 m 行，每行包含 n 个整数，其中第 i 行第 j 个整数表示 pij。

输出格式

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

数据范围

前三个测试点满足 1≤T≤5，2≤n×m≤100。
所有测试点满足1≤T≤10⁴，2≤n，2≤n×m≤10⁵，1≤pij≤10⁹，一个测试点内所有数据的 n×m 值相加不超过 10⁵。

输入样例1：

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

二、解题报告

1、思路分析

思路来源：AcWin 4863. 构造新矩阵（AcWing杯 - 周赛）
y总yyds

（1）通过逆向进行考虑，即若存在L最大值是否能够在原矩阵中选择n-1行使每列的最大值都大于等于L。
（2）可以通过二分来找满足的L的最大值，小于等于L最大值的一定满足条件，而大于L最大值的一定不满足条件，具有二段性，而由题目范围可知L的取值范围在1~10⁹，所以可以通过二分来找L的最大值。
（3）针对m与n-1的关系可以分为两种情况。

• m<=n-1。此时我们就是将矩阵的所有行都已选到，所以只需要判断整个矩阵，是否每列都最大值大于等于L即可。
• m>n-1。这个时候我们是从原矩阵阵中选n-1行，所以说原矩阵中存在一列的值都小于当前L。则无法使选出行中每列都大于等于L，无法满足条件；如果原矩阵中每一列都存在大于等于L的数，但是由于我们选的是n-1行，如果说每行中只有某一列的值大于等于L，而且我们选中的n-1行中每行中大于等于L的值都在不同列，这时候最多也只能有n-1列满足最大值大于等于L，所以我们必须要在上述条件下并且使这n-1行中，至少有一行存在两个大于等于L的数才能够满足条件，否则无法满足。

（4）模拟上述情况进行判断即可。

2、时间复杂度

时间复杂度为O(n²logn)

3、代码详解

#include <iostream>
#include <vector>
using namespace std;
const int N=100010;
int n,m;
vector<int> a[N];   //不能直接开二维数组，会爆空间
bool st[N];       //判断是否存在一行中含有两个不同列的列中最大值
int t;
bool check(int mid){for(int i=0;i<m;i++) st[i]=false;bool flag1=false;     //flag1代表是否存在一行中包含两个不同列的最大值for(int i=0;i<n;i++){bool flag=false;         //flag代表该列是否存在大于等于L的数for(int j=0;j<m;j++){if(a[j][i]>=mid){flag=true;if(st[j]) flag1=true;   //如果当前行已包含一个最大值，说明至少存在两个不同列的最大值st[j]=true;}}if(!flag) return false;     //如果该列中不存在大于等于L的数返回false}return flag1;
}
int main(){cin>>t;while(t--){cin>>m>>n;for(int i=0;i<m;i++){a[i].resize(n);for(int j=0;j<n;j++){cin>>a[i][j];}}//二分L，来求出满足条件最大的Lint l=1,r=1e9;while(l<r){int mid=l+r+1>>1;if(check(mid)) l=mid;else r=mid-1;}cout<<r<<endl;}return 0;
}