Codeforces Round 926 (Div. 2)(A B C)

本文主要是介绍Codeforces Round 926 (Div. 2)(A B C)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

比赛：Codeforces Round 926 (Div. 2)

目录：A B C

A题

题目：Sasha and the Beautiful Array

标签: 构造（constructive algorithms）贪心（greedy）排序（sortings）

题目大意

• 有一个长度为 n, 数值为 1 − 1e9的数组a。重新排列数组 a 中的元素使得(a_i - a_i-1) i从2到n总和最大，求最大和。

思路

• 对所有(a_i- a_i-1) i 取值2~n 求和，即(a₂ - a₁) + (a₃ - a₂) + (a₄ - a₃) +… + (a_n - a_n-1) = a_n - a₁，转化为对a数组从新排序使a_n - a₁最大
• 所以将最大值放在最后，最小值放在最前是最优的，a数组中最大值减最小值即为答案

AC代码

#include <bits/stdc++.h>
using namespace std;
void solve()
{int n; cin >> n;vector<int> a(n);for (int i = 0; i < n; i++)cin >> a[i];int ans = *max_element(a.begin(), a.end()) - *min_element(a.begin(), a.end());cout << ans << "\n";
} 
int main()
{int T; cin >> T;while(T--)solve();return 0;
}

B题

题目：Sasha and the Drawing

标签: 构造（constructive algorithms）贪心（greedy）数学（math）

题目大意

• 在一个nxn的正方形网格中涂色使得至少K条对角线经过至少有一个着色的单元格，求最少要涂色多少单元格
• 大小为 n×n 的正方形网格共有 4n−2 条对角线。

思路

• 考虑涂色一个单元格使其覆盖尽可能多的对角线，不难看出涂色一个单元格最多覆盖两条对角线，最多同时有2n - 2个单元格能达到覆盖两条对角线（所有被覆盖的对角线不重复)共可覆盖4n - 4条对角线，剩余两条对角线每条需要涂色一个单元格
• 当要被覆盖对角线条数k<=4n - 4 时答案就是: k除以2上取整，k>4n-4时就是: 2n - 2 + (k - (4n - 4))

AC代码

#include <bits/stdc++.h>
using namespace std;
void solve()
{int n, k;cin >> n >> k;if(k <= 4*n - 4)	cout << (k + 1) / 2 << endl;else cout << 2*n - 2 + (k - (4*n - 4)) << endl;
} 
int main()
{int T; cin >> T;while(T--)solve();return 0;
}

C题

题目：Sasha and the Casino

标签: 二分搜索（binary search）暴力枚举（brute force）动态规划（dp）博弈论（games）贪心（greedy）数学（math）

题目大意

• 每次可以下注y个硬币，赢了将获得k*y个硬币（即硬币数量将增加 y⋅(kz−1)），输了将输掉全部赌注(即硬币数量将减少 y )。
• 投注金额必须始终是一个正整数，并且不能超过当前手里的硬币数量。
• 连续输的次数不会超过x次。
• 给定：k(赢了时的倍率)，x(最多连续输的次数)，a(初始手里的硬币数)，问：是否可以下注保证赢取任意数量的硬币

思路

• 需要保证赢钱即：找到一种下注方式让其每轮只可能赢钱不可能输钱，
• 在一轮中已经输了sum个硬币，那么下局如果要赢回需要增加: (sum / (k - 1) + 1 ）* (k - 1)枚硬币，即：下注y = sum / (k - 1) + 1

AC代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve()
{int k, x, a;cin >> k >> x >> a;// 每次下注y，一轮累计输钱sum（假设每局下注都输）int y, sum = 0;// 一轮最多连续输x次，加最后一次赢，共x+1次下注for(int i = 0; i <= x; i ++ ){// 保证每次下注如果赢了都能将输的捞回 y = sum / (k - 1) + 1;sum += y;// 如果将手上钱输光了if(sum > a){cout << "NO" << endl;return;} }cout << "YES" << endl;
} 
signed main()
{int T; cin >> T;while(T--)solve();return 0;
}

logo

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

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

这篇关于Codeforces Round 926 (Div. 2)(A B C)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---