Codeforces Round 929 (Div. 3)

Codeforces Round 929 (Div. 3) (A~E)

目录：A B C D E

A题：Turtle Puzzle: Rearrange and Negate

标签: 贪心策略（greedy）数学（math）排序算法（sortings）

题目大意

• 给一个由 n个整数组成的数组 a。必须对数组执行以下两个操作：
• 1. 任意重新排列数组元素或保持元素顺序不变。
• 2. 最多选择一个连续的元素段，并将该元素段中所有元素的符号替换为相反符号。
• 进行这两次操作后，数组元素的最大和是多少？

思路

• 将所有负数排列到一起，对该连续段执行第二操作，这样所有数都为正数了

AC代码

#include <bits/stdc++.h>
using namespace std;
void solve()
{
	int n; cin >> n;
	int a, res = 0;
	for(int i = 0; i < n; i++)
	{
		cin >> a;
		res += abs(a);
	 } 
	 cout << res << endl;
} 
int main()
{
	int T; cin >> T;
	while(T--)
		solve();
	return 0;
}

B题：Turtle Math: Fast Three Task

标签: 实现问题，编程技巧，模拟（implementation）数论（number theory）

题目大意

• 给一个由 n个整数组成的数组 a，在一次移动中，你可以执行以下两种操作中的任何一种：
• 1. 移除一个数
• 2. 选择一个数+1
• 找出使a 数组中的元素之和能被 3 整除所需的最少移动次数

思路

• 求a数组中的所有值的和，如果该值模3为0则不需要移动，模3为2则执行第二种操作一次即可
• 模3为1，如果数组a中含有模3为1的元素将其移除即可，反之最少执行两次操作

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
void solve()
{
	int n; cin >> n;
	int sum = 0, cnt = 0;
	for(int i = 0; i < n; i++)
	{
		int a; cin >> a;
		sum += a;
		if(a % 3 == 1) cnt ++;
	}
	sum %= 3;
	if(sum == 0) cout << 0 << endl;
	else if(sum == 2) cout << 1 << endl;
	else 
	{
		if(cnt >= 1) cout << 1 << endl;
		else cout << 2 << endl;
	}
} 
int main()
{
	int T; cin >> T;
	while(T--)
		solve();
	return 0;
}

C题：Turtle Fingers: Count the Values of k

标签: 暴力枚举（brute force）数论（number theory）

题目大意

• 给你三个正整数 a、b和 l( a, b, l > 0 )。
• 可以证明，总有一种方法可以选择非负的整数 k 、 x 和 y，使得 l=k⋅a^x^ ⋅ b^y^
• 找出所有这些方法中 k 的不同可能值的个数。

思路

• k = $\frac{l}{a^x ⋅ b^y}$，枚举x，y满足k是整数再对k去重即可

AC代码

#include <bits/stdc++.h>
using namespace std;
void solve()
{
	int a, b, l; 
	cin >> a >> b >> l;
	set<int> s;
	// i = a ^ x, j = b ^ y 
	for (int i = 1; l % i == 0; i *= a) 
		for (int j = 1; l/i % j == 0; j *= b) 
			s.insert(l/i/j);		
	cout << s.size() << '\n';
} 
int main()
{
	int T; cin >> T;
	while(T--)
		solve();
	return 0;
}

D题：Turtle Tenacity: Continual Mods

标签: 贪心策略（greedy）实现问题，编程技巧，模拟（implementation）

题目大意

• 给定数组 a1,a2,…,an判断是否有可能将其元素重排为 b1,b2,…,bn，从而得到 b1modb2mod…modbn≠0。

思路

• 重点：小的数对大的数取模，还是小的数，不会得到0
• 如果最小的数重复出现可以考虑通过大数对最小的数取模得到一个更小的数（不为0）
• 1. 如果可以得到，用这个最小的数模后面所有的数一定为自己本身，即不为0
• 2. 因为对最小的数取模一定比最小的数还要小，得不到情况一定是所有数都是最小的数的倍数（取模全为0），又在在最小的数重复出现条件下可以发现一定是NO

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
void solve()
{
	int n; cin >> n;
	int cnt1 = 0;
	int Min = 0x3f3f3f3f;
	for(int i = 0; i < n; i++)
	{
		cin >> a[i]; 
		Min = min(a[i], Min);
	} 
	for(int i = 0; i < n; i++)
	{
		if(a[i] == Min) cnt1++;
		if(a[i] % Min != 0) 
		{
			cout << "YES" << endl;
			return; 
		} 
	} 
	if(cnt1 == 1) cout << "YES" << endl; 
	else cout << "NO" << endl;
} 
int main()
{
	int T; cin >> T;
	while(T--)
		solve();
	return 0;
}

E题：Turtle vs. Rabbit Race: Optimal Trainings

标签: 二分搜索（binary search）数学（math）三分搜索（ternary search）

题目大意

• 有 n条跑道可供使用，i条跑道( 1 ≤ i ≤ n )由 ai个等长的部分组成。
• • 完成 第1部分会使能力提高 u 。
• • 完成 第2部分会使能力提高 u−1 。
• • 完成 第3部分会使能力提高 u−2 。
• • ……
• • 完成 第k部分( k ≥ 1)会使能力提高 u+1−k （可以为负数）
• 给定整数u， l，选择一个整数 r，使完成al到ar跑道的全部部分能力最大
• 回答 q 个不同值的 l 和 u 。

思路

• 共完成k部分，能力提高u * k - k * (k - 1) / 2，其中第k部分提高u + 1 - k，可以看出k不断接近u时能力越高，超出部分能力不增反降
• 二分查找一个r 使∑^r^i=l al+al+1+…+ar 接近u，但小于等于u，(多次求区间和，用前缀和优化)
• 考虑超出部分后的一条跑道部分可能是正收益需要对查找r，r + 1能得到能力取最大值

AC代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int a[N];
void solve()
{
	int n; cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i]; 
		a[i] += a[i-1];
	}
	int q; cin >> q;
	while(q--)
	{
		int L, u;
		cin >> L >> u;
		int l = L, r = n;
		while(l < r)
		{
			int mid = l + r + 1 >> 1;
			if(a[mid] - a[L-1] <= u) 
				l = mid;
			else r = mid - 1;
		}
		int k1 = a[r] - a[L-1];
		int k2 = a[r+1] - a[L-1];
		int t1 = k1 * u - k1 * (k1 - 1) / 2;
		int t2 = k2 * u - k2 * (k2 - 1) / 2;
		if(t1 >= t2 || r == n) cout << r << " ";
		else cout << r + 1 << " ";
	}
	cout << endl;
	
} 

signed main()
{
	int T; cin >> T;
	while(T--)
		solve();
	return 0;
}

logo

//へ　　　　　／|
//　　/＼7　　　 ∠＿/
//　 /　│　　 ／　／
//　│　Z ＿,＜　／　　 /`ヽ
//　│　　　　　ヽ　　 /　　〉
//　 Y　　　　　`　 /　　/
//　ｲ●　､　●　　⊂⊃〈　　/
//　()　 へ　　　　|　＼〈
//　　>ｰ ､_　 ィ　 │ ／／
//　 / へ　　 /　ﾉ＜| ＼＼
//　 ヽ_ﾉ　　(_／　 │／／
//	　　7　　　　　　　|／
//

/*
          __   _,--="=--,_   __
         /  \."    .-.    "./  \
        /  ,/  _   : :   _  \/` \
        \  `| /o\  :_:  /o\ |\__/
         `-'| :="~` _ `~"=: |
            \`     (_)     `/
     .-"-.   \      |      /   .-"-.
.---{     }--|  /,.-'-.,\  |--{     }---.
 )  (_)_)_)  \_/`~-===-~`\_/  (_(_(_)  (
(                         				)
 )                                     (
'---------------------------------------'
*/