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阵。三个整数 a_1,1 、 c 和 d 并按照以下规则构造一个累进正方形：
• a_i+1,j = a_i,j + c
• a_i,j+1 = a_i,j + d
• 即：每一行每一列都是等差数列，公差分别为c，d
• 问题：给n，c，d 和一个长n × n的数组，问此数组是否是个累进正方形

思路

• 找到数组中最小值一定被作为a_1,1，知道a_1,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 艘飞船的耐久度为 a_i。
• 攻击次数：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 的元素，计算有多少个数组是好的
• 换句话说，求元素 a_l,a_l+1,…,a_l+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\ |\__/
         `-'| :="~` _ `~"=: |
            \`     (_)     `/
     .-"-.   \      |      /   .-"-.
.---{     }--|  /,.-'-.,\  |--{     }---.
 )  (_)_)_)  \_/`~-===-~`\_/  (_(_(_)  (
(                         				)
 )                                     (
'---------------------------------------'
*/