Codeforces Round 942 (Div. 2)

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

Codeforces Round 942 (Div. 2)

Codeforces Round 942 (Div. 2)

A. Contest Proposal

题意：给出两个长度为n的非递减排序的ab序列，通过向a序列中插入新元素，然后排序后删除最大元素，使得两个长度为n的排列中每一个$a_i$<=$b_i$;

思路：双指针，以a为基准从后往前找不符合条件的元素， 通过插入操作向后位移即可删除。

AC code：

void solve() {int n; cin >> n;int a[n + 1], b[n + 1];for (int i = 1; i <= n; i ++) cin >> a[i];for (int i = 1; i <= n; i ++) cin >> b[i];int cnt = 0;int l = n, r = n;for (int i = n; i > 0; i --) {if (a[i] > b[l]) cnt ++;else l --;}cout << cnt << endl;
}

B. Coin Games

题意：n枚硬币围成一个圈，A和B轮流操作，每次选择一枚正面的硬币拿走，然后翻转相邻的两枚硬币，当一人无法操作时另一人胜利。

思路：看正面朝上的硬币数量，奇数先手胜，否则后手胜。

AC code：

 void solve() {int n; cin >> n;string s; cin>> s;int u = 0, d = 0;for (auto c : s) if (c == 'U') u ++;else d ++;if (u % 2) cout << "YES" << endl;else cout << "NO" <<endl;
}

C. Permutation Counting

题意：有n张卡片，每种牌有$a_i$张，可以到商店买任意卡片，买一张需要1个金币，一共有k枚金币，买完牌重新排列后最多有多少连续子数组可以构成完整的1到n的排列。

思路：二分出最多可以补l套完整的卡牌，这些牌可以组成(l * n - (n - 1))，然后多余的卡牌每种可以增加一次答案。

AC code：

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define db double
#define pb push_back
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;typedef long long LL;
typedef pair<char, int> PCI;
typedef pair<int, int> PII;
const int N = 2e5+10, M = 2001;
const int INF = 0x3f3f3f3f3f, MOD = 998244353;
int T;
int n, k;
int a[N];
map<int, int> mp;bool check (int x) {int now = k;for (int i = 1; i <= n; i ++) {if (a[i] < x) now -= (x - a[i]);if (now < 0) return false;}if (now < 0) return false;return true;
}void solve() {cin >> n >> k;mp.clear();for (int i = 1; i <= n; i ++) cin >> a[i];if (n == 1) {cout << a[1] + k << endl;return;}int l = 0, r = 1e18;while (l < r) {int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}//cout << l << "----" << endl;for (int i = 1; i <= n; i ++) {if (a[i] < l) k -= (l - a[i]);mp[i] = max(l, a[i]);}//cout << n << ' ' << now << "++" << endl;int pos;int ans = l * n - (n - 1);for (int i = 1; i <= n; i ++) {if (a[i] > l) ans ++;}ans += k;cout << ans << endl;
}signed main() {fast();T = 1;cin >> T;while (T --) {solve();}return 0;
}

D1. Reverse Card (Easy Version)

题意：找出两个元素a和b，范围分别为[1,n]和[1, m]，找出符合(a+b)%(b*gcd(a,b)) == 0的对数。

思路：注意，gcd(a,b)一定是等于b，问题转换为(a+b)%(b*b) == 0；

然后枚举b来找a，且a一定是b的倍数，注意，枚举a会超时;

AC code :

void solve() {int n, m; cin >> n >> m;int cnt = 0;for (int b = 1; b <= min(n, m); b ++) {for (int a = b; a <= n; a += b) {  if ((a + b) % (b * b) == 0) {cnt ++;}}}cout << cnt << endl;
}

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

---