A.Phoenix and Balance
题意:
给定一个数,将划分为数量相等的两部分,使两部分的和的差最小
题解:
将最大的和前划分为一部分,剩下划分为一部分即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 4e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; void solve() { int n; cin >> n; cout << 2 * (pow(2, n) + pow(2, n / 2) - 2) - (pow(2, n + 1) - 2) << endl; } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
B.Phoenix and Beauty
题意:
给定一个序列,可以在任意位置插入任意个的数要求满足每个长度为的子序列的和相等。输出一个满足条件的序列,否则输出
题解:
如果序列中不同的数超过个则找不到一个满足条件的序列,否则用序列中不同的数和中的其他数补成一个长度为的任意两个数字均不相同的序列,循环次这个序列肯定是满足要求的
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 4e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; void solve() { set<int> s; int n, k; scanf("%d%d", &n, &k); for (int i = 0, x; i < n; i++) { scanf("%d", &x); s.insert(x); } if (s.size() > k) { puts("-1"); return; } for (int i = 1; s.size() < k; i++) s.insert(i); printf("%d\n", n * k); for (int i = 0; i < n; i++) for (int j : s) printf("%d ", j); puts(""); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
C.Phoenix and Distribution
题意:
给定一个长度为的字符串,要求将其分为份,每份均不为空,使得其中字典序最大的字符串的字典序尽可能小,并输出这一份。
题解:
贪心将升序排序,如果和不相同,就可以将都放在后面,最大的就是
否则,如果和相同,再判断是否都相同,相同则平分,不相同则全部放在后面
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; char s[maxn]; void solve() { int n, k; scanf("%d%d%s", &n, &k, s); sort(s, s + n); printf("%c", s[k - 1]); if (s[k - 1] == s[0]) { if (s[k] == s[n - 1]) for (int i = 0; i < (n - 1) / k; i++) printf("%c", s[k]); else for (int i = k; i < n; i++) printf("%c", s[i]); } puts(""); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
D.Phoenix and Science
题意:
有一个质量为的细菌,白天可以选择将一部分细菌进行分裂(可以选择所有细菌都不分裂),晚上每份细菌的质量都增加,询问最少多少天总质量可以恰好达到
题解:
首先可以明确总质量不会减少,那么每天的增量就是当天的细菌份数,一天的增量在之间,为当天刚开始的细菌份数。因此只需要就可以达到,同时只需要满足每天的单调不减即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; void solve() { int n; scanf("%d", &n); int sum = 1, add = 1; vector<int> v; while (sum <= n) { int now = n - sum; if (add * 2 >= now) { v.push_back(now - add); break; } v.push_back(min(now / 2 - add, add)); add += v.back(); sum += add; } printf("%d\n", v.size()); for (int x : v) printf("%d ", x); puts(""); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }