知识点：贪心。
对于一个轨道，要么一次性清理，要么一个一个清理。显然，如果行星个数大于直接清理的花费，那么选择直接清理，否则一个一个清理。即 (\sum \min (c,cnt[i]))，其中 (cnt[i]) 表示轨道 (i) 的行星个数。
时间复杂度 (O(n))
空间复杂度 (O(1))
#include
#define ll long long
using namespace std;
int cnt[107];
bool solve() {
int n, c;
cin >> n >> c;
memset(cnt, 0, sizeof(cnt));
for (int i = 1;i > x;
cnt[x]++;
}
int ans = 0;
for (int i = 1;i > t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
知识点：三分。
按位置从小到大排列，显然约会花费是一个关于 (x_0) 的单谷函数，因此可以三分位置。
由于位置最大有 (10^8) ，但点的个数只有 (10^5) ，考虑先用 map 存储有序对 ((x,t)) ，其中 (t) 是位置 (x) 的人最大打扮时间，因为比这个时间少的一定不影响结果。遍历结束以后把 map 内容移到 vector 中用 pair 存储用以三分， check 函数则只要遍历一遍 vector 即可。
时间复杂度 (O(n \log \max(eps)))
空间复杂度 (O(n))
知识点：贪心。
把 (t) 等效进位置，如果 (x_i) 在 (x_0) 左侧，则等效位置是 (xi – t) ;如果 (x_i) 在 (x_0) 右侧，则等效位置是 (x_i + t) 。
所有点的左侧等效位置最左的位置，就是等效区间左端点；所有点的右侧等效位置最右的位置就是等效区间的右端点。
时间复杂度 (O(n))
空间复杂度 (O(n))
#include
#define ll long long
using namespace std;
int x[100007];
map mp;
vector> v;
double check(double mid) {
double mx = 0;
for (auto [i, j] : v) {
mx = max(mx, abs(i - mid) + j);
}
return mx;
}
bool solve() {
mp.clear();
v.clear();
int n;
cin >> n;
for (int i = 1;i > x[i];
mp[x[i]] = 0;
}
for (int i = 1;i > T;
mp[x[i]] = max(mp[x[i]], T);
}
for (auto [i, j] : mp) {
v.push_back({ i,j });
}
double l = 0, r = v.back().first;
while (abs(r - l) >= 1e-7) {
double mid1 = l + (r - l) / 3;
double mid2 = r - (r - l) / 3;
if (check(mid1) > t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
#include
#define ll long long
using namespace std;
int x[100007], T[100007];
bool solve() {
int n;
cin >> n;
int l = 1e9, r = 0;
for (int i = 1;i > x[i];
for (int i = 1;i > T[i];
for (int i = 1;i > t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
知识点：贪心。
因为要字典序最小，那么一个数字他后面没有更小的数字则可以保留，其他都应该删除，所以从右往左找一个合法的保留序列，其他的数字加一，并且都是位置随意的，于是可以插入到保留下来的序列，并使插入后的序列是从小到大字典序最小的排列。因此直接把保留序列外的数字加一以后，对整个序列排序即可。
也可以直接桶排序。
时间复杂度 (O(n \log n))
空间复杂度 (O(n))
#include
#define ll long long
using namespace std;
bool solve() {
string s;
cin >> s;
int mi = 10;
for (int i = s.size() - 1;i >= 0;i--) {
if (s[i] - '0' > t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
知识点：构造。
注意到操作不会改变无序对 ((a_i, b_{ n – i + 1 })) 数量以及种类。
引理：(a = b) ，当且仅当无序对是 回文的。
充分性：
当 (a = b) 时，如果 (i) 处存在一组无序对 ((x, y)) ，则必然会在 (n-i+1) 产生相同一组无序对 ((y, x)) ，除非当 (n) 为奇数时，可以在中间产生一个元素相同的无序对 ((x,x)) ，因此 (a = b) 时，无序对必然成回文状。
必要性：
当无序对是回文的，则第 (i) 组无序对 ((x,y)) 可以对应第 (n-i+1) 组无序对 ((y,x)) ，即 (a_i = b_i) ,所以 (a = b) 。
充要条件：YES 当且仅当无序对 ((a_i, b_{ n – i + 1 })) 中元素不同的无序对有偶数个，元素相同的无序对仅在 (n) 为奇数时至多 (1) 种有奇数个。
充分性：
根据引理，显然满足右边条件。
必要性：
显然没有任何限制时，给出的无序对条件能排列成回文的，现在尝试证明其必然可构造无序对回文。
注意到操作 (k = i) 可以使得 (a[1 \cdots k]) 和 (b[k\cdots n]) 交换位置，即 ((a[k], b[n – k + 1])) 这一组无序对被置换到了 (1) 号位置，同时 ((a[1],b[n])) 这一组无序对被置换到了 (i) 号位置，但这不会改变 (a[k+1 \cdots n]) 和 (b[1\cdots k-1]) 的顺序，即第 (k+1) 到 (n) 组无序对及其实际元素顺序没有改变。因此，如果我们想要将无序对通过操作变成一个我们想要的顺序，可以从右往左构造。
假设 (i+1) 到 (n) 的无序对都安排好了，现在 (i) 号位置想要 (j (j\leq i)) 号位置的无序对时，可以先 (k=j) ，将 (j) 号替换到 (1) 号，然后 (k=i) ，将 (1) 号替换 (i) 号，过程中 (i+1 \cdots n) 的无序对不会改变，包括实际元素顺序。
上述操作最后结果是无序对 (j) 替换到 (i) ，且 (j) 号无序对元素的实际顺序不会改变。但如果我们希望实际元素的顺序也发生改变，我们可以加一个步骤 (k = 1) 在中间，即通过 (k = j, k = 1, k = i) 替换 (i) 号后的 (j) 号元素实际顺序与原来是相反的，这也是为什么我们只需要知道无序对顺序即可，因为元素实际顺序是可以随时改变的。
通过上述操作我们可以实现无序对的任意排列，以及无序对实际元素的顺序。因此无序对满足回文条件时，必然可以构造出无序对回文。于是根据引理，得到 (a = b) 。
时间复杂度 (O(n))
空间复杂度 (O(n))
#include
#define ll long long
using namespace std;
string a, b;
int cnt[26][26];
bool solve() {
memset(cnt, 0, sizeof(cnt));
int n;
cin >> n;
string a, b;
cin >> a >> b;
for (int i = 0;i < n;i++) {
int x = a[i] - 'a', y = b[n - 1 - i] - 'a';
if (x > y) swap(x, y);
cnt[x][y]++;
}
bool ok = true;
int esum = 0;
for (int i = 0;i < 26;i++) {
for (int j = i;j < 26;j++) {
if (i == j) esum += cnt[i][j] & 1;
else ok &= !(cnt[i][j] & 1);
}
}
if (ok && esum > t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
Original: https://www.cnblogs.com/BlankYang/p/16753089.html
Author: 空白菌
Title: Codeforces Round #823 (Div. 2) A-D
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/801500/
转载文章受原作者版权保护。转载请注明原作者出处！