A. New World, New Me, New Array
Greedy wants to assign a $p $ every time. If the sum is $k $, the answer is\(k/p\), otherwise\(k/p+1\)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
void solve() {
int n, k, p;
cin >> n >> k >> p;
if (n * p < abs(k)) {
cout << -1 << '\n';
return;
}
int ans = abs(k / p);
if (k % p != 0) ans++;
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(0), (0), (0);
int t = 1;
cin >> t;
while (t--)
solve();
}
B. Having Been a Treasurer in the Past, I Help Goblins Deceive
Just think about it,\(O(n)\)Scan and record how many "-" to put before and after each will make the most sub-sequences, and just calculate it directly.
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
void solve() {
string s;
int n;
cin >> n;
cin >> s;
int cnt = 0, cnt1 = 0;
for (auto t : s) {
if (t == '-') cnt++;
}
int mx = 0;
cnt1 = () - cnt;
for (int i = 1; i <= cnt; i++) {
int x = i, y = cnt - i;
mx = max(mx, x * y);
}
cout << mx*cnt1 << '\n';
}
signed main() {
ios::sync_with_stdio(0), (0), (0);
int t = 1;
cin >> t;
while (t--)
solve();
}
C. Creating Keys for StORages Has Become My Main Skill
Greedy,\([0,n-1]\)Take, maintain or value as much as possible, if exactly\(x\)That's the answer. Otherwise, modify the largest item as much as possible.\(x\),so\(MEX\)maximum.
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
void solve() {
int n, x;
cin >> n >> x;
int now = 0;
vector<int> ans(n+10, 0);
for (int i = 1; i < n; i ++ ) {
if ((x | i) == x) {
ans[i] = i;
now |= i;
}
}
if (now != x) {
ans[n - 1] = x;
}
for (int i = 0; i < n; i ++ ) {
cout << ans[i] << ' ';
}
cout << '\n';
}
signed main() {
ios::sync_with_stdio(0), (0), (0);
int t = 1;
cin >> t;
while (t--)
solve();
}
D. For Wizards, the Exam Is Easy, but I Couldn't Handle It
It is obvious that the number of inverted numbers changes are only related to the selected interval and have nothing to do with the numbers outside the interval. The contribution of the interval is that the interval is smaller than that in the interval.\(l\)The number of minus\(l\)number of .
\(n^2\)Violence enumeration, note down in the process\([l,r]\)The interval is greater than\(l\)and less than\(l\)The answer is the number of numbers and then the range with the largest contribution in statistics is the answer.
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int ans = 0;
pair<int, int> anss;
for (int l = 1; l <= n; l++) {
int x = 0, y = 0;
for (int r = l; r <= n; r++) {
if (a[r] > a[l]) x++;
if (a[r] < a[l]) y++;
if (y - x >= ans) {
ans = y - x;
= l, = r;
}
}
}
cout << << ' ' << << '\n';
}
signed main() {
ios::sync_with_stdio(0), (0), (0);
int t = 1;
cin >> t;
while (t--)
solve();
}
E. Do You Love Your Hero and His Two-Hit Multi-Target Attacks?
The general meaning of the question: Akito needs to place $n$ root staff in the coordinate system, and the positions of these staffs must be different integer coordinate points. After being placed, there happens to be $k $ on the staff located on the same horizontal or vertical line.
Construct the problem and use the knowledge of combining numbers\(C(x,2)\)Just construct as much as possible.
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
void solve() {
int n;
cin >> n;
if (n == 0) {
cout << "2\n0 0\n1 1\n";
return;
}
vector<pair<int, int>> ans;
int yu = n;
int ls = 1, d = 0;
while (yu > 2) {
for (int i = 2; i <= 500; i++) {
int x = (i - 1) * i / 2;
if (x > yu) {
int res = (i - 1) * (i - 2);
yu -= res / 2;
for (int j = ls; j <= ls + i - 1 - 1; j++) {
ans.push_back({-j, d});
}
ls = ls + i - 1;
d -= 1;
break;
}
}
}
if (yu == 2) {
ans.push_back({1, 1});
ans.push_back({2, 1});
ans.push_back({3, 2});
ans.push_back({4, 2});
} else if (yu == 1) {
ans.push_back({1, 1});
ans.push_back({2, 1});
}
cout << () << '\n';
for (pair<int, int> p : ans) {
cout << << ' ' << << '\n';
}
}
signed main() {
ios::sync_with_stdio(0), (0), (0);
int t = 1;
cin >> t;
while (t--)
solve();
}
F. Goodbye, Banker Life
If you look at the rules on the table, you will find that the $n$th row is transferred from the nearest $n-2^x$ row. It is obvious that you can recurse and record the answers recursively and process the direct output. The code implementation is relatively abstract, and it depends on the code in detail.
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
int n, x;
int ksm(int x, int y) {
int ans = 1;
while (y) {
if (y & 1)
ans = ans * x;
y >>= 1;
x = x * x;
}
return ans;
}
vector<int> po;
void init() {
for (int i = 32; i >= 0; i--) {
int x = ksm(2, i);
po.push_back(x);
}
}
deque<pair<string, int>> de;
void dfs(int u) {
if (u == 1 || (u & (u - 1)) == 0) {
if (u == 1) {
de.push_front({"1", 1});
} else {
de.push_back({"1", u});
}
return;
}
for (int i = 0; i < 32; i++) {
if (po[i] <= u) {
dfs(u - po[i]);
int yu = u - 2 * (u - po[i]);
de.push_back({"0", yu});
de.push_back({"x", 0});
return;
}
}
}
void pr();
void pr1(int l, int r);
void pr0(int l, int r);
void solve() {
while (()) de.pop_front();
cin >> n >> x;
string s = to_string(1);
for (int i = 0; i < 32; i++) {
if (n == po[i]) {
pr();
return;
}
}
dfs(n);
vector<pair<string, int>> p;
while (()) {
pair<string, int> it = ();
de.pop_front();
p.push_back(it);
}
for (int i = 0; i < (); i++) {
string a = p[i].first;
int b = p[i].second;
if (a == "0") {
pr0(1, b);
}
else if (a == "1") {
pr1(1, b);
}
else if (a == "x") {
int len = 0;
if (p[i - 1].first == "0") len = i - 1;
else len = i;
string lp = "";
for (int j = 0; j < len; j++) {
int cnt = p[j].second;
if (p[j].first == "0")
for (int k = 1; k <= cnt; k++) {
cout << 0 << ' ';
lp += "0";
}
else if (p[j].first == "1") {
for (int k = 1; k <= cnt; k++) {
cout << x << ' ';
lp += "1";
}
}
else
for (char t : p[j].first) {
if (t == '1') cout << x << ' ', lp += "1";
else if (t == '0') cout << 0 << ' ', lp += "0";
}
}
p[i].first = lp;
}
}
cout << '\n';
}
void pr() {
for (int i = 1; i <= n; i++)
cout << x << ' ';
cout << '\n';
}
void pr1(int l, int r) {
for (int i = l; i <= r; i++) cout << x << ' ';
}
void pr0(int l, int r) {
for (int i = l; i <= r; i++) cout << 0 << ' ';
}
signed main() {
ios::sync_with_stdio(0), (0), (0);
int t = 1;
init();
cin >> t;
While (t--)
solve();
}
/*
Line 1: 1
Line 2: 1 1
Line 3: 1 0 1
Line 4: 1 1 1 1
Line 5: 1 0 0 0 1
Line 6: 1 1 0 0 1 1
Line 7: 1 0 1 0 1 0 1
Line 8: 1 1 1 1 1 1 1 1 1
Line 9: 1 0 0 0 0 0 0 0 0 1
Line 10: 1 1 0 0 0 0 0 0 0 1 1
*/