本文主要是介绍Codeforces Round 938 (Div. 3) (A~E)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Codeforces Round 938 (Div. 3) (A~E)
目录：A B C D E
A题：Yogurt Sale
标签: 数学（math）
题目大意
- 酸奶价格， a 元一份，b元两份n
- 问：买n份最少多少钱
思路
- a元一份，b元两份，总有一个比较低，一份一份买或两份两份买取小的一个即可，特判n为奇数多买一个a
AC代码
#include <bits/stdc++.h>
using namespace std;
void solve()
{int n, a, b;cin >> n >> a >> b;cout << min(n * a, n / 2 * b + n % 2 * a) << endl;
}
int main()
{int T; cin >> T;while(T--)solve();return 0;
}B题：Progressive Square
标签: 构造算法（constructive algorithms）数据结构（data structures）实现问题，编程技巧，模拟（implementation）排序算法（sortings）
题目大意
- 一个 n × n阵。三个整数 a1,1 、 c 和 d 并按照以下规则构造一个累进正方形：
- ai+1,j = ai,j + c
- ai,j+1 = ai,j + d
- 即：每一行每一列都是等差数列，公差分别为c，d
- 问题：给n，c，d 和一个长n × n的数组，问此数组是否是个累进正方形
思路
- 找到数组中最小值一定被作为a1,1，知道a1,1，c，d直接将累进正方形计算出 与 给定数组比较即可
AC代码
#include <bits/stdc++.h>
using namespace std;
const int N = 250010;
int a[N], b[N];
void solve()
{int n, c, d;int idx = 0;cin >> n >> c >> d;for(int i = 0; i < n * n; i++)cin >> a[i];sort(a, a + n * n);int t = a[0];for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)b[idx++] = t + i * c + j * d; sort(b, b + n * n);for(int i = 0; i < n * n; i++)if(a[i] != b[i]) {cout << "NO" << endl;return;}cout << "YES" << endl;
}
int main()
{int T; cin >> T;while(T--)solve();return 0;
}C题：Inhabitant of the Deep Sea
标签: 贪心策略（greedy）实现问题，编程技巧，模拟（implementation）数学（math）
题目大意
- n 艘飞船编号从 1 到 n ，依次递增；第 i 艘飞船的耐久度为 ai。
- 攻击次数：k 次
- 攻击力： 1
- 攻击顺序：攻击第一艘飞船，然后是最后一艘，接着又是第一艘，以此类推。
- 当船只的耐久度下降到 0时，它就会沉没，不再受到攻击
- 问：攻击k次后沉没几艘飞船
思路
- 分两种情况
- 1、攻击次数大于等于耐久度和，那么全部飞船都会沉没
- 2、攻击次数小于耐久度和，那么左边飞船共被攻击(k / 2 + k % 2)次，右侧飞船共被攻击k / 2次
- 枚举计算攻击次数能击沉左边多少艘，右边多少艘即可
AC代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 200010;
int a[N];
void solve()
{LL n, k, cnt = 0;cin >> n >> k;for(int i = 1; i <= n; i++){cin >> a[i];cnt += a[i];}if(k >= cnt){cout << n << endl;return;}LL t1 = k / 2 + k % 2; // 左侧先被攻击，所以k为奇数时左侧比右侧多1次LL t2 = k / 2;int l = 1, r = n;while(l <= n && t1 >= a[l])t1 -= a[l++];while(r >= 1 && t2 >= a[r])t2 -= a[r --];// 左侧被击沉l - 1艘，右侧被击沉n - r艘cout << l - 1 + n - r << endl;
}
int main()
{int T; cin >> T;while(T--)solve();return 0;
}
D题：Inaccurate Subsequence Search
标签: 数据结构（data structures）双指针算法（two pointers）
题目大意
- 有一个由 n 个整数组成的数组 a 和一个由 m 个整数组成的数组 b ( m ≤ n )。
- 好数组定义：如果数组 c 中的元素可以重新排列，使得其中至少有 k 个元素与数组 b 中的元素匹配，那么认为长度为 m 的数组 c 是好数组。
- 问：选择长度为 m 的数组 a 的每个子段作为数组 c 的元素，计算有多少个数组是好的
- 换句话说，求元素 al,al+1,…,al+m−1构成一个好数组的位置1 ≤ l ≤ n − m + 1 的个数。
思路
- 滑动窗口暴力模拟即可，具体看代码(含注释)
AC代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 200010;
int a[N], b[N];
void solve()
{int n, m, k;cin >> n >> m >> k;for(int i = 1; i <= n; i++)cin >> a[i];//mp1记录b中数与其数量，mp2记录每个长为m的a的子数组中数(动态维护) map<int, int> mp1, mp2; for(int i = 1; i <= m; i++) {cin >> b[i];mp1[b[i]] ++; }// cnt维护每个长为m的窗口与b匹配数的个数，res记录答案 int cnt = 0, res = 0;for(int i = 1; i <= n; i++){// i <= m时只添加数，添加a[i]到mp2 if(i <= m){// 添加a[i]到mp2 // 如过添加的数在b中还未匹配的数中存在，匹配数+1 if(mp2[a[i]] < mp1[a[i]]) cnt ++;mp2[a[i]] ++; }else {if(cnt >= k) res ++; // 如果当前子数组匹配数大于k，答案+1 // 上同 if(mp2[a[i]] < mp1[a[i]]) cnt ++;mp2[a[i]] ++; // 重点：如果当前子数组中a[i-m]的数量小于等于b中的数量，那么删除a[i-m]才会影响匹配数 if(mp2[a[i-m]] <= mp1[a[i-m]]) cnt --;mp2[a[i - m]] --;}}// 最后一次变化后没判断 if(cnt >= k) res ++;cout << res << endl;
}
int main()
{int T; cin >> T;while(T--)solve();return 0;
}
E题：Long Inversions
标签: 暴力枚举（brute force）贪心策略（greedy）实现问题，编程技巧，模拟（implementation）排序算法（sortings）
题目大意
- 给出长度为 n 的仅由字符 "1 "和 "0 "组成的字符串 s。
- 选择一个整数 k ( 1 ≤ k ≤ n)，然后任意多次执行以下操作：
- 选择字符串中连续的 k 个字符并将其反转，即用 "1 "替换所有 “0”，反之亦然。
- 通过这些操作，您需要使字符串中的所有字符都等于 “1”。
- 求：k 的最大值
思路
- 两步一起可交换或反转每相隔为k + 1位置的数字
- 例如k = 3如图1，反转红线和黑线，即交换和反转相隔为k + 1位置的数字
- 那么如图2中的相连的数字都可以任意交换位置
- 一种做法：用以上方法将0全部移到前1 ~ k 个字符上，然后将其反转，判断能否全部反转即可
AC代码
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int a[N], b[N], n;
string s;
bool check(int x)
{int res = 0;for(int i = 0; i < x; i++){int cnt = 0;for(int j = i; j < n; j += x)if(s[j] == '0') cnt ++;res += cnt % 2;}return res % x;
}
void solve()
{cin >> n >> s;int k = n;while(check(k)) k--;cout << k << endl;
}
int main()
{int T; cin >> T;while(T--)solve();return 0;
}
logo
//へ ／|
// /＼7 ∠＿/
// / │ ／ ／
// │ Z ＿,＜ ／ /`ヽ
// │ ヽ / 〉
// Y ` / /
// ｲ● ､ ● ⊂⊃〈 /
// () へ | ＼〈
// >ｰ ､_ ィ │ ／／
// / へ / ﾉ＜| ＼＼
// ヽ_ﾉ (_／ │／／
// 7 |／
//
/*__ _,--="=--,_ __/ \." .-. "./ \/ ,/ _ : : _ \/` \\ `| /o\ :_: /o\ |\__/`-'| :="~` _ `~"=: |\` (_) `/.-"-. \ | / .-"-.
.---{ }--| /,.-'-.,\ |--{ }---.) (_)_)_) \_/`~-===-~`\_/ (_(_(_) (
( )) (
'---------------------------------------'
*/
这篇关于Codeforces Round 938 (Div. 3) (A~E)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
