Codeforces Round #726 (Div. 2) A B C E1 题解
2021/6/19 6:27:15
本文主要是介绍Codeforces Round #726 (Div. 2) A B C E1 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
A. Arithmetic Array
题意:
给你n个数的数组 问最多加几个非负数 可以让数组总和/元素个数等于1
思路:
分类讨论 假设总和为sum,数组个数为n 假设加了cnt个非负数x 目标是 sum + cnt * x = n + cnt 这个式子不难发现右边每次只可以加1 左边可以加任何非负数 所以 如果sum = n 答案为0 如果sum < n 答案为1 如果sum > n 因为右边每次只能加1 左边x可以为0 等价于 sum = n + cnt 所以答案为 sum - n
时间复杂度:O n
#include<bits/stdc++.h> #define fer(i,a,b) for(re i = a ; i <= b ; ++ i) #define re register int #define pll pair<int,int> #define x first #define y second #define sf(x) scanf("%d",&x) #define sfl(x) scanf("%lld",&x) typedef long long ll ; using namespace std; const int N = 1e6 + 10 , M = 1010 , inf = 0x3f3f3f3f , mod = 1e9 + 7 ; int t ; int n ; int a[N] ; int main() { cin >> t ; while(t--) { cin >> n ; int sum = 0 , res = 0 ; fer(i,1,n) { cin >> a[i] ; if(a[i] > 0) sum += a[i] ; else if(a[i] < 0) res += a[i] ; } if(sum + res == n) puts("0") ; else if(sum + res < n) puts("1") ; else { cout << sum + res - n << "\n" ; } } return 0; }
B. Bad Boy
题意:
一个n*m的地图,一个人一开始在sx,sy这个位置 问如何安排2个溜溜球的位置, 使得他所走的距离最大化 并且要拿起这2个溜溜球 最后回到起点sx,sy这个位置
思路:
因为只能上下左右走 所以距离是曼哈顿距离 并且如果距离要最大 肯定是把这2个溜溜球放在4个端点的其中2个 {{1,1},{1,m},{n,1},{n,m}} 所以枚举这2个端点 求出最大值即可 后面发现1,1,n,m一定是最优解 所以直接输出即可
时间复杂度:O n
#include<bits/stdc++.h> #define fer(i,a,b) for(re i = a ; i <= b ; ++ i) #define re register int #define pll pair<int,int> #define x first #define y second #define sf(x) scanf("%d",&x) #define sfl(x) scanf("%lld",&x) typedef long long ll ; using namespace std; const int N = 1e6 + 10 , M = 1010 , inf = 0x3f3f3f3f , mod = 1e9 + 7 ; int t ; int n , m , sx , sy ; int main() { cin >> t ; while(t--) { cin >> n >> m >> sx >> sy ; cout << 1 << " " << 1 << " " << n << " " << m << "\n" ; } return 0; }
C. Challenging Cliffs
题意:
给n个数的数组h[n] 可以按任意顺序排序 求当abs(h[1]-h[n])最小的时候 h[i] <= h[i+1]的i的个数最大 (1 <= i <= n - 1)
思路:
贪心 首先从小到大排序之后 首先找到2个下标sx,sy 使得abs(h[sx]-h[sy])最小 可以发现 1 <= i < sx h[i] <= h[i+1] sy <= i < n h[i] <= h[i+1] 所以把sy到n中的数放前面 把1到sx中的数放后面 当h[sx]!=h[sy]的时候 h[i] <= h[i+1]的i的个数最大为n-1 当h[sx]==h[sy]的时候 为n
时间复杂度:O tnlogn
#include<bits/stdc++.h> #define fer(i,a,b) for(re i = a ; i <= b ; ++ i) #define re register int #define pll pair<int,int> #define x first #define y second #define sf(x) scanf("%d",&x) #define sfl(x) scanf("%lld",&x) typedef long long ll ; using namespace std; const int N = 1e6 + 10 , M = 1010 , inf = 0x3f3f3f3f , mod = 1e9 + 7 ; int t ; int n ; int a[N] ; int main() { cin >> t ; while(t--) { cin >> n ; fer(i,1,n) sf(a[i]) ; sort(a + 1 , a + 1 + n) ; int res = 1e9 ; fer(i,2,n) { res = min(res,a[i] - a[i-1]) ; } int sx , sy ; fer(i,2,n) { if(a[i] - a[i-1] == res) { sx = i - 1 ; sy = i ; break ; } } //cout << res << "\n" ; //cout << sx << " " << sy << "\n" ; if(n >= 3) { for(int i = sy ; i <= n ; i ++) { cout << a[i] << " " ; } for(int i = 1 ; i <= sx ; i ++) { cout << a[i] << " " ; } } else if(n == 2) { for(int i = 1 ; i <= n ; i ++) cout << a[i] << " " ; } cout << "\n" ; } return 0; }
E1. Erase and Extend (Easy Version)
题意:
给定n,k,和一个字符串s 2个操作 1是s = s + s 2是删除s的最后一个字符 每个操作可以进行任意次 求经过任意次操作的且长度为k的且字典序最小的字符串 1 <= n,k <= 5000
思路:
考虑n,k的范围 可以暴力n^2做 不管最后怎么进行操作 长度为k的的字符串只有n种情况 因为最后的字符串长度如果大于k了 你可以减到k 所以暴力求出这n个字符串 sort排序一下 输出第一个即可
时间复杂度:O n^2
#include<bits/stdc++.h> #define fer(i,a,b) for(re i = a ; i <= b ; ++ i) #define re register int #define pll pair<int,int> #define x first #define y second #define sf(x) scanf("%d",&x) #define sfl(x) scanf("%lld",&x) typedef long long ll ; using namespace std; const int N = 1e6 + 10 , M = 1010 , inf = 0x3f3f3f3f , mod = 1e9 + 7 ; char a[N] ; int b[N] ; int z = 0 ; string q[N] ; int main() { int n , k ; cin >> n >> k ; cin >> a + 1 ; int c = 0 ; for(int i = 1 ; i <= n ; i ++) { string x = "" ; for(int j = 1 ; j <= i ; j ++) { x += a[j] ; } string y = "" ; for(int j = 1 ; j <= k / i + 5 ; j ++) { y += x ; } q[++ c] = y.substr(0,k) ; //cout << y.substr(0,k) << "\n" ; // cout << y << "\n" ; } sort(q + 1 , q + 1 + c) ; cout << q[1] << "\n" ; return 0; }
这篇关于Codeforces Round #726 (Div. 2) A B C E1 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享