第一题 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(n2)
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≤105，1≤ai≤bi≤n。
输入样例1：
10 5
1 2
3 3
4 6
7 7
8 10
输出样例1:
OK
1
输入样例2：
10 5
1 2
2 3
4 5
7 8
9 10
输出样例2：
2 2
1
输入样例3：
10 5
1 2
3 3
5 7
7 7
7 10
输出样例3：
4 0
1
二、解题报告
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"; //如果花没死，输出OK
return 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≤104，2≤n，2≤n×m≤105，1≤pij≤109，一个测试点内所有数据的 n×m 值相加不超过 105。
输入样例1：
5
2 2
1 2
3 4
4 3
1 3 1
3 1 1
1 2 2
1 1 3
2 3
5 3 4
2 5 1
4 2
7 9
8 1
9 6
10 8
2 4
6 5 2 1
7 9 7 2
输出样例：
3
2
4
8
2
1
2
3
4
5
二、解题报告
1、思路分析
思路来源：AcWin 4863. 构造新矩阵（AcWing杯 - 周赛）
y总yyds
（1）通过逆向进行考虑，即若存在L最大值是否能够在原矩阵中选择n-1行使每列的最大值都大于等于L。
（2）可以通过二分来找满足的L的最大值，小于等于L最大值的一定满足条件，而大于L最大值的一定不满足条件，具有二段性，而由题目范围可知L的取值范围在1~109，所以可以通过二分来找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(n2logn)
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，来求出满足条件最大的L
int 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;
}
