Codeforces Round 1006 (Div. 3)(部分题解)

A. New World, New Me, New Array

思路：这题挺简单的，在对k取绝对值后会更简单一点。

然后注意上取整。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'void solve()
{int n, k, p;cin >> n >> k >> p;k = abs(k);if (n*p < k) cout << -1 << endl;else {cout << (k+p-1)/p << endl;}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

B. Having Been a Treasurer in the Past, I Help Goblins Deceive

思路：统计‘-’和‘_’的数量，‘-’会分在‘_’的两边，保证左右乘积最大，即尽可能平均分配。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'void solve()
{int n;string s;cin >> n;cin >> s;int n1 = count(s.begin(), s.end(), '-');int n2 = n-n1;if (n1 < 2 || n2 < 1) cout << 0 << endl;else {int cnt = n1/2;cout << cnt*(n1-cnt)*n2 << endl;}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

C. Creating Keys for StORages Has Become My Main Skill

思路：我看了半天才看懂MEX(S)的意思，这里补充介绍一下，就是它的值为0到后第一个没在S集合里面的值，因此它的最大值不会超过n-1，所以我们要让它最大，就要从0开始枚举。这里代码(i&x)==i表示i的二进制数都包含在x中，一旦枚举到不满足，MEX值定了，所以我们可以为任何(i&x)==i的i值，显然0必定符合且简单，所以不满足就输出0，当枚举到最后一个数时，我们还要考虑前面所有的OR是否等于x，这里我们考虑到如果加上次i=n-1满足也可以输出该i，不满足我们就要输出一个能让其满足的数，即(num^x)可以帮缺少的二进制1都补上。（二进制）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'void solve()
{int n, x;cin >> n >> x;int num = 0;for (int i = 0; i<n; i++){if (i == n-1){if ((i|num) == x){cout << i << endl;}else cout << (num^x) << endl;return ;}if ((i&x)==i){cout << i << " ";num |= i;}else{cout << 0 << " ";}}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

D. For Wizards, the Exam Is Easy, but I Couldn't Handle It

思路：这道题由于n的范围比较小，可以直接暴力做出来，对于一个位置，往后枚举比较。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'void solve()
{int n;cin >> n;vector<int> a(n);for (int i = 0; i<n; i++) cin >> a[i];int sum = 0;for (int i = 0; i<n; i++){for (int j = i+1; j<n; j++){sum += (a[i] > a[j]?1:0);}}int l = 0, r = 0;int ans = sum;for (int i = 0; i<n; i++){int cur = sum;for (int j = i+1; j<n; j++){cur -= (a[i] > a[j]?1:0);cur += (a[i] < a[j]?1:0);if (cur < ans){ans = cur;l = i;r = j;}}}cout << l+1 << " " << r+1 << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

E. Do You Love Your Hero and His Two-Hit Multi-Target Attacks?

思路：首先看到有公式之类要想着化简或者转化，这里对公式化简为

所以只要x轴相等或者y轴相等就可以为一对，我们可以指定一个轴，然后来满足此条件。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'void solve()
{int k;cin >> k;vector<array<int, 2>> ans;int x = 0, y = 0;while (k){x++;int s = 1;while (s*(s+1)/2 <= k) s++;k -= s*(s-1)/2;for (int i = 1; i<=s; i++){y++;ans.push_back({x, y});}}cout << ans.size() << endl;for (auto [x, y]:ans){cout << x << " " << y << endl;}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}