长沙建站优化,化学商城网站建设,wordpress适合seo,saas系统架构文章目录第一题 AcWing 4861. 构造数列一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解第二题 AcWing 4862. 浇花一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解第三题 AcWing 4861. 构造数列一、题目1、原题…
文章目录第一题 AcWing 4861. 构造数列一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解第二题 AcWing 4862. 浇花一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解第三题 AcWing 4861. 构造数列一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解第一题 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≤100001≤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(){cint;while(t--){cinn;string tmpto_string(n); //tmp存储将n代表的数字转为字符串cnt0;for(int i0;itmp.size();i){if(tmp[i]!0) cnt; //cnt统计非零数字的个数}coutcntendl;for(int i0;itmp.size();i){if(tmp[i]!0){ //如果当前位置非0输出它在原数中所代表的数是多少即该位数字乘它在原数中的权重couttmp[i];for(int j0;jtmp.size()-i-1;j){cout0;}cout ;}}coutendl;}return 0;
}第二题 AcWing 4862. 浇花
一、题目
1、原题链接 4862. 浇花 2、题目描述 某公司养有观赏花这些花十分娇贵每天都需要且仅需要浇水一次。 如果某一天没给花浇水或者给花浇水超过一次花就会在那一天死亡。 公司即将迎来 n 天假期编号 1∼n。 为了让花能够活过整个假期公司领导安排了 m 个人编号 1∼m来公司浇花其中第 i 个人在第 [ai,bi] 天每天来公司浇一次花。 领导是按照时间顺序安排的浇花任务保证了对于 1≤i≤m−1均满足 bi≤ai1。 给定领导的具体安排请你判断花能否活过整个假期如果不能请你输出它是在第几天死的以及那一天的具体浇水次数。 输入格式 第一行包含两个整数 n,m。 接下来 m 行每行包含两个整数 ai,bi。 输出格式 输出一行结果。 如果花能活过整个假期则输出 OK。 如果花不能活过整个假期则输出两个整数 x,y 表示花是在第 x 天死的这一天花被浇了 y 次水。 数据范围 前 4 个测试点满足 1≤n,m≤10。 所有测试点满足 1≤n,m≤1051≤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 N100010;
int n,m;
int d[N]; //d存储花每天被浇的次数
int a,b;
//差分
void insert(int l,int r,int c){d[l]c;d[r1]-c;
}
int main(){cinnm;;for(int i1;im;i){cinab;insert(a,b,1);}//差分数组求前缀和得到原数组for(int i1;in;i){d[i]d[i-1];if(d[i]0){ //如果某天花没有被浇花死了输出该天以及该天的浇水次数couti d[i];return 0;}if(d[i]1){ //如果某天花被浇了超过1次花死了输出该天以及该天的浇水次数couti d[i];return 0;}}coutOK; //如果花没死输出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≤52≤n×m≤100。 所有测试点满足1≤T≤1042≤n2≤n×m≤1051≤pij≤109一个测试点内所有数据的 n×m 值相加不超过 105。 输入样例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~109所以可以通过二分来找L的最大值。 3针对m与n-1的关系可以分为两种情况。
mn-1。此时我们就是将矩阵的所有行都已选到所以只需要判断整个矩阵是否每列都最大值大于等于L即可。mn-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 N100010;
int n,m;
vectorint a[N]; //不能直接开二维数组会爆空间
bool st[N]; //判断是否存在一行中含有两个不同列的列中最大值
int t;
bool check(int mid){for(int i0;im;i) st[i]false;bool flag1false; //flag1代表是否存在一行中包含两个不同列的最大值for(int i0;in;i){bool flagfalse; //flag代表该列是否存在大于等于L的数for(int j0;jm;j){if(a[j][i]mid){flagtrue;if(st[j]) flag1true; //如果当前行已包含一个最大值说明至少存在两个不同列的最大值st[j]true;}}if(!flag) return false; //如果该列中不存在大于等于L的数返回false}return flag1;
}
int main(){cint;while(t--){cinmn;for(int i0;im;i){a[i].resize(n);for(int j0;jn;j){cina[i][j];}}//二分L来求出满足条件最大的Lint l1,r1e9;while(lr){int midlr11;if(check(mid)) lmid;else rmid-1;}coutrendl;}return 0;
}
